c++ - Is there any boost/stl container which supports the following operation?

Question

I was looking for stl/boost container which can provide following functionality:

1. Auto insert element in sorted order. (log n)
2. Return the index/depth of element from starting node. (log n)

If there isn't one, what would be the best way to achieve this? I am thinking of a solution using a doubly link list. Would that be good choice to solve this problem ?

Answer 1

UPDATE

You need an order statistic tree. The C++ Standard Library doesn't have any, nor does it offer an easy way to implement one, see

• Rank Tree in C++

• How to find rank of an element in stl set in O(logn)

• ith order statistic using C++'s STL

Nor does boost, see under Future work and at the question linked just above.

However, the good news is, that such a tree is available in libstdc++ as an extension!

• GNU Policy-Based STL MAP implemented as order statistic tree

• Example in the doc or here

---

_{(Original answer:)}

1. Auto insert element in sorted order. (log n)
2. Return index/depth of element from starting node. (log n)

It seems to me that neither the C++ Standard Library nor boost offer a container that would provide these complexity guarantees out-of-the-box. You either have to implement this container yourself or relax your complexity requirements and allow O(n) for at least one of them.

if not: What will be the best way to achieve this ? I am thinking a solution using double link list. Will it be good choice to solve this problem ?

std::list is a doubly-linked list but you can only achieve linear time insertion. std::list is a big performance killer due to its poor use of the cache.

You might be better off with boost::container::flat_set which also offers only linear time insertion but still may surprise you with its speed due the excellent use of the cache (thanks to the hardware prefetcher). And as a bonus, you get random access iterators, so the index can be found in O(1) time if you already have the element.

If both complexity requirements are a must, then I don't see any easier way than implementing a self-balancing binary search tree and storing the subtree size as well on each parent node. Maintaining this extra information won't ruin the O(log n) complexity. It is significant and non-trivial work to implement it, even if you start with one of the red-black tree implementation of std::map (not guaranteed to be a red-black tree but in libstdc++ it is and it is open-source).

---

One more thing comes to mind: What is your usage pattern? Are your doing insertions and index look-ups completely at random, one after the other? If not, or at least mainly not, then you might switch datastructures in between and get away with one of the stl or boost containers.