Реализация C ++ с двойным списком ссылок

Есть ли у кого-нибудь предложения по улучшению этого?

В частности:

  • Я правильно передаю и возвращаю ссылки, чтобы предотвратить ненужное копирование?
  • Я использую деструкторы и ключевое слово delete, чтобы предотвратить утечку памяти?
  • Правильно ли выбрасываю исключения?

Кроме того, просто интересно, возможно ли при вставке элемента просто объявить узел как

list_node_generic node;

вместо

list_node_generic* node = new list_node_generic();

Это выполнимо? Если да, то поощряется или не поощряется и почему?

#ifndef list_generic_hpp
#define list_generic_hpp

#include <iostream>

namespace ds{

    template <typename T>
    class list_generic{

        private:

            class list_node_generic{

                private:
                    list_node_generic* prev;
                    list_node_generic* next;
                    T data;

                public:
                    list_node_generic(){
                        prev = nullptr;
                        next = nullptr;
                    }

                    ~list_node_generic(){
                        delete next;
                        delete prev;
                    }

                    //Get Functions.
                    list_node_generic* get_prev(){
                        return prev;
                    }

                    list_node_generic* get_next(){
                        return next;
                    }

                    T& get_data(){
                        return data;
                    }

                    //Set Functions.
                    void set_prev(list_node_generic* p){
                        prev = p;
                    }

                    void set_next(list_node_generic* n){
                        next = n;
                    }

                    void set_data(T& d){
                        data = d;
                    }

            };


            list_node_generic* first;
            list_node_generic* last;
            int length;


        public:
            list_generic(){
                list_node_generic* dummy = new list_node_generic();
                first = dummy;
                last = dummy;
                length = 0;
            }


            list_generic(list_generic& other){
                list_node_generic* dummy = new list_node_generic();
                first = dummy;
                last = dummy;
                length = 0;
                list_node_generic* current = other.first->get_next();
                for (int i = 0; i < other.length; ++i){
                    append(current->get_data());
                    current = current->get_next();
                }
            }


            list_generic operator=(list_generic& other){
                list_generic replacement = (*new list_generic(other));

                return replacement;

            }



            int size(){
                return length;
            }

            bool empty(){
                if (length == 0){
                    return true;
                }
                else{
                    return false;
                }
            }


            void print(){
                list_node_generic* current = first;
                cout << "{";
                for (int i = 0; i < length - 1; ++i){
                    current = current->get_next();
                    cout << current->get_data() << ", ";
                }
                current = current->get_next();

                cout << current->get_data() << "}";
            }


            void insert(int index, T element){
                if (index > length){    
                    throw "Error: Index goes out of bounds.";
                }


                list_node_generic* node = new list_node_generic();
                node->set_data(element);




                if(index == length){
                    last->set_next(node);
                    node->set_prev(last);
                    last = node;
                    ++length;
                    return; 
                }


                list_node_generic* current = first->get_next();

                for (int i = 0; i < index; ++i){
                    current = current->get_next();
                }

                node->set_prev(current->get_prev());
                node->set_next(current);
                current->get_prev()->set_next(node);
                current->set_prev(node);
                ++length;
                return;
            }

            void prepend(T element){
                insert(0, element);
            }

            void append(T element){
                insert(length, element);
            }


            T& get(int index){
                if (empty()){
                    throw "Error: List is Empty... returning -1";
                }

                int real_index = index % length;
                list_node_generic* current = first->get_next();
                for (int i = 0; i < real_index; ++i){
                    current = current->get_next();
                }

                return current->get_data();
            }


            T& front(){

                if (empty()){
                    throw "Error: List is empty...";
                }

                return first->get_next()->get_data();

            }


            T& back(){
                if (empty()){
                    throw "Error: List is Empty... returning -1";
                }

                return last->get_data();
            }


            int search(T element){
                if (empty()){
                    return -1;
                }

                list_node_generic* current = first;
                for (int i = 0; i < length; ++i){
                    if (current->get_data() == element){
                        return i;
                    }
                    current = current->get_next();
                }

                std::cout << endl << element << " is not in the list" << endl;
                return -1;

            }

            void remove(int index){
                if (index >= length || index < 0){
                    return;
                }

                list_node_generic* current = first->get_next();

                if (index == length - 1){
                    last = last->get_prev();
                    current = last->get_next();
                    current->get_prev()->set_next(nullptr);
                    length--;
                    return;
                }



                for (int i = 0; i < index; ++i){
                    current = current->get_next();
                }


                current->get_prev()->set_next(current->get_next());
                current->get_next()->set_prev(current->get_prev());

                length--;


                return;


            }

            void pop_front(){
                if(empty()){
                    return;
                }

                remove(0);
            }



