Реализовать двунаправленный список в духе списка из STL

@ForEveR · Регистрация: 24.06.2010

Студворк — интернет-сервис помощи студентам

Все-таки видимо у меня всегда останутся с этим проблемы.
Само определение скидывать не буду, я пытаюсь сделать, что-то вроде STL-ного списка.
Спросить хочу только одно.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
    void push_back(const T& el)
    {
        Node* tmp=new Node(el);
        if(empty())
        {
            head=tmp;
            tail=tmp;
            ++sz;
            return;
        }
        tail->next=tmp;
        tail=tmp;
        ++sz;
    }

После этого список можно прогонять только в одну сторону. С головы в хвост. В хвосте же только последний элемент и в prev ничего нет. В чем мб проблема?
Хотя вообще как я понял это для однонаправленного только катит... А вот как сделать для двунаправленного - второй день догнать не могу.

@ForEveR · 16.04.2011, 09:37 **[ТС]**

bigredcat, Про наследование.

Итераторы в list MSVS.

C++
1
2
3
    template <bool _SECURE_VALIDATION>
    class _Iterator
        : public _Const_iterator<_SECURE_VALIDATION>

@bigredcat · 16.04.2011, 11:31

ForEveR, да, это так. Но в отличае от вашей реализации, там наследование имеет смысл. В MSVC в производном классе итератора поле для хранения указателя на узел не определяется заново (по крайней мере то, что я видел в STL VC2008). Это поле уже есть в базовом классе. Зачем его еще в производный добавлять?
Я хочу сказать, что поскольку в вашей реализации все поля переопределяются в производном классе заново, то и смысл наследования теряется. Это при том еще, что базовый класс практически ничего больше, в добавление к этим указателям, не содержит, кроме операторов, которые все-равно требуется переопределить в производном.
Кроме того не совсем понятно зачем хранить еще два указателя, если предыдущий и следующий могут быть получены из текущего. Спасти от неопределенного состояния итератора в случае удаления текущего узла они все-равно в общем случае не могут, так как могут быть удалены и соседние узлы. Так что одного указателя в базовом классе вполне достаточно.

@zarko97 · 24.08.2016, 18:07

ещё можно добавить

C++
1
2
3
List(std::initializer_list<value_type> l) : List(l.begin(), l.end())
{
}

@HelicopterK52 · 24.08.2016, 18:09

Сообщение от zarko97

ещё можно добавить

Особенно, если учесть, что тема создана до выхода C++11

@zarko97 · 24.08.2016, 18:18

ну на дату особо не смотрю...
+недостает

C++
1
2
3
4
5
6
7
8
9
10
11
template <class T>
inline bool operator==(const list<T> &x, const list<T> &y)
{
    return x.size() == y.size() && std::equal(x.begin(), x.end(), y.begin());
}
 
template <class T>
inline bool operator< (const list<T> &x, const list<T> &y)
{
    return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
}

и тд.

Добавлено через 1 минуту
+ неплохо перегрузить >> и <<

Новые блоги и статьи Все статьи Все блоги /
Был там один разговор по поводу свободы в материальном мире. kumehtar 19.08.2026 Суть: рассматривается живое существо, оказавшееся внутри довольно странной системы (этого мира) и пытающееся обустроить в ней свой кусок пространства. Жизнь действительно предъявляет каждому. . .	Когда логика программы не спасает от человеческих ошибок Maks 18.08.2026 В последнее время всё чаще и чаще сталкиваюсь с таким явлением, как абсолютная невнимательность (или глупость) пользователей. Проявляется это чаще всего на работе в коллективе. Допустим, человек с. . .	Лето уходит kumehtar 17.08.2026	Мысли в слух kumehtar 17.08.2026 Забавно, насколько сейчас стала доступна информация. Например о магии, духовном развитии, медитациях, и других подобных направлениях, ранее зачастую тайных, передаваемых от учителя к ученику. Хотя. . .
Перемещение строк из ТЧ в другой документ с учетом текущего пробега Maks 17.08.2026 Реализация из решения ниже выполнена на примере нетипового документа "Автозапчасти", с ТЧ "Шины". За основу взят алгоритм отсюда: https:/ / www. cyberforum. ru/ blogs/ 359708/ 10838. html Задача: . . .	Саморегулирующийся социальный контракт для сервера cross-section. Hrethgir 14.08.2026 С кодом конечно таких глубоких размышлений пока не было, впрочем я уже привык к алгоритмизации. Суть предмета записи: снова в диалоге с нейросетью (я взял пока себе ник для учётки админа - Rector). . . .	Часы электронные Uhbif79 12.08.2026 Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .	Часы с будильником на основе класса QLCDNumber Uhbif79 12.08.2026 Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .

@bigredcat 375 / 322 / 32 Регистрация: 24.02.2011 Сообщений: 1,512 Записей в блоге: 1
	16.04.2011, 11:31
	ForEveR, да, это так. Но в отличае от вашей реализации, там наследование имеет смысл. В MSVC в производном классе итератора поле для хранения указателя на узел не определяется заново (по крайней мере то, что я видел в STL VC2008). Это поле уже есть в базовом классе. Зачем его еще в производный добавлять? Я хочу сказать, что поскольку в вашей реализации все поля переопределяются в производном классе заново, то и смысл наследования теряется. Это при том еще, что базовый класс практически ничего больше, в добавление к этим указателям, не содержит, кроме операторов, которые все-равно требуется переопределить в производном. Кроме того не совсем понятно зачем хранить еще два указателя, если предыдущий и следующий могут быть получены из текущего. Спасти от неопределенного состояния итератора в случае удаления текущего узла они все-равно в общем случае не могут, так как могут быть удалены и соседние узлы. Так что одного указателя в базовом классе вполне достаточно. 0

Опции темы