在 C 中std::set（通常使用紅黑二叉搜索樹實作），元素被自動排序，任意位置的鍵查找和洗掉需要時間 O(log n) [攤銷，即當大小變得太大時忽略重新分配當前容量]。
在已排序的 C 中std::vector，查找也很快（實際上可能比 快一點std::set），但插入很慢（因為保持排序需要時間 O(n)）。
但是，已排序的 C std::vector具有另一個屬性：它們可以快速找到范圍內的元素數量（時間為 O(log n)）。
即，排序后的 C std::vector可以快速回答：給定的 x,y 之間有多少元素？
std::set 可以快速找到范圍開始和結束的迭代器，但不知道有多少元素。
那么，是否有一種資料結構既可以實作 C 的所有速度std::set（快速查找和洗掉），又可以快速計算給定范圍內的元素數量？
（快速，我的意思是時間 O(log n)，或者可能是 log n 中的多項式，或者甚至是 sqrt(n)。只要它比 O(n) 快，因為 O(n) 幾乎相同作為微不足道的 O(n log n) 來搜索所有內容）。
（如果不可能，即使是對固定因子內的數字的估計也是有用的。對于整數，一個微不足道的上限是 y-x 1，但如何獲得下限？對于具有排序的任意物件，則沒有這樣的估計）。
編輯：我剛剛看到了 相關的問題，它本質上是問一個人是否可以計算前面元素的數量。（抱歉，之前沒看到是我的錯）。這顯然等同于這個問題（要獲取范圍內的數字，只需計算開始/結束元素并減去等）
然而，這個問題也允許資料被計算一次然后被修復，不像這里，所以這個問題（和排序的向量答案）實際上不是這個問題的重復。
uj5u.com熱心網友回復：
所有資料結構都有其優缺點，這也是標準庫提供一堆容器的原因。
并且規則是在修改的速度和資料提取的速度之間通常存在平衡。在這里，您希望輕松訪問范圍內的元素數量。基于樹的結構中的一種可能性是在每個節點中快取其子樹的元素數量。這將在每次插入或洗掉時添加平均 log(N) 操作（樹的高度），但會大大加快范圍內元素數量的計算。不幸的是，C 標準庫中很少有類是為派生量身定制的（而 AFAIKstd::set不是），因此您必須從頭開始實作您的樹。
uj5u.com熱心網友回復：
您正在尋找的資料結構是訂單統計樹
它通常實作為二叉搜索樹，其中每個節點還存盤其子樹的大小。
不幸的是，我很確定 STL 沒有提供。
uj5u.com熱心網友回復：
也許你正在尋找LinkedHashSet替代的C https://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashSet.html。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/339983.html
上一篇：UDP客戶端池發送但不接收