벡터 <int> :: iterator 대 list <int> :: std :: map의 반복자 키

vector :: iterator의 map을 int로 정의 할 수 있지만 int에 대한 list :: iterator의 map을 정의 할 수없는 이유는 무엇입니까?벡터 <int> :: iterator 대 list <int> :: std :: map의 반복자 키

#include <vector> 
#include <list> 
#include <map> 
#include <algorithm> 
using namespace std; 


int main() 
{ 
    int ia[] = {1,2,3,4,5,6,7,8,9,0}; 

    vector<int> v(begin(ia), end(ia)); 
    auto it1 = find(begin(v), end(v), 4); 
    map< vector<int>::const_iterator, int > m1; 
    m1.insert(map<vector<int>::const_iterator, int>::value_type(it1,*it1)); 

    list<int> l(begin(ia), end(ia)); 
    auto it2 = find(begin(l), end(l),5); 
    map< list<int>::const_iterator, int> m2; 
    m2.insert(map<list<int>::const_iterator, int>::value_type(it2,*it2)); //doesn't compile 

}

오류 1 오류 C2678 : 이진 '<'없음 연산자 타입의 왼쪽 피연산자 취하는 발견 'CONST 성병 :: _ List_const_iterator < _Mylist>'(또는 허용 가능한 없다 문제의 두 반복자가 같은 벡터에서 오는 당신은 어떤 T.에 대한 std::list<T>에서 반복자를 비교할 수 없습니다 변환)

출처

2012-10-06 hhbilly

그리고 무엇이 오류입니까? – Useless

오류 오류 C2678 : 2 진 '<': 'const std :: _ List_const_iterator <_Mylist>'형식의 왼쪽 피연산자를 사용하는 연산자가 없습니다 (또는 허용되는 변환이 없음) – hhbilly

질문에 나는 그것을 추가했다). 흥미로운 점은'm2.insert' 라인이나 m2의 _declaration_에 관한 것입니까? – Useless

std::map은 < 또는 제공된 비교기를 사용하여 키를 비교할 것을 요구합니다.

개념적으로 랜덤 액세스 반복기는 비슷하지만 양방향 반복기는 비교할 수 없습니다. std::vector 반복자는 랜덤 액세스이고 std::list 반복자는 양방향입니다.

따라서 목록 반복기가 std::map 키 유형의 비교 요구 사항을 충족하지 못합니다. 이 일 수있는 비교기를 유용하게 결정하면이 값을지도에 전달하면됩니다. 러프 스케치 :

struct ListIterCmp { 
    bool operator() (list<int>::const_iterator a, list<int>::const_iterator b) 
    { 
     // how? 
    } 
}; 
map< list<int>::const_iterator, int, ListIterCmp> m2; 
// this should work now...

cppreference 문서 나에 대한 이전 SGI 문서를 사용하는 데 사용되는 모든 것을 포함, 여전히 업데이트됩니다. 두 가지 모두 BidirectionalIterator 개념이 아니라 RandomAccessIterator에 대해 a<b을 설명합니다.

출처

2012-10-06 20:11:01 Useless

실제로, 의심되는 것으로. 허용 된 모든 표현을 링크 목록에 제공해 주셔서 감사합니다. 양방향 반복자는 <,>을 지원하지 않지만 <=,> = 물론 어느 방향 으로든 증가 할 수 있으므로 키 유형의 엄격한 약한 순서를 위반합니다. – hhbilly

이 [cplusplus.com] (http://www.cplusplus.com/reference/std/iterator/) 문서는 약간 더 잘 정리 된 것처럼 보입니다. – hhbilly

는 사실, std::vector<T>::iterator 만 비교합니다.

출처

2012-10-06 20:00:20 Puppy

std::list 반복자를 비교할 수없는 이유는 대단히 비효율적이라는 것입니다. 다른 요소가 발견되지 않을 경우 전체 목록의 끝까지 이동해야합니다. 이는 <과 같은 단순한 연산에 대해 원하지 않는 복잡도 인 O(N)입니다.

나는 당신이 그것을 위해 필요한 것을 모르기 때문에, 대체 할 것을 제안 할 수 없다. std::list의 주소가 안정하므로 map에 대한 키로 사용할 수 있습니다. 그러나 이것이 어떻게 유용 할지를 보지 못했습니다.

출처

2012-10-06 20:06:32 jpalecek

벡터 <int> :: iterator 대 list <int> :: std :: map의 반복자 키

답변

관련 문제