如何像数组一样使用平衡树和哈希表？

Question

这种容器我的理解是：重载了operator[]，时间复杂度<=O（logn）insert（）函数，插入一个元素 <=O（logn）erase（）函数，删除一个元素<=O（logn）之前见过平衡树和哈希表，但觉得它们和数组的使用方式不太一样比如用map,以int做下标，比如a[5]=1,a[6]=2,a[7]=3删除a[6]数组中：a[5]=1,a[6]=3平衡树：a[5]=1,a[6]无,a[7]=3不好用

Answer 1

没有。C++的所有容器没有一样能达到这个效果:
A. Sequence Container
- basic_string
- vector
- list
- forward_list( since 11)
- deque
- array
B. associative container
- map/multimap
- set/multiset
- unordered_map/unordered_multimap( since 11)
- set同上。
其他都不叫容器，包括你可能以为是容器的stack queue any等等。
你要的容器很显然就只能是map。但是正如你所说，它的下标无法做到邻接，因为维护一次邻接需要的复杂度达到nlogn级别。
但是这样的要求真的无法实现吗？不。有一种叫做order statistic tree(名次树)的数据结构能够达到这个要求，它维护键的排名，从而可以以logn级别时间查询到第k大键所在位置，这样，如果你的键是浮点数，那么你就可以达到利用浮点数的数量多这一优点几乎完美(甚至可以认为是完美)地实现你的目的。
gcc拓展pbds(policy-based data structure)中有名次树的红黑树实现，可以使用。
最后作为题外话提醒你一下渐进记号的使用。O(f(n))本身就代表上界，没有T(n)<=O(f(n))这种说法。当然对于渐进记号的讨论超出了这个问题。

Answer 2

你确定平衡树不好用？

#include <map>using namespace std; int main() {    map<int, int> s;    s[5] = 1;    s[6] = 2;    s[7] = 3;    s.erase(6); //删除元素    return 0;}