C ++ sorted range view - how to create const_iterator?

Question

I am trying to write a class that should act as a sorted view for some basic sequence of elements. So far I have come up with a version of const . Now I have problems adapting it to provide const_iterator functionality.

The code that I still have looks like this:

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

And the corresponding iterator is as follows:

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

An example of use looks like this:

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

Output:

 2 3 4 5 

How do I configure my iterator for const case? It would be easier if the iterator were obscured by the base type ( int for example) instead of InputIt . Is there a better way to define this class?

I assume that this can be solved, for example, using the range-v3 library, however, I try not to add any dependencies and do not rely on C ++ 11/14.

Answer 1

You are using the wrong type for T You have:

 using T = typename InputIt::value_type; 

But value_type the same for iterator and const_iterator . They have different types of links. You should prefer:

 using R = typename std::iterator_traits<InputIt>::reference; R operator*() { ... } 

This has the added benefit of working with pointers.

Alternatively, you can avoid iterator_traits by simply trying to dereference the iterator itself:

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

---

Side note, shouldn't sorted_range sort itself by outline? Otherwise, it is easy to abuse.