컨테이너

Question

나는이

class MyClass 
{ 
    int Identifier; 
    int Context; 
    int Data; 
} 

같은 클래스를하고 난

vector<MyClass> myVector; 

같은 STL 컨테이너에 저장 할 계획하지만 난에 액세스해야합니다 그것은 extenal 색인에 의하여 (myVector[index]를 사용하여); 이 경우 내가

vector<MyClass>::iterator myIt; 
for(myIt = myVector.begin(); myIt != myVector.end(); myIt++) 
{ 
    if((myIt->Idenfifier == target_id) && 
     (myIt->Context == target_context)) 
     return *myIt; //or do something else... 
} 

처럼 뭔가 검색을 수행 할 Identifier 및 Context의 조합은 더 나은 저장하는 방법 또는 인덱스 데이터가 있습니까?

Answer 1

Boost::Multi-Index에는 부스트 의존성을 제공 할 수있는이 기능이 있습니다 (머리말 만). 배열과 같은 색인에 random_access 색인을 사용하고 식별자와 컨텍스트를 함께 비교하는 기능기를 사용하여 hashed_unique, hashed_non_unique, ordered_unique 또는 ordered_non_unique (원하는 특성에 따라 다름) 중 하나를 사용합니다.

Answer 2

예, 속도를 원한다면 공간을 희생해야합니다. 식별자/컨텍스트를 키로 사용하여 STL 집합과 같은 컬렉션에 저장하고 동시에 벡터에 저장합니다. 물론 두 개의 데이터 복사본이 필요하지 않으므로 스마트 포인터 (auto_ptr 또는 variant)를 사용하여 집합에 저장하고 바보 포인터를 사용하여 벡터에 저장합니다.

Answer 3

사용법을 알아야합니다. 왜을 색인으로 가져올 수 있어야하며 특정 요소를 찾기 위해 얼마나 자주 컨테이너를 검색해야합니까?

에 저장하면 검색 시간은 O (ln n)이지만 색인으로 참조 할 수는 없습니다.

std::vector을 사용하는 경우 색인을 생성 할 수 있지만 std::find을 사용해야 O (n)이됩니다.

그러나 색인을 사용하여 다른 것을 전달해야하는 경우 포인터를 사용할 수 있습니다. 즉,보다 빠른 검색을 위해 집합을 사용하고 특정 요소에 포인터 (색인이 아닌)를 전달합니다.