Поддержание правильности итераторов std :: list посредством вставки - PullRequest
Новая
       40

Поддержание правильности итераторов std :: list посредством вставки

6 голосов
/ 03 июня 2011

Примечание: Это не вопрос, должен ли я использовать список или 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 () делает недействительными всех итераторов. Это бесполезно.Может быть, использование счетчика лучше, чем итератор, для отслеживания позиции в деке?)

Ответы [ 4 ]

5 голосов
/ 03 июня 2011 
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;
}

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

4 голосов
/ 03 июня 2011

С http://www.sgi.com/tech/stl/List.html

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

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

Однако ...

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

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

0 голосов
/ 17 июня 2014

Я действительно был плотным. Стандарт дает нам все необходимые инструменты. В частности, требования к контейнеру последовательности 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() до вставки, то оно все еще остается после вставки, поскольку вставка не делает недействительными любых итераторов , даже конца.

0 голосов
/ 03 июня 2011

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

Рассматривали ли вы вместо этого std::dequeue<char>

[править]

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

...