Is there a c++ standard library container of size N that has log(N) insertion and search yet has N iteration instead N*log(N)?

Question

I looked at this question: boost::flat_map and its performance compared to map and unordered_map and discovered that v.oddou's answer shows iterator plots for std::map versus other containers and I discovered that std::map is very slow at iterating over all the elements. What puzzled me about this is I assume the reason std::map is slow at iterating is because it presents all elements in key order. I believe that if std::map was constructed as an array and using the special index formula (I do not remember where its referenced) for keeping track of the binary tree structure, then you could iterate quick through the array sequentially, but the keys will be presented unordered. However, I have been unable to find a standard container that does this in c++. The only bottleneck for an array like map is that dynamic resizing will be expensive, however if you are only interested in doubling the array size each time you hit the size limit, you can achieve N*log(N) average insertion time over a long computation. I looked at the pseudo code that explains the construction of nodal pointers that have tree association directions (parent, left child, right child) and I was unable to determine if this nodal structure can be modified to add a one-dimensional unordered associativity.

Is there a c++ standard library container of size N that has log(N) insertion and search yet has N iteration instead N*log(N)?

Edit:

There appears to be confusion regarding insertion complexity, where some have suggested its N and not N*log(N) for ordered maps. In my OP I did not make it clear, but I was thinking of insertion of one element at a time where you do not know what the next element will be. I believe that if you have all of the elements at once you could probably do it N time. My source is map::insert.

Answer 1

I believe that if std::map was constructed as an array and using the special index formula (I do not remember where its referenced) for keeping track of the binary tree structure, then you could iterate quick through the array sequentially, but the keys will be presented unordered.

This would come at a price of invalidating iterators and pointers due to re-allocation when array needs growth. Also iterators and pointers may invalidate on any insertion due to re-balancing.

Iterators and pointers invalidation makes it impossible to use such structure for std::map.

The only bottleneck for an array like map is that dynamic resizing will be expensive

Also re-balancing on insertion/deletion is somewhat more complex, you'll have to move elements data around (probably caring about exception safety). Yet, such a container may be useful.

---

If you want linear iteration, you can always use intrusive double-linked list for elements of your std::map. See boost::intrusive::list. Though this "linear" will not be as fast as iterating over an array, since continuous array is more cache-friendly.

Answer 2

Is there a c++ standard library container of size N that has log(N) insertion and search yet has N iteration instead N*log(N)?

Both ordered and unordered map / set satisfy these requirements. However, insertion into unordered container is only constant in average case, and linear in worst case.

---

I believe that if std::map was constructed as an array and using the special index formula (I do not remember where its referenced) for keeping track of the binary tree structure, then you could iterate quick through the array sequentially, but the keys will be presented unordered. However, I have been unable to find a standard container that does this in c++.

That's because such container is not in the standard library.

Answer 3

You may be wanting to use an std::vector and execute std::sort on it, then lookup for your keys with std::binary_search.

https://en.cppreference.com/w/cpp/algorithm/binary_search

(If you only ever need access to max element, you may also use make_heap, or priority_queue)

The constraint is that you'll need to have a clear time separation between all insertions and THEN, queries. If you intertwine queries with insertions the complexity you'll pay is off your requirements because of the need to re-sort.

(not true for the heap case, push_heap will preserve your requirements)

---

In case the above 2 possibilities are too constraining for your requirements, your last chance is to design an in-house allocator for map. It's not that hard, especially if you never delete elements, you'll be finished in no time. Your allocator should work like the underlying allocation strategy of vector. Just add at the end, and copy all to new reallocated space when full. With that technique you can create a custom iterator that doesn't follow the node pointers, but just do += sizeof(node)