這種容器我的理解是：重載了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不好用
2 回答
滄海一幻覺
TA貢獻1824條經驗 獲得超5個贊
沒有。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))這種說法。當然對于漸進記號的討論超出了這個問題。
月關寶盒
TA貢獻1772條經驗 獲得超5個贊
你確定平衡樹不好用？
#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;} |
- 2 回答
- 0 關注
- 159 瀏覽
添加回答
舉報
0/150
提交
取消