Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
MrGluck
Модератор
Эксперт CЭксперт С++
7005 / 4176 / 595
Регистрация: 29.11.2010
Сообщений: 11,082
#1

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

28.01.2013, 21:55. Просмотров 1158. Ответов 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();
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.01.2013, 21:55     Собственная реализация стека. Критика
Посмотрите здесь:

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

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

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

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

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

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

Реализация и использование стека - C++
Господа, помогите разобраться со стеком. Хотя бы расскажите, как его правильно объявлять и заполнять. Я смотрел много всяких тем и сайтов,...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Igor3D
938 / 471 / 42
Регистрация: 01.10.2012
Сообщений: 2,331
28.01.2013, 22:16     Собственная реализация стека. Критика #2
1) Не вижу оснований запрещать копирование

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

3) Не лучше/проще ли сделать на базе std::vector или std::list?
Croessmah
Модератор
Эксперт CЭксперт С++
12980 / 7292 / 812
Регистрация: 27.09.2012
Сообщений: 18,007
Записей в блоге: 3
Завершенные тесты: 1
28.01.2013, 22:19     Собственная реализация стека. Критика #3
Цитата Сообщение от Igor3D Посмотреть сообщение
Не лучше/проще ли сделать на базе std::vector или std::list?
тогда лучше сразу std::stack использовать.
dederkay
34 / 34 / 0
Регистрация: 08.12.2010
Сообщений: 161
28.01.2013, 22:24     Собственная реализация стека. Критика #4
Цитата Сообщение от Igor3D Посмотреть сообщение
Нет пула памяти (new/delete на каждый чих)
да, тут согласен, пул бы немного ускорил работу с памятью. И сам не знаю что да как сейчас с конструктором перемещения, сам не делал(к сожалению), но хотелось бы увидить, что да как)
MrGluck
Модератор
Эксперт CЭксперт С++
7005 / 4176 / 595
Регистрация: 29.11.2010
Сообщений: 11,082
28.01.2013, 22:35  [ТС]     Собственная реализация стека. Критика #5
Не вижу оснований запрещать копирование
Не нашел эффективного способа реализовать Stack(Stack &) или Stack& operator= (const Stack &) без ввода доп.переменных.
Насчет пула, да, была даже мысль об этом, почему то потерял по ходу реализации)

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

Цитата Сообщение от MrGluck Посмотреть сообщение
Не нашел эффективного способа реализовать Stack(Stack &) или Stack& operator= (const Stack &) без ввода доп.переменных.
Ну так эфективно или нет, но ведь это же не повод от чего-то отказываться Вставка данных в строку в опред. позицию например может тоже не очень эфективная, но при реализации string её же написали...
gray_fox
What a waste!
1411 / 1140 / 55
Регистрация: 21.04.2012
Сообщений: 2,362
Завершенные тесты: 3
28.01.2013, 22:55     Собственная реализация стека. Критика #7
Цитата Сообщение от MrGluck Посмотреть сообщение
Насчет пула, да, была даже мысль об этом, почему то потерял по ходу реализации)
Может добавить аллокатор? А там уже с пулом\ещё чем будет от него зависеть.
Croessmah
Модератор
Эксперт CЭксперт С++
12980 / 7292 / 812
Регистрация: 27.09.2012
Сообщений: 18,007
Записей в блоге: 3
Завершенные тесты: 1
28.01.2013, 22:57     Собственная реализация стека. Критика #8
Цитата Сообщение от gray_fox Посмотреть сообщение
Может добавить аллокатор?
Итераторы тоже будут кстати.
MrGluck
Модератор
Эксперт CЭксперт С++
7005 / 4176 / 595
Регистрация: 29.11.2010
Сообщений: 11,082
29.01.2013, 01:20  [ТС]     Собственная реализация стека. Критика #9
Цитата Сообщение от Gepar Посмотреть сообщение
Реализация стека в обход stl с внутернеей реализацией операции через stl ?
ты про InputIterator ? Так я имел ввиду, что не хочу реализовывать одни STL контейнеры через другие.
Цитата Сообщение от Gepar Посмотреть сообщение
Ну так эфективно или нет, но ведь это же не повод от чего-то отказываться Вставка данных в строку в опред. позицию например может тоже не очень эфективная, но при реализации string её же написали...
Так не все так просто в STL, тот же operator[] у list не определен, можно, конечно это сделать, но ради реализации копирования, операций присваивания и сравнения будет страдать эффективность всего класса.
Цитата Сообщение от gray_fox Посмотреть сообщение
Может добавить аллокатор?
Боюсь, експы не хватит)
Цитата Сообщение от Croessmah Посмотреть сообщение
Итераторы тоже будут кстати.
Думаю, это плохая идея, т.к. это не последовательность, тут есть top и все, с другим мы работать, по-хорошему не можем.
0x10
2459 / 1631 / 238
Регистрация: 24.11.2012
Сообщений: 4,009
29.01.2013, 06:02     Собственная реализация стека. Критика #10
Цитата Сообщение от MrGluck Посмотреть сообщение
Так не все так просто в STL, тот же operator[] у list не определен
Потому что оператор[] должен работать за константное время, а для списка трудоемкость такой операции определяется как O(N). И что будет если пользователь решит перебрать элементы списка в цикле, используя индекс?
0x10
2459 / 1631 / 238
Регистрация: 24.11.2012
Сообщений: 4,009
29.01.2013, 06:03     Собственная реализация стека. Критика #11
Цитата Сообщение от MrGluck Посмотреть сообщение
Так не все так просто в STL, тот же operator[] у list не определен
Потому что оператор[] должен работать за константное время, а для списка трудоемкость такой операции определяется как O(N). И что будет если пользователь решит перебрать элементы списка в цикле, используя индекс?

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

А какие препятствия для реализации конструктора копирования у стека?
Неэффективность. Придется создавать вспомогательный временный стек, перекачовывать туда элементы, а потом из него в новый. Или же вводить доп. переменные.
Jupiter
Каратель
Эксперт С++
6552 / 3972 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
29.01.2013, 12:20     Собственная реализация стека. Критика #13
Цитата Сообщение от MrGluck Посмотреть сообщение
Неэффективность. Придется создавать вспомогательный временный стек, перекачовывать туда элементы, а потом из него в новый. Или же вводить доп. переменные.
для конструктора копирования всего-то проитерировать все элементы
для оператора присваивания - copy & swap
MrGluck
Модератор
Эксперт CЭксперт С++
7005 / 4176 / 595
Регистрация: 29.11.2010
Сообщений: 11,082
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_);
}
Jupiter
Каратель
Эксперт С++
6552 / 3972 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
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 Посмотреть сообщение
Не хочется вот так вот делать:
либо так, либо вводить указатель на предыдущий элемент, либо выделять память последовательно.
вообще стоит придерживаться того что стек - это адаптер который содежит контейнер и лишь регулирует вставку/удаление элементов и доступ к верхушке. а у контейнера соответсвенно уже определен свой конструктор корирования, оператор присваивания и т.д.
MrGluck
Модератор
Эксперт CЭксперт С++
7005 / 4176 / 595
Регистрация: 29.11.2010
Сообщений: 11,082
29.01.2013, 15:12  [ТС]     Собственная реализация стека. Критика #16
Цитата Сообщение от Jupiter Посмотреть сообщение
вот такие фугасы закладывать не надо
я тоже так считаю
Цитата Сообщение от MrGluck Посмотреть сообщение
Самому мне не очень нравится момент с завершением работы программы в catch блоке, но не знаю как обойти возврат мусора в функции, возвращающей T&.
Но лучше ведь, чем работать с мусором. Рад бы сделать так, чтоб возврата не было, но пока изящных решений не встречал и не придумал.

Цитата Сообщение от Jupiter Посмотреть сообщение
выделять память последовательно.
если переопределить операторы new и delete, можно ли будет перемещаться с начала до конца контейнера, используя арифметику указателей?
0x10
2459 / 1631 / 238
Регистрация: 24.11.2012
Сообщений: 4,009
29.01.2013, 15:19     Собственная реализация стека. Критика #17
Цитата Сообщение от MrGluck Посмотреть сообщение
Самому мне не очень нравится момент с завершением работы программы в catch блоке
Ну представь: начал использовать в своей программе какую-то стороннюю библиотеку, а она в случае ошибки тебе все приложение закрывает. Лучше бы кидала исключения.
MrGluck
Модератор
Эксперт CЭксперт С++
7005 / 4176 / 595
Регистрация: 29.11.2010
Сообщений: 11,082
29.01.2013, 15:26  [ТС]     Собственная реализация стека. Критика #18
0x10, оно кидает исключение и завершает работу.
Чем вам работа с мусором больше нравится?
Если есть другой вариант - предложите.
Работа завершается лишь при некорректном использовании с указанием на ошибку.
dederkay
34 / 34 / 0
Регистрация: 08.12.2010
Сообщений: 161
29.01.2013, 18:54     Собственная реализация стека. Критика #19
Цитата Сообщение от MrGluck Посмотреть сообщение
если переопределить операторы new и delete
правильнее сделать базовый класс с собственными ню и делит) и унаследовать ваш стек от базового(управляющего памятью), ну и при правильной работе с памятью можно ускорить работу стека.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.01.2013, 19:21     Собственная реализация стека. Критика
Еще ссылки по теме:

Реализация стека массивом - C++
При реализации стека массивом обеспечить размещение двух стеков в одном массиве. Один стек размещается в начале массива и растет до конца,...

Реализация стека на указателях - C++
Стек на указателях: #include &lt;iostream&gt; using std::cin; using std::cout; using std::endl; enum FirstNodeEnum{NoFirstNode,...

Реализация стека. Но ошибка - C++
написала программу но выдает ошибку. #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; const int max_size=60; class...

Реализация стека с шаблонами - C++
Вообщем, реализую стек известная проблема, не могу понять почему не компилирует, хотя 20 раз все проверил #include &lt;iostream&gt; ...

Реализация стека FIFO и LIFO - C++
Собственно, если у кого-нить будет время посмотреть мои реализации FIFO и LIFO стеков, и высказать замечания, буду очень признателен =) ...


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

Или воспользуйтесь поиском по форуму:
soon
2539 / 1304 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
29.01.2013, 19:21     Собственная реализация стека. Критика #20
Цитата Сообщение от dederkay Посмотреть сообщение
правильнее сделать базовый класс с собственными ню и делит) и унаследовать ваш стек от базового(управляющего памятью), ну и при правильной работе с памятью можно ускорить работу стека.
Правильнее делегировать объект, который будет управлять памятью.
Цитата Сообщение от MrGluck Посмотреть сообщение
0x10, оно кидает исключение и завершает работу.
Чем вам работа с мусором больше нравится?
Если есть другой вариант - предложите.
Работа завершается лишь при некорректном использовании с указанием на ошибку.
Библиотека не должна решать, завершать программу или нет.
Yandex
Объявления
29.01.2013, 19:21     Собственная реализация стека. Критика
Ответ Создать тему
Опции темы

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