-1

It's well known, that next element search complexity in binary tree is O(log(N)). But whether tree nodes are also double linked list nodes, complexity would be O(1).

So, the question is: are std::set nodes also double linked list nodes by C++ standard, or it depends on realization? In other worlds, has it++ operation complexity O(log(N) or O(1), where N is the number of set elements?

I didn't find corresponding subsection or paragraph in section "Iterators library" of https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1905.pdf Maybe I searched badly.

Misha T
  • 56
  • 5
  • Only about _iterator_ _increment_ complexity – Misha T Aug 30 '23 at 08:20
  • 1
    Is [this](https://stackoverflow.com/q/11779859/10871073) a duplicate? The answers imply (one even states) that an individual increment should be in amortized constant time complexity. – Adrian Mole Aug 30 '23 at 08:34

1 Answers1

4

From [iterator.requirements.general] p13:

All the categories of iterators require only those functions that are realizable for a given category in constant time (amortized). Therefore, requirement tables and concept definitions for the iterators do not specify complexity.

This paragraph isn't found in the C++03 standard (which you've linked); it has been added in C++11.

std::set, std::multiset, std::map, and std::multimap provide BidirectionalIterators, so they support ++i, and --i for an iterator i, and this must have amortized constant complexity.

Also, the C++ standard doesn't require that std::set is implemented as a balanced binary tree where nodes have a link to their parent, but the requirements imposed on it strongly suggest such an implementation. A simple doubly linked list couldn't satisfy all the complexity requirements.

See Also

Jan Schultke
  • 17,446
  • 6
  • 47
  • 96
  • Thanks a lot. Actually "searched badly". I hoped, that complexity is simply constant, not _amortized_. – Misha T Aug 30 '23 at 08:56
  • @MishaT A [skip list](https://en.wikipedia.org/wiki/Skip_list) also satisfies the requirements in a straightforward way (and does have strictly constant iterator increment). – john Aug 30 '23 at 08:59
  • @n.m.couldbeanAI yeah, I mean a tree structure where there are at least links that would allow forward and backward navigation. I've improved the wording to make things more clear. – Jan Schultke Aug 30 '23 at 09:22