Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.77/13: Рейтинг темы: голосов - 13, средняя оценка - 4.77
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453

Собственная реализация стека. Критика

28.01.2013, 21:55. Показов 2921. Ответов 20
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Покритикуйте пожалуйста реализацию. Самому мне не очень нравится момент с завершением работы программы в catch блоке, но не знаю как обойти возврат мусора в функции, возвращающей T&. Ведь данные могут быть и обработаны какой-нибудь другой функцией, принимающей результат работы в качестве аргумента. Но если этого нет, то, в принципе, программа остается дееспособной.

Stack.h
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#ifndef _STACK_H_
#define _STACK_H_
#include <cstddef>
#include <iterator>
#include <stdexcept>
#include <cstdlib>
 
template <class T>
class Stack
{
    public:
        Stack();
        template <class InputIterator>
        Stack(InputIterator beg, InputIterator end);
        ~Stack();
 
        bool empty() const;
        void push(const T& obj);
        void pop();
        std::size_t size() const;
        const T& top() const;
        T& top();
 
    private:
        Stack(const Stack &);             // prohibit copy
        Stack& operator= (const Stack &); // and assignment
        T& getTopData() const;
 
        struct Node
        {
            T data_;
            Node *next_;
            Node(const T &data, Node *nextNode);
            Node(const Stack::Node &);             // prohibit copy
            Node& operator= (const Stack::Node &); // and assignment
        } *Top;
        std::size_t counter_;
};
 
 
template <class T>
Stack<T>::Stack() : Top(nullptr), counter_(0) {}
 
template <class T>
template <class InputIterator>
Stack<T>::Stack(InputIterator beg, InputIterator end) : Stack()
{
    while(beg != end)
    {
        push(*beg);
        ++beg;
    }
}
 
template <class T>
Stack<T>::~Stack()
{
    while(Top)
        pop();
}
 
template <class T>
bool Stack<T>::empty() const
{
    return Top == nullptr;
}
 
template <class T>
void Stack<T>::push(const T& obj)
{
    Top = new Node(obj, Top);
    counter_++;
}
 
template <class T>
void Stack<T>::pop()
{
    if (!Top)
        return;
    Node *tmp = Top;
    Top = Top->next_;
    delete tmp;
    counter_--;
}
 
template <class T>
std::size_t Stack<T>::size() const
{
    return counter_;
}
 
template <class T>
const T& Stack<T>::top() const
{
    return getTopData();
}
 
template <class T>
T& Stack<T>::top()
{
    return getTopData();
}
 
template <class T>
T& Stack<T>::getTopData() const
{
    try
    {
        if (!Top) throw std::out_of_range("Trying to access to nothing");
        return Top->data_;
    }
    catch (const std::exception &e)
    {
        std::cerr << e.what() << std::endl;
        exit(1);
    }
}
 
template <class T>
Stack<T>::Node::Node(const T &data, Node *next) : data_(data), next_(next) {}
 
#endif


main.cpp (для теста)
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include "Stack.h"
 
class A
{
    public:
        A() { std::cout << "A()\n"; }
        A(const A &a) { std::cout << "A(A &)\n"; }
        ~A() { std::cout << "~A()\n"; }
};
 
int main()
{
    Stack<A> s;
    s.push(A());
    s.push(A());
 
    while(!s.empty())
    {
        s.pop();
    }
    s.top();
}
1
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
28.01.2013, 21:55
Ответы с готовыми решениями:

Собственная реализация паттерна "Слушатель" - нужна конструктивная критика
Добрый день, наворотил код по работе с паттерном слушатель - есть класс контейнер данных и при их изменении всех кто подписался должен...

Shared_ptr собственная реализация
Здравствуйте, написал собственную реалицацию &quot;умных&quot; указателей для класса object. Прежде чем попробовать написать шаблонную версию хочу...

Собственная реализация функции конкатенации
Вопрос в комментарии к коду. Объясните пожалуйста (см. ниже что именно) #include &lt;stdio.h&gt; void strсat(char *s1, char *s2) ...

20
1963 / 819 / 114
Регистрация: 01.10.2012
Сообщений: 4,767
Записей в блоге: 2
28.01.2013, 22:16
1) Не вижу оснований запрещать копирование

2) Нет пула памяти (new/delete на каждый чих)

3) Не лучше/проще ли сделать на базе std::vector или std::list?
1
Неэпический
 Аватар для Croessmah
18144 / 10728 / 2066
Регистрация: 27.09.2012
Сообщений: 27,026
Записей в блоге: 1
28.01.2013, 22:19
Цитата Сообщение от Igor3D Посмотреть сообщение
Не лучше/проще ли сделать на базе std::vector или std::list?
тогда лучше сразу std::stack использовать.
0
 Аватар для dederkay
46 / 46 / 4
Регистрация: 08.12.2010
Сообщений: 161
28.01.2013, 22:24
Цитата Сообщение от Igor3D Посмотреть сообщение
Нет пула памяти (new/delete на каждый чих)
да, тут согласен, пул бы немного ускорил работу с памятью. И сам не знаю что да как сейчас с конструктором перемещения, сам не делал(к сожалению), но хотелось бы увидить, что да как)
0
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
28.01.2013, 22:35  [ТС]
Не вижу оснований запрещать копирование
Не нашел эффективного способа реализовать Stack(Stack &) или Stack& operator= (const Stack &) без ввода доп.переменных.
Насчет пула, да, была даже мысль об этом, почему то потерял по ходу реализации)

но вот STL через STL не вижу смысла делать
0
 Аватар для Gepar
1186 / 543 / 78
Регистрация: 01.07.2009
Сообщений: 3,517
28.01.2013, 22:42
Цитата Сообщение от MrGluck Посмотреть сообщение
но вот STL через STL не вижу смысла делать
Реализация стека в обход stl с внутернеей реализацией операции через stl ?

Цитата Сообщение от MrGluck Посмотреть сообщение
Не нашел эффективного способа реализовать Stack(Stack &) или Stack& operator= (const Stack &) без ввода доп.переменных.
Ну так эфективно или нет, но ведь это же не повод от чего-то отказываться Вставка данных в строку в опред. позицию например может тоже не очень эфективная, но при реализации string её же написали...
0
What a waste!
 Аватар для gray_fox
1610 / 1302 / 180
Регистрация: 21.04.2012
Сообщений: 2,733
28.01.2013, 22:55
Цитата Сообщение от MrGluck Посмотреть сообщение
Насчет пула, да, была даже мысль об этом, почему то потерял по ходу реализации)
Может добавить аллокатор? А там уже с пулом\ещё чем будет от него зависеть.
0
Неэпический
 Аватар для Croessmah
18144 / 10728 / 2066
Регистрация: 27.09.2012
Сообщений: 27,026
Записей в блоге: 1
28.01.2013, 22:57
Цитата Сообщение от gray_fox Посмотреть сообщение
Может добавить аллокатор?
Итераторы тоже будут кстати.
0
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
29.01.2013, 01:20  [ТС]
Цитата Сообщение от Gepar Посмотреть сообщение
Реализация стека в обход stl с внутернеей реализацией операции через stl ?
ты про InputIterator ? Так я имел ввиду, что не хочу реализовывать одни STL контейнеры через другие.
Цитата Сообщение от Gepar Посмотреть сообщение
Ну так эфективно или нет, но ведь это же не повод от чего-то отказываться Вставка данных в строку в опред. позицию например может тоже не очень эфективная, но при реализации string её же написали...
Так не все так просто в STL, тот же operator[] у list не определен, можно, конечно это сделать, но ради реализации копирования, операций присваивания и сравнения будет страдать эффективность всего класса.
Цитата Сообщение от gray_fox Посмотреть сообщение
Может добавить аллокатор?
Боюсь, експы не хватит)
Цитата Сообщение от Croessmah Посмотреть сообщение
Итераторы тоже будут кстати.
Думаю, это плохая идея, т.к. это не последовательность, тут есть top и все, с другим мы работать, по-хорошему не можем.
0
3258 / 2060 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
29.01.2013, 06:02
Цитата Сообщение от MrGluck Посмотреть сообщение
Так не все так просто в STL, тот же operator[] у list не определен
Потому что оператор[] должен работать за константное время, а для списка трудоемкость такой операции определяется как O(N). И что будет если пользователь решит перебрать элементы списка в цикле, используя индекс?
0
3258 / 2060 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
29.01.2013, 06:03
Цитата Сообщение от MrGluck Посмотреть сообщение
Так не все так просто в STL, тот же operator[] у list не определен
Потому что оператор[] должен работать за константное время, а для списка трудоемкость такой операции определяется как O(N). И что будет если пользователь решит перебрать элементы списка в цикле, используя индекс?

А какие препятствия для реализации конструктора копирования у стека?
0
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
29.01.2013, 12:08  [ТС]
Цитата Сообщение от 0x10 Посмотреть сообщение
Потому что оператор[] должен работать за константное время, а для списка трудоемкость такой операции определяется как O(N). И что будет если пользователь решит перебрать элементы списка в цикле, используя индекс?

А какие препятствия для реализации конструктора копирования у стека?
Неэффективность. Придется создавать вспомогательный временный стек, перекачовывать туда элементы, а потом из него в новый. Или же вводить доп. переменные.
0
Каратель
Эксперт С++
6610 / 4029 / 401
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
29.01.2013, 12:20
Цитата Сообщение от MrGluck Посмотреть сообщение
Неэффективность. Придется создавать вспомогательный временный стек, перекачовывать туда элементы, а потом из него в новый. Или же вводить доп. переменные.
для конструктора копирования всего-то проитерировать все элементы
для оператора присваивания - copy & swap
1
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
29.01.2013, 13:43  [ТС]
С оператором присвоений то понятно, но он в своей реализации упирается на конструктор копий.
C++
1
2
3
4
5
6
7
template <class T>
Stack<T>& Stack<T>::operator= (const Stack &s)
{
    if(this != &s)
        Stack(s).swap(*this);
    return *this;
}
Цитата Сообщение от Jupiter Посмотреть сообщение
для конструктора копирования всего-то проитерировать все элементы
А как проитерировать, зная лишь верхушку и количество элементов?
Я такой вот только бред могу написать:
C++
1
2
3
4
5
6
template <class T>
Stack<T>::Stack(const Stack &s) : Stack()
{
    for (int c = static_cast<int>(s.counter_) - 1; c >= 0; c--)
        this->push((s.Top - c)->data_);
}
Не хочется вот так вот делать:
C++
1
2
3
4
5
6
7
8
9
template <class T>
Stack<T>::Stack(const Stack &s) : Stack()
{
    Stack tmp;
    for (Node *n = s.Top; n; n = n->next_)
        tmp.push(n->data_);
    for (Node *n = tmp.Top; n; n = n->next_)
        this->push(n->data_);
}
0
Каратель
Эксперт С++
6610 / 4029 / 401
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
29.01.2013, 14:22
Цитата Сообщение от MrGluck Посмотреть сообщение
C++
1
2
3
4
5
6
template <class T>
T& Stack<T>::getTopData() const
{
* ...
* exit(1); 
}
вот такие фугасы закладывать не надо

Добавлено через 22 минуты
Цитата Сообщение от MrGluck Посмотреть сообщение
Не хочется вот так вот делать:
либо так, либо вводить указатель на предыдущий элемент, либо выделять память последовательно.
вообще стоит придерживаться того что стек - это адаптер который содежит контейнер и лишь регулирует вставку/удаление элементов и доступ к верхушке. а у контейнера соответсвенно уже определен свой конструктор корирования, оператор присваивания и т.д.
0
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
29.01.2013, 15:12  [ТС]
Цитата Сообщение от Jupiter Посмотреть сообщение
вот такие фугасы закладывать не надо
я тоже так считаю
Цитата Сообщение от MrGluck Посмотреть сообщение
Самому мне не очень нравится момент с завершением работы программы в catch блоке, но не знаю как обойти возврат мусора в функции, возвращающей T&.
Но лучше ведь, чем работать с мусором. Рад бы сделать так, чтоб возврата не было, но пока изящных решений не встречал и не придумал.

Цитата Сообщение от Jupiter Посмотреть сообщение
выделять память последовательно.
если переопределить операторы new и delete, можно ли будет перемещаться с начала до конца контейнера, используя арифметику указателей?
0
3258 / 2060 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
29.01.2013, 15:19
Цитата Сообщение от MrGluck Посмотреть сообщение
Самому мне не очень нравится момент с завершением работы программы в catch блоке
Ну представь: начал использовать в своей программе какую-то стороннюю библиотеку, а она в случае ошибки тебе все приложение закрывает. Лучше бы кидала исключения.
0
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
29.01.2013, 15:26  [ТС]
0x10, оно кидает исключение и завершает работу.
Чем вам работа с мусором больше нравится?
Если есть другой вариант - предложите.
Работа завершается лишь при некорректном использовании с указанием на ошибку.
0
 Аватар для dederkay
46 / 46 / 4
Регистрация: 08.12.2010
Сообщений: 161
29.01.2013, 18:54
Цитата Сообщение от MrGluck Посмотреть сообщение
если переопределить операторы new и delete
правильнее сделать базовый класс с собственными ню и делит) и унаследовать ваш стек от базового(управляющего памятью), ну и при правильной работе с памятью можно ускорить работу стека.
0
 Аватар для soon
2554 / 1319 / 178
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
29.01.2013, 19:21
Цитата Сообщение от dederkay Посмотреть сообщение
правильнее сделать базовый класс с собственными ню и делит) и унаследовать ваш стек от базового(управляющего памятью), ну и при правильной работе с памятью можно ускорить работу стека.
Правильнее делегировать объект, который будет управлять памятью.
Цитата Сообщение от MrGluck Посмотреть сообщение
0x10, оно кидает исключение и завершает работу.
Чем вам работа с мусором больше нравится?
Если есть другой вариант - предложите.
Работа завершается лишь при некорректном использовании с указанием на ошибку.
Библиотека не должна решать, завершать программу или нет.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
29.01.2013, 19:21
Помогаю со студенческими работами здесь

Шаблонный класс list, собственная реализация
Привет всем. Я по чуть-чуть пишу шаблонный класс list с добавлением элементов в начало списка. Уже на свой страх и риск реализовал три...

Собственная реализация strtok, стоит ли применить статическую переменную?
Добрый день! Пришла мысль реализовать свою strtok. Хотел проконсультироваться. Следует ли в этой strtok применять статическую...

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

Реализация стека
Реализация стека (добавить 1 элемент, вытащить 1 элемент в стеке, определить, когда стек будет пустой). Помогите пожалуйста написать...

Реализация стека
Подскажите, как создать класс, который реализует стек? А также методы включения и выключения элементов?


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Access
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru