Storing in std::map/std::set vs sorting a vector after storing all data

Question

• Language: C++

• One thing I can do is allocate a vector of size n and store all data and then sort it using sort(begin(),end()). Else, I can keep putting the data in a map or set which are ordered itself so I don't have to sort afterwards. But in this case inserting an element may be more costly due to rearrangements(I guess).

  So which is the optimal choice for minimal time for a wide range of n(no. of objects)

Answer 1

It depends on the situation.

map and set are usually red-black trees, they should do a lot of work to be balanced, or the operation on it will be very slow. And it doesn't support random access. so if you only want to sort one time, you shouldn't use them.

However, if you want to continue insert elements into the container and keep order, map and set will take O(logN) time, while the sorted vector is O(N). The latter is much slower, so if you want frequently insert and delete, you should use map or set.