14

I guess most people understand that the complexity of size() function is not guaranteed to be constant. Though in some implementations, it is constant.

The G++ compiler is probably the most commonly used compiler. So, in G++'s implementation, what's the complexity of size()? If it varies by different containers, what containers have linear complexity? For the most commonly used ones (such as list, vector, deque, set, & map), are they all constant?

Andrew Marshall
  • 95,083
  • 20
  • 220
  • 214
CuriousMind
  • 15,168
  • 20
  • 82
  • 120
  • Actually, it depends on your standard library implementation and not the compiler. – Jon Dec 12 '11 at 02:17
  • @Jon Then, what's the best way of asking this question? I thought compiler implements the standard library? How do I find out who implements it and how it was being implemented? – CuriousMind Dec 12 '11 at 02:19
  • That's a good question, which is why I just looked into the standard to see what it has to say. Turns out it outright specifies the complexity implementations should have -- see answer below. – Jon Dec 12 '11 at 02:22
  • Should is just a strong recommendation. Some things that are required don't even make the cut :) – Joe McGrath Dec 12 '11 at 02:26
  • possible duplicate of [What are the Complexity guarantees of the standard containers?](http://stackoverflow.com/questions/181693/what-are-the-complexity-guarantees-of-the-standard-containers) – Martin York Dec 12 '11 at 03:26
  • 1
    @LokiAstari Similar question for sure, but different because asking about specific implementation of standard beyond it's guarantees. Which does matter for `std::list` in GNU's STL. – Joe McGrath Dec 12 '11 at 03:34

3 Answers3

17

For C++11, the standard (23.2.1) specifies that size is O(1) for all containers in conformant implementations of the standard library (unfortunately this doesn't mean that all implementations are conformant; e.g. gcc has this issue).

For C++03, the standard (23.1) says that size "should have constant complexity", which as it turns out (thank you, commenters) is a strong but non-binding suggestion; that means you have to read the documentation for the implementation provided with each compiler.

Jon
  • 428,835
  • 81
  • 738
  • 806
  • I though the (C++03) standard relaxed the O(1) constraint for `std::list<>::size()` since there is *either* O(1) `.splice()` *or* O(1) `.size()` but not both and that it was up to the implementation to decide whether to store the list size or compute it. – André Caron Dec 12 '11 at 02:34
  • @AndréCaron: Can't find anything to that effect for `size`. OTOH it does say that `splice` can be linear (23.2.2.4-14). – Jon Dec 12 '11 at 02:38
  • 1
    AFAIK, storing the size means O(1) `.size()` and O(n) `.splice()` whereas computing it means O(1) `.splice()` and O(n) `.size()`. If it says that `.size()` *should* have constant complexity and that `.splice()` *can* be linear, then there it is. Maybe the standard committee though that `.size()` having different complexity on different implementations was a bad idea after all and now imposes linear complexity for `.splice()`. Any idea what it says about `.splice()` in C++11? – André Caron Dec 12 '11 at 02:42
  • @AndréCaron: Exactly the same as for 03. But `splice` can be done in constant time, so the "linear if the source and target lists are different" (didn't clarify this before) exception seems to be there specifically so that the size can be cached. – Jon Dec 12 '11 at 02:43
  • @AlfP.Steinbach: Indeed, without O(1) splicing, there is hardly any reason ever to use `std::list`, though its iterator invalidation rules can be convenient (subtle, but still). – André Caron Dec 12 '11 at 02:46
  • @AndréCaron: C++98, C++03 and C++11 (or N3290) and they all say the same thing for the general splice: "Constant time if &x == this; otherwise, linear time". On its own this maximum complexity requirement allows constant time for general splicing. In C++03 §23.1/5 "should have constant complexity" for size, allows linear time for size. But the C++11 §23.2.1/4 requirement of constant .size() makes that impossible. :-( It means C++11 std::list has no advantage for anything, and the fix of now allowing non-assignable members is like closing barn door after the animals have left... – Cheers and hth. - Alf Dec 12 '11 at 03:03
10

It may change depending on the version of the standard library.

For GCC recent versions (atleast up to 4.6.2) List and ones based off of List are not constant time, but implemented as { return std::distance(begin(), end()); }.

MSVC standard library keeps track of size as it changes and just returns its value (which makes splice() O(n) because it has to count when it splices).

From my /usr/include/c++/4.6.2/bits/stl_list.h :

/**  Returns the number of elements in the %list.  */
      size_type
      size() const
      { return std::distance(begin(), end()); }

vector, set, deque, and map are constant time. ,

this is std::deque's

  size_type
  size() const
  { return this->_M_impl._M_finish - this->_M_impl._M_start; }

queue and stack are actually container adapters and depend on the underlying container, which can be specified. However the default is deque, which is constant.

Joe McGrath
  • 1,481
  • 10
  • 26
  • How is "up to 4.1" ([released on February 28, 2006](http://gcc.gnu.org/releases.html)) recent? – Ben Voigt Dec 12 '11 at 02:26
  • I'm not sure whether I was using different versions but there might also be differences like O(1) on linux and O(n) on mac os. At least I encountered that problem a few months ago. – Alex Dec 12 '11 at 02:27
  • Sorry meant 4.6.1 but just checked 4.6.2 and it is still O(n). Thanks for pointing that out. – Joe McGrath Dec 12 '11 at 02:31
  • @JoeMcGrath Thanks for your reply. Do you know about the complexity of vector::size(), set::size(), map::size(), deque::size() then? Thanks a lot! – CuriousMind Dec 12 '11 at 03:07
  • @CodeNoob Updated to add those to answer. – Joe McGrath Dec 12 '11 at 03:21
  • Only the three-iterator overloads of splice needs, and is allowed, to be O(n) by 23.3.5.5 of C++11 draft http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3242.pdf. The others are O(1). – Martin Dorey Oct 08 '13 at 00:02
1

For G++ 5.4.0, file /usr/include/c++/5.4.0/bits/stl_list.h

  /**  Returns the number of elements in the %list.  */
  size_type
  size() const _GLIBCXX_NOEXCEPT
  { return this->_M_node_count(); }

For G++ 4.8.5, file /usr/include/c++/4.8.5/bits/stl_list.h

  /**  Returns the number of elements in the %list.  */
  size_type
  size() const _GLIBCXX_NOEXCEPT
  { return std::distance(begin(), end()); }

So it is linear for 4.8.5 and constant for 5.4.0

user31264
  • 6,557
  • 3
  • 26
  • 40