C++ sortierte Ansicht des Bereichs - wie man const_iterator erstellt?

Question

Ich versuche, eine Klasse zu schreiben, die als eine sortierte Sicht auf einige zugrunde liegende Sequenz von Elementen fungieren soll. Bis jetzt habe ich eine nicht const Version gefunden. Jetzt habe ich Probleme, es anzupassen, um auch const_iterator Funktionalität zur Verfügung zu stellen.

Der Code habe ich sieht so weit wie folgt aus:

// 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); } 
}; 

und die entsprechenden Iterator sieht wie folgt aus:

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; 
    } 
}; 

Ein Anwendungsbeispiel wie folgt aussieht:

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; 
} 

Ausgabe:

2 
3 
4 
5 

Wie adaptiere ich meinen Iterator für den const Fall? Es wäre einfacher, wenn der Iterator auf dem zugrunde liegenden Typ (int zum Beispiel) anstatt auf InputIt gestempelt würde. Gibt es eine bessere Möglichkeit, diese Klasse zu definieren?

Ich nehme an, dass man dies zum Beispiel mit der Bibliothek range-v3 lösen könnte, aber ich versuche, keine weiteren Abhängigkeiten hinzuzufügen und mich auf C++ 11/14-Funktionen zu verlassen.

Answer 1

Sie verwenden nur den falschen Typ für T. Sie haben:

using T = typename InputIt::value_type; 

Aber value_type das gleiche für iterator und const_iterator ist. Was sie haben, sind unterschiedlich Referenz Typen. Sie sollten bevorzugen:

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

R operator*() { ... } 

Dies hat den zusätzlichen Vorteil der Arbeit mit Zeigern.

Alternativ könnte iterator_traits vermeiden, indem nur zu versuchen, dereferenzieren Iterator selbst:

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

---

Side-Note, sollte nicht sorted_range Art selbst auf dem Bau? Ansonsten leicht zu missbrauchen.