            void pop_back(){
                if (empty()){
                    return;
                }

                remove(length - 1);
            }





            ~list_generic(){

            }

    };

}



#endif
11 голосов | спросил user146276 10 AM00000050000004631 2017, 05:23:46

4 ответа


18

Неплохая первая трещина в связанном списке. Вот некоторые вещи, которые мне кажутся очевидными:

  1. Ваши получатели и сеттеры для list_node_generic на самом деле не очень много инкапсулируются. Они позволяют беспрепятственный доступ к закрытым полям. По сути, эти поля являются общедоступными, но с многословием. Так как вы не намерены допускать использование какого-либо кода, кроме прилагаемого list_generic, я предлагаю вам иметь только узловые объекты со всеми открытыми полями .

  2. Суффикс _generic для меня избыточен. Вы создаете шаблон, любой программируемый C ++ программист поймет, что он предназначен для генерации конкретных классов при заданных параметрах типа. Суффикс - это просто шум. Кроме того, list_node должен быть просто node , Нет префиксов, потому что полное имя типа для него - ds::list_generic::node. Нет никакой двусмысленности для защиты. И, кстати, хорошее использование пространства имен. Хотя, возможно, что-то более длинное и более описательное для идентификатора пространства имен было бы лучше.

  3. Код list_generic копирует c'tor и оператор присваивания. Вы пытаетесь повторно использовать копию c'tor в операторе присваивания. Это удивительное осознание необходимости повторного использования кода. Однако у вас есть несколько серьезных ошибок:

    list_generic replacement = (*new list_generic(other));
    

    Это распределяет копию другого списка динамически. Затем он сразу же разыгрывает указатель и создает другую локальную копию. Устранение динамических распределений памяти (поскольку вы не вызываете delete).

    Затем вы возвращаете вновь скопированный список. Но вы не изменили *this. Ничего не было назначено!

    Улучшение и лучшее повторное использование копии c'tor - это идиома копирования и свопинга. Во-первых, вы добавляете функцию простого обмена, которая может менять внутренности двух списков. Что-то вроде этого:

    void list_generic::swap(list_generic& other) {
      using std::swap;
      swap(first, other.first);
      swap(last, other.last);
      swap(length, other.length);
    }
    

    Используется std::swap. Обычно рекомендуется использовать стандартную библиотеку. Это полно вещей, которые спасают вас от работы. Теперь, вернемся к делу, оператор присваивания:

    list_generic& operator=(list_generic other) {
      other.swap(*this);
      return *this;
    }
    

    Обратите внимание на две вещи: во-первых, мы принимаем список other по значению. Это означает, что список, который мы присваиваем, будет либо скопирован, либо перемещен (если вы добавите семантику перемещения в свой класс), в зависимости от того, откуда она взялась. В любом случае, мы получаем готовый список, который мы заменяем с помощью объекта this. Во-вторых, мы возвращаем ссылку на текущий объект (а не на лишнюю копию). Это каноническая реализация, которая позволяет цепочки присваивания.

  4. empty - очень простой метод, написанный довольно подробно. Это можно упростить до return size() == 0;

  5. Вместо того, чтобы бросать строковые литералы, выкиньте объект исключения. Вам не нужно раскатывать свои собственные, это может быть один из стандартных. То есть:

    throw std::out_of_range("Error: List is Empty");
    

    Это дает улавливающему коду конкретный тип, который нужно уловить. И имя типа указывает на проблему. Для контраста catch (char const*) не говорит, что не так. Если вызывающий код хочет обрабатывать ошибку, ему придется разбирать строки. Это действительно неоптимально.

  6. ~list_generic - пустой деструктор! Как все освобожденные вами узлы будут освобождены? Здесь должен быть цикл, который удаляет все узлы от первого до последнего.


Следующее, учитывая комментарии ниже:

noexcept

Это говорит компилятору, что не будет никаких исключений, назначенных назначенной функцией. Добавление спецификатора noexcept позволяет использовать дополнительные возможности оптимизации, если ваш компилятор настолько склонен. Поскольку swap всегда считается операцией без метания, давайте отметим еекак таковой:

void list_generic::swap(list_generic& other) noexcept { // In the declaration as well
  // Same as before
}

Перемещение объектов

Я коснулся этого изначально. Предлагаемый оператор присваивания является реализацией, которая должна работать как для copy-c'tor, так и для move-c'tor. Итак, добавим семантику переноса в ваш класс. На самом деле это довольно просто, c'tor может украсть другое внутреннее состояние объектов, если он знает, что другой объект истечет. Компилятор может сказать вам, что, связываясь со ссылкой на r-значение:

list_generic(list_generic&& other) : list_generic() {
  // We delegate to the default c'tor to make this object have
  // "empty" state. And now we swap with the other object:
  other.swap(*this);
}

Пустые объекты

Как я уже отмечал выше, мы делегировали по умолчанию c'tor, чтобы создать «пустой» объект для обмена. Однако ваш по умолчанию c'tor выделяет память с места в карьер. Попытайтесь переформулировать свое решение, чтобы этого избежать. Это позволит вам пометить это как не что иное, и тогда, конечно, move-c'tor не может быть исключен из-за вызова только не метательных операций.

ответил StoryTeller 10 AM00000080000003531 2017, 08:41:35
4

Ошибка ждет вас

Ваш код получит ошибку сегментации , когда вы попытаетесь исправить деструктор списка, например add delete first в деструкторе.

Вот его главное:

int main()
{
    ds::list_generic<int> list;
    list.append(0);
    list.append(1);
    list.append(2);
    list.print();
}

Причина

Позволяет воспроизвести список в приведенном выше коде.

nullptr <- 0 -> <- 1 -> <- 2 -> nullptr
  1. Будет запущен деструктор узла, содержащего 0.

  2. Затем он вызовет деструктор узла, содержащий 1..

  3. Деструктор узла, содержащего 1, вызовет деструктор узла, содержащий 0.

  4. Перейдите к 2.

Как вы можете видеть, нет конца этой рекурсии. Обратите внимание, что проблема не исчезнет, ​​изменив порядок вещей, как сейчас, это фундаментальная проблема.

Решение

Способ исправить это - сделать то, что сказал @StoryTeller:

    current_node <- first
  1. while current_node не nullptr

    2,1. next_node <- current_node.next

    2,2. delete current_node

    2,3. current_node = next_node

Ошибки компиляции

Некоторые из cout и endl не имеют std:: с ними. После добавления их код скомпилирован плавно.

ответил Incomputable 10 PM00000010000003531 2017, 13:10:35
2

Нейминг:

  1. Макросы и константы препроцессора обычно ALL_UPPERCASE_WITH_UNDERSCORES, поэтому они выделяются, поскольку они не уважают области. Два символа подчеркивания или начиная с подчеркивания, за которым следует верхний регистр, зарезервированы для реализации, и вы избегаете этой ошибки.

  2. Претензии для размещения вашего библиотечного кода в собственном пространстве имен, но его имя должно быть достаточно отличительным, чтобы сделать конфликты маловероятными. ds слишком короткий. Пользователь может легко определить псевдоним пространства имен для своего удобства позже.

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

  4. Если вы что-то называете, не повторяйте его контекст, как это указано. Брешивость - это добродетель, если вы не идете за борт.

  5. Соблюдайте правила вашей структуры, когда это возможно. Интеграция вашего кода будет намного проще, как непосредственно программистами, использующими его, так и шаблонами, не требующими специального кода вашего кода. В частности, посмотрите на интерфейс std::list .

    print() -> оператор, не являющийся членом stream-insertion. Нужен лучший публичный интерфейс
    prepend() -> push_front()
    append() -> push_back()
    get() -> indexing-operator (T& operator[](std::size_t))
    search() -> find()
    remove() -> erase()

Инкапсуляция:

  1. node 's наблюдатели и модификаторы выставляют все свои внутренние элементы, они фактически не абстрагируют что-либо.

  2. В любом случае, поскольку node является деталью реализации list, и он тесно связан с ним, они являются единицей и пытаются общаться на расстоянии вытянутой руки, это бесполезное упражнение в бесполезности. Добавляйте только члены (ctors, dtor, ...) в node, если это упрощает реализацию list + node и отказаться от контроля доступа.

  3. list недостаточно. Поскольку доступ по индексу вместо использования итераторов, это \ $ O (n) \ $ для чего угодно, кроме начала и конца.

Ошибка обработки:

  1. Некоторые из ваших функций тихо проглатывают ошибки (remove(), pop_front(), pop_back()). Лучше бросить исключение.

  2. Другие функции вызывают указатель cstring. Это очень необычно, так как тип даже не намекает на реальную проблему и обертывает его в

  3. Ваш оператор-оператор не может изменить std::out_of_range и вернуть его. Вместо этого он просачивает копию аргумента и возвращает копию аргумента.

  4. search() в настоящее время первый по умолчанию - инициализирует член данных, а затем копирует-присваивает реальное значение. Помимо соображений эффективности и ограниченной общности, если присвоение не выполняется, вы протекаете новый узел.

  5. noexcept утечка удалённого *this

  6. Ваш dtor ничего не делает, хотя он должен удалить все remove() в цикле. Удалите dtor node, так как он неисправен и приведет к бесконечной рекурсии, поскольку каждый delete пытается удалить двух своих соседей.

