std::map and std::vector containers

[Frank14]

Hello all,

The container std::vector uses an array and for searching it starts from the beginning to the desired element or to the end. The price is said to be O(N). On the other hand, std::map uses a binary tree (which is ordered) for storing the data. The search price is said to be of the depth and therefore Log(N) in base 2. So, that way, std::map is said to be faster than the vector. But making a binary tree itself takes time. We call it mt1. Then searching in on that three takes mt2 time. Storing the elements in a vector takes vt1 time and "is we sort that vector" the time would be vt2. What I say is, the whole time for the two containers might be equal or near equal: mt1+mt2 = vt1+vt2. So presumably we can't say searching in an std::map is "always"faster than an std::vector. It might or might not be, I think. Agree?

[TheIdeasMan]

On the other hand, std::map uses a binary tree (which is ordered) for storing the data.

The implementation of STL containers is not specified in the standard. See http://en.cppreference.com/w/cpp/container/map

cppreference wrote:

Maps are usually implemented as red-black trees.

Edit []
There are several other considerations: Move semantics, cache effects, [concurrency,] the sorting algorithm

Basically the only real way to find out, is to test with varying amounts of data, you might have to go into the tens of millions of items before you get one out performing the other. In the past I have been surprised about how well std::vector performs versus other containers. For example, up to a point vector performed better than std::unordered_map, and that included initializing and sorting, and finding. IIRC I had to have about 8 million items before std::unordered_map out performed vector in total time, but lookup is still quicker for std::unordered_map,. JLBorges & Cubbi helped a lot to demonstrate and explain about that.

With the sorting algorithm, a bucket sort is very efficient. I had some thoughts about this: If there were 1 million ints, then instead of having say 1000 buckets with 1000 items in each, have 1 million buckets. There could be a relatively easy hash function to convert the int into it's bucket position, and relatively small chance of clash. To handle clashes, each bucket could contain a list with a very small number of items - 5 say. This of course is all at the expense of extra memory.

[helios]

For what it's worth, a few months ago I compared std::set<T> to a sorted std::vector<T>. Items could be added or removed at any time. The set turned out to be considerably faster than the vector even for relatively small sizes (1000-10000). For bigger sizes the set absolutely demolished the vector.

But, if you just need a set/map that may be written once and then only read then yes, a vector is better.
* Vectors use less memory and cause less memory fragmentation.
* Populating a vector *once* takes asymptotically as long as a set/map (linearithmic time), but the vector may still be faster due to a smaller constant factor, due to fewer allocations.
* Assuming random queries, searching a vector takes as long as searching a set/map. Binary search typically exhibits poor locality of reference, so CPU caches don't help much.
* Iterating a vector in order is faster than the same for a set/map. Linear time vs. linearithmic time. Also, unlike for a set/map, iterating a vector in order does exhibit good LOR, so CPU caches do help, making it even faster.

[HArray]

std::map is really slow Key/Value container
There are containers in 10 times faster than std::map and they have even more functionality and consumes less memory. For e.g. https://github.com/Bazist/HArray

Good Key/Value container it is always balance at least between:
Insert time/Search time/Delete time/Consuming Memory

Also sometimes important it's Scans by Range, Scans by Subtree.

In other dimension there are many other parameters in KV containers which can be floating according: Amount of Keys, Nature of Keys, Requiring recreate structure (rebuild). Load keys by one or by batches. How it works with Hard Drive. How it's growing in memory. How hard delete an element (spaces in structure) etc.

std::vector it's not Key/Value storage at all, this structure designed as different.
But on small sets (few or ten elements), full scan will be even faster that something else.
You need create a benchmark in your particular case.

[helios]

Technically std::vector<T> is a key-value store. The key just happens to always be an integer. ;-)

[HArray]

echnically std::vector<T> is a key-value store. The key just happens to always be an integer. ;-)

Only if T is ordered positive number like 0,1,2,3,4...
These numbers only tiny spot in random integer keys world.

[helios]

The key is the index to the operator[]() overload, not the T.

[HArray]

And what should be under operator[]() ?
Wait a minute, HArray with 8 thousands lines implementation ;)
Good KV storage also implements Memory Manager