FIFO实现

Question

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

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

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

最后，如果这是一种不好的实践，我该如何实现更好的FIFO。

编辑：大家，这都是关于实现的问题。我足够熟悉STL库，并且了解几个库中的许多容器。我只想与那些能够提供良好实现或良好建议的人讨论。

- Narek

Answer 1

这是一个好的做法吗？

我没有发现任何特别的问题。

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

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

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

我会使用 std::queue ;)

- Cogwheel

Answer 2

显然，您正在使用链表作为队列的基本实现。这并没有什么特别不好的地方。

只是提醒一下，在实现方面，std::queue本身使用std::deque作为其基础实现。std::deque是一种更复杂的数据结构，由巧妙管理的动态数组块组成。

它比链表更好，因为：

1. 使用链表，每次插入都意味着您必须进行昂贵的动态内存分配。使用动态数组则不需要这样做。只有在缓冲区需要增长时才分配内存。 2. 数组元素是连续的，这意味着可以很容易地在硬件中对元素访问进行缓存。

- ryaner

Answer 3

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

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

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

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

请注意，info_现在是指向T实例的指针。使用指针的想法是，分配指针比复制复杂对象更经济。

- Nick Strupat

---

好的，但是指针会引发所有权问题。现在谁负责删除info呢？ - Steven Sudit

Answer 4

在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也可以用于此目的，但它们还提供其他功能。

- Nikolai Fetissov

Answer 5

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

- Stephen

---

这是关于实现的。我知道哪里可以找到一个好的容器 ;)。 - Narek

@Narek：我有点想到这种情况，但没有时间写更多 :) 我同意其他评论-你的实现没有问题，但使用deque会更好地提高性能。 - Stephen