5
std::vector과 같이 색인이 생성되지만 빠른 삽입, 삭제 및 색인 생성을하는 C++ 컨테이너 클래스를 찾고 있습니다. 예를 들어 기본 균형 트리로 구현 된 vector 인터페이스에는 O (logN) 삽입/삭제와 O (logN) 인덱싱도 포함됩니다.빠른 인서트와 색인이 포함 된 컨테이너입니까?
명확하게 : 나는 찾고 있지 않다. std::map<int, T>. 인덱스 N에 요소를 삽입하면 배열의 모든 후속 요소의 인덱스가 증가합니다 (std::map<int, T>의 경우는 그렇지 않습니다).
내가 찾던 바로는 AVL Array입니다. 올바른 인터페이스가 있지만 다른 옵션이 있는지 알고 싶습니다.
다른 (프로덕션 수준의) 구현을 알고 계십니까? 어쩌면 좀 더 대중적 일 수도 있습니다 (부스트는 그런 종류의 것을 가지고 있습니까?). 더 작은 메모리 풋 프린트로 뭔가? (AVL Array에 포인터가있는 노드는 내 컴퓨터에서 64 바이트입니다.)
당신은 당신이 랜덤 액세스를 요구하는 이유에 대해 자세히 설명 할 수 있습니까? – BeyelerStudios
이것은 주제가 아닌 것으로 보이며 소프트웨어/라이브러리 권장 사항을 찾습니다. –
데이터 구조 측면에서 보면 원하는 것을 수행하는 것이 더 간단하다고 생각하지 않기 때문에 부모/왼쪽/오른쪽에 원래 포인터를 더한 다음/이전에 3 ptrs가 필요합니다. 64 비트 환경에서는 총 6 개의 포인터 = 48 바이트입니다. 이것이 메모리 사용량면에서 최소한으로 달성 할 수 있습니다 (필자는 생각합니다). – mostruash