代码之家 › 专栏 › 技术社区 › suszterpatt

在STL映射/集合中end()是否必须是常量?

iterator stl c++

suszterpatt · 技术社区 · 16 年前

现在,考虑下面的情况:您想要实现一个具有唯一编号的节点的图,其中每个节点都有固定数量(比如说4)的邻居。利用上述规则,您可以这样做:

class Node {
    private:
        // iterators to neighboring nodes
        std::map<int, Node>::iterator neighbors[4];
        friend class Graph;
};

class Graph {
    private:
        std::map<int, Node> nodes;
};

编辑 :不完全像这样,因为 Node 第4行(请参见回复/评论),但无论如何都要遵循这些原则)

这很好,因为这样可以插入和删除节点,而不会使结构的一致性失效(假设跟踪删除并从每个节点的数组中删除删除的迭代器)。

nodes.end() ... 或者我们可以吗?有什么保证吗 nodes.end() 上午8点将与在无数次插入/删除之后的晚上10点?也就是说,我能安全吗 == nodes.end() 在某种图形方法中?

如果不是的话,这会起作用吗?

class Graph {
    private:
        std::map<int, Node> nodes;
        std::map<int, Node>::iterator _INVALID;
    public:
        Graph() { _INVALID = nodes.end(); }
};

也就是说,我可以储存吗 nodes.end() _INVALID ?

如果这也不起作用,怎么办可以

10 回复 | 直到 16 年前

sbi 16 年前

§23.1.2.8标准中规定,集合/映射上的插入/删除操作不会使任何迭代器失效 对那些物体 (指向已删除元素的迭代器除外)。

实际上,23.1.2/8的文本有点不同(我再次强调):

插入成员不得影响迭代器和引用的有效性 ,且擦除成员应仅使迭代器和对已擦除元素的引用无效。

std::map<K,V>::end() 获取“映射的迭代器”,不应通过插入/删除使其无效。

当然,这就留下了一个问题,“notinvalidated”是否意味着它将始终具有相同的值。我个人的假设是,这没有具体说明。然而,为了让“不失效”这句话有意义,所有的结果 标准::地图<K、 V>::完()

my_map_t::iterator old_end = my_map.end();
// wildly change my_map
assert( old_end == my_map.end() );

old_end 在映射的整个更改过程中保持“有效”(作为标准约定),则该断言应通过。

免责声明 当前位置我不是以英语为母语的人,有非常

P Shved 16 年前

23.1/7表示end()返回一个迭代器

是容器的结束值。

首先,它证实了什么 end() 完() .

Michael Krelin - hacker 16 年前

好吧,没有什么可以阻止特定的集合实现 end() 完() 价值可能会改变,但是 old_end == end() . (编辑:虽然在阅读了j_random_hacker的评论后,我怀疑这段话本身的评价是否正确。) 真的

我也怀疑你能用 std::map<int,Node>::iterator 在 Node

此外,由于节点的编号是唯一的,因此可以使用 int 用于键入它们,并为无效的保留一些值。

piotr 16 年前

(多)集合和(多)映射中的迭代器在插入和删除中不会失效,因此 将.end()与以前存储的.end()值进行比较,始终会得到true

以GNU libstdc++实现为例,其中maps中的.end()返回 Rb_tree_node

从stl_tree.h:

  _M_initialize()
  {
    this->_M_header._M_color = _S_red;
    this->_M_header._M_parent = 0;
    this->_M_header._M_left = &this->_M_header;
    this->_M_header._M_right = &this->_M_header;
  }

Dewfy 16 年前

假设(1)映射是用红黑树实现的(2)您使用相同的实例“在大量的插入/删除之后”——回答“是”。

我可以说,我所知道的stl的所有化身都使用树算法。

Kieveli 16 年前

有两点:

2) 我认为,您在节点中存储一个由4个迭代器组成的数组的想法可能会有所改变,以使整个问题更有意义。您想要的是向Graph对象添加一个新的迭代器类型,该迭代器类型能够遍历单个节点的邻居。该迭代器的实现将需要访问映射的成员,这可能会引导您走上使Graph类扩展映射集合的道路。如果Graph类是扩展的std::map,那么语言就会改变,您不再需要存储无效的迭代器,而只需要编写算法来确定谁是映射中的“下一个邻居”。

j_random_hacker 16 年前

我认为很清楚:

end()将迭代器返回给传递结束的元素。
插入/删除不会影响现有迭代器,因此返回的值始终有效(除非尝试删除传递的元素,然后结束(但这将导致未定义的行为)。
因此,由end()生成的任何新迭代器(可能不同,但是)与使用运算符==的原始迭代器相比,将返回true。

因此,是的,存储end()返回的迭代器是有效的(但这只是因为关联容器的保证,因此它对vector等无效)。

记住迭代器不一定是指针。它可能是一个对象,其中容器的设计器定义了类上的所有操作。

Zan Lynx 16 年前

我相信这完全取决于所使用的迭代器的类型。

在向量中,end()是结束指针之后的一个,它会随着元素的插入和删除而明显改变。

我相信集合迭代器和映射迭代器是第二种,但我不知道有什么需要以这种方式实现它们。

Kirill V. Lyadvinsky 16 年前

C++标准声明迭代器应该保持有效。的确如此。本标准在23.1.2/8中明确规定:

不应影响 迭代器 和参考资料 到集装箱

在21.1/7中:

end()返回一个 迭代器 哪一个是过去的结束值 集装箱 .

所以迭代器 old_end 和 new_end 将是有效的。这意味着我们可以 --old_end (叫它 it1 --new_end (叫它 it2 )它将是终值迭代器(从什么定义 end() 关联容器的迭代器是 (根据23.1.2/6)和 --r

现在 it1 it2 条件是 a==b意味着+a==+b . 及 ++it1 和 ++it2 将给予 老东区 新东区 迭代器(来自++r操作表74的定义)。现在我们明白了 老东区 和应该是 .

Collin Dauphinee 15 年前

我最近有一个类似的问题,但我想知道是否打电话给你 end() 为了进行比较而检索迭代器可能具有竞争条件。

&*a == &*b 或者如果两者都不能取消引用。 找到粗体声明需要一段时间,在这里非常相关。

std::map::iterator 除非它所指向的元素已被删除,否则不能使其无效,可以保证 end ,无论获取时地图的状态如何,都将始终相互比较为true。