CODEWITHSUNDEEP
c++stltime-complexityarray-algorithms
Eduard Rostomyan
Eduard Rostomyan

Reputation: 6546

Container complexity

Hence I have a std::set<int> and std::list<int>.
I want to have my container sorted.
For set I will have complexity like O(nlogn) for n inserted elements.
For list I will have complexity like O(n) for insertion of n elements + O(nlogn) for calling list::sort.
In both cases the complexity is O(nlogn), but there is extra O(n) operations in case of std::list. And I have some constant time for set rebalancing.

Here is the question, which container will work faster?

Upvotes: 1

Views: 306

Answers (1)

Jarod42
Jarod42

Reputation: 217293

As you want a 'const' sorted container, I suggest std::vector which is cache friendly.

During initialization:

  • push_back all elements O(n).
  • std::sort the vector O(n log n).
  • std::unique if you want to remove duplicate (as std::set does). O(n).

So initialisation is O(n log n).

To check if element exists, use std::binary_search to have O(log n) instead of O(n).

Upvotes: 2

Related Questions