CODEWITHSUNDEEP
vectorstlsettime-complexity
stark
stark

Reputation: 52

time complexity issues for set and vector stl c++

what is the difference in time between accessing element in a set and vector and between for example :

int val = 5;
set <int> a;
int x = *lower_bound(a.begin(), a.end(), val); // i got time limit exceed 
int y = *a.lower_bound(val); // i got accepted time

Upvotes: 0

Views: 1294

Answers (2)

Marshall Clow
Marshall Clow

Reputation: 16670

You're making two different calls here:

  • first, there's the free function std::lower_bound that takes two iterators and a value
  • second, you're calling the member function std::set::lower_bound, which takes a set (implicitly) and a value.

The first routine is a general implementation of lower_bound and does a binary search for the answer. Since std::set::const_iterator is not random-access, that requires a lot of forward and backwards link tracking (first, advance to the middle, etc).

The second routine has knowledge of the underlying set (implemented as a tree). It starts at the root, and walks down the tree to find the value that it needs. This is much more efficient.

Upvotes: 1

skypjack
skypjack

Reputation: 50540

Are you speaking about complexity?

For the std::vector, as from the documentation:

Random access - constant O(1)

Insertion or removal of elements at the end - amortized constant O(1)

Insertion or removal of elements - linear in distance to the end of the vector O(n)

For a std::unordered_set, as from the documentation:

Search, insertion, and removal have average constant-time complexity.

The difference in time does not make much sense, for it depends on a lot of factors (as an example, how can it be the same on an i7 and a mobile phone?)

Upvotes: 0

Related Questions