Ведение std:: list итераторов, допустимых с помощью вставки

Примечание. Это не вопрос, следует ли мне "использовать список или deque". Это вопрос о действительности итераторов в лице insert().

Это может быть простой вопрос, и я просто слишком плотный, чтобы увидеть правильный способ сделать это. Я использую (к лучшему или худшему) буфер сетевого трафика как std::list<char> buf, и я поддерживаю текущую позицию чтения как итератор readpos.

Когда я добавляю данные, я делаю что-то вроде

buf.insert(buf.end(), newdata.begin(), newdata.end());

Теперь мой вопрос: как я могу сохранить итератор readpos? Если он указывает на середину старого buf, тогда это должно быть хорошо (по гарантии итератора для std:: list), но обычно я мог читать и обрабатывать все данные, и у меня есть readpos == buf.end(). После вставки я хочу, чтобы readpos всегда указывал на следующий непрочитанный символ, который в случае вставки должен быть первым вставленным.

Любые предложения? (Не дожидаясь замены буфера на std::deque<char>, который, по-видимому, намного лучше подходит для задачи, как показано ниже.)

Обновление: Из быстрого теста с GCC4.4. Я наблюдаю, что deque и list ведут себя по-разному относительно readpos = buf.end(): после вставки в конце readpos разбивается в списке, но указывает к следующему элементу в deque. Является ли это стандартной гарантией?

(Согласно cplusplus, любая deque:: insert() недействительна для всех итераторов. Это нехорошо. Возможно, использование счетчика лучше чем итератор для отслеживания позиции в deque?)

Ответы

Ответ 1

if (readpos == buf.begin())
{
    buf.insert(buf.end(), newdata.begin(), newdata.end());
    readpos = buf.begin();
}
else
{
    --readpos;
    buf.insert(buf.end(), newdata.begin(), newdata.end());
    ++readpos;
}

Не элегантный, но он должен работать.

Ответ 2

Из http://www.sgi.com/tech/stl/List.html

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

Следовательно, readpos должен оставаться в силе после вставки.

Однако...

std::list< char > - очень неэффективный способ решения этой проблемы. Каждому байту, который вы храните в std::list, требуется указатель для отслеживания байта, а также размер структуры списка node, как правило, еще два указателя. Это не менее 12 или 24 байта (32 или 64 бит) памяти, используемой для отслеживания одного байта данных.

std::deque< char>, вероятно, лучший контейнер для этого. Подобно std::vector, он обеспечивает постоянную установку времени сзади, но также обеспечивает постоянное удаление времени спереди. Наконец, например, std::vector std::deque является контейнером с произвольным доступом, поэтому вы можете использовать смещения/индексы вместо итераторов. Эти три функции делают его эффективным выбором.

Ответ 3

Я действительно был плотным. Стандарт дает нам все необходимые инструменты. В частности, требования контейнера последовательности 23.2.3/9 говорят:

Итератор, возвращаемый из a.insert(p, i, j), указывает на копию первого элемента, вставленного в a, или p, если i == j.

Далее, описание list::insert говорит (23.3.5.4/1):

Не влияет на достоверность итераторов и ссылок.

Итак, если pos - мой текущий итератор внутри списка, который потребляется, я могу сказать:

auto it = buf.insert(buf.end(), newdata.begin(), newdata.end());

if (pos == buf.end()) { pos = it; }

Диапазон новых элементов в моем списке [it, buf.end()), а диапазон еще необработанных элементов [pos, buf.end()). Это работает, потому что если pos было равно buf.end() перед вставкой, то оно все равно после вставки, поскольку вставка не делает недействительными любые итераторы, даже не конец.

Ответ 4

list<char> - очень неэффективный способ хранения строки. Это, вероятно, в 10-20 раз больше, чем сама строка, плюс вы преследуете указатель для каждого символа...

Считаете ли вы использование std::dequeue<char> вместо этого?

[править]

Чтобы ответить на ваш фактический вопрос, добавление и удаление элементов не приводит к недействительности итераторов в list... Но end() по-прежнему будет end(). Поэтому вам нужно будет проверить это как специальный случай в том месте, где вы вставляете новый элемент, чтобы обновить итератор readpos.