Конкретность и общая аргументация:

  1. Если вы не изменяете аргумент (включая неявный node для функций-членов), принимайте его с помощью ссылки или если он эффективно копируется по значению.

  2. Как правило, инвестируйте в move-семантику, чтобы избежать копирования.

  3. Разрешить создание значения node. Это может быть значительно более эффективным или даже единственным возможным способом сделать это.

Избегать выделения:

  1. Измените свой код, поэтому инициализация по умолчанию не выделяет память. Это намного эффективнее и позволяет инициализировать во время компиляции. Также посмотрите на node, пока вы на нем.

Другие вещи:

  1. Не используйте *this, если вам действительно не нужно явно очищать поток. Промывка разрушает производительность вашего кода.

  2. Не используйте node. Особенно не в заголовке, так как он заражает все включенные сайты. Прочитайте « Почему« использование пространства имен std »считается плохой практикой? « почему ».

  3. Заголовок должен быть самодостаточным. constexpr то, что вам нужно, не больше и не меньше, принесите выделенные символы в область видимости, если хотите, но не зависите от кого-либо еще сделав это.

  4. Вы можете и должны возвращать логическое выражение напрямую. Не нужно обфускировать его, обернув его с помощью std::endl - using namespace std; -construct

  5. Использование #include в качестве адресата по умолчанию в порядке, но пользователь должен действительно иметь возможность выбирать, куда идет выход .

ответил Deduplicator 10 PM00000050000000531 2017, 17:24:05
1

Вы спросили, можно ли пойти с

list_node_generic node;

при создании нового узла.

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

Подумайте о собственности. Кто должен владеть этой переменной, контролировать ее жизнь и так далее? Ответ - это список. Поэтому вам следует сделать список.

Тем не менее, другой тоже не так хорош:

list_node_generic* node = new list_node_generic();

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

Я спрашиваю вас: можете ли вы гарантировать, что экземпляр вашего класса списка согласован? Это означает, что существует четкая цепочка узлов, с this.next.prev = это, если не null и так далее. Можете ли вы гарантировать, что никто не может использовать ваш класс для создания объекта, который не имеет этой вероятности? Нет, ты не можешь. Я мог бы создавать с ним самые дикие структуры.

Ответственность за целостность объекта лежит на классе. Ни один метод не сможет его сломать. Я рекомендую эту архитектуру:

Пусть класс списка выполняет всю основную работу по вставке. Попросите пользователя вставить только фактические данные узла, а не узел. Если данные узла могут быть большими и могут исходить из других источников, подумайте о том, чтобы сделать данные умным указателем и использовать перемещение при создании нового узла.

Если класс списка также возвращает постоянную ссылку на данные всякий раз, когда этого достаточно. Возможно, с сигнатурой const T& или const T* или weak_ptr<const T>

Ни в коем случае не делайте что-то вроде set_next. Это задание класса списка.

Итак, в качестве ответа: вы можете технически делать то, что говорили, но не должны. Вы должны предоставить объекту списка только то, что ему обязательно нужно, а именно данные. Затем объект списка создает собственный узел. Если он не должен копировать данные, переместите семантику помощи интеллектуальных указателей.

Тем не менее, я хочу добавить к ответу Incomputable о проблеме с вашим деструктором:

Другим решением будет использование интеллектуальных указателей. Рассмотрим это:

shared_ptr<list_node_generic> next; //owns and thus kills the child
weak_ptr<list_node_generic> prev; //does not own - a raw pointer would also work here

Это создает четкую иерархию собственности. Каждый узел принадлежит его предшественнику. Первый узел принадлежит объекту списка. Деструктор можно оставить пустым.

Узлы, переданные наружу, передаются как weak_ptr<const list_node_generic> (или не const, но вы должны предпочесть const, когда это возможно). Это гарантирует, что случай, когда список умирает до указателя, действительно уничтожит объект, пока пользователь сможет проверить, произошло ли это.

Другое дело, ваш геттер также является сеттер:

                T& get_data(){
                    return data;
                }

Это неконстантная ссылка. Я мог бы сделать это:

T& data = node.get_data(); //probably with the correct type instead of T here
data = 12345; //assuming that an int value is fine for T

, и это изменит данные в фактическом узле. Который я предполагаю, что вы не хотите быть, поскольку у вас есть отдельный сеттер. Пойдите вместо этого:

                const T& get_data() const {
                    return data;
                }

При этом T& data = node.get_data(); приведет к ошибке, поэтому const T& data = node.get_data(); data = 12345;.

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

ответил Aziuth 10 PM00000060000005031 2017, 18:01:50

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132