kalimm's blog

What Is The Complexity Of Set In C++
By kalimm, history, 10 years ago, In English 
set < int > s;
...
for(set < int > :: iterator it = s.begin(); it != s.end(); it++)
    doSomething();

What is the complexity of this code? Cost of it++ is O(1) or O(log(n)) or another complexity? Do you have any ideas about it?

Thanks for help.

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
10 years ago, hide # |
 
Vote: I like it +13 Vote: I do not like it

The complexity of full cicle is O(n), however it++ is O(log(n)), but for going over all set its O(n) cause its simply dfs. Soory for bad englando

→ Reply
»
10 years ago, hide # |
 
Vote: I like it -46 Vote: I do not like it

travelling set?

→ Reply