Как мы перебираем все элементы набора, вставляя в него новые элементы?

Question

учитывайте это:

// set_iterator.cpp : Defines the entry point for the console application.

#include "stdafx.h"
#include <iostream>
#include <set>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
    set<int> a1;
    set<int> a2;

    a1.insert(3);
    a1.insert(4);
    a1.insert(5);
    a2.insert(1);
    a2.insert(2);
    a2.insert(6);

    set<int>::iterator iter;
    int x = 0;
    for (iter = a1.begin(); iter != a1.end(); ++iter)
    {
        if (x == 0) {
            x = 1;
            a1.insert(a2.begin(), a2.end());
        }
        cout << *iter << endl;
    }

    system("pause");

    return 0;
}

цель - посетить каждый элемент набора ровно один раз. я думаю, что итератор недействителен после того, как мы вставим элементы в a1.

вывод 3 4 5 6

1,2 не печатаются.

как мы кодируем такую ​​ситуацию.

Answer 1

На самом деле, итератор равен , все еще действителен. Набор - это контейнер на основе узла.

Проблема в том, что в наборе элементы всегда сортируются. Перед вставкой ваш набор выглядит так:

3 4 5
^
iter

После вставки ваш набор выглядит следующим образом:

1 2 3 4 5 6
    ^
    iter

Вам придется использовать другой контейнер, если вы хотите делать то, что делаете.

Answer 2

Я хочу посетить каждый элемент набора ровно один раз, так как его размер увеличивается при обходе. Есть ли способ сделать это? - iamrohitbanga 1 час назад

В вашем коде a1 = [3, 4, 5]. Затем вы получаете итератор, который указывает на начало a1, которое равно «3». Затем вы вставляете новые элементы в a1, что приводит к [1, 2, 3, 4, 5, 6]. Тем не менее, вы по-прежнему указываете на то же значение, «3». Так что теперь вы продолжаете итерацию, и вы напечатаете 3, 4, 5, 6.

До сих пор неясно, почему вы хотите вставить список после получения итератора. Почему вы не можете вставить элементы до того, как итерирует их, как упомянул @camh?

Если вы все еще хотите это сделать, используйте вектор, поскольку это позволит вам добавлять элементы в конец списка, а это означает, что вы все равно будете указывать на «3», но список теперь будет [3 , 4, 5, 1, 2, 6], и те будут напечатаны в таком порядке.

Или добавить это:

    for (iter = a1.begin(); iter != a1.end(); ++iter)
    {
            if (x == 0) {
                    x = 1;
                    a1.insert(a2.begin(), a2.end());
                    // Reset the iterator since we've modified the list
                    iter = a1.begin();
            }
            cout << *iter << endl;
    }

Это некрасивый взломанный код, который будет работать только при определенных обстоятельствах. Лучшее решение - @ camh's. Если у вас есть причина, по которой вы не можете сделать это таким образом, нам нужны более подробные сведения.

Answer 3

Проблема не в правильности итераторов.

Проблема в том, что у набора нет определенного порядка (хотя в этом случае он выбирает отсортированный порядок, но я не верю, что требования сложности STL требуют, чтобы другая реализация могла выбрать другой порядок).

Таким образом, любые итераторы по-прежнему действительны после вызова insert (так что вы можете продолжать разыменовывать указатель и продвигать его, и он гарантированно достигнет end ()). Но любые вставленные элементы могут находиться перед вашим итератором, и вы их не увидите, если не вызовете begin () снова.

Answer 4

как мы кодируем такую ​​ситуацию.

Вы признаете, что код в блоке "if (x == 0)" выполняется только один раз, и что ничто в этом блоке не ссылается на переменную (и) цикла и, следовательно, должно быть перемещено за пределы цикла.

    a1.insert(a2.begin(), a2.end());
    for (iter = a1.begin(); iter != a1.end(); ++iter)
    {
            cout << *iter << endl;
    }

Я не знаю, может ли ваш реальный код быть подвергнут рефакторингу подобным образом, но что касается действительности вашего итератора после вставки, this говорит:

Набор имеет важное свойство, вставка нового элемента в набор не делает недействительными итераторы, которые указать на существующие элементы.

Таким образом, ваш итератор остается действительным, но вы не можете обязательно предполагать, что все вставленные элементы придут «после» текущей позиции и что они будут достигнуты любыми текущими прямыми итераторами.