c++ c++迭代器失效 - 迭代器失效规则





如下stl容器中哪些在增加或者删除节点时指向其它节点的iterator不会失效 (5)


C ++ 11 (来源: 迭代器失效规则(C ++ 0x)

插入

序列容器

  • vector :插入点之前的所有迭代器和引用不受影响,除非新的容器大小大于先前的容量(在这种情况下,所有迭代器和引用都将失效)[23.3.6.5/1]
  • deque :所有迭代器和引用都是无效的,除非插入的成员在deque的末端(前或后)(在这种情况下,所有迭代器都是无效的,但对元素的引用不受影响)[23.3.3.4/1]
  • list :所有迭代器和引用不受影响[23.3.5.4/1]
  • forward_list :所有迭代器和引用不受影响(适用于insert_after [23.3.4.5/1]
  • array(n / a)

关联容器

  • [multi]{set,map} :所有迭代器和引用不受影响[23.2.4 / 9]

未分类的关联容器

  • unordered_[multi]{set,map} :所有迭代器在发生重新哈希时都失效,但引用不受影响[23.2.5 / 8]。 如果插入不会导致容器的大小超过z * B ,则不会发生重新散列,其中z是最大加载因子, B是当前桶的数量。 [23.2.5 / 14]

容器适配器

  • stack :从底层容器继承
  • queue :从底层容器继承
  • priority_queue :从底层容器继承

擦除

序列容器

  • vector :擦除点处或之后的每个迭代器和引用无效[23.3.6.5/3]
  • deque :擦除最后一个元素只会使迭代器和对擦除元素和过去末端迭代器的引用无效; 擦除第一个元素只会使迭代器和对擦除元素的引用无效; 擦除任何其他元素使所有迭代器和引用无效(包括过去末端迭代器)[23.3.3.4/4]
  • list :只有迭代器和对擦除元素的引用无效[23.3.5.4/3]
  • forward_list :只有迭代器和对擦除元素的引用无效(适用于 erase_after [23.3.4.5/1]
  • array(n / a)

关联容器

  • [multi]{set,map} :只有迭代器和对擦除元素的引用无效[23.2.4 / 9]

无序的关联容器

  • unordered_[multi]{set,map} :只有迭代器和对擦除元素的引用无效[23.2.5 / 13]

容器适配器

  • stack :从底层容器继承
  • queue :从底层容器继承
  • priority_queue :从底层容器继承

调整

  • vector :按照插入/擦除[23.3.6.5/12]
  • deque :根据插入/擦除[23.3.3.3/3]
  • list :按照插入/擦除[23.3.5.3/1]
  • forward_list :按照插入/擦除[23.3.4.5/25]
  • array :(n / a)

注1

除非另有规定 (明确地或通过用其他函数定义函数),调用容器成员函数或将容器作为参数传递给库函数不应使迭代器无效或更改该容器内对象的值。 [23.2.1 / 11]

笔记2

没有swap()函数会使任何引用,指针或迭代器引用正在交换的容器元素。 [注意: end()迭代器不引用任何元素,所以它可能会失效 。 - 结束] [23.2.1 / 10]

注3

除了关于swap()的上述警告之外, 还不清楚“end”迭代器是否受到上面列出的每个容器规则的约束 ; 无论如何,你应该假设他们是。

注4

vector和所有无序的关联容器支持reserve(n) ,这保证了不会自动调整大小,至少在容器的大小增长到n 。 应该注意无序的关联容器,因为未来的提议将允许指定最小的加载因子,这将允许在足够的erase操作将容器大小减小到最小值之后insert时发生再次散列; erase后应该认为保证可能无效。

什么是C ++容器的迭代器失效规则?

最好以摘要列表格式。

(注意:这意味着要成为的C ++常见问题解答的入口,如果您想批评在此表单中提供常见问题解答的想法,那么启动所有这些工作的meta上的贴子将成为这样做的地方。该问题在C ++聊天室中进行监控,常见问题解决方案首先出现在C ++聊天室中,因此您的答案很可能会被提出这一想法的人阅读。)




C ++ 03 (来源: 迭代器失效规则(C ++ 03)

插入

序列容器

  • vector :插入点之前的所有迭代器和引用不受影响,除非新的容器大小大于先前的容量(在这种情况下,所有迭代器和引用都将失效)[23.2.4.3/1]
  • deque :所有迭代器和引用都是无效的,除非插入的成员在deque的末端(前面或后面)(在这种情况下,所有迭代器都是无效的,但对元素的引用不受影响)[23.2.1.3/1]
  • list :所有迭代器和引用不受影响[23.2.2.3/1]

关联容器

  • [multi]{set,map} :所有迭代器和引用不受影响[23.1.2 / 8]

容器适配器

  • stack :从底层容器继承
  • queue :从底层容器继承
  • priority_queue :从底层容器继承

擦除

序列容器

  • vector :擦除点后的每个迭代器和引用都被无效[23.2.4.3/3]
  • deque :所有迭代器和引用都是无效的,除非被擦除的成员在deque的末端(前面或后面)(在这种情况下,只有迭代器和对被擦除成员的引用无效)[23.2.1.3/4]
  • list :只有迭代器和对擦除元素的引用无效[23.2.2.3/3]

关联容器

  • [multi]{set,map} :只有迭代器和对擦除元素的引用无效[23.1.2 / 8]

容器适配器

  • stack :从底层容器继承
  • queue :从底层容器继承
  • priority_queue :从底层容器继承

调整

  • vector :根据插入/擦除[23.2.4.2/6]
  • deque :按照插入/擦除[23.2.1.2/1]
  • list :根据插入/擦除[23.2.2.2/1]

注1

除非另有规定 (明确地或通过用其他函数定义函数),调用容器成员函数或将容器作为参数传递给库函数不应使迭代器无效或更改该容器内对象的值。 [23.1 / 11]

笔记2

在C ++ 2003中,不清楚“结束”迭代器是否遵守上述规则 ; 无论如何,你应该假设他们是(实际上就是这种情况)。

注3

指针失效的规则与引用失效的规则相同。




可能值得添加的是,只要所有插入操作都是通过此迭代器执行的,并且没有其他迭代器无效事件,则任何类型的插入迭代器( std::back_insert_iteratorstd::front_insert_iteratorstd::insert_iterator )都将保持有效发生。

例如,当您使用std::insert_iterator将一系列插入操作执行到std::vector ,该向量很可能会遇到重新分配事件,这将使所有“指向”该向量的迭代器无效。 但是,问题中的插入迭代器保证保持有效,即可以安全地继续插入序列。 根本不需要担心触发矢量重新分配。

这同样仅适用于通过插入迭代器本身执行的插入。 如果迭代器无效事件是由容器上的一些独立操作触发的,那么插入迭代器也会根据一般规则失效。

例如,这个代码

std::vector<int> v(10);
std::vector<int>::iterator it = v.begin() + 5;
std::insert_iterator<std::vector<int> > it_ins(v, it);

for (unsigned n = 20; n > 0; --n)
  *it_ins++ = rand();

保证在向量中执行有效的插入序列,即使向量“决定”在此过程中的某个地方重新分配也是如此。




由于这个问题吸引了太多的投票,并且成为常见问题解答,我想最好是写一个单独的答案来提及C ++ 03和C ++ 11之间关于std::vector的影响之间的一个显着区别插入操作对迭代器的有效性以及对reserve()capacity()引用,这是最有争议的答案未能注意到的。

C ++ 03:

重新分配将使所有引用序列中元素的引用,指针和迭代器无效。 保证在调用reserve()之后发生的插入过程中不发生重新分配,直到插入将使向量的大小大于最近调用reserve()时指定的大小为止。

C ++ 11:

重新分配将使所有引用序列中元素的引用,指针和迭代器无效。 确保在调用reserve()之后发生的插入过程中不发生重新分配,直到插入将使vector的大小大于capacity()的值为止。

所以在C ++ 03中,它不是“ unless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated) ”,而是在其他答案中提到的,而应该是“ greater than the size specified in the most recent call to reserve() “。 这是C ++ 03与C ++ 11不同之处。 在C ++ 03中,一旦insert()导致vector的大小达到前一个reserve()调用中指定的值(这可能小于当前capacity()因为reserve()会导致更大capacity()要求),任何后续的insert()都可能导致重新分配并使所有迭代器和引用无效。 在C ++ 11中,这种情况不会发生,您可以始终相信capacity()可以确定地知道下一次重新分配不会在大小超过capacity()之前发生。

总之,如果您使用的是C ++ 03向量,并且希望确保在执行插入操作时不会发生重新分配,那么它是您之前传递给reserve()的参数值,您应该检查其大小而不是对capacity()的调用的返回值,否则您可能会对“ 过早 ”重新分配感到惊讶。




当对象生命周期结束并被销毁时,会自动调用对象的析构函数。 您通常不应手动调用它。

我们将使用此对象作为示例:

class Test
{
    public:
        Test()                           { std::cout << "Created    " << this << "\n";}
        ~Test()                          { std::cout << "Destroyed  " << this << "\n";}
        Test(Test const& rhs)            { std::cout << "Copied     " << this << "\n";}
        Test& operator=(Test const& rhs) { std::cout << "Assigned   " << this << "\n";}
};

C ++中有三种(C ++ 11中有四种)不同类型的对象,对象的类型定义了对象的生命周期。

  • 静态存储持续时间对象
  • 自动存储持续时间对象
  • 动态存储持续时间对象
  • (在C ++ 11中)线程存储持续时间对象

静态存储持续时间对象

这些是最简单的,等同于全局变量。 这些对象的生命周期(通常)是应用程序的长度。 这些(通常)是在我们退出main之后在main输入和销毁之前(以创建的相反顺序)构造的。

Test  global;
int main()
{
    std::cout << "Main\n";
}

> ./a.out
Created    0x10fbb80b0
Main
Destroyed  0x10fbb80b0

注1:还有另外两种类型的静态存储持续时间对象。

类的静态成员变量。

就生命周期而言,这些意义和目的与全局变量相同。

函数内的静态变量。

这些是懒惰创建的静态存储持续时间对象。 它们是在第一次使用时创建的(在C ++ 11的线程安全庄园中)。 与其他静态存储持续时间对象一样,它们在应用程序结束时被销毁。

施工/销毁顺序

  • 编译单元内的构造顺序定义明确,与声明相同。
  • 编译单元之间的构造顺序是不确定的。
  • 破坏的顺序与构造顺序完全相反。

自动存储持续时间对象

这些是最常见的对象类型,99%的情况下你应该使用它们。

这些是三种主要类型的自动变量:

  • 函数/块内的局部变量
  • 类/数组中的成员变量。
  • 临时变量。

局部变量

退出函数/块时,将破坏在该函数/块内声明的所有变量(按创建的相反顺序)。

int main()
{
     std::cout << "Main() START\n";
     Test   scope1;
     Test   scope2;
     std::cout << "Main Variables Created\n";


     {
           std::cout << "\nblock 1 Entered\n";
           Test blockScope;
           std::cout << "block 1 about to leave\n";
     } // blockScope is destrpyed here

     {
           std::cout << "\nblock 2 Entered\n";
           Test blockScope;
           std::cout << "block 2 about to leave\n";
     } // blockScope is destrpyed here

     std::cout << "\nMain() END\n";
}// All variables from main destroyed here.

> ./a.out
Main() START
Created    0x7fff6488d938
Created    0x7fff6488d930
Main Variables Created

block 1 Entered
Created    0x7fff6488d928
block 1 about to leave
Destroyed  0x7fff6488d928

block 2 Entered
Created    0x7fff6488d918
block 2 about to leave
Destroyed  0x7fff6488d918

Main() END
Destroyed  0x7fff6488d930
Destroyed  0x7fff6488d938

成员变量

成员变量的生命周期绑定到拥有它的对象。 当业主的寿命结束时,其所有成员的寿命也将结束。 因此,您需要查看遵守相同规则的所有者的生命周期。

注意:成员始终以所有者的相反顺序销毁。

  • 因此,对于类成员,它们是按声明的顺序创建的
    并按照相反的声明销毁
  • 因此,对于数组成员,它们按0 - >顶部顺序创建
    并以相反的顺序销毁 - > 0

临时变量

这些是作为表达式的结果创建但未分配给变量的对象。 临时变量就像其他自动变量一样被销毁。 只是它们的范围的结尾是它们被创建的语句的结尾(这通常是';')。

std::string   data("Text.");

std::cout << (data + 1); // Here we create a temporary object.
                         // Which is a std::string with '1' added to "Text."
                         // This object is streamed to the output
                         // Once the statement has finished it is destroyed.
                         // So the temporary no longer exists after the ';'

注意:有些情况下可以延长临时寿命。
但这与这个简单的讨论无关。 当你明白这个文件对你来说是第二天性的时候,在它延长之前,临时的生命并不是你想做的事情。

动态存储持续时间对象

这些对象具有动态生命周期,并使用new创建并通过调用delete来销毁。

int main()
{
    std::cout << "Main()\n";
    Test*  ptr = new Test();
    delete ptr;
    std::cout << "Main Done\n";
}

> ./a.out
Main()
Created    0x1083008e0
Destroyed  0x1083008e0
Main Done

对于来自垃圾收集语言的开发人员来说,这看起来很奇怪(管理对象的生命周期)。 但问题并不像看起来那么糟糕。 在C ++中直接使用动态分配的对象是不常见的。 我们有管理对象来控制他们的生命周期。

与大多数其他GC收集的语言最接近的是std::shared_ptr 。 这将跟踪动态创建的对象的用户数量,并且当它们全部消失时将自动调用delete (我认为这是普通Java对象的更好版本)。

int main()
{
    std::cout << "Main Start\n";
    std::shared_ptr<Test>  smartPtr(new Test());
    std::cout << "Main End\n";
} // smartPtr goes out of scope here.
  // As there are no other copies it will automatically call delete on the object
  // it is holding.

> ./a.out
Main Start
Created    0x1083008e0
Main Ended
Destroyed  0x1083008e0

线程存储持续时间对象

这些是该语言的新功能。 它们非常类似于静态存储持续时间对象。 但是,与他们所生活的应用程序生活相同的生命,只要与它们相关联的执行线程。





c++ c++11 iterator c++03 c++-faq