5

私は C++ を学び始めており、演習として単純なLinkedListクラスを実装することにしました (以下にコードの一部があります)。コピー コンストラクターを実装する方法と、オリジナルのデータにアクセスする最善の方法について質問がLinkedListあります。

    template <typename T>
    class LinkedList {

        struct Node {
            T data;
            Node *next;

            Node(T t, Node *n) : data(t), next(n) {};
        };

    public:
        LinkedList();
        LinkedList(const LinkedList&);
        ~LinkedList();

        //member functions
        int size() const;              //done
        bool empty() const;            //done
        void append(const T&);         //done
        void prepend(const T&);        //done
        void insert(const T&, int i); 
        bool contains(const T&) const; //done
        bool removeOne(const T&);      //done
        int  removeAll(const T&);      //done
        void clear();                  //done
        T& last();                     //done
        const T& last() const;         //done
        T& first();                    //done
        const T& first() const;        //done
        void removeFirst();            //done
        T takeFirst();                 //done
        void removeLast();
        T takeLast();


        //delete when finished
        void print();                  
        //end delete

        //operators
        bool operator ==(const LinkedList<T> &other) const;    //done
        bool operator !=(const LinkedList<T> &other) const;    //done
        LinkedList<T>& operator =(const LinkedList<T> &other); //done


    private:
        Node* m_head;
        Node* m_tail;
        int   m_size;

    };

    template<typename T>
    LinkedList<T>::LinkedList() : m_head(0), m_tail(0), m_size(0) {

    }
...

コピー コンストラクターは、オリジナルの各ノードのデータにLinkedList直接アクセスする必要がありますか?

template<typename T>
LinkedList<T>::LinkedList(const LinkedList& l) {

    m_head = 0;
    m_tail = 0;
    m_size = 0;

    Node *n = l.m_head;

    // construct list from given list
    while(n) {
        append(n->data);
        n = n->next;
    }
}

または、対応するアクセサーを介してデータにアクセスする必要がありますか? (アクセサが定義されていないことはわかっています)。

また、カスタム イテレータを作成して、 を反復処理できるようにするつもりLinkedListです。各ノードのデータにアクセスするには、コピー コンストラクターで使用する必要がありますか?

別の質問 (完全にトピックから外れていることは承知しています)、いつ、および/またはなぜ、へのポインターを宣言する必要があるかLinkedList

LinkedList<int> *l = new LinkedList<int>();

それ以外の

LinkedList<int> l;
4

2 に答える 2

3

I assume append will properly handle the initial head/tail details, yes? If so, what you have now is great and simple: Go through the other list, and take its item and add a copy to my list. Perfect.

Well, almost. Use an initializer list to initialize member variables:

template<typename T>
LinkedList<T>::LinkedList(const LinkedList& l) :
m_head(0), m_tail(0), m_size(0)
{
 // ...
}

Also, maybe a matter of style, this woks instead of a while loop:

// construct list from given list
for (Node *n = l.m_head; n != 0; n = n->next)
    append(m->data);

In fact, I'd recommend this instead. When you have iterators, you'd do something like:

for (const_iterator iter = l.begin(); iter != l.end(); ++iter)
    append(*iter);

It just follows the style of a for-loop better. (Initialize something, check something, do something). Though for iterators, it'll probably be different. (More later)

Or should I access the data through the corresponding accessor? (I know that I don't have the accessor(s) defined).

Also, I intend to create a custom iterator so that it can be possible to iterate over the LinkedList. Should I use in the copy constructor to access the data on each node?

Those iterators are your accessors. You don't want to expose your internal head-tail pointers, that a recipe for disaster. The purpose of the class is to not expose the details. That said, iterators are the abstract wrapper around those details.

Once you have your iterators, then you could use them to iterate through the list instead of pointer arithmetic. This ties in to this recently asked question. In general, you should use your abstractions to deal with your data. So yes once you have your iterators in place, you should use those to iterate across the data.

Most classes that provide iterators also provide a way to insert data given a beginning and ending iterator. This is usually called insert, like this: insert(iterBegin, iterEnd). This loops through the iterators, appending it's data to the list.

If you had such functionality, your copy-constructor would simply be:

insert(l.begin(), l.end()); // insert the other list's entire range

Where insert is implemented like the for-loop we had above.

Another question (completely off-topic, I know), when and/or why should we declare a pointer to a LinkedList

LinkedList *l = new LinkedList(); instead of LinkedList l;

The first is dynamic allocation, the second is automatic (stack) allocation. You should prefer stack allocation. It's almost always faster, and safer too (since you don't need to delete anything). In fact, a concept called RAII relies on automatic storage, so destructors are guaranteed to run.

Only use dynamic allocation when you have to.

于 2010-03-03T19:50:19.927 に答える
0

独自の連結リストを実装することは、ポインターやデータ構造などの詳細を学ぶのに役立つため、依然として非常に価値のある演習だと思います。既存のライブラリが多数あるため、実際のコードで連結リスト クラスを使用しないように注意してください。すでに書かれ、テストされています。最良のコードは、記述する必要のないコードです。std::listを参照してください。

コピー コンストラクターの実装方法に問題はありません。ただし、コードを専用のコピー関数に移動し、それをコンストラクターから呼び出すと、維持する必要のあるコードが少なくて済みます。しかし、一般に、クラス自体からクラスの実装の詳細を使用することは、受け入れられるだけでなく、多くの場合、可能な限り高速になるため好まれます。

new を使用してリストを作成するか、スタック上にリストを作成するかについては、これはクラスだけでなく、一般的なデータ構造にも適用される決定です。単純化しすぎた経験則: 可能であればスタックに割り当て、必要に応じてヒープに割り当てます。たとえば、リストが作成された関数よりも長く存続する必要がある場合は、リストを作成する必要があります。

また、独自のコードを手動でローリングしないことに戻ります。newヒープに割り当てることにした場合は、メモリを自分で管理しようとするのではなく、スマート ポインターを使用する必要があります。今すぐこの習慣を身につけてください。「実際の」コードに取り組むまで待たないでください。あなたが遭遇する多くの人々は、あなたがより良いコードを書くためにあなたの役に立たず、「ただ使うだけ」と主張するでしょうnew。

于 2010-03-03T19:55:59.510 に答える