Реализация FIFO

Question

При реализации FIFO я использовал следующую структуру:

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

Я думаю, что это хорошо известный прием для большого количества контейнеров STL (например, для List).Это хорошая практика?Что это значит для компилятора, когда вы говорите, что Node имеет член с типом указателя?Является ли это своего рода бесконечным циклом?

И, наконец, если это плохая практика, как я могу реализовать лучший FIFO.

РЕДАКТИРОВАТЬ: Люди, это все о реализации.Я достаточно знаком с библиотекой STL и знаю множество контейнеров из нескольких библиотек.Просто я хочу поговорить с людьми, которые могут дать хорошую реализацию или хороший совет.

Answer 1

Очевидно, что вы используете связанный список в качестве базовой реализации вашей очереди.В этом нет ничего особенно плохого.

Только к сведению, что с точки зрения реализации, сама std :: queue использует std :: deque в качестве своей базовой реализации.std :: deque - более сложная структура данных, которая состоит из блоков динамических массивов, которые управляются умно.В конечном итоге он оказывается лучше связанного списка, потому что:

1. При использовании связанного списка каждая вставка означает, что вам необходимо выполнить дорогостоящее динамическое выделение памяти.С динамическими массивами вы этого не сделаете.Вы выделяете память только тогда, когда необходимо увеличить буфер.
2. Элементы массива являются смежными, и это означает, что доступ к элементам может быть легко кэширован в аппаратном обеспечении.

Answer 2

Это хорошая практика?

Я не вижу в этом ничего особенно плохого.

Что это значит для компилятора, когда вы говоритечто у узла есть член с типом указателя?

Нет ничего плохого в том, что класс хранит указатель на объект того же класса.

И наконец,если это плохая практика, как я могу реализовать лучший FIFO.

Я бы использовал std::queue;)

Answer 3

Указатели на объекты объявленного типа хороши как на 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 могут быть использованы для этой цели, но также предоставляют другие возможности.

Answer 4

Это хороший способ реализации узла. Указатель узла используется для создания ссылки на следующий узел в контейнере. Вы правы, хотя, это может быть использовано для создания цикла. Если последний узел в контейнере ссылается на первый, итерация этого контейнера будет проходить по всем узлам.

Например, если контейнер представляет собой очередь FIFO, указатель будет ссылаться на следующий узел в очереди. То есть значение link_ будет адресом другого экземпляра класса Node.

Если тип значения T реализует дорогой конструктор копирования, более эффективный класс Node будет

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

Обратите внимание, что info_ теперь является указателем на экземпляр T. Идея использования указателя заключается в том, что назначение указателя обходится дешевле, чем копирование сложных объектов.

Answer 5

Вы можете использовать существующий FIFO, std :: queue .