0

我正在阅读 C++ 标准模板库中的列表。我读取的元素无法使用索引访问。谁能告诉我这些列表是如何存储在内存中的？是顺序的吗？我知道链表是​​如何实现的。STL 中的列表是否也以相同的方式实现？即一个指针将具有下一个元素的地址？

如果是这种情况，迭代器的增量如何能够指向列表中的下一个元素？迭代器上的增量运算符是否重载？

4

3 回答 3

3

std::list<>是一个序列容器，就像std::vector<>,一样std::deque。它们的实现方式取决于实现。但是它们的行为和要求的特性是由标准定义的。

例如，列表必须具有恒定时间插入。向量不需要恒定时间插入，但确实有其他要求（例如恒定时间随机访问）。这样的要求倾向于实现通用算法（例如std::list，通常是传统意义上的双链表）。

迭代器在容器上“工作”，例如std::list<>通过将容器状态附加到迭代器。例如，列表迭代器可以通过指向底层实现中当前节点的指针知道它的迭代容器及其在序列枚举中的“位置”。推进迭代器只是意味着让它通过内部节点指针移动到该指针的“下一个”。

不要试图为强制行为下的实施附加太多意义。只要满足行为要求，底层实现实际上可以是任何东西。

于 2014-03-09T23:48:34.980 回答
1

std::list通常实现为链表，每个节点存储一个列表元素和指向前一个和下一个节点的指针。在链表的最开始和链表的末尾使用绑定假节点来实现链表是很常见的（它使实现更简单、更美观）。在 gcc 实现中，它们仅使用一个节点作为起始和结束假节点，因此列表实际上是循环的。这个假节点不包含任何列表元素（如果它包含，由于许多原因，这将是一个问题）。这个节点有一个非模板类型（比如说basic_node），它看起来像这样：

struct basic_node
{
    basic_node * prev, * next;
};

其他包含值的节点被模板化：

template <typename T>
struct node : basic_node
{
    T value;
};

std::list::iterator存储指向basic_node. 这带来了以下优势：大多数迭代器的代码独立于模板参数。例如，要增加迭代器，我们可以执行类似node_ptr = node_ptr->next;, where node_ptrhas type之类的操作basic_node。

取消引用时，std::list<T>::iterator可以将指向节点的指针转换为适当的模板节点：return static_cast<node<T> *>(node_ptr)->value;.

于 2014-03-10T09:28:14.297 回答
0

列表不是按顺序存储的。你正在寻找std::vector如果那是你想要的。

从文档中，“列表是序列容器，允许在序列中的任何位置进行恒定时间插入和擦除操作，并在两个方向上进行迭代。列表容器被实现为双向链表”

于 2014-03-09T22:58:45.717 回答