I need a vector-like container, with integer indexation, but where some indices are omitted. So what is the common way to represent such sparse array in C++?
I have an intuition that std::map is mostly used for such purposes. But it is rather slow for container where new items aren't usually added. What can you propose?
UPD: Not very "sparse". Maybe about 5%. Items mostly added during initialization step (and not very often after). But access is frequent (obviously I would not start this topic, if it was not crucial).
Items mostly added during initialization step (and not very often after). But access is frequent
In this case boost::container::flat_map can be a good option for you. It is basically just a sorted vector. Advantages (stolen from the website):
A potential drawback:
Even if the worst case happens during insertion or deletion (moving elements of the underlying vector), it is still not that bad thanks to (1) the good use of the cache, (2) relocation of the underlying elements may be vectorized (vector instructions). You would have to try it in your application to see if insertion / deletion is a problem, given your usage pattern.
flat_map is not suitable for you, I would try