3

在实现 FIFO 时，我使用了以下结构：

struct Node
{
    T info_;
    Node* link_;
    Node(T info, Node* link=0): info_(info), link_(link)
    {}
};

我认为对于许多 STL 容器（例如 List）来说，这是一个众所周知的技巧。这是一个好习惯吗？当你说 Node 有一个类型为它的指针的成员时，这对编译器意味着什么？这是一种无限循环吗？

最后，如果这是一个不好的做法，我该如何实现更好的 FIFO。

编辑：人们，这都是关于实施的。我对 STL 库足够熟悉，并且知道来自多个库的大量容器。只是我想与可以提供良好实施或良好建议的人讨论。

4

5 回答 5

2

这是一个好习惯吗？

我看不出有什么特别的问题。

当你说 Node 有一个类型为它的指针的成员时，这对编译器意味着什么？

存储指向同一类对象的指针的类没有任何问题。

最后，如果这是一个不好的做法，我该如何实现更好的 FIFO。

我会用std::queue;)

于 2010-06-13T19:25:01.663 回答
2

显然，您使用链表作为队列的底层实现。没有什么特别糟糕的。

仅供参考，就实现而言， std::queue 本身使用 std::deque 作为其底层实现。std::deque 是一种更复杂的数据结构，由巧妙管理的动态数组块组成。它最终比链表更好，因为：

  1. 使用链表，每次插入都意味着您必须进行昂贵的动态内存分配。使用动态数组，您不需要。仅当缓冲区必须增长时才分配内存。
  2. 数组元素是连续的，这意味着可以在硬件中轻松缓存元素访问。
于 2010-06-13T19:45:41.830 回答
1

您可以使用现有的 FIFO，std::queue。

于 2010-06-13T19:23:58.513 回答
1

这是实现节点的一种好方法。节点指针用于创建指向容器中下一个节点的链接。你是对的，它可以用来创建一个循环。如果容器中的最后一个节点引用第一个节点，则迭代该容器将遍历所有节点。

例如，如果容器是 FIFO 队列，则指针将引用队列中的下一个节点。也就是说， 的值link_将是 class 的另一个实例的地址Node。

如果值类型T实现了昂贵的复制构造函数，则更高效的Node类将是

struct Node
{
    T * info_;
    Node* link_;
    Node(T * info, Node* link=0): info_(info), link_(link)
    {}
};

请注意，info_现在是一个指向T. 使用指针背后的想法是分配指针比复制复杂对象更便宜。

于 2010-06-13T19:30:35.823 回答
1

指向正在声明的类型对象的指针在 C 和 C++ 中都很好。这是基于指针是固定大小的对象（例如，在 32 位平台上始终为 32 位整数）这一事实，因此您不需要知道所指向类型的完整大小。

事实上，您甚至不需要完整的类型声明来声明指针。前向声明就足够了：

class A; // forward declared type

struct B
{
    A* pa; //< pointer to A - perfectly legal
};

当然，您需要在实际访问成员时在范围内进行完整声明：

#include <A.hpp> // bring in full declaration of class A
...
B b;
b.pa = &a; // address of some instance of A
...
b.pa->func(); // invoke A's member function - this needs full declaration

对于 FIFO，请查看std::queue. std::list、std::deque和都std::vector可以用于此目的，但也提供其他功能。

于 2010-06-13T19:33:30.763 回答