29

With this code:

#include <iostream>
#include <list>

int main() {
    std::cout << sizeof(std::list<void*>) << std::endl;
};

I managed to notice that on GCC 4.7 the size of std::list<void*> on C++98 is 16 bytes, and its size on C++11 is 24 bytes.

I was wondering what changed on std::list that made it bigger.

Wolf
  • 9,679
  • 7
  • 62
  • 108
André Puel
  • 8,741
  • 9
  • 52
  • 83
  • 12
    From a technical standpoint, this behavior is completely implementation-specific. The library authors could, if they liked, decide arbitrarily to make the class 100x larger without any justification. It's probably not a good idea to write any code that depends on the size of a list being exactly 16 bytes; what were you doing where this actually caused a bug? – templatetypedef Apr 08 '12 at 18:03
  • Take a look at here: http://en.cppreference.com/w/cpp/container/list You will see some member types have changed in c++11 in std::list. – dexametason Apr 08 '12 at 18:04
  • 3
    They probably cached the list size. 24 bytes is three 64-bit values - a start pointer, an end pointer, and a size. – Borealid Apr 08 '12 at 18:05
  • 4
    Without noticing, I was linking a C++98 lib with a C++11 application. This lib had a few inlines getter that were getting the wrong memory variable because of the different class memory layout the std::list caused. – André Puel Apr 08 '12 at 18:05
  • @dexametason- I'm sorry, but I don't see any change to the interface that would force the implementation to use a larger size. Can you point out specifically what it was that you're referring to? – templatetypedef Apr 08 '12 at 18:06

1 Answers1

46

C++11 requires list::size() to execute in constant time. GCC made this possible by adding the size as a data member. GCC did not do so for C++98 mode, because that would break binary compatibility.

Don't mix code compiled in C++98 mode with code compiled in C++11 mode. It doesn't work.

Update: apparently, the GCC folks had a change of heart, and C++11 conformance is less important than maintaining compatibility for now, so list::size() will no longer execute in constant time in GCC 4.7.2. It will in a future version, in both C++98 and C++11 modes.

  • 2
    What is the complexity of `std::list::splice`, now? – André Puel Apr 09 '12 at 16:44
  • @André : It depends which overload you call. Some overloads are O(1), some are O(N). – ildjarn Apr 09 '12 at 18:28
  • You need to update the size field, and so you need to count the amount of items being referenced by the iterators. – André Puel Apr 09 '12 at 18:37
  • The two and three argument splices are constant time, the four argument version (iterator range on the from list) is linear in the iterator range distance unless &from == this in which case it's constant time. – emsr Apr 09 '12 at 19:04
  • @emsr That's what the standard requires, did you check that or did you also check whether GCC's implementation conforms in that regard? –  Apr 09 '12 at 19:42
  • @hvd This is the requirement in the standard. Also,gcc did add a _M_size member which is used to speed things up. For the four argument splice and this != &__x std::distance must be used to update the size. – emsr Apr 10 '12 at 18:38
  • @emsr I asked because the bug report I linked to (which resulted in adding that member) was a case where GCC did not conform to C++11, so I'm curious whether there might be more subtle issues. –  Apr 10 '12 at 18:39
  • The bug you reference is marked RESOLVED FIXED for gcc-4.7 (just released) and the code certainly looks like the C++11 complexity should be honored. I'm not seeing anything in Bugzilla about splice not meeting the standard. – emsr Apr 10 '12 at 22:01
  • Does this mean they reverted all the ABI breaking changes when in C++11 mode? The GCC wiki still says that there's breakage: http://gcc.gnu.org/wiki/Cxx11AbiCompatibility – Joseph Garvin Sep 21 '12 at 18:40
  • @hvd: Then reverting the breakage seems pointless, except to create even more breakage. Unless full ABI compat is maintained everyone has to recompile when enabling the switch anyway. – Joseph Garvin Sep 22 '12 at 06:55
  • Perhaps? I assumed when you said "No, that isn't what this means" that you were speaking as someone in the know about the libstdc++/GCC projects. If you were just commenting that we don't know whether they removed the other ABI changes based on what @emsr said that isn't particularly helpful; that's why I asked him. – Joseph Garvin Sep 22 '12 at 14:32
  • @hvd: Yes, and my point is that goal isn't actually met in any useful way unless they've removed them all, which is my hope. – Joseph Garvin Sep 22 '12 at 21:41
  • @hvd: Because they overlap for this discussion. The ABI incompatibilities in GCC 4.7.0 and 4.6.x in C++11 mode are from them implementing more C++11 behaviors. In 4.6.x, even in C++11 mode, 4.6.x was behaving in C++03 ways due to the new features not being implemented. Undoing those changes in 4.7.2 has both the effect of fixing ABI with 4.6.x *and* making it so there are less ABI differences between C++03 and C++11 in 4.7.2 which is what is actually useful for people concerned with ABI. If they had a change of heart regarding std::list, they should revert the other incompatibilities too. – Joseph Garvin Sep 22 '12 at 22:34
  • @hvd: Nobody cares about GCC 4.6 to 4.7 compatibility when C++11 mode is enabled. They care about C++03 to C++11 ABI breakage (and that being more obvious is what likely caused the complaints leading to reverting the changes in 4.7, though I'm admittedly speculating), because that prevents most people from being able to enable the feature. That's my point. – Joseph Garvin Sep 23 '12 at 15:06
  • @hvd: That's one effect of what they did, not evidence that people care. I'm open to the possibility that sometimes people use poor phrasing, or don't explain their entire thought process all the time, or may have intentions other than the letter of what they put in the change log. But anyway, this comment thread is fruitless, so I'm abandoning it unless emsr or another GCC/libstdc++ maintainer chimes in. – Joseph Garvin Sep 23 '12 at 23:15