Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
MrGluck
Модератор
Эксперт CЭксперт С++
7801 / 4845 / 754
Регистрация: 29.11.2010
Сообщений: 13,212
#1

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

28.01.2013, 21:55. Просмотров 1272. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.01.2013, 21:55
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Собственная реализация стека. Критика (C++):

Собственная реализация паттерна "Слушатель" - нужна конструктивная критика - 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++
Дали следующее задание. Не совсем понимаю с чего начинать и как дальше быть. Сказали, что нужно через шаблоны сделать. Если у кого-нибудь...

20
Igor3D
991 / 594 / 71
Регистрация: 01.10.2012
Сообщений: 2,844
28.01.2013, 22:16 #2
1) Не вижу оснований запрещать копирование

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

3) Не лучше/проще ли сделать на базе std::vector или std::list?
1
Croessmah
Ушел
13783 / 8033 / 928
Регистрация: 27.09.2012
Сообщений: 19,801
Записей в блоге: 3
Завершенные тесты: 1
28.01.2013, 22:19 #3
Цитата Сообщение от Igor3D Посмотреть сообщение
Не лучше/проще ли сделать на базе std::vector или std::list?
тогда лучше сразу std::stack использовать.
0
dederkay
39 / 39 / 0
Регистрация: 08.12.2010
Сообщений: 161
28.01.2013, 22:24 #4
Цитата Сообщение от Igor3D Посмотреть сообщение
Нет пула памяти (new/delete на каждый чих)
да, тут согласен, пул бы немного ускорил работу с памятью. И сам не знаю что да как сейчас с конструктором перемещения, сам не делал(к сожалению), но хотелось бы увидить, что да как)
0
MrGluck
Модератор
Эксперт CЭксперт С++
7801 / 4845 / 754
Регистрация: 29.11.2010
Сообщений: 13,212
28.01.2013, 22:35  [ТС] #5
Не вижу оснований запрещать копирование
Не нашел эффективного способа реализовать Stack(Stack &) или Stack& operator= (const Stack &) без ввода доп.переменных.
Насчет пула, да, была даже мысль об этом, почему то потерял по ходу реализации)

но вот STL через STL не вижу смысла делать
0
Gepar
1181 / 537 / 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 её же написали...
0
gray_fox
What a waste!
1552 / 1257 / 74
Регистрация: 21.04.2012
Сообщений: 2,634
Завершенные тесты: 3
28.01.2013, 22:55 #7
Цитата Сообщение от MrGluck Посмотреть сообщение
Насчет пула, да, была даже мысль об этом, почему то потерял по ходу реализации)
Может добавить аллокатор? А там уже с пулом\ещё чем будет от него зависеть.
0
Croessmah
Ушел
13783 / 8033 / 928
Регистрация: 27.09.2012
Сообщений: 19,801
Записей в блоге: 3
Завершенные тесты: 1
28.01.2013, 22:57 #8
Цитата Сообщение от gray_fox Посмотреть сообщение
Может добавить аллокатор?
Итераторы тоже будут кстати.
0
MrGluck
Модератор
Эксперт CЭксперт С++
7801 / 4845 / 754
Регистрация: 29.11.2010
Сообщений: 13,212
29.01.2013, 01:20  [ТС] #9
Цитата Сообщение от Gepar Посмотреть сообщение
Реализация стека в обход stl с внутернеей реализацией операции через stl ?
ты про InputIterator ? Так я имел ввиду, что не хочу реализовывать одни STL контейнеры через другие.
Цитата Сообщение от Gepar Посмотреть сообщение
Ну так эфективно или нет, но ведь это же не повод от чего-то отказываться Вставка данных в строку в опред. позицию например может тоже не очень эфективная, но при реализации string её же написали...
Так не все так просто в STL, тот же operator[] у list не определен, можно, конечно это сделать, но ради реализации копирования, операций присваивания и сравнения будет страдать эффективность всего класса.
Цитата Сообщение от gray_fox Посмотреть сообщение
Может добавить аллокатор?
Боюсь, експы не хватит)
Цитата Сообщение от Croessmah Посмотреть сообщение
Итераторы тоже будут кстати.
Думаю, это плохая идея, т.к. это не последовательность, тут есть top и все, с другим мы работать, по-хорошему не можем.
0
0x10
2549 / 1729 / 264
Регистрация: 24.11.2012
Сообщений: 4,351
29.01.2013, 06:02 #10
Цитата Сообщение от MrGluck Посмотреть сообщение
Так не все так просто в STL, тот же operator[] у list не определен
Потому что оператор[] должен работать за константное время, а для списка трудоемкость такой операции определяется как O(N). И что будет если пользователь решит перебрать элементы списка в цикле, используя индекс?
0
0x10
2549 / 1729 / 264
Регистрация: 24.11.2012
Сообщений: 4,351
29.01.2013, 06:03 #11
Цитата Сообщение от MrGluck Посмотреть сообщение
Так не все так просто в STL, тот же operator[] у list не определен
Потому что оператор[] должен работать за константное время, а для списка трудоемкость такой операции определяется как O(N). И что будет если пользователь решит перебрать элементы списка в цикле, используя индекс?

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

А какие препятствия для реализации конструктора копирования у стека?
Неэффективность. Придется создавать вспомогательный временный стек, перекачовывать туда элементы, а потом из него в новый. Или же вводить доп. переменные.
0
Jupiter
Каратель
Эксперт С++
6568 / 3989 / 227
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
29.01.2013, 12:20 #13
Цитата Сообщение от MrGluck Посмотреть сообщение
Неэффективность. Придется создавать вспомогательный временный стек, перекачовывать туда элементы, а потом из него в новый. Или же вводить доп. переменные.
для конструктора копирования всего-то проитерировать все элементы
для оператора присваивания - copy & swap
1
MrGluck
Модератор
Эксперт CЭксперт С++
7801 / 4845 / 754
Регистрация: 29.11.2010
Сообщений: 13,212
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
Jupiter
Каратель
Эксперт С++
6568 / 3989 / 227
Регистрация: 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 Посмотреть сообщение
Не хочется вот так вот делать:
либо так, либо вводить указатель на предыдущий элемент, либо выделять память последовательно.
вообще стоит придерживаться того что стек - это адаптер который содежит контейнер и лишь регулирует вставку/удаление элементов и доступ к верхушке. а у контейнера соответсвенно уже определен свой конструктор корирования, оператор присваивания и т.д.
0
29.01.2013, 14:22
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.01.2013, 14:22
Привет! Вот еще темы с ответами:

Реализация стека - C++
Всем доброго времени суток! Нашел в на просторах интернета исходник реализации стека. Но не совсем понятен код. Что бы понять - я...

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

Реализация стека - C++
вот такие ошибки при реализации: stack.h(26) : error C2953: 'Stack' : class template has already been defined liststack.h(10) : error...

Реализация стека - C++
Здравствуйте, помогите пожалуйста с реализацией стека без использования STL. Стек отображен в памяти Вектором, память статическая(1...


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

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

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