Последовательные контейнеры || C++ Primer Fifth Edition Упражнение 9.22

Question

Я сбив с толку этим упражнением.

Упражнение 9.22: Предполагая, что iv является вектором ints, что не так в следующей программе? Как вы можете исправить проблемы?

vector<int>::iterator iter = iv.begin(), 
         mid = iv.begin() + iv.size()/2; 

while(iter != mid)  
    if(*iter == some_val) 
     iv.insert(iter, 2 * some_val) 

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

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

так a) вектор будет расти следующим образом?

{1,2,3,4,5} 
{(2),1,2,3,4,5} 
{2,(2),1,2,3,4,5} 
{2,2,(2),1,2,3,4,5} 

Первая проблема в этом случае, вставка в вектор, скорее всего, мгновенно аннулирует итераторы. Вместо этого мы могли бы использовать список, но тогда мы не сможем использовать арифметику итератора для вычисления середины. Вычисление середины только один раз, как в примере, недостаточно, так как в списке, таком как.), Он будет указывать на 3 и продолжать указывать на 3, просто потому, что мы вызвали итератор в середине и инициализировали его элементом в середина не означает, что она все еще указывает на середину после всех этих вставок.

Так вот что я сделал:

vector<int>::iterator iter=iv.begin(); 

while(iter!=iv.begin()+iv.size()/2){ //calculating mid each time 
    if(*iter==some_val) 
     iv.insert(iter,2*some_val); 

    iter=iv.begin();      //revalidate iter 
    while(*iter!=some_val)     //find the original first element 
     ++iter; 
} 

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

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

Answer 1

Давайте пройдемся по программе шаг за шагом, и обновить стиль кода на современном C++:

auto iter = iv.begin(); // type will be std::vector<int>::iterator 
const auto mid = iv.begin() + iv.size()/2; // type will be std::vector<int>::iterator 

while(iter != mid) 
{ 
    if(*iter == some_val) 
    iv.insert(iter, 2 * some_val); 
} 

Первые две строки создать свой итератор пара. Цикл повторяется до тех пор, пока вы не достигнете середины вашего вектора. Условие внутри цикла проверяет, что значение в позиции iter, указывающее на, равно некоторому предопределенному значению someval. Следующая строка кода вставляет новый элемент в вектор, равный удвоенному значению some_val.

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

iter = iv.insert(iter, 2*some_val); 

Но это по-прежнему оставляет нас с mid. Существует не достаточно информации в вашем вопросе, чтобы исправить этот бит, но возможны варианты:

while(std::distance(iter, iv.end()) > iv.size()) // shift the middle when the vector grows 

const auto half = iv.size()/2; 
while(std::distance(iter, iv.begin()) < half) // only iterate until iter is halfway the original length by insertion 

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

auto iter = iv.begin(); 

while(std::distance(iter, iv.begin()) < iv.size()/2) // iterate until halfway the current vector 
{ 
    if(*iter == some_val) 
    iter = iv.insert(iter, 2 * some_val); 
    else 
    ++iter; 
} 

Но это может, конечно, не намеченный решение.

Answer 2

Исходный код не продвигает и аннулирует все использованные итераторы.

vector<int>::iterator iter = iv.begin(), 
          mid = iv.begin() + iv.size()/2; 

while(iter != mid) 
     if(*iter == some_val) 
        iv.instert(iter, 2 * some_val); 

Есть больше проблем

vector<int>::iterator iter = iv.begin(), 
         mid = iv.begin() + iv.size()/2; 
int s = iv.size()/2; // assuming we should stop at the original position 

while(iter != iv.begin() + s) { // update end condition if that is the intended function 
    if(*iter == some_val) { 
       iter = iv.instert(iter, 2 * some_val); // gets new valid iter 
       ++s; // update position of mid 
       ++iter; // skips the inserted 
    } 
    ++iter; // advance in vector. 
}