Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.73/11: Рейтинг темы: голосов - 11, средняя оценка - 4.73
Форумчанин
Эксперт CЭксперт С++
8164 / 5012 / 1436
Регистрация: 29.11.2010
Сообщений: 13,455
1

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

28.01.2013, 21:55. Просмотров 1982. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
28.01.2013, 21:55
Ответы с готовыми решениями:

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

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

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

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

__________________
Помогаю в написании студенческих работ здесь.
Записывайтесь на профессиональные курсы C++ разработчиков
20
1229 / 596 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
28.01.2013, 22:16 2
1) Не вижу оснований запрещать копирование

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

3) Не лучше/проще ли сделать на базе std::vector или std::list?
1
Don't worry, be happy
16972 / 9853 / 1897
Регистрация: 27.09.2012
Сообщений: 24,431
Записей в блоге: 1
28.01.2013, 22:19 3
Цитата Сообщение от Igor3D Посмотреть сообщение
Не лучше/проще ли сделать на базе std::vector или std::list?
тогда лучше сразу std::stack использовать.
0
45 / 45 / 4
Регистрация: 08.12.2010
Сообщений: 161
28.01.2013, 22:24 4
Цитата Сообщение от Igor3D Посмотреть сообщение
Нет пула памяти (new/delete на каждый чих)
да, тут согласен, пул бы немного ускорил работу с памятью. И сам не знаю что да как сейчас с конструктором перемещения, сам не делал(к сожалению), но хотелось бы увидить, что да как)
0
Форумчанин
Эксперт CЭксперт С++
8164 / 5012 / 1436
Регистрация: 29.11.2010
Сообщений: 13,455
28.01.2013, 22:35  [ТС] 5
Не вижу оснований запрещать копирование
Не нашел эффективного способа реализовать Stack(Stack &) или Stack& operator= (const Stack &) без ввода доп.переменных.
Насчет пула, да, была даже мысль об этом, почему то потерял по ходу реализации)

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

Цитата Сообщение от MrGluck Посмотреть сообщение
Не нашел эффективного способа реализовать Stack(Stack &) или Stack& operator= (const Stack &) без ввода доп.переменных.
Ну так эфективно или нет, но ведь это же не повод от чего-то отказываться Вставка данных в строку в опред. позицию например может тоже не очень эфективная, но при реализации string её же написали...
0
What a waste!
1588 / 1287 / 173
Регистрация: 21.04.2012
Сообщений: 2,696
28.01.2013, 22:55 7
Цитата Сообщение от MrGluck Посмотреть сообщение
Насчет пула, да, была даже мысль об этом, почему то потерял по ходу реализации)
Может добавить аллокатор? А там уже с пулом\ещё чем будет от него зависеть.
0
Don't worry, be happy
16972 / 9853 / 1897
Регистрация: 27.09.2012
Сообщений: 24,431
Записей в блоге: 1
28.01.2013, 22:57 8
Цитата Сообщение от gray_fox Посмотреть сообщение
Может добавить аллокатор?
Итераторы тоже будут кстати.
0
Форумчанин
Эксперт CЭксперт С++
8164 / 5012 / 1436
Регистрация: 29.11.2010
Сообщений: 13,455
29.01.2013, 01:20  [ТС] 9
Цитата Сообщение от Gepar Посмотреть сообщение
Реализация стека в обход stl с внутернеей реализацией операции через stl ?
ты про InputIterator ? Так я имел ввиду, что не хочу реализовывать одни STL контейнеры через другие.
Цитата Сообщение от Gepar Посмотреть сообщение
Ну так эфективно или нет, но ведь это же не повод от чего-то отказываться Вставка данных в строку в опред. позицию например может тоже не очень эфективная, но при реализации string её же написали...
Так не все так просто в STL, тот же operator[] у list не определен, можно, конечно это сделать, но ради реализации копирования, операций присваивания и сравнения будет страдать эффективность всего класса.
Цитата Сообщение от gray_fox Посмотреть сообщение
Может добавить аллокатор?
Боюсь, експы не хватит)
Цитата Сообщение от Croessmah Посмотреть сообщение
Итераторы тоже будут кстати.
Думаю, это плохая идея, т.к. это не последовательность, тут есть top и все, с другим мы работать, по-хорошему не можем.
0
3239 / 2047 / 350
Регистрация: 24.11.2012
Сообщений: 4,897
29.01.2013, 06:02 10
Цитата Сообщение от MrGluck Посмотреть сообщение
Так не все так просто в STL, тот же operator[] у list не определен
Потому что оператор[] должен работать за константное время, а для списка трудоемкость такой операции определяется как O(N). И что будет если пользователь решит перебрать элементы списка в цикле, используя индекс?
0
3239 / 2047 / 350
Регистрация: 24.11.2012
Сообщений: 4,897
29.01.2013, 06:03 11
Цитата Сообщение от MrGluck Посмотреть сообщение
Так не все так просто в STL, тот же operator[] у list не определен
Потому что оператор[] должен работать за константное время, а для списка трудоемкость такой операции определяется как O(N). И что будет если пользователь решит перебрать элементы списка в цикле, используя индекс?

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

А какие препятствия для реализации конструктора копирования у стека?
Неэффективность. Придется создавать вспомогательный временный стек, перекачовывать туда элементы, а потом из него в новый. Или же вводить доп. переменные.
0
Каратель
Эксперт С++
6598 / 4017 / 401
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
29.01.2013, 12:20 13
Цитата Сообщение от MrGluck Посмотреть сообщение
Неэффективность. Придется создавать вспомогательный временный стек, перекачовывать туда элементы, а потом из него в новый. Или же вводить доп. переменные.
для конструктора копирования всего-то проитерировать все элементы
для оператора присваивания - copy & swap
1
Форумчанин
Эксперт CЭксперт С++
8164 / 5012 / 1436
Регистрация: 29.11.2010
Сообщений: 13,455
29.01.2013, 13:43  [ТС] 14
С оператором присвоений то понятно, но он в своей реализации упирается на конструктор копий.
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
Каратель
Эксперт С++
6598 / 4017 / 401
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
29.01.2013, 14:22 15
Цитата Сообщение от MrGluck Посмотреть сообщение
C++
1
2
3
4
5
6
template <class T>
T& Stack<T>::getTopData() const
{
* ...
* exit(1); 
}
вот такие фугасы закладывать не надо

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

Цитата Сообщение от Jupiter Посмотреть сообщение
выделять память последовательно.
если переопределить операторы new и delete, можно ли будет перемещаться с начала до конца контейнера, используя арифметику указателей?
0
3239 / 2047 / 350
Регистрация: 24.11.2012
Сообщений: 4,897
29.01.2013, 15:19 17
Цитата Сообщение от MrGluck Посмотреть сообщение
Самому мне не очень нравится момент с завершением работы программы в catch блоке
Ну представь: начал использовать в своей программе какую-то стороннюю библиотеку, а она в случае ошибки тебе все приложение закрывает. Лучше бы кидала исключения.
0
Форумчанин
Эксперт CЭксперт С++
8164 / 5012 / 1436
Регистрация: 29.11.2010
Сообщений: 13,455
29.01.2013, 15:26  [ТС] 18
0x10, оно кидает исключение и завершает работу.
Чем вам работа с мусором больше нравится?
Если есть другой вариант - предложите.
Работа завершается лишь при некорректном использовании с указанием на ошибку.
0
45 / 45 / 4
Регистрация: 08.12.2010
Сообщений: 161
29.01.2013, 18:54 19
Цитата Сообщение от MrGluck Посмотреть сообщение
если переопределить операторы new и delete
правильнее сделать базовый класс с собственными ню и делит) и унаследовать ваш стек от базового(управляющего памятью), ну и при правильной работе с памятью можно ускорить работу стека.
0
2552 / 1317 / 178
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
29.01.2013, 19:21 20
Цитата Сообщение от dederkay Посмотреть сообщение
правильнее сделать базовый класс с собственными ню и делит) и унаследовать ваш стек от базового(управляющего памятью), ну и при правильной работе с памятью можно ускорить работу стека.
Правильнее делегировать объект, который будет управлять памятью.
Цитата Сообщение от MrGluck Посмотреть сообщение
0x10, оно кидает исключение и завершает работу.
Чем вам работа с мусором больше нравится?
Если есть другой вариант - предложите.
Работа завершается лишь при некорректном использовании с указанием на ошибку.
Библиотека не должна решать, завершать программу или нет.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
29.01.2013, 19:21

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь или здесь.

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.