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

迭代、插入和删除?

c++
  •  2
  • Jookia  · 技术社区  · 15 年前

    梦想输出:

     /* DREAM OUTPUT:
     INT: 1
     TESTINT: 1
     TESTINT: 2
     TESTINT: 23
     TESTINT: 24
     TESTINT: 25
     TESTINT: 3
     TESTINT: 4
     TESTINT: 5
     TESTINT: 6
     INT: 23
     INT: 24
     INT: 25
     INT: 3
     INT: 4
     INT: 5
     INT: 6
    

    问题

     ERROR 1: Not erasing the '2' causes a bizzare effect.
     ERROR 2: Erasing the '2' causes memory corruption.
    

    代码

     #include <cstdlib>
     #include <iostream>
     #include <vector>
    
     int main(int argc, char* argv[])
     {
        std::vector<int> someInts;
    
        someInts.push_back(1);
        someInts.push_back(2);
        someInts.push_back(3);
        someInts.push_back(4);
        someInts.push_back(5);
        someInts.push_back(6);
    
        for(std::vector<int>::iterator currentInt = someInts.begin();
            currentInt != someInts.end(); ++currentInt)
         if(*currentInt == 2)
         {
            std::vector<int> someNewInts;
    
            someNewInts.push_back(23);
            someNewInts.push_back(24);
            someNewInts.push_back(25);
    
            someInts.insert(currentInt + 1, someNewInts.begin(), someNewInts.end());
            //someInts.erase(currentInt);
    
            for(std::vector<int>::iterator testInt = someInts.begin();
                testInt != someInts.end(); ++testInt)
             std::cout << "TESTINT: " << *testInt << '\n';
         }
         else
            std::cout << "INT: " << *currentInt << '\n';
    
        return 0;
     }
    

    代码很简单,但我想知道这里发生了什么。这是一个复制品,它使用了一个更大的项目中正在发生的事情的整数。这使我困惑不解。

    4 回复  |  直到 15 年前
        1
  •  2
  •   gbjbaanb    15 年前

    您需要了解STL集合之间的区别。

    向量是一个连续的(通常)内存块。当您插入中间时,它会尝试重新分配足够的内存来存储现有的数据和新的数据,然后将所有数据复制到正确的位置,并让您像什么都没有发生一样继续工作。然而,正如你所发现的-发生了一些事情。用于引用旧内存块的迭代器仍然指向那里——但数据已被移动。如果你试图使用它们,就会出现内存错误。

    一个答案是确定迭代器用于指向何处,并将其更新为指向新位置。通常情况下,人们会使用[]操作符,但您可以使用begin()+x(其中x是向量的索引)。

    或者,使用迭代器不会因插入而无效的集合。最好的是清单。列表是由小内存块(每个项目1个)和指向下一个块的指针构成的。这使得插入非常快速和容易,因为不需要修改内存,只需要指向新项两边的块的指针。您的迭代器仍然有效!

    擦除是相同的,除非您删除了迭代器引用的项,否则它是无效的(显然),因此您不能对其进行任何操作。即使是++操作符也不会工作,因为内存可能在向量中发生了变化,或者列表指针不同。因此,您可以首先获取下一个元素的迭代器,存储它,然后在删除了一个项后使用它,或者使用erase()方法中的返回值。

        2
  •  3
  •   PeterK    15 年前

    在向量中插入元素会导致与之相关的迭代器无效,因为向量可以增长,从而重新分配其内部存储空间。

        3
  •  3
  •   Greg Domjan    15 年前

    AS someInts.erase(currentInt); 使currentint无效。只有将其设置正确,才能使用它。

    事情就是这样发生的 erase() 返回列表中要继续的有效迭代器。

    一种迭代器,它指定第一个元素在任何删除的元素之外,如果不存在这样的元素,则指定指向向量结尾的指针。

    尝试

    currentInt = someInts.erase(currentInt);
    

    它将把外部循环放在测试数据开始的“23”处,并为下一个循环步进到“24”。

        4
  •  0
  •   CashCow    15 年前

    如果您使用list而不是vector作为集合,那么您将不会获得随机访问,它可能会使用更多的内存,但是您将在集合的中间不断插入时间,这样做不会使迭代器失效。

    例外情况是您正在擦除的那个,所以在循环结束时您将无法将其++化。您必须通过存储下一个元素的副本来处理这种情况。