1樓：暮無井見鈴
我應該回答過很類似的問題了。這裡提供一點個人見解：
既存實現上無法使得此操作的時間複雜度低於 O(N) 。既然如此不如用 std::distance 更明顯地表達複雜度。
二叉搜尋樹可以使求元素順位的操作時間複雜度為 O(log(N)) ，但這要求每個結點上多維護乙個元素數的計數。最初的 SGI STL 用了紅黑樹，而 Alexander Stepanov 可能因為（待驗證）認為求元素順位不是足夠常用的需求，而且紅黑樹加上這個東西有額外開銷，就未加上它。後來的 STL 實現和標準也沿襲了這點。
後來（ 2006 年）有人設計出了專門適用於求元素順位設計的二叉搜尋樹——大小平衡樹（ size balanced tree ）。這種樹用元素數計數維護平衡。 SBT 與紅黑樹相比，在不需要求元素順位的場合開銷更高，但在需要求元素順位的場合擁有天生更低的開銷。
由於 SBT 誕生較晚，目前似乎沒有將基於 SBT 的容器加入標準的提案。而基於實現 ABI 向後相容，目前的紅黑樹實現也不太可能被靜默地替換成 SBT 。也許未來有一日 SBT 會以新容器的形式進入標準，然而 C++ 標準很久沒考慮過新增容器了。
另一方面，就目前實現來說，紅黑樹的空間開銷不一定就比 SBT 小。由於目前實現的紅黑樹顏色標籤沒有整合到其他物件中，而是專門占有乙個分離的子物件，故即使理論上此標籤只需要 1 位，實現上由於對齊往往需要多佔乙個 size_t 的空間。
2樓：
歪個樓，set自己不維護size，那麼你幫它維護：
template
T>struct RBtree void fix_all (node*it ,node *end)} }void insert (constT& x)intselect (intk) return static_cast *>(p )->key; }int rank (intx) return res; }node *get_root ()void print ()void print_node (const node*it ,string str) cout < static_cast Node *>(it )->key; cout <<"("<< static_cast Node *>(it )->size <<")"<< endl ;print_node(it ->l, str+ " " );print_node(it ->r, str+ " ");} #undef l #undef r #undef p #undef node #undef key #undef size };RBtree 當然pbds是個好東西。 回歸正題，題主的問題我不知道答案，但是可以找到stackoverflow上有人問過類似的問題： How to find rank of an element in stl set in O(logn) C++ set: counting elements less than a value p.s. 最後日常噴一下輪子：不會的話不需要強答的。 3樓：zcysky 不明白上面的回答者為啥統一的提到SBT 什麼平衡樹都可以的吧 而且以size為平衡條件的概念也不是只有SBT一家（何況我還感覺SBT那套其實是強行拖過來的） 4樓：李魔劍 說白了就是需要乙個rank操作 但是這個可能和set本身的定位有關 畢竟,雖然你知道內部是個排序2叉樹(更準確的說是紅黑樹)維護個size域就可以方便的計算rank 但是標準有規定set一定要用排序2叉樹來實現? 畢竟它叫作set而不是rbt 所以想要這個功能網上抄個sbt就好了 我就是這麼幹的... 5樓： STL裡面是沒有這種功能的，要實現需要在紅黑樹的每個節點裡面維護乙個子樹大小的size資訊。這樣就很容易實現這個需求了。 可以自己實現乙個加入了size的紅黑樹，或者乾脆使用利用size來保持平衡的Size Balanced Tree。 如果論為什麼不這麼設計的話……畢竟要引入額外的空間來儲存size，帶來多餘的開銷。標準委員會大概認為這種操作不常見，也不太符合container的一般使用模式，所以就不多增加開銷了。反正要用的地方額外實現起來也很簡單。 6樓： 私以為紅黑樹並沒有設計成方便維護rank與元素的對映……況且從設計角度看，set應該只需滿足查詢某乙個元素存在與否的需求即可……為了使得效能穩定使用紅黑樹是不錯的選擇，所以標準實現才會是這樣。 這種需要維護查詢rank與元素的雙射的需求，推薦使用SBT，基於子樹大小的平衡樹。 7樓：冒泡 只需要維護乙個size域即可簡單做到，不過STL沒這麼設計，應該是需求不那麼普遍 相對應的需求主要在比如遊戲排行榜之類的，redis的zset就實現了，用的skiplist，跟平衡樹等價 8樓：王二 shiyuen的思路是對的, 如果用紅黑樹實現集合，需要額外維護乙個size屬性 小於x的元素個數： smallerThanX(node, x)if node == nil return 0 elseif node.value == xif node.left == nil return 0 elsereturn node.left.sizeelseif node.value > xreturn smallerThanX(node.left, x)else if node.left == nil count = 1 else count = 1 + node.left.sizereturn count + smallerThanX(node.right) 第K個元素 kthElement(node, k) r = node.left.size + 1if k == r return node elseif k < r return kthElement(node.left, k)else return kthElement(node.right, k - r) 兩個演算法的複雜度都為O(lgn) 9樓：少年之翼 logn不行吧。 紅黑樹已經可以滿足set的需求，如果紅黑樹做不到的事，就已經不在標準管轄範圍內。 對於set/map/multiset/multimap這4個associative container，主要的規定包括迭帶器是bidirectional iterator，a.find(k)和a.lower/upper_bound(k)的複雜度是對數級別，而其他相關的演算法基於迭帶器而受制於此。 只有random access iterator做減法可以O(1)，否則只能std::distance(iter1, iter2)，線性複雜度。 可以把set當作有序排列的鍊錶，你只能通過begin()和end()獲取一次只能O(1)移動一格的迭帶器，以及整個序列的尺寸。 題主可以考慮自己實現乙個帶random access iterator的associative container，這就可以logn了，但似乎很難。 10樓：陳碩 std::distance(myset.begin(), myset.upper_bound(x)); auto it = myset.begin(); std::advance(it, k); 兩個都是 O(N) 時間。 克瑞思藝術留學 今年的話大部分都是線上輔導為主，發給你義大利公尺蘭理工大學景觀專業案例和申請文書解析，可以深入了解一下。像國外院校的申請和作品集要求，每年都會有些調整，單純找專業老師的話未必熟悉最新的申請注意要點。建議要制定全面的留學計畫，從巨集觀角度出發去學習作品集和準備最佳。克瑞斯藝術留學 義大... 這個老師是ART23當代藝術館 可以查到的，在廣州很有名氣的民營藝術館來的 的館長，要不是朋友告訴我我都不知道她會收學生呢。她會根據學生的基礎先幫學生搞清楚西方藝術教育的脈絡，然後一對一訂製教學計畫，而不是把教學大綱先告訴你，直接硬教那種。她的學生大多是那種希望得到更優秀的老師指引，然後達到更好的目... 行走天地間 集權是絕對的，民主是相對的。穩定和和平只在人類歷史上存在了很短暫的時間，只是最近幾十年的和平讓大家感到和平是天經地義的。在和平的時期，民主的權力大家都有，總會有存在野心的人覬覦，想掌握更多，於是動亂就會產生，平衡被打破，權力迅速的被少數人掌握。而民主的程序是逆向的，當集權者掌握巨大的權力...求推薦乙個景觀建築作品集輔導老師
求推薦乙個純藝作品集輔導老師，不要機構
為什麼科幻背景的作品中一定會有乙個君主集權制的「xx帝國」勢力存在？