In a C std::set (often implemented using red-black binary search trees), the elements are automatically sorted, and key lookups and deletions in arbitrary positions take time O(log n) [amortised, i.e. ignoring reallocations when the size gets too big for the current capacity].

In a sorted C std::vector, lookups are also fast (actually probably a bit faster than std::set), but insertions are slow (since maintaining sortedness takes time O(n)).

However, sorted C std::vectors have another property: they can find the number of elements in a range quickly (in time O(log n)).

i.e., a sorted C std::vector can quickly answer: how many elements lie between given x,y?

std::set can quickly find iterators to the start and end of the range, but gives no clue how many elements are within.

So, is there a data structure that allows all the speed of a C std::set (fast lookups and deletions), but also allows fast computation of the number of elements in a given range?

(By fast, I mean time O(log n), or maybe a polynomial in log n, or maybe even sqrt(n). Just as long as it's faster than O(n), since O(n) is almost the same as the trivial O(n log n) to search through everything).

(If not possible, even an estimate of the number to within a fixed factor would be useful. For integers a trivial upper bound is y-x 1, but how to get a lower bound? For arbitrary objects with an ordering there's no such estimate).

CodePudding user response：

All data structures have their pros and cons, the reason why the standard library offers a bunch of containers.

And the rule is that there is often a balance between quickness of modifications and quickness of data extraction. Here you would like to easily access the number of elements in a range. A possibility in a tree based structure would be to cache in each node the number of elements of its subtree. That would add an average log(N) operations (the height of the tree) on each insertion or deletion, but would highly speedup the computation of the number of elements in a range. Unfortunately, few classes from the C standard library are tailored for derivation (and AFAIK std::set is not) so you will have to implement your tree from scratch.

CodePudding user response：

Maybe you are looking for LinkedHashSet alternate for C https://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashSet.html.