保持std :: list迭代器通过插入有效

Question

注意:这不是我应该"使用list还是deque"的问题.这是一个关于迭代器在面对的有效性的问题insert().

---

这可能是一个简单的问题,我只是太密集了,看不到正确的方法来做到这一点.我正在实现(无论好坏)网络流量缓冲区作为a std::list<char> buf,并且我将当前的读取位置保持为迭代器readpos.

当我添加数据时,我会做类似的事情

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

我现在的问题是,如何保持readpos迭代器有效？如果它指向旧的中间buf,那么它应该没问题(通过std :: list的迭代器保证),但通常我可能已经读取并处理了所有数据而且我有readpos == buf.end().在插入之后,我readpos 总是希望指向下一个未读的字符,在插入的情况下应该是第一个插入的字符.

有什么建议？(没有将缓冲区更改为a std::deque<char>,这似乎更适合任务,如下所示.)

更新:从使用GCC4.4的快速测试中我发现deque和list的行为方式不同readpos = buf.end():插入结束后,readpos在列表中被破坏,但指向deque中的下一个元素.这是标准保证吗？

(根据cplusplus,任何deque :: insert()都会使所有迭代器失效.这没有用.可能使用计数器比迭代器更好地跟踪双端队列中的位置？)

Answer 1

来自http://www.sgi.com/tech/stl/List.html

“列表有一个重要的特性，即插入和拼接不会使列表元素的迭代器无效，甚至删除也只会使指向被删除元素的迭代器无效。”

因此，readpos插入后应该仍然有效。

然而...

std::list< char >是解决这个问题的一种非常低效的方法。存储在 a 中的每个字节都std::list需要一个指针来跟踪该字节，加上列表节点结构的大小，通常还有两个指针。即至少 12 或 24 字节（32 或 64 位）的内存用于跟踪单个字节的数据。

std::deque< char>可能是一个更好的容器。就像std::vector它在后面提供恒定时间插入一样，但它也在前面提供恒定时间移除。最后，likestd::vector std::deque是一个随机访问容器，因此您可以使用偏移量/索引而不是迭代器。这三个功能使其成为有效的选择。

Answer 2

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;
}

不优雅,但它应该工作.