为 gcc 编译器设置 std::map.end() 的哨兵值

Question

这里我特别只关心GCC编译器和运行时代码的效率。

考虑下面的代码试试我

#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;
}

第2 部分也适用于我在 Godbolt 中测试的 GCC 编译器，尽管它end()以一种奇怪的方式使用。

在GCC中，map是否分配一个节点std::pair来表示结束？添加/删除元素时它会发生变化吗？这与地图的end()实际实现方式有关，我很想知道它。

正如许多人指出的那样，如果 a 被取消引用，C++ 标准将其定义为 UB end()。

然而，根据这个答案end()，GCC 似乎已经以指向根节点的方式实现了映射。有了这个，我认为将根节点的值设置为X这里似乎是一个有效的操作。这是否意味着上面的代码应该适用于 GCC？

Answer 1

由于问题涉及end()容器的实现方式std::map，因此我将处理它，尽管该想法适用于 libstdc++ 中几乎所有基于节点的容器。

std::map与其他关联容器一样，界面的大部分是_Rb_tree对象的包装器。头文件中还有基本节点_Rb_tree_node_base和节点的实现_Rb_tree_node。该节点是基节点的派生类，其中添加了存储成员。准确地说，从 C++11 开始，存储成员不再是 type T，而是用该类型的 GCC 版本定义std::aligned_storage。

技巧是使用基节点的实例作为哨兵节点，它既代表最后一个元素（根据定义，哨兵节点是专门设计的节点，用作路径遍历终止符）又代表之前的元素。 -第一个元素。本质上，哨兵节点被解释为最后一个元素之后的位置和第一个元素之前的位置。GCC 实现设计了std::map容器的哨兵节点，以便分别使用其指向父元素、左子元素和右子元素的指针来跟踪根元素、最左边的元素和最右边的元素。

原来的实现如下：

_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; }

因此，该_M_header对象是哨兵节点。对于基于节点的容器使用这种方法有几个优点，包括以下两个：

• 由于end()迭代器直接指向哨兵节点，因此它不是悬空指针，即使容器为空也不会表现出特定行为（在这种情况下， 和 都begin()引用end()相同的事物，即哨兵节点）；
• 由于哨兵节点既用来表示倒数最后一个位置，又表示倒数第一之前位置，因此在开始之前和结束之后总会有一个有效节点，然后可以进行插入、擦除和拼接操作任何位置都以同样的方式。

此实现的一个很好的副作用是，如果迭代器end()递增，它将落在容器的开头。如前所述，std::forward_list容器不具有其他基于节点的容器的相同功能，因为它不完全是哨兵节点容器。

对于所有其他哨兵节点容器，例如std::list，以下代码有效：

std::list<int> x{0, 1, 2, 3, 4, 5};
if(++x.end() == x.begin())
  std::cout << "It works!\n";

尝试取消end()引用迭代器是 UB。