최소한의 사용자 지정 연산자를 작성하십시오. std :: sort를 사용하려면 내 유형에 대해 디그가되어야합니다.

Question

연습으로 std::sort에서 사용할 사용자 지정 반복기를 작성하려고합니다. 그 문서에서, 나는 읽기 :

[My iterator] must meet the requirements of ValueSwappable and
RandomAccessIterator .

완전히 그 ¹를 구현하지 않고, 나는이 MCVE에 왔어요 :

#include <iostream> 
#include <algorithm> 

struct mcve_random_access_iterator 
{ 
    using size_type = std::size_t; 
    using value_type = int; 

    size_type _index; 
    value_type* _values; 
    mcve_random_access_iterator(value_type* values) : _index(0), _values(values) {} 

    mcve_random_access_iterator& operator-(const mcve_random_access_iterator& rhs) { _index-=rhs._index ; return *this; } 
    value_type& operator*() { return _values[_index]; } 
    friend bool operator==(mcve_random_access_iterator& lhs, mcve_random_access_iterator& rhs) { return lhs._index == rhs._index; } 
    friend bool operator!=(mcve_random_access_iterator& lhs, mcve_random_access_iterator& rhs) { return !(lhs == rhs); } 
}; 

void swap(mcve_random_access_iterator& lhs, mcve_random_access_iterator& rhs) 
{ 
    std::swap(*lhs, *rhs); 
} 

struct mcve_container 
{ 
    int _values[3]; 
    mcve_container() : _values{2, 3, 1} {} 
    mcve_random_access_iterator begin() { return {_values}; } 
    mcve_random_access_iterator end() { auto b = begin(); b._index = sizeof(_values)/sizeof(_values[0]); return b; } 
}; 

int main() 
{ 
    mcve_container data; 
    std::sort(data.begin(), data.end()); 
    for (auto n : data._values) 
     std::cout << n << ", "; 
    std::cout << "\n"; 
} 

는 g ++ 7.2.0로 컴파일, 나는 다음과 같은 오류가 발생합니다 :

/usr/local/include/c++/7.2.0/bits/stl_algo.h:1969:14: error: no matching function for call to '__lg(mcve_random_access_iterator&)' 
std::__lg(__last - __first) * 2, 

demo from coliru

왜이 오류가 발생하며 어떻게 해결할 수 있습니까?

---

¹⁾ 나는 여전히 오류를 재현 mcve_random_access_iterator에서 RandomAccessIterator의 모든 요구 사항을 제거했습니다.

Answer 1

두 RandomAccessIterators의 차이는 숫자 std::iterator_traits<It>::difference_type입니다 (특히 하나의 반복자와 다른 반복자 사이의 요소 수를 설명하는 숫자). 너는 그렇지 않아.

std::__lg은 빨간색 청어입니다. 관련 부분은 __last - __first과 다른 유형을 예상한다는 것입니다.

http://en.cppreference.com/w/cpp/concept/RandomAccessIterator

는 @milleniumbug에서 답을 완료하려면

Answer 2

(식 b - a에 해당하는 요구 사항을 참조) : 여기 std::sort에 적합한 사용자 정의 반복자의 최소 작업의 구현입니다.

struct random_access_iterator 
{ 
    using size_type = std::size_t; 
    using value_type = int; 
    using difference_type = std::size_t; 
    using reference = int&; 

    size_type _index; 
    value_type* _values; 


    random_access_iterator(value_type* values) : _index(0), _values(values) {} 
    random_access_iterator(random_access_iterator const& other) : _index(other._index), _values(other._values) {} 
    random_access_iterator& operator=(random_access_iterator const& other) { _index = other._index ; _values = other._values; return *this;} 

    // Iterator 
    value_type& operator*() { return _values[_index]; } 
    random_access_iterator& operator++() { ++_index; return *this; } 

    // InputIterator 
    friend bool operator==(random_access_iterator& lhs, random_access_iterator& rhs) { return lhs._index == rhs._index; } 
    friend bool operator!=(random_access_iterator& lhs, random_access_iterator& rhs) { return !(lhs == rhs); } 
    value_type& operator->() { return _values[_index]; } 
    random_access_iterator operator++(int) { const auto tmp = *this; ++*this; return tmp; } 

    // ForwardIterator 
    random_access_iterator() : _index(0), _values(nullptr) {}  

    // BidirectionalIterator 
    random_access_iterator& operator--() { --_index; return *this; } 
    random_access_iterator operator--(int) { const auto tmp = *this; --*this; return tmp; } 

    // RandomAccessIterator 
    random_access_iterator& operator+=(difference_type rhs) { _index+=rhs; return *this; } 
    friend random_access_iterator operator+(random_access_iterator const& lhs, difference_type rhs) { auto tmp = lhs; tmp+=rhs; return tmp; } 
    friend random_access_iterator operator+(difference_type lhs, random_access_iterator const& rhs) { return rhs + lhs; } 

    random_access_iterator& operator-=(difference_type rhs) { _index-=rhs; return *this; } 
    friend random_access_iterator operator-(random_access_iterator const& lhs, difference_type rhs) { auto tmp = lhs; tmp-=rhs; return tmp; } 
    friend random_access_iterator operator-(difference_type lhs, random_access_iterator const& rhs) { return rhs - lhs; } 
    friend difference_type operator-(random_access_iterator const& lhs, random_access_iterator const& rhs) { return lhs._index - rhs._index; } 

    reference operator[](size_type i) const { return *(*this + i); } 

    friend bool operator<(random_access_iterator const& lhs, random_access_iterator const& rhs) { return lhs._index < rhs._index; } 
    friend bool operator<=(random_access_iterator const& lhs, random_access_iterator const& rhs) { return lhs._index <= rhs._index; } 
    friend bool operator>(random_access_iterator const& lhs, random_access_iterator const& rhs) { return lhs._index > rhs._index; } 
    friend bool operator>=(random_access_iterator const& lhs, random_access_iterator const& rhs) { return lhs._index >= rhs._index; } 
}; 

namespace std 
{ 
    template<> 
    struct iterator_traits<random_access_iterator> 
    { 
     using size_type   = random_access_iterator::size_type; 
     using value_type  = random_access_iterator::value_type; 
     using difference_type = random_access_iterator::difference_type; 
     using reference   = random_access_iterator::reference; 
     using iterator_category = random_access_iterator_tag; 
    }; 
} 

void swap(random_access_iterator& lhs, random_access_iterator& rhs) 
{ 
    std::swap(*lhs, *rhs); 
} 

나는 간단한 라이브 데모를 작성하여 this iterator in action with std::sort을 보았습니다.