집합의 정렬 된 하위 집합에 액세스하기위한 데이터 구조 C++

Question

V 값이 인 i->V[i] 인디 시아를 통해 액세스 할 수 있습니다. V[i] 값 (예 : 큰 값에서 작은 값)에 따라이 값을 반복해야합니다. 또한 원래의 indecies I_1, I2,..., I_N의 하위 집합이 있고 동일한 순서 (큰에서 작은)로 해당 값에 액세스해야합니다.

올바른 데이터 구조와 절차는 무엇입니까? 나는이 문제로 얼마 동안 고생하여 도움을받을 수있었습니다.

값 (V[i])은 항상 업데이트되며 액세스는 항상 인덱스 i입니다. set 값을 나타내는 데 사용한 경우 업데이트 된 요소를 제거하고 힌트가있는 위치에 다시 삽입해야합니다 (매우 이전에 설정된 위치에 가까울 가능성이 큽니다). 하지만 세트에는 V 만 포함되며 i를 통해 요소에 액세스 할 수 없습니다. 반면에 Map 또는 Multimap 요소는 V이 아닌 I으로 정렬됩니다. 내가 등 포인터와 세트의 조합을 사용할 필요하지만 난 그것을 알아낼 수 없습니다 것으로 보인다

... 당신 말이 맞아

Answer 1

, 당신은 조합이 필요합니다. 여기에 내가 무엇을 할 것이라고입니다 :

std::map<SomeKey, SomeObject> sortedObjects; 
std::vector<std::map<SomeKey, SomeObject>::iterator> indexedObjects; 

는 객체를 삽입 :

indexedObjects.push_back(sortedObjects.emplace(newKey, newObject).first); 

여기 아이디어는 객체가 실제로 map하지만 인덱스로 액세스 할 수있는 vector에서이 iterator의를 보유하고 있다는 것입니다

지도의 객체에 추가합니다. 두 가지 모두가 아니라면 컨테이너가 수정되지 않는 것이 중요합니다. 이 두 컨테이너를 함께 포장하는 클래스를 작성하여 은을 수정할 수 없으며 수정할 수 없거나 실수하지 않도록 할 수 있습니다.

indexedObjects의 색인과 sortedObjects의 키를 사용하여 요소에 액세스하십시오. 가운데 색인에서 요소를 추가/제거해야하는 경우 vector 대신 list을 사용하면 컨테이너 가운데에서 추가/제거 할 수 있습니다. 별도의 키가 없으면 map이 아니라 set을 사용하십시오. 키/객체가 중복되는 경우 multiset 또는 multimap을 사용하십시오.