1

At school I learned that a linked list consists of elements with a pointer to the next element in the list, and that a disadvantage with linked lists is that finding the size has linear complexity because you have to go through each element and count. I noticed however that in C++11, std::list.size() has constant complexity. How is this possible?

Andreas Winther Moen
  • 399
  • 3
  • 10

2 Answers2

7

Likely just keeping a member variable around that gets updated whenever you add or remove elements. Or if you merge two lists together, just add their counts together.

Then you don't have to traverse the entire list just to count elements.

NathanOliver
  • 171,901
  • 28
  • 288
  • 402
Cory Kramer
  • 114,268
  • 16
  • 167
  • 218
7

How is easy. It caches it. You can cache anything, so long as you don't let it get invalid. And how hard can keeping a cache valid be?1

Why in C++11? And what does it mean?

Prior to C++11, std::list::size did not mention how complex it was.

Some implementations kept a size field, others did not. The advantage of keeping a size field was that .size() was constant time; the advantage of not was that some splicing operations could be done in constant time.

With size() being kept track of, the splicing operation required you count the nodes being spliced. This prevented it from being constant time, and it became O(n).

C++11 decided that because all of the other .size() functions are constant time, they would mandate that list also have a constant time size. This broke the ABI of some std::lists, and preventing constant time splice.

1 There are two hard problems in computer programming. Naming things, cache invalidation, and off by one errors.

Yakk - Adam Nevraumont
  • 262,606
  • 27
  • 330
  • 524
  • ABI as in Application Binary Interface? How is that concept related to the implementation of a C++ class? I don't understand what you meant by "broke the ABI". – Violet Giraffe May 15 '17 at 19:34
  • @VioletGiraffe Adding a member to a class makes it larger, and already breaks ABI. – lisyarus May 15 '17 at 19:36
  • @VioletGiraffe The library ABI. See https://gcc.gnu.org/onlinedocs/libstdc++/manual/abi.html for libstdc++ talking about what I mean by ABI here. Basically, breaks binary compatability with previous versions of `std::list` so that code compiled against the pre-C++11 `std::list` and the C++11 compliant one have a different `sizeof(std::list)` for all `T`, because extra field. – Yakk - Adam Nevraumont May 15 '17 at 19:36
  • 1
    It does break that, but I don't believe C++ ever guaranteed binary compatibility between different standard versions or even between different library implementations. It never was reasonable to expect an application to work with a library binary different from what it's been compiled with. – Violet Giraffe May 15 '17 at 19:44
  • @VioletGiraffe C++ guarantees very little; shockingly so if you stretch it. However, various C++ compiler vendors do guarantee binary compatibility and list exceptions when it fails. Many standard changes do not require a ABI break; this is one of them. – Yakk - Adam Nevraumont May 15 '17 at 19:45
  • How does `size()` being O(1) prevent splicing being O(1)? You need the two sizes (both O(1) operations) and you need to manipulate a few pointers (also O(1)). That effectively makes the whole thing O(1) - doesn't it? – Jesper Juhl May 15 '17 at 19:53
  • @JesperJuhl Unless you're only splicing a portion of another list and it's specified as a pair of iterators. Then you need to walk the nodes to determine how many are being added. – Andrew Durward May 15 '17 at 20:00
  • @Andrew Durward but `size()` being O(1) doesn't change that. Does it? If so, how? – Jesper Juhl May 15 '17 at 20:01
  • 1
    @JesperJuhl Walking the nodes during `splice(pos, sourceList, begin, end)` is only required if we want to update the cached size value in the lists being manipulated. And we only need to do that if `size()` is guaranteed to be O(1). – Andrew Durward May 15 '17 at 20:04
  • @Andrew Durward - riiight, I see now; thanks. – Jesper Juhl May 15 '17 at 20:06