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

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- arrayB. 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&nbsp;<map>using&nbsp;namespace&nbsp;std;&nbsp;int&nbsp;main()&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;map<int,&nbsp;int>&nbsp;s;&nbsp;&nbsp;&nbsp;&nbsp;s[5]&nbsp;=&nbsp;1;&nbsp;&nbsp;&nbsp;&nbsp;s[6]&nbsp;=&nbsp;2;&nbsp;&nbsp;&nbsp;&nbsp;s[7]&nbsp;=&nbsp;3;&nbsp;&nbsp;&nbsp;&nbsp;s.erase(6);&nbsp;//删除元素&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;0;}