1

我想要提供的东西：

std::list head;
std::list::node node;
while (node = head->next) {
    do something with this node
};

列表没有下一个指针对我来说很奇怪。

4

3 回答 3

4

由于 C++11 stl 有一个单链表。它的使用类似于普通的双链表。

尤其：

std::forward_list<node> my_list;

for(auto iter = my_list.begin(); iter != my_list.end(); ++iter)
{
   node &curr_node = *iter;
   // Do something with curr_node.
}
于 2012-10-06T01:22:23.023 回答
4

确实如此。只是界面发生了变化。

  1. std::list就像您的链表一样存储项目。如果您查找 GCC 4.6.1 标准库源代码文件std_list.h，您会发现：

    struct _List_node_base
{
   _List_node_base* _M_next;
   _List_node_base* _M_prev;
   //...
};

    一个双链表。

  2. std::list<T>::iterator让您以与使用“下一个”指针相同的方式浏览所有元素。同一个文件，第 151 行，内容如下：

    _Self&
operator++()
{
  _M_node = _M_node->_M_next;
  return *this;
}

  3. 对程序员隐藏所有实现细节的原因之一是它可以让您轻松更改容器。如果出于性能原因，您想使用另一个容器或制作自己的容器，则只需更改类型即可。

    typedef std::list<MyItems> itemContainer;
for (itemContainer::const_iterator it = allItems.begin(); it != allItems.end(); ++it) 
{
     // do something
}
于 2012-10-06T01:24:16.983 回答
3

列表的实际实现是隐藏的。由于标准规定元素在给定位置的插入和擦除应该可以在恒定时间内进行，我们可以假设将使用像节点这样的东西：

23.3.5 类模板列表[列表]

23.3.5.1 类模板列表概述[list.overview]

Alist是一个序列容器，它支持双向迭代器，并允许在序列中的任何位置进行恒定时间的插入和擦除操作，并自动处理存储管理。与向量 (23.3.6) 和双端队列 (23.3.3) 不同，不支持对列表元素的快速随机访问，但许多算法无论如何只需要顺序访问。

然而，关于 C++ 容器的重要一点是它们都提供了相同的接口来实际遍历内容：迭代器：

for(std::list<double>::iterator it = list.begin(); it != list.end(); ++it){
   *it += 3.0; // add 3.0 to each element
}

如果您将列表视为 C 风格的对象

struct node{
    struct node * next;
    struct node * prev;
    double value;
};

struct list{
    struct node * first;
    struct node * last;
}

上面的循环有点等价于

for(struct node * it = list.first; it != list.last + 1; it = it->next){
   *it += 3.0; // add 3.0 to each element
}

但是，诸如此类it = it->next的东西隐藏在std::list::iterator. 由于它们为所有类提供了几乎*统一的接口，因此您应该学习使用它们。

* 有些确实提供了比其他更多的功能，例如RandomAccessIteratorsvs. BidirectionalIterators，但这是您稍后将了解的内容。

于 2012-10-06T01:27:39.327 回答