範圍的C++排序視圖 - 如何創建const_iterator？

我想寫一個類，應該作爲一些基本的元素序列的排序視圖。到目前爲止，我已經拿出一個非const版本。現在我遇到了問題，以適應它也提供const_iterator功能。範圍的C++排序視圖 - 如何創建const_iterator？

的代碼，我到目前爲止是這樣的：

// forward declare iterator 
template <class InputIt> 
class sorted_range_iter; 

template <class InputIt> 
class sorted_range { 
    friend class sorted_range_iter<InputIt>; 

    private: 
    using T = typename InputIt::value_type; 
    InputIt _first; 
    InputIt _last; 
    std::vector<size_t> _indices; 

    public: 
    using iterator = sorted_range_iter<InputIt>; 

    sorted_range() = default; 
    sorted_range(InputIt first, InputIt last) 
     : _first(first), _last(last), _indices(std::distance(_first, _last)) { 
     std::iota(_indices.begin(), _indices.end(), 0); 
    }; 

    template <class Compare = std::less<T>> 
    void sort(Compare comp = Compare()) { 
     std::sort(_indices.begin(), _indices.end(), 
        [this, &comp](size_t i1, size_t i2) { 
         return comp(*(_first + i1), *(_first + i2)); 
        }); 
    } 

    size_t size() const { return _indices.size(); } 
    T& operator[](size_t pos) { return *(_first + _indices[pos]); } 
    const T& operator[](size_t pos) const { return (*this)[pos]; } 

    iterator begin() { return iterator(0, this); } 
    iterator end() { return iterator(size(), this); } 
};

而且相應的迭代器看起來是這樣的：

template <class InputIt> 
class sorted_range_iter 
    : public std::iterator<std::forward_iterator_tag, InputIt> { 

    friend class sorted_range<InputIt>; 

    private: 
    using T = typename InputIt::value_type; 

    size_t _index; 

    sorted_range<InputIt>* _range; 
    sorted_range_iter(size_t index, sorted_range<InputIt>* range) 
     : _index(index), _range(range) {} 

    public: 
    T& operator*() { return *(_range->_first + _range->_indices[_index]); } 

    // pre-increment 
    const sorted_range_iter<InputIt>& operator++() { 
     _index++; 
     return *this; 
    } 

    // post-increment 
    sorted_range_iter<InputIt> operator++(int) { 
     sorted_range_iter<InputIt> result = *this; 
     ++(*this); 
     return result; 
    } 

    bool operator!=(const sorted_range_iter<InputIt>& other) const { 
     return _index != other._index; 
    } 
};

的使用示例如下：

std::vector<int> t{5, 2, 3, 4}; 
auto rit = ref.begin(); 
sorted_range<std::vector<int>::iterator> r(begin(t), end(t)); 
r.sort(); 

for(auto& x : r) 
{ 
    std::cout << x << std::endl; 
}

輸出：

如何使我的迭代器適應const的情況？如果將迭代器模板化爲基礎類型（例如int）而不是InputIt，則會更容易。有沒有更好的方法來定義這個類？

我想可以通過使用range-v3庫解決這個問題，但我試圖不添加任何更多的依賴關係，並依賴於C++ 11/14函數。

來源

2015-10-08 fuji

你只是使用了錯誤的類型T。您有：

using T = typename InputIt::value_type;

但value_type是iterator和const_iterator相同。他們有什麼不同參考類型。你應該更喜歡：

using R = typename std::iterator_traits<InputIt>::reference; 

R operator*() { ... }

這有額外的好處，使用指針。

或者，可以通過只是想提領迭代器本身避免iterator_traits：

using R = decltype(*std::declval<InputIt>());

側面說明，不應sorted_range施工排序本身？否則，容易被誤用。

來源

2015-10-08 15:55:26 Barry

啊，這樣做很有道理，非常感謝！我們需要明確地調用「sort」的原因是，我希望對排序執行的時間進行全面控制，因爲這可能是一個非常昂貴的函數調用。我也有一個相關的問題：現在我需要聲明的排序範圍如下所示：''sorted_range :: iterator>''。最好，我只想說''sorted_range ''。有沒有辦法做到這一點？ – fuji

@ j.dog不，你需要迭代器類型。你可以做一個函數'sorted_range make_sorted_range（T，T）;'這樣你就不必自己拼寫迭代器類型。 – Barry

範圍的C++排序視圖 - 如何創建const_iterator？

回答

相關問題