O(1) 조회가있는 C++의 데이터 구조가 있습니까?C (++)에서 O (1) 조회
std::map에는 O(log(n))의 검색 시간 (오른쪽?)이 있습니다.
std에서 뭔가를 찾고 있습니다 (Boost pls가 아님). 또한, 있다면, 어떻게 작동합니까?
편집 : 좋아, 나는 충분히 추측하지 않았다. 나는 map과 같은 가치들을 연관시키고 싶다. 그래서 나는 std::map<int,string>과 같은 것을 원하고 find과 insert은 O(1)을 취해야합니다.
어레이는 O (1) 검색을 갖는다. C++ 11의 Hashtable (std :: unordered_map)에는 O (1) 조회가 있습니다. (상각되었지만 상수는 더 많거나 적음)
지도와 같은 트리 기반 데이터 구조는 큰 장점이 있으며 log (n)만으로 충분하지 않은 경우가 많습니다.
편집에 대한 응답 -> 배열의 인덱스를 말 그대로 값 중 하나에 연결할 수 있습니다. 또한 해시 테이블은 연관성이 있지만 완벽한 해시 (각 키는 정확히 1 개의 값으로 매핑 됨)를 얻는 것은 실제로 어렵습니다.
언급 할 가치가있는 또 하나의 것 : 어레이는 훌륭한 캐시 성능을 가지고 있습니다 (지역성으로 인해 일명 요소가 바로 옆에 있으므로 prefecting 엔진에서 캐시로 프리 페치 할 수 있습니다). 나무가 아니라. 합리적인 양의 요소를 사용하면 해시 성능이 점근 적 성능보다 더 중요 할 수 있습니다.
또한 TR1에 정렬되지 않은지도가 있음을 언급 할 가치가 있습니다. VS2008 및 이전 GCC와 같은 일부 컴파일러는 TR1을 구현하지만 C++ 11은 구현하지 않습니다. – Puppy
@scarletamaranth 배열이 그렇게 뛰어난 이유는 서로가 옆에 있기 때문입니다 - 시스템은 메모리에서 (인덱스 + 끝 (size) * 인덱스의 끝) 점프합니다. 말한 것처럼 정확히 분명하지는 않습니다. 캐시의. –
@Shingetsu 그건 내가 말한거야 ... – ScarletAmaranth
데이터 구조가 포함
균형 트리는 것 O (로그 n)에서 가끔 과 O (k)에서 빠져 나올 수 있습니다. 참고로
모든 데이터, 특히 키의 유형 및 * 가능한 값에 따라 달라집니다. 따라서 어떤 종류의 데이터를 저장 하시겠습니까? – Nawaz
링크 된 배열과 비슷한 것이있을 수 있습니까? 그것은 O (1)에 관한 것입니다. 링크 된 배열은 연결된 배열의 목록입니다. –
'std :: unordered_map <>'. 네임 스페이스'std'에있는 이유는 그것이'boost' 네임 스페이스에 있었기 때문입니다. – ildjarn