xem C++ sắp xếp phạm vi - cách tạo const_iterator?

Question

Tôi đang cố viết một lớp nên hoạt động như một khung nhìn được sắp xếp trên một số phần tử cơ bản. Cho đến nay tôi đã đưa ra một phiên bản không const. Bây giờ tôi có vấn đề thích ứng với nó cũng cung cấp chức năng const_iterator.

Mã này tôi đã cho đến nay trông như thế này:

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

Và iterator tương ứng trông như thế này:

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

Một ví dụ sử dụng trông như thế này:

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

Đầu ra:

2 
3 
4 
5 

Làm cách nào để điều chỉnh trình lặp của tôi cho trường hợp const? Sẽ dễ dàng hơn nếu trình lặp sẽ được tạo mẫu trên kiểu cơ bản (ví dụ: int) thay vì InputIt. Có cách nào tốt hơn để xác định lớp này không?

Tôi cho rằng người ta có thể giải quyết điều này bằng cách sử dụng thư viện range-v3, tuy nhiên tôi đang cố gắng không thêm bất kỳ phụ thuộc nào nữa và dựa vào các hàm C++ 11/14.

Answer 1

Bạn đang sử dụng sai loại cho T. Bạn có:

using T = typename InputIt::value_type; 

Nhưng value_type là như nhau cho iterator và const_iterator. Những gì họ có khác nhau là tham chiếu loại. Bạn nên chọn:

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

R operator*() { ... } 

Điều này có thêm lợi ích khi làm việc với con trỏ.

Ngoài ra, có thể tránh iterator_traits bởi chỉ cố gắng để dereference iterator bản thân:

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

---

Side-lưu ý, không nên sorted_range loại cứ vào xây dựng? Nếu không, dễ dàng để lạm dụng.