Sorting and querying using different containers, C++, STL

Question

Once when I was interviewing I was asked this question, and I consider the interviewer has mistaken.

Here is the question:

Consider we have a data type which has operator <. We have 2 choices.

1. To add all this data in the std::set and then querying and adding elements with std::find and std::insert. In this case the insertion of first N elements is N*logN, and each query and insertion is logN.

2. The second is to insert all this values in std::list, then sort it, and after query and insert with std::binary_search and insert. Here the insertion if N + sorting N*logN (according the interviewer) and each binary_search and insert logN.

I have answered that first case is faster, but the interviewer told me that as std::set is implemented via red-black trees, than the rebalancing is a expensive operation, thus the std::list case is faster. But after I noticed that sort for std::list can not be N*logN because it has no random access iterators.

Please help me finally understand which case is better and why?

Answer 1

Sort on a list can be done in O(n*log(n)) using merge sort. However there is a bigger problem - binary search can not be applied on the list precisely because of the lack of random access.

Still please note that a list can be implemented in many different ways, including using an array as backing and in that case you will also have random access(this is not the case with std::list, though).

The best solution to the problem is to use a std::vector and perform binary search on it(after you sort it). This way you know there is random access operator.

EDIT: as it seems the values in your container can change interactively, pre-sorting and then performing a binary search is not an option. It is so because after you insert a new value, you will have to sort the elements again. More complex version of list like skip list support that, but otherwise set should be faster by far.

Answer 2

Yes the interviewer is wrong.

Yes you should continue interviewing until you find a better firm :-)