stl :: set이 이 아닌 STL 구현을 본 사람이 있습니까?은 적색 - 검은 색 트리로 구현 되었습니까?stl :: set 구현체에 red-black 트리가 사용되지 않습니까?
내가 묻는 이유는 B-2B 나무가 B의 값에 따라 stl :: set (및 다른 빨강 - 검정 트리 구현)보다 2에서 4 배 뛰어나다는 것입니다. 사용할 수있는 더 빠른 데이터 구조가있을 때 적 - 검은 나무를 사용해야 할 강력한 이유가 있다면 궁금 할 것입니다.
Google에서 일부 사람들은 실제로 B-tree based implementation of the C++ standard library containers.을 구축했습니다. 표준 바이너리 트리 구현보다 성능이 훨씬 좋아지는 것 같습니다.
캐치가 있지만. C++ 표준은 맵이나 세트에서 요소를 삭제하면 맵이나 세트의 같은 요소를 가리키는 다른 반복자 만 무효화됩니다. 노드 스플릿 및 통합으로 인해 B 트리 기반 구현에서 이러한 새 구조의 지우기 멤버 함수는 반복자를 트리의 다른 요소로 무효화 할 수 있습니다. 결과적으로 이러한 구현은 표준 구현에 대한 완벽한 대체물이 아니며 준수 구현에 사용할 수 없습니다.
희망이 도움이됩니다.
아하. 그게 내가 찾고 있던거야. 나는 잡아야한다고 생각했습니다. 트리에 다른 반복자가있을 때 트리에 수정을 허용한다는 표준을 알지 못했습니다. 이것은 꽤 비표준적인 유스 케이스이다. 그것이 발생할 때 해킹이 가능해야합니다. –
당신이 지적한 페이지를 읽고, 나는 그들이 신중하게 이미 그러한 해킹을 제공 한 것을 본다 : https://code.google.com/p/cpp-btree/wiki/UsageInstructions#Safe_B-Tree_maps_and_sets –
붉은 검정 나무 대신 AVL 나무를 기준으로 적어도 one implementation이 있습니다.
이 구현의 적합성을 확인하지는 않았지만 B- 트리 기반 구현과 달리 적어도 은이 표준 요구 사항에 완벽하게 부합 할 수 있습니다.
저는 알고리즘 전문가는 아니지만, 표준에 의해 설정된 엄격한 최대 복잡성 ("big-O") 요구 사항이 있습니다. 대체 구현이 이러한 모든 요구 사항을 충족시킬 수 있습니까? –
다음과 같은 내용을 볼 수 있습니다 : [왜 set을 사용하면 안되며 (대신 사용해야하는 것은 무엇입니까?)] (http://lafstern.org/matt/col1.pdf). – davidhigh
@TristanBrindle : 예. B-2B 나무는 동일한 복잡성을 보장합니다. 실제로 빨강 - 검정 나무는 실제로 이진 트리를 사용하여 2-3-4 나무를 시뮬레이션 한 것이므로 더 복잡하고 느려집니다. –