인덱스

Question

에 의해지도 값을 액세스 [0]?

지도가 내부적으로 정렬되어 있고 이것으로 문제가 없다는 것을 알고 색인에 의한지도에서 값을 가져 오려고합니다. 나는 [0]에는 myMap 해봤지만 오류 얻을 :

Error 1 error C2679: binary '[' : no operator found which takes a right-hand operand of type 'int' (or there is no acceptable conversion) 

나는 이런 식으로 뭔가 할 수있는 실현 :

string getKeyAtIndex (int index){ 
    map<string, int>::const_iterator end = myMap.end(); 

    int counter = 0; 
    for (map<string, int>::const_iterator it = myMap.begin(); it != end; ++it) { 
     counter++; 

     if (counter == index) 
      return it->first; 
    } 
} 

을하지만 확실히 이것은 상당히 비효율적이다? 더 좋은 방법이 있습니까?

Answer 1

귀하의 map은 위치가 아닌 키에 의해 색인 된 방식으로 액세스 할 수 없습니다. map 반복자는 list과 같이 양방향이므로 사용중인 함수는 위치에 따라 list에 액세스하는 것보다 비효율적입니다. 귀하의 기능은 std::advance(iter, index)의 도움으로 begin()에서 시작할 수 있습니다. 당신이 위치에 의하여 무작위 접근을 원하는 경우에 vector 또는 deque를 사용하십시오.

Answer 2

글쎄, 실제로는 그렇게 할 수 없습니다. 당신이 발견 한 방법은 매우 불충분합니다. 연산 복잡도가 O (n)입니다 (n은 최악의 경우, n은 맵의 요소 수입니다).

벡터 나 배열의 항목에 액세스하는 것은 비교 (일정한 계산 복잡도, 단일 연산)로 복잡성 O (1)을 갖습니다.

지도가 내부적으로 빨간색 검정색 트리 (또는 구현에 따라 다름)로 구현되었으며 모든 삽입, 삭제 및 검색 작업은 O (로그 n) 최악의 경우 (기본 2 작업에서 로그가 필요함) 트리에서 요소를 찾으려면), 꽤 좋습니다.

당신이 처리 할 수있는 방법은 벡터와지도 모두 안에있는 사용자 지정 클래스를 사용하는 것입니다. 클래스 끝의 삽입은 평균 O (1), 이름 조회는 O (log n), 색인 조회는 O (1)이되지만 제거 조작은 O (n)이됩니다.

Answer 3

이전 대답 (주석 참조) 단지 myMap.begin();

에 대해 당신은 본질적 쌍의 벡터이다 벡터 백업 저장을 사용하여 랜덤 액세스 맵을 구현할 수있는 방법. 물론 그 시점에서 표준 라이브러리 맵의 모든 이점을 잃게됩니다.

Answer 4

목표를 달성하기위한 구현 전용 (휴대 가능하지 않은) 방법이 있지만 휴대용은 아닙니다.

일반적으로 std::map은 일반적으로 키순으로 정렬되는 이진 트리 유형으로 구현됩니다. 첫 번째 요소의 정의는 순서에 따라 다릅니다. 또한 정의에서 element [0]는 트리 맨 위의 노드 또는 가장 왼쪽의 리프 노드입니까?

많은 이진 트리가 링크 된 목록으로 구현됩니다. 대부분의 링크 된 목록은 배열과 같이 직접 액세스 할 수 없습니다. 요소 5를 찾으려면 링크를 따라야하기 때문입니다. 이것은 정의에 의한 것입니다.

당신은 모두 std::vector과 std::map를 사용하여 문제를 해결할 수 있습니다

1. 동적 메모리에서 개체를 할당합니다.
2. std::map에 키와 함께 포인터를 저장하십시오.
3. std::vector의 포인터를 에서 원하는 위치에 저장하십시오.

std::map은 키로 개체에 액세스하는 효율적인 방법을 허용합니다.
std::vector은 효율적인 방법으로 인덱스를 통해 개체에 액세스 할 수 있습니다. 포인터를 저장하면 여러 복사본을 유지 관리하지 않고도 개체 인스턴스를 하나만 사용할 수 있습니다.

Answer 5

컨테이너와 같은 다른지도를 사용할 수 있습니다.
크기 필드를 유지하면 이진 검색 트리를 임의 액세스에 쉽게 만들 수 있습니다.
여기에 내가 지금보고 내 구현 ...
표준 스타일, 랜덤 액세스 반복자 ...
크기 균형 트리 ...
https://github.com/mm304321141/zzz_lib/blob/master/sbtree.h
및 B + 트리 ...
https://github.com/mm304321141/zzz_lib/blob/master/bpptree.h