Подробности реализации конструктора копирования LinkedList - PullRequest
Новая
       5

Подробности реализации конструктора копирования LinkedList

5 голосов
/ 03 марта 2010

Я начинаю изучать 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;

Ответы [ 2 ]

3 голосов
/ 03 марта 2010

Я предполагаю, что append будет правильно обрабатывать начальные детали головы / хвоста, да? Если это так, то, что у вас есть сейчас, великолепно и просто: просмотрите другой список, возьмите его предмет и добавьте копию в мой список. Идеально подходит.

Ну, почти. Используйте список инициализатора для инициализации переменных-членов: 

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

Также, возможно, дело стиля, это вместо цикла while: 

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

На самом деле, я бы порекомендовал это вместо этого. Когда у вас есть итераторы, вы делаете что-то вроде: 

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

Это лучше следует стилю цикла for. (Что-то инициализировать, что-то проверить, что-то сделать). Хотя для итераторов это, вероятно, будет другим. (Позже)

Или я должен получить доступ к данным через соответствующий метод доступа? (Я знаю, что я не определил аксессор (ы)).

Кроме того, я собираюсь создать собственный итератор, чтобы можно было перебирать LinkedList. Должен ли я использовать в конструкторе копирования для доступа к данным на каждом узле?

Эти итераторы - ваши методы доступа. Вы не хотите разоблачить свои внутренние указатели «голова-хвост», что может стать причиной катастрофы. Цель занятия - , а не раскрыть детали. Тем не менее, итераторы являются абстрактной оберткой вокруг этих деталей.

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

Большинство классов, которые предоставляют итераторы, также предоставляют способ вставки данных с учетом начала и конца итератора. Обычно это называется insert, например: insert(iterBegin, iterEnd). Это перебирает итераторы, добавляя их данные в список.

Если бы у вас была такая функциональность, ваш конструктор копирования был бы просто: 

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

Где insert реализован как цикл for, который мы имели выше.

Другой вопрос (я знаю, что это совершенно не по теме), когда и / или почему мы должны объявлять указатель на LinkedList

LinkedList * l = новый LinkedList (); вместо LinkedList l;

Первое - динамическое распределение, второе - автоматическое (стековое) распределение. Вы должны предпочесть распределение стека. Это почти всегда быстрее и безопаснее (поскольку вам не нужно ничего удалять). Фактически, концепция RAII основана на автоматическом хранении, поэтому деструкторы гарантированно будут работать.

Используйте динамическое распределение только тогда, когда это необходимо.

0 голосов
/ 03 марта 2010

Я думаю, что это все еще очень ценное упражнение для реализации вашего собственного связанного списка, так как он помогает вам изучить детали указателей, структур данных и т. Д. Просто убедитесь, что вы не используете свой класс связанного списка в реальном коде, поскольку есть много существующих библиотек, которые уже написаны и протестированы. Лучший код - это код, который вам не нужно писать. См. std :: list .

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

Что касается создания списка с новым против создания в стеке, это решение, которое применяется не только к вашему классу, но и к структурам данных в целом. Чрезмерно упрощенное правило: выделять в стеке, если можете, выделять в куче, если нужно. Например, вам понадобится, если вам нужен список, чтобы пережить функцию, в которой он создан.

И снова возвращаясь к тому, чтобы не свернуть свой собственный код вручную, если вы решите использовать new для размещения в куче, вы должны использовать умные указатели, а не пытаться управлять памятью самостоятельно. Займись этой привычкой сейчас. Не ждите, пока вы работаете над «реальным» кодом. Многие люди, с которыми вы столкнетесь, будут вам бесполезны при поиске лучшего кода и будут настаивать на «просто использовании new».

...