6

注意：这不是我应该“使用列表还是双端队列”的问题。这是一个关于迭代器有效性的问题insert()。

这可能是一个简单的问题，我太密集了，看不到正确的方法。我正在将网络流量缓冲区（无论好坏）实现为 a std::list<char> buf，并且我将当前的读取位置保持为 iterator readpos。

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

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

我现在的问题是，如何保持readpos迭代器有效？如果它指向buf旧readpos == buf.end(). 插入后，我希望readpos 始终指向下一个未读字符，在插入的情况下应该是第一个插入的字符。

有什么建议么？（没有将缓冲区更改为 a std::deque<char>，这似乎更适合该任务，如下所示。）

更新：从 GCC4.4 的快速测试中，我观察到 deque 和 list 的行为不同readpos = buf.end()：在末尾插入后，readpos 在列表中被破坏，但指向 deque 中的下一个元素。这是标准保证吗？

（根据cplusplus，任何 deque::insert()都会使所有迭代器失效。这不好。也许使用计数器比迭代器更好地跟踪双端队列中的位置？）

4

4 回答 4

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

不优雅，但它应该工作。

于 2011-06-03T17:38:01.560 回答
4

来自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是一个随机访问容器，因此您可以使用偏移量/索引而不是迭代器。这三个特点使它成为一个有效的选择。

于 2011-06-03T17:53:35.690 回答
0

我确实很密集。该标准为我们提供了我们需要的所有工具。具体来说，序列容器要求 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()，那么它仍然在插入之后，因为插入不会使任何迭代器无效，甚至不会使结尾无效。

于 2014-06-16T20:21:16.880 回答
-1

list<char>是一种非常低效的存储字符串的方式。它可能比字符串本身大 10-20 倍，而且您正在为每个字符追逐一个指针......

您是否考虑过std::dequeue<char>改用？

[编辑]

要回答您的实际问题，添加和删除元素不会使迭代器无效list... 但end()仍将是end(). 因此，您需要在插入新元素以更新readpos迭代器时将其作为特殊情况进行检查。

于 2011-06-03T17:17:55.187 回答