1

そのため、キューの指示を含む独自の実装ファイルを作成しようとしています。リンク リストを使用して Queue クラスを実装することにしました。つまり、独自の Node 構造体を使用する必要があります。残念ながら、私は立ち往生しており、これをファイルに適切に含める方法がわかりません。

これは私がこれまでに持っているものです:

#include <string>

#ifndef NODE
template <class DataType>
struct Node
{
  DataType data;
  Node *next;
};
#endif

template <class DataType>
class Queue
{
  public: 
    Queue();
    bool isEmpty() const;
    void push(const DataType& parameter);
    bool peek(DataType& parameter) const;
    bool pop(DataType& parameter);
    void makeEmpty();

  private:
    Node<DataType>* front;
    Node<DataType>* end;
};

template <class DataType>
Queue<DataType>::Queue()
: front(0), end(0)
{
}

template <class DataType>
bool Queue<DataType>::isEmpty() const {return 0 == front;}

template <class DataType>
void Queue<DataType>::push(const DataType& parameter)
{
  Node<DataType>* node = new Node<DataType>;
  node->data = parameter;
  node->next = 0;
  if (end) end->next = node;
  else front = node;
  end = node;
}

template <class DataType>
bool Queue<DataType>::peek(DataType& parameter) const
{
  if (0 == front) return false; // failed
  parameter = front->data;
  return true; // success
}

template <class DataType>
bool Queue<DataType>::pop(DataType& parameter)
{
  if (0 == front) return false; // failed
  parameter = front->data;
  Node<DataType>* p = front->next;
  delete front;
  front = p;
  if (front == 0) end = 0;
  return true; // success
}

template <class DataType>
void Queue<DataType>::makeEmpty()
{
  end = 0;
  Node<DataType>* p;
  while (front) 
{ 
  p = front->next; 
  delete front; 
  front = p;
} 
}

#ifndef で構造体を正しく囲んでいるかどうかはわかりません (これが私が取るべきルートであるかどうかさえわかりません:/)、これと同様のことをすべきか、何かをすべきか他に構造体のコードはありますか？

4

1 に答える 1

4

＃ifdef /＃endifを完全に削除できます

これはクラステンプレートであり、すべてのオカレンスが同一である限り、複数の翻訳単位で何度も発生する可能性があります（1つの定義ルール）

別

これNode<>は純粋に個人的な関心事なので、ネストしたものにしstructます。

これは、このより「モダンなC++」スタイルを作成する小さなデモです。

編集いくつかの改善点を示し、これをレビューしてくれた@R.MartinhoFernandesに感謝します。

#include <memory>

template <typename T>
struct Queue {
    Queue() : front(), end(/*nullptr*/) {}

    // Copy-And-Swap idiom
    // see http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Copy-and-swap
    // or  http://stackoverflow.com/questions/3279543/what-is-the-copy-and-swap-idiom
    void swap(Queue& q) noexcept {
        using std::swap;
        swap(q.front, front);
        swap(q.end, end);
    }
    Queue(Queue const& q) : front(), end() {
        for(auto it=q.front.get(); it; it=it->next.get())
            push(it->data);
    }
    Queue& operator=(Queue q) {
        std::swap(*this, q);
        return *this;
    }
    // end Copy-and-swap

    // prevent stack overflows in ~Node if the list grows large (say >1k elements) 
    ~Queue() { clear(); }

    bool isEmpty() const { 
        return !front; 
    }
    void push(T const& data) {
        Ptr node(new Node(data));
        if (end)
            end->next = std::move(node);
        else
            front = std::move(node);
        end = node.get();
    }
    bool peek(T& data) const {
        if(front) data = front->data;
        return front.get();
    }
    bool pop(T& data) {
        if(!front) return false;

        data           = front->data;
        front          = std::move(front->next);
        if(!front) end = nullptr;

        return true;
    }
    void clear() {
        end = nullptr;
        while(front) front = std::move(front->next);
    }
private:
    struct Node;
    typedef std::unique_ptr<struct Node> Ptr;
    struct Node {
        Node(T data) : data(std::move(data)), next() {}
        T   data;
        Ptr next;
    };
    Ptr front;
    Node* end;
};

#include <iostream>

int main(int argc, const char *argv[]) {
    Queue<int> test;
    test.push(1);
    test.push(2);
    test.push(3);
    test.push(5);
    test.clear();
    test.push(32028);
    test.push(10842);
    test.push(1839);
    test.push(23493);
    test.push(9857);
    int x;
    test.peek(x);
    while(test.pop(x)) {
        std::cout << x << '\n';
    }
}

注：コードがpush少し行き過ぎている可能性がありますが、最近のC ++で必要な手持ちがはるかに少ないことを示しています（がなくてもstd::make_unique）。

Clangが次のバージョンを正しく処理する方法に注意してください（つまり、暗黙的std::move）：

void push(const DataType& parameter) {
    end = ((end? end->next : front) = Ptr(new Node(parameter))).get();
}

gccがそれを拒否する理由はよくわかりません。

于 2012-11-17T23:20:05.353 に答える