Динамически размещаемый список в C ++

Question

Я сделал симпатичный универсальный (т.е. шаблон) List класс для обработки списков в C ++. Причина в том, что я нашел класс std::list ужасно уродливым для повседневного использования, и, поскольку я постоянно использую списки, мне нужен новый. Главное улучшение в том, что с моим классом я могу использовать [], чтобы получить предметы из него. Кроме того, еще предстоит внедрить систему IComparer для сортировки.

Я использую этот класс List в OBJLoader, мой класс, который загружает файлы Wavefront .obj и преобразует их в сетки. OBJLoader содержит списки указателей на следующие «типы»: трехмерные позиции, трехмерные нормали, координаты текстурных ультрафиолетовых лучей, вершины, грани и сетки. В списке вершин есть объекты, которые должны быть связаны с некоторыми объектами во всех трехмерных позициях, трехмерных нормалях и списках координат текстур. Лица ссылаются на вершины, а сетки - на грани. Таким образом, они все взаимосвязаны.

Для простоты, давайте рассмотрим, что в некотором контексте есть только два списка указателей: List<Person*> и List<Place*>. Класс Person содержит, помимо прочего, поле List<Place*> placesVisited, а класс Place содержит поле List<Person*> peopleThatVisited. Итак, у нас есть структура:

class Person
{
    ...
  public:
    Place* placeVisited;
    ...
};

class Place
{
    ...
  public:
    List<People*> peopleThatVisited;
};

Теперь у нас есть следующий код:

Person* psn1 = new Person();
Person* psn2 = new Person();

Place* plc1 = new Place();
Place* plc2 = new Place();
Place* plc2 = new Place();


// make some links between them here:
psn1->placesVisited.Add(plc1, plc2);
psn2->placesVisited.Add(plc2, plc3);

// add the links to the places as well
plc1->peopleThatVisited.Add(psn1);
plc2->peopleThatVisited.Add(psn1, psn2);
plc3->peopleThatVisited.Add(plc3);

// to make things worse:

List<Person*> allThePeopleAvailable;

allThePeopleAvailable.Add(psn1);
allThePeopleAvailable.Add(psn2);

List<Place*> allThePlacesAvailable;

allThePlacesAvailable.Add(plc1);
allThePlacesAvailable.Add(plc2);
allThePlacesAvailable.Add(plc3);

Все сделано. Что происходит, когда мы достигаем }? Вызываются все dtors, и программа вылетает, потому что она пытается удалить вещи два или более раз.

Дтор моего списка выглядит так:

~List(void)
{
    cursor = begin;
    cursorPos = 0;

    while(cursorPos < capacity - 1)
    {
        cursor = cursor->next;
        cursorPos++;
        delete cursor->prev;
    }

    delete cursor;
}

, где Elem:

struct Elem
{
  public:
    Elem* prev;
    T value;
    Elem* next;
};

и T - это тип List.

Что возвращает нас к вопросу: как можно безопасно удалить мои List классы? Элементы внутри могут быть или не быть указателями, и, если они являются указателями, я хотел бы иметь возможность, когда я удаляю свой List, указать, хочу ли я удалять элементы внутри или только оболочки Elem вокруг них. ,

Умные указатели могут быть ответом, но это будет означать, что у меня не может быть List<bubuType*>, а просто List<smart_pointer_to_bubuType>. Это может быть хорошо, но опять же: объявление List<bubuType*> не вызовет ошибок или предупреждений, а в некоторых случаях умные указатели вызовут некоторые проблемы в реализации: например, я мог бы объявить List<PSTR> для некоторых возвращаемых WinAPI , Я думаю, что получить эти PSTR внутри умных указателей было бы уродливой работой. Таким образом, решение, которое я ищу, я думаю, должно быть как-то связано с системой освобождения из шаблона List.

Есть идеи?

Answer 1

Даже не глядя на твой код, я говорю: отбрось его!

C ++ имеет шаблон класса списка, который примерно эффективен по мере поступления, хорошо известен всем программистам C ++ и без ошибок поставляется с вашим компилятором.

Научитесь использовать STL. ¹ Исходя из других ОО-языков, STL может показаться странным, но есть основная причина его странности, Чужая красота , сочетающая в себе абстракцию и производительность - что-то считалось невозможным до того, как Степанов пришел и придумал STL.
Будьте уверены, что вы не единственный, кто борется с пониманием STL. Когда он натолкнулся на нас, мы все изо всех сил пытались понять его концепции, изучить его особенности, понять, как это происходит. STL - это странный зверь, но тогда ему удается объединить две цели, которые, как все думали, никогда не удастся объединить, поэтому поначалу он может показаться незнакомым.

Могу поспорить, что написание собственного класса связанного списка раньше был вторым по популярности внутренним видом спорта программистов на C ++ - сразу после написания вашего собственного строкового класса. Те из нас, кто занимался программированием на C ++ 15 лет назад, в настоящее время любят вырывать изнутри ошибочные, неэффективные, странные и неизвестные классы строк, списков и словарей, гниющие в старом коде, и заменять их чем-то очень эффективные , общеизвестные и без ошибок . Начало вашего собственного класса списка (кроме образовательных) должно быть одной из худших ересей.

Если вы программируете на C ++, как можно скорее привыкните к одному из самых мощных инструментов в его коробке.

¹ _{Обратите внимание, что термин "STL" называет ту часть стандартной библиотеки C ++, которая происходит из библиотеки Степанова (плюс такие вещи, как std::string, к которой интерфейс STL был присоединен в качестве запоздалой мысли) , а не вся стандартная библиотека.}

Answer 2

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

И просто используйте стандартный список. Вот для чего это.

Answer 3

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

В частности, в отношении людей и сайтов, которые они посетили, скорее всего, ни один из них не должен быть естественным образом ответственным за жизнь других людей: люди могут жить независимо от сайтов, которые они посетили,и места существуют независимо от того, были ли они посещены.Кажется, это намекает на то, что время жизни людей и сайтов не связано с остальными, и что удерживаемые указатели не связаны с управлением ресурсами, а скорее являются ссылками (не в смысле C ++).

Когда вы знаете, кто отвечает за управление ресурсом, это должен быть код, который должен delete (или лучше хранить ресурс в контейнере или подходящем интеллектуальном указателе, если он должен быть динамически выделен), и вы должныубедитесь, что удаление не произойдет до того, как другие объекты, которые ссылаются на те же элементы, закончат с ними.

Если в конце дня ваше владение проектом неясно, вы можете вернуться к использованию shared_ptr (либо boost, либо std), стараясь не создавать циклические зависимости, которые могут привести к утечкам памяти.Снова, чтобы правильно использовать shared_ptr s, вы должны вернуться и подумать, подумать о времени жизни объектов ...

Answer 4

В строках: // сделаем несколько ссылок между ними здесь: psn1-> placeVisited.Add (plc1, plc2);psn2-> placeVisited.Add (plc2, plc3);

// также добавляем ссылки на места plc1-> peopleThatVisited.Add (psn1);plc2-> peopleThatVisited.Add (psn1, psn2);plc3-> peopleThatVisited.Add (plc3);

---

У вас есть экземпляры в куче, которые содержат указатели друг на друга.Не только один, но и добавление одного и того же указателя на место более чем одному человеку также вызовет проблему (удаление более одного раза одного и того же объекта в памяти).

Указание изучать STL или использовать shared_ptr (Boost) может быть хорошим советом, однако, как сказал Дэвид Родригес, нужно подумать о времени жизни объектов.Другими словами, вам нужно изменить дизайн этого сценария, чтобы объекты не содержали указатели друг на друга.

Пример: действительно ли необходимо использовать указатели?- в этом случае, и если вам требуются списки или векторы STL, вам нужно использовать shared_ptr, но опять же, если объекты ссылаются друг на друга, даже лучшая реализация shared_ptr не сделает это.

Если этотребуется связь между местами и людьми, разработайте класс или используйте контейнер, который будет нести ссылки друг на друга, вместо того, чтобы люди и места указывали друг на друга.Как таблица «многие ко многим» в РСУБД.Тогда у вас будет класс / контейнер, который позаботится об удалении указателей в конце процесса.Таким образом, никакие отношения между Местами и Людьми не будут существовать, только в контейнере.

С уважением, J. Rivero

Answer 5

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

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

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

while ( cursor not at end ) {
    Elem* next = cursor->next;
    delete cursor;
    cursor = next;
}

- Джеймс Канзе

Answer 6

И вы можете легко реализовать [] вокруг обычного списка:

template <class Type> 
class mystdlist : public std::list<Type> { 
public: 
    Type& operator[](int index) { 
       list<Type>::iterator iter = this.begin(); 

       for ( int i = 0; i < index; i++ ) { 
          iter++; 
       }
       return *iter; 
    }  
};  

Почему вы хотите сделать это странно, ИМХО. Если вы хотите O (1) доступ, используйте вектор.

Answer 7

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

Answer 8

Прежде всего, я бы, конечно, использовал STL (стандартную библиотеку шаблонов), но я вижу, что вы изучаете C ++, поэтому в качестве упражнения было бы неплохо написать такую ​​вещь как шаблон List.

Прежде всего, вы никогда не должны подвергать членов данных (например, placeVisited и peopleThatVisited).Это золотое правило в объектно-ориентированном программировании.Для этого вы должны использовать методы getter и setter.

Относительно проблемы, связанной с двойным удалением: единственное решение - иметь класс-обертку вокруг ваших указателей, который отслеживает выдающиеся ссылки.Взгляните на boost :: shared_ptr .( Boost - еще одна великолепная библиотека C ++).

Answer 9

Не смотря на точный код функции Add и деструктор вашего списка, трудно точно определить проблему.

Однако, как сказано в комментариях, основная проблема с этим кодом заключается в том, что вы не используете std::list или std::vector. Есть проверенные эффективные реализации, которые соответствуют тому, что вам нужно.