여기에 내가 풀어보고 싶은 문제가있다. C++에서 map, multimap 등의 반복자는 두 가지 바람직한 기능이 없다. (1) 실행 시간에 유효성을 검사 할 수 없다. (2)있다. 그들에 대해 연산자 <이 정의되어 있지 않습니다. 즉, 다른 연관 컨테이너의 키로 사용할 수 없습니다. (나는 운영자 <이 키 순서와 어떤 관계가 있는지 상관하지 않고 같은 맵에서 반복자에 최소한 <을 사용할 수 있기를 바랍니다.)C++ 맵 할당자는 벡터에 항목을 저장합니까?
이 문제에 대한 가능한 해결책은 다음과 같습니다. convince map, multimap 등을 사용하여 키/데이터 쌍을 벡터에 저장 한 다음 반복자를 벡터 자체 및 아래 첨자 인덱스에 대한 포인터가 들어있는 작은 구조체로 만들 수 있습니다. 그런 다음 최소한 동일한 컨테이너에 대한 두 개의 이터레이터를 비교할 수 있으며 (인덱스 인덱스를 비교하여) 반복기가 유효한지 여부를 런타임에 테스트 할 수 있습니다.
표준 C++에서이 솔루션을 사용할 수 있습니까? 특히, 맵 클래스의 'Allocator'를 정의하여 실제로 벡터에 항목을 넣은 다음 Allocator :: 포인터 유형을 마지막 단락에서 설명한 작은 구조체로 정의 할 수 있습니까? Allocator :: 포인터 유형과 관련된지도의 반복자는 어떻게됩니까? Allocator :: 포인터는 실제 포인터가되어야합니까? 아니면 역 참조 연산을 지원하는 것도 될 수 있습니까?
업데이트 2013-06-11 : 응답을 이해하지 못합니다. 벡터에 (키, 데이터) 쌍이 저장되어 있으면 직접 포인터를 가졌을 때보 다 약간 더 나쁜 하위 첨자가있는 항목을 얻으려면 O (1)이므로 점근선에는 아무런 변화가 없습니다. 응답자가지도 반복기가 "주변에 보관되지"않는다고 말하는 이유는 무엇입니까? 표준에서는 참조하는 항목이 삭제되지 않는 한 반복자는 유효한 상태로 유지됩니다. '실제 문제'에 관해서는 : 심볼 테이블 (변수 이름 -> 저장 위치, 내부 범위의 변수 이름이 동일한 이름의 변수를 감싸기 때문에 맵보다는 다중 맵)에 대해 멀티 맵을 사용한다고 가정하십시오. 이제는 변수로 키잉 된 두 번째 데이터 구조가 필요하다고 말하십시오. 분명히 쉬운 해결책은 두 번째 맵의 키로 사용하는 것입니다. 이터레이터에는 연산자 < 만있는 경우 작동하는 첫 번째 맵에서 변수 이름의 특정 인스턴스에 반복기를 사용하십시오.
이렇게하면'std :: map'과 친구들에게 필요한 O (log N) 시간에 요소를 삽입하고 제거 할 수 없게됩니다. – aschepler
지도에 맞춤 비교 기능을 사용할 수 있습니다. –
해결할 실제 문제는 무엇입니까? –