使用C ++的STL命令统计 [英] ith order statistic using C++'s STL
问题描述
给定一个空数组，我需要进行两种查询。
Given an empty array, I need to make two type of queries
-
在数组中插入一个元素
Inserting an element in the array
查找某些元素 k的索引（显然数组必须保持排序）
Finding the index of some element k (obviously the array has to be kept sorted)
可以使用设置容器
set<int> st;
set.insert(t);
这将在 O（log（n））。
第二个查询
set<int>::iterator it;
it = st.find(k);
idx = distance(st.begin(), it);
这需要 O（n）时间。 （ O（n） [for distance（） [+ O（log（n） [for set :: find（）]）。
This takes O(n) time. (O(n) [for distance()[ + O(log(n) [for set::find()] ).
有没有办法使用C ++的预定义容器在 O（log（n））中执行两个查询？
Is there any way to do both queries in O(log(n)) using the predefined containers of C++?
http://www.cplusplus.com/reference/stl/
推荐答案
不可以（使用预定义的容器）C ++标准库的序列容器有：
No. It is not possible (with the predefined containers). The sequence containers of the C++ Standard Library have either:
- O（1）随机访问和O（N）插入/删除
或 - O（N）随机访问和O（1）插入/删除
请注意， deque 是一个例外，但是只有当插入/删除发生在数组的末尾时，一般情况下仍然是O（N）。
Note that deque is an exception, but only when the insertion/removal takes place at the ends of the array. The general case is still O(N).
此外，迭代器的分类不包括这种情况的类别。你有双向的迭代器（列表，设置， multiset ， map 和 multimap ），它们将O（N）时间跳到随机位置，下一个类别是用于随机访问迭代器（ vector ， deque 和 string ）。没有中间类别。
Furthermore, the classification of iterators does not include a category for this case. You have the bidirectional iterators (those of list, set, multiset, map and multimap), which take O(N) time to jump to a random position, and the next category is for random access iterators (those of vector, deque and string). There is no intermediate category.
添加一个新类别根本不是微不足道的。该库还实现了与容器一起使用的大量算法（例如 for_each ）。每个迭代器类别都有一个实现。
Adding a new category would not be trivial at all. The library also implements a lot of algorithms (like for_each) that work with containers. There is an implementation for every iterator category.
订单统计树已经在升级几次。据我了解：
Order statistic trees have been proposed at Boost several times. As far as I know:
- 2004: First suggestion (I don't know if it was implemented)
- 2006: "Hierarchical Data Structures"
- 2006: AVL Array (renamed as "Rank List" in Boost)
- 2012: Counter tree
他们被接受的主要困难是广义的意见，他们不是一个好处，而是一个危险。今天的程序员习惯于用典型的容器来解决他们所知道的所有问题。有经验的程序员担心，新手可能会盲目使用所提出的容器，而不是仔细选择。
The main difficulty for them being accepted was the generalized opinion that they were not a benefit, but a hazard. Today's programmers are used to solve all the problems they know with the typical containers. Experienced programmers fear that newbies might blindly use the proposed container for everything, instead of choosing carefully.
这篇关于使用C ++的STL命令统计的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
