Как вставить во вложенный вектор без аннулирования итераторов

У меня есть несколько логических выражений для оценки и обработки. Возможно, с Boost все было бы лучше, но я все еще изучаю STL и не пошел по этому пути. Сейчас я изучаю проверку итератора или INvalidation, в зависимости от обстоятельств. Есть ли способ безопасно вставить новый элемент в этот вложенный вектор ниже? Если вы не хотите, чтобы взрослый мужчина плакал, не предлагайте мне все переписать :) Если серьезно, я бы также приветствовал предложения о том, как переписать это более элегантно after Я исправляю свою более насущную проблему, которая, как я подозреваю, является недействительным итератором...

... Я не очень беспокоюсь о производительности. Основываясь на этом и читая другие сообщения, возможно, std::List вместо std::vector было бы лучше, но нужно ли мне это на каждом уровне вложенности?

----nested.h 

#include <vector>

struct Term {
    uint32_t termNumber;
    std::string content;
    uint32_t importance;
    uint32_t numAppearances;
    uint32_t ContextFlags;
};

struct SubClause {
    std::string typeName;
    std::vector<Term> terms;
    std::string clauseExpression;
};

struct Clause {
    std::vector<SubClause> subClauses;
};

-----nested.cpp

#include <iostream>
#include "nested_container.h"

int main (int argc, char * const argv[]) {
    std::vector< Clause > expression;

    std::vector< Clause >::iterator clauseIter = expression.begin();
    std::vector< Clause >::iterator clauseEnd = expression.end();
    for( ; clauseIter != clauseEnd ; clauseIter++ )
    {
        std::vector< SubClause >::iterator subIter = clauseIter->subClauses.begin();
        std::vector< SubClause >::iterator subEnd = clauseIter->subClauses.end();
        for( ; subIter != subEnd ; subIter++ )
        {
            std::vector< Term >::iterator termIter = subIter->terms.begin();
            std::vector< Term >::iterator termEnd = subIter->terms.end();

            for( ; termIter != termEnd ; termIter++ )
            {

                /* Evaluate SubClause Terms based on some criteria
                 */
                /* if criteria true  */
                if( true/* criteria true? */ )
                {
                    Term newTerm = { };
                    /* fillOutTerm(newTerm) */
                    /* Invalidates the subIter pointer, pretty sure.  Anything else???? */
                    subIter->terms.push_back( newTerm ); //BAD?
                 }
            }

        }
    }

    return 0;
}

c++ nested-loops iterator vector
person user106740    schedule 20.11.2009    source источник
comment
возможный дубликат правил аннулирования итератора   -  person Lightness Races in Orbit    schedule 17.02.2013

Ответы (4)


arrow_upward
1
arrow_downward

Когда вы push_back входите в вектор, вы (потенциально) аннулируете итераторы в этот вектор, но если этот вектор оказывается одним из элементов в другом векторе, итераторы в этом другом векторе не затрагиваются.

С другой стороны, в этом случае кажется, что индексы (по крайней мере, мне) создают код, который значительно короче, проще и чище, чем итераторы:

for (i=0; i<clause.size(); i++) {
    std::vector<term> &terms = clause[i].terms;
    for (j=0; j<terms.size(); j++)
        if (criteria)
            terms.push_back(term(x, y, z));
}

В данных обстоятельствах использование итераторов кажется мне чистой потерей. С достаточной осторожностью они позволят вам хранить данные в std::list (например), но это не кажется (в данном случае) компенсацией дополнительной длины и сложности чтения. Итераторы очень полезны для общих алгоритмов, которые можно разумно применять к большому количеству контейнеров, но в остальном они часто мало что делают или вообще ничего не делают.

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

person Jerry Coffin    schedule 20.11.2009

arrow_upward
1
arrow_downward

Есть три вещи, которые делают недействительными векторные итераторы:

  • уничтожь вектор :P
  • push_back causing a reallocation (invalidates all iterators)
    • invalidates end() even without a reallocation
  • insert or erase
    • only invalidates iterators after the affected items, except an insert that causes a reallocation, which invalidates every iterator

Другие операции, которые определяются в их терминах, такие как присваивание (стирание+вставка) или очистка (стирание), ведут себя аналогично.

Vector перераспределяет память, когда size() необходимо превысить емкость(), вы можете вызвать backup(), чтобы убедиться, что capacity() имеет определенное значение.

Поскольку вы добавляете в свой внутренний цикл, он должен выглядеть примерно так:

std::vector<Term>::iterator termIter = subIter->terms.begin();
for (; termIter != terms.end(); ++termIter) {
  if (true/* criteria true? */) {
    Term newTerm = { };
    std::vector<Term>::size_type cur_pos = termIter - subIter->terms.begin();
    subIter->terms.push_back(newTerm);
    termIter = subIter->terms.begin() + cur_pos;
  }
}

Это использует свойство итераторов произвольного доступа для сохранения позиции и ее восстановления для termIter, независимо от того, должен ли вектор перераспределяться для push_back. А поскольку конечный итератор всегда получается из вектора, он всегда действителен.

Хотя не все на сайте относится к stdlib, у SGI есть хороший справочник по STL (это не то же самое, что stdlib или шаблоны в stdlib) и концепции, которые он использует.

person Community    schedule 20.11.2009
comment
Просто FWIW, push_back, который вызывает перераспределение, делает недействительными все итераторы в векторе. - person Jerry Coffin; 20.11.2009
comment
Возможно, вы имеете в виду другой контейнер. Все, что может привести к увеличению std::vector, может сделать недействительными все итераторы. - person Martin York; 20.11.2009
comment
Джерри: да, я имел в виду, что push_back делает недействительным end() даже без перераспределения; исправлено. - person ; 20.11.2009

arrow_upward
0
arrow_downward

Один из вариантов — создать копию внутреннего вектора, выполнить любые обновления для него, а затем заменить копию.

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

person user207462    schedule 20.11.2009

arrow_upward
0
arrow_downward

Я думаю, что вы слишком далеко заходите с аннулированием:

/* fillOutTerm(newTerm) */
/* Invalidates the subIter pointer, pretty sure.  Anything else???? */
subIter->terms.push_back( newTerm ); //BAD?

В этом push_back() добавляются только те итераторы, которые также связаны между собой subIter->terms. (т.е. subIter) не затрагивается, так как вы не изменяете вектор, членом которого является subIter. Глядя на ваш код, это потенциально сделает недействительными «termIter» и «termEnd».

person Martin York    schedule 20.11.2009