What’s the time complexity of iterating through a std::set/std::map?

by

In the draft C++11 standard N3337 the answer can be found in § 24.2.1 paragraph 8:

All the categories of iterators require only those functions that are
realizable for a given category in constant time (amortized).

Since each operation on an iterator must be constant time, iterating through n elements must be O(n).

More Related Contents:

  1. What’s the difference between “STL” and “C++ Standard Library”?
  2. What are the complexity guarantees of the standard containers?
  3. Is std::vector or boost::vector thread safe?
  4. Is list::size() really O(n)?
  5. Search a vector of objects by object attribute
  6. Is the C++ std::set thread-safe?
  7. Can std::begin work with array parameters and if so, how?
  8. How can I use Standard Library (STL) classes in my dll interface or ABI?
  9. How do I erase elements from STL containers?
  10. How can std::make_heap be implemented while making at most 3N comparisons?
  11. Syntax for using std::greater when calling std::sort in C++
  12. what does `using std::swap` inside the body of a class method implementation mean?
  13. Can you remove elements from a std::list while iterating through it?
  14. Is std::vector so much slower than plain arrays?
  15. How to convert wstring into string?
  16. How do I erase an element from std::vector by index?
  17. printf with std::string?
  18. Compelling examples of custom C++ allocators?
  19. How do I Search/Find and Replace in a standard string?
  20. How to get std::vector pointer to the raw data?
  21. Heterogeneous containers in C++
  22. Why use functors over functions?
  23. How to iterate over a priority_queue?
  24. How do I store arrays in an STL list?
  25. How does std::copy work with stream iterators
  26. Is there a standard date/time class in C++?
  27. Which type of sorting is used in the std::sort()?
  28. what is the difference between const_iterator and iterator? [duplicate]
  29. Why vector access operators are not specified as noexcept?
  30. std::ofstream, check if file exists before writing

Leave a Comment