1. 9
  1. 1

    But Microsoft’s STL (based on Dinkumware’s) stores an extra “sentinel node” out there on the heap with the rest of the list’s nodes. So, on MSVC, both std::list’s default constructor and its move constructor need to allocate a sentinel node, and that memory allocation might (hypothetically) throw an exception.

    I don’t get this: why doesn’t the move constructor just adopt the existing sentinel node along with the rest of the nodes?

    1. 1

      I am assuming because then the moved from instance would be left in the undesirable state (without the sentinel). That’s probably why the default constructor is mentioned in that sentence.

      1. 1

        That’s almost fine according to the language spec: an object that has been moved from is in an undefined state and so doing almost anything with it is allowed to break. The problem is that there is one thing that you must be able to do: call the destructor. The destructor for a collection will, in general, iterate over everything and call its destructor. You probably could elide the sentinel for all std::list<T> where T has a trivial destructor.

        The real question for me is why the sentinel is a separate allocation and not part of std::list structure. I’d expect it to be something like:

          struct list_element_base
            list_element *next;
            list_element *prev;
        template<typename T>
        struct list
          struct list_element : list_element_base
            T element;
          list_element_base sentinel = {nullptr, nullptr};
          list_element_base *first = &sentinel;
          list_element_base *last = &sentinel;

        If even an empty list needs to have sentinel then there’s no reason to allocate it anywhere other than as a field of the structure.

        1. 2

          an object that has been moved from is in an undefined state and so doing almost anything with it is allowed to break.

          No, a moved from object is in an unspecified (by the language) but valid state. From cppreference:

          […] and leave the argument in some valid but otherwise indeterminate state. For example, moving from a std::string or from a std::vector may result in the argument being left empty. However, this behavior should not be relied upon. For some types, such as std::unique_ptr, the moved-from state is fully specified.

          So for something like std::list it’s perfectly valid to call clear() (since this function is valid to call in any valid state) and then continue using the instance as usual. But, practically, empty is a pretty natural state for a moved from std::list and so an implementation that goes out of its way to do something different would be pretty surprising to the user.