FIFO实现

尽管实现我用以下结构的FIFO：FIFO实现

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

我认为这是一个众所周知的伎俩很多STL容器（例如用于列表）。这是一个很好的做法吗？当你说Node有一个指针类型的成员时，它对编译器意味着什么？这是一种无限循环吗？

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

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

来源

2010-06-13 Narek

指向正在声明的类型的对象的指针在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-13 19:33:30

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

来源

2010-06-13 19:23:58 Stephen

这是关于实施的。我知道在哪里找到一个好的容器;）。 – Narek 2010-06-13 19:26:44

@Narek：我觉得应该是这样，但没有时间写更多:)我同意其他评论 - 你的实现没有任何问题，但使用'deque'会更好的性能。 – Stephen 2010-06-13 23:21:56

这是一个很好的做法吗？

我没有看到任何特别的错误。

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

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

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

我会使用std::queue;）

来源

2010-06-13 19:25:01 Cogwheel

deque比排队方式更冷 – Inverse 2010-06-13 19:36:26

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

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

如果值类型T实施昂贵的拷贝构造函数，更有效的Node类将是

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

注意info_现在是一个指针的T一个实例。使用指针的想法是分配指针比复制复杂对象要便宜。

来源

2010-06-13 19:30:35

好的，但是指针会带来所有权问题。现在谁负责删除'info'？ – 2010-08-06 04:55:03

显然你使用链表作为队列的底层实现。这没有什么特别的坏处。

虽然只是FYI，在实现方面，std :: queue本身使用std :: deque作为它的底层实现。 std :: deque是一个更复杂的数据结构，它由巧妙管理的动态数组块组成。它最终比链表更好，因为：

对于链接列表，每个插入意味着您必须执行昂贵的动态内存分配。使用动态数组，你不需要。缓冲区必须增长时才分配内存。
数组元素是连续的，这意味着元素访问可以在硬件中轻松缓存。

来源

2010-06-13 19:45:41 ryaner

回答

相关问题