итератор — последовательные контейнеры || Учебник по C ++, пятое издание, упражнение 9.22
Я сбит с толку этим упражнением.
Упражнение 9.22. Если предположить, что iv — это вектор целых чисел, что не так с следующей программой? Как вы можете исправить проблему (ы)?
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, искать значение не в начале — тривиальное исправление, но тогда нужно будет проверить это значение на самом деле находится в первой половине контейнера))
так а) вектор будет расти так?
{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}
Первая проблема в этом случае, вставка в вектор, скорее всего, мгновенно делает недействительными итераторы.
Вместо этого мы могли бы использовать список, но тогда мы не можем использовать арифметику итератора для вычисления среднего значения.
Вычисления mid только один раз, как в примере, недостаточно, поскольку в списке, подобном a.), Он будет указывать на 3 и продолжать указывать на 3, просто потому, что мы вызвали итератор mid и инициализировали его с элементом в середине не означает, что он все еще указывает на середину после всех этих вставок.
Итак, вот что я сделал:
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 (похоже, они забыли все, чему научили всего несколько глав назад).
Решение
Давайте пройдемся по программе шаг за шагом и обновим стиль кода до современного 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;
}
Но это, конечно, не может быть намеченным решением.
Другие решения
Исходный код не продвигается и делает недействительными все используемые итераторы.
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.
}