set a sentinel value for std::map.end() for gcc compiler

Question

Here I specifically only care about the GCC compiler and run time code efficiency.

Consider the following code try me

#include <iostream>
#include <map>

char Find(const std::map<int, char>& map, int key) {
    auto iter = map.find(key);
    if (iter == map.end()) 
        return 'X';
    return iter->second;
}

char Find2(const std::map<int, char>& map, int key) {
    return map.find(key)->second;
}

int main()
{
    // part 1
    std::map<int, char> x{{0,'0'}, {4,'4'}};
    std::cout << Find(x, 3) << std::endl;
    std::cout << Find(x, 4) << std::endl;
    std::cout << (int)Find2(x, 3) << std::endl; // returns 0
    std::cout << Find2(x, 4) << std::endl;

    // part 2: Find2 is a shortcut
    std::map<int, char> y(x);
    y.end()->second = 'X';
    std::cout << Find2(y, 3) << std::endl;
    std::cout << Find2(y, 4) << std::endl;
}

The part 2 also works for a GCC compiler I tested in Godbolt, despite it uses the end() in a weird way.

In GCC, does map allocate a node std::pair to represent the end? Will it be changing when elements are added/deleted? This is related to how the map's end() is really implemented, and I am curious to know it.

As many people pointed out, the C++ standard defines it as UB if a the end() is dereferenced.

However, according to this answer, which GCC seems to have implemented the map in a way that the end() is pointing to a root node. With this I think setting the root node's value to X here seems to be a valid operation. Does this mean that the above code should work for GCC?

Answer 1

Since I had read several GCC implementations of STL containers, I have a fair understanding of how the end() sentinel is implemented. Since the question refers to how end() is implemented for the std::map container, I will deal with it, although the idea applies to almost all STL node-based containers.

The majority of the std::map interface, like the other associative containers, is a wrapper around a _Rb_tree object, that is implemented in the stl_tree.h file and partly in the tree.tcc file. And it is precisely in the header file that the implementation of the base node, _Rb_tree_node_base, and the node,_Rb_tree_node, can be found. The node is a derived class of the base node, to which the storage member is added. To be precise, since C++11 the storage member is no more of type T, but is defined with the GCC version of the std::aligned_storage type.

The trick is to use an instance of the base node as a sentinel node, that represents both the past-the-last element - by definition, the sentinel node is a specifically designed node that is used as a path traversal terminator - and the before-the-first element. Essentially, the sentinel node is interpreted as both the element after the last element and the element before the first element. The GCC implementation has designed the std::map's sentinel node in order to keep track of the root element, the leftmost element and the rightmost element using its pointers to the parent, the left child and the right child, respectively.

The original implementation is the following:

_Base_ptr&
       _M_root() _GLIBCXX_NOEXCEPT
       { return this->_M_impl._M_header._M_parent; }

_Base_ptr&
       _M_leftmost() _GLIBCXX_NOEXCEPT
       { return this->_M_impl._M_header._M_left; }

_Base_ptr&
      _M_rightmost() _GLIBCXX_NOEXCEPT
      { return this->_M_impl._M_header._M_right; }

The _M_header member is then the sentinel node. There are several advantages to using this approach for node-based containers, but std::forward_list, and the main benefits are the following two:

• since the end() iterator points directly to the sentinel node, it is not a dangling pointer and do not exhibits a particular behavior even if the container is empty - in this case, both begin() and end() refer to the same thing, the sentinel node;
• since the sentinel node is used to represent both the past-the-last element and the before-the-first element, there will always be a valid node before the beginning and after the end and then insert, erase and splice operations can be performed at any position in the same way.

A nice side effect of this implementation is that if the iterator end() is incremented, it will land at the beginning of the container. As mentioned before, the std::forward_list container does not have the same features of the other node-based containers, because its sentinel node improperly represents only the before-the-first element, pointed by the before_begin() iterator, and the std::nullptr is used to represent the past-the-last element. Then, if the before_begin() iterator is incremented, it will land at the beginning of the sequence, but if the end() iterator is incremented, it will lead to UB.

For all other node-based containers, such as std::list, the following code is always valid:

std::list<int> l{0, 1, 2, 3, 4, 5, 6};
auto it{l.cend()};
if(++it == l.cbegin())
  std::cout << "Wow!\n";

You may have guessed from this that trying to dereference the end() iterator is UB.