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

Стек на шаблонах - оцените реализацию - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.88
GetHelp
-8 / 60 / 6
Регистрация: 27.02.2013
Сообщений: 1,112
17.07.2014, 00:21     Стек на шаблонах - оцените реализацию #1
просто хочу узнать чужое мнение, написал стек через шаблоны, оцените реализацию
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
template <typename T>
class Stack
{
private:
    size_t size;
    T* data;
public:
    Stack();
    void Push(T value);
    T Pop();
};
 
template <typename T>
Stack<T>::Stack()
{
    size = sizeof(T);
    data = new T;
}
 
template <typename T>
void Stack<T>::Push(T value)
{
    data = data + size;
    *data = value;
}
 
template <typename T>
T Stack<T>::Pop()
{
    int tmp = *data;
    data = data - size;
    T* ptr = data + size;
    ptr = nullptr;
    return tmp;
}
Добавлено через 1 минуту
з.ы. сначала пытался париться как это в идеале надо prev, next (т.е. предыдущий и следующий элементы) потом забил, толку с них никакого, все равно по смещению ищу значение
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.07.2014, 00:21     Стек на шаблонах - оцените реализацию
Посмотрите здесь:

Вопрос по исключениям в шаблонах классов C++
C++ Программа добавляет введенный массив 5*5 в стек и выводит полученный стек двумя столбцами
C++ пытаюсь сделать реализацию через считывание из файла кол-ва чисел, i,но незнаю как сделать реализацию из файла в массив и сортировки.
Доступ к элементам tuple в шаблонах C++
Тип, зависимый от условия в шаблонах C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
GetHelp
-8 / 60 / 6
Регистрация: 27.02.2013
Сообщений: 1,112
17.07.2014, 19:05  [ТС]     Стек на шаблонах - оцените реализацию #61
Цитата Сообщение от 0x10 Посмотреть сообщение
Сам же уперся в то, что не знаешь что возвращать из функции pop. Ссылку нельзя - поскольку объект с вершины должен быть удален. Указатель - тоже нельзя, потенциальные утечки. Копию - необоснованные накладные расходы.
я не говорил что не знаю... я возвращаю указатель на копию я не понимаю о каких накладных речь выделяется всего лишь память на 1 элемент, который и возвращается функцией, а там уже что с ним будут делать не моя забота...
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
0x10
2425 / 1597 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
17.07.2014, 19:06     Стек на шаблонах - оцените реализацию #62
Цитата Сообщение от GetHelp Посмотреть сообщение
я не говорил что не знаю... я возвращаю указатель на копию
Про утечки памяти уже сказали.
GetHelp
-8 / 60 / 6
Регистрация: 27.02.2013
Сообщений: 1,112
17.07.2014, 19:08  [ТС]     Стек на шаблонах - оцените реализацию #63
Цитата Сообщение от 0x10 Посмотреть сообщение
Про утечки памяти уже сказали.
я же их устранил
Цитата Сообщение от GetHelp Посмотреть сообщение
а да и правда потерял, вот так исправил
C++
1
2
3
4
5
6
7
8
9
10
11
template <typename T>
T* Stack<T>::Pop()
{
    if (!head) return nullptr;
    T *value = new T;
    *value = head->data;
    NODE *tmp = head;
    head = head->prev;
    delete tmp;
    return value;
}
а других утечек я не вижу...
0x10
2425 / 1597 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
17.07.2014, 19:10     Стек на шаблонах - оцените реализацию #64
Цитата Сообщение от GetHelp Посмотреть сообщение
а других утечек я не вижу...
Кто должен освобождать память, выделенную под value?
GetHelp
-8 / 60 / 6
Регистрация: 27.02.2013
Сообщений: 1,112
17.07.2014, 19:10  [ТС]     Стек на шаблонах - оцените реализацию #65
Цитата Сообщение от 0x10 Посмотреть сообщение
Кто должен освобождать память, выделенную под value?
Цитата Сообщение от GetHelp Посмотреть сообщение
выделяется всего лишь память на 1 элемент, который и возвращается функцией, а там уже что с ним будут делать не моя забота...
тот кто вызывал функцию Pop очевидно
0x10
2425 / 1597 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
17.07.2014, 19:12     Стек на шаблонах - оцените реализацию #66
Цитата Сообщение от GetHelp Посмотреть сообщение
а там уже что с ним будут делать не моя забота
Значит, у библиотеки хреновый интрфейс, котороый провоцирует утечки памяти, ибо ответа на вопрос о ее освобождении нет.
GetHelp
-8 / 60 / 6
Регистрация: 27.02.2013
Сообщений: 1,112
17.07.2014, 19:16  [ТС]     Стек на шаблонах - оцените реализацию #67
Цитата Сообщение от 0x10 Посмотреть сообщение
Значит, у библиотеки хреновый интрфейс, котороый провоцирует утечки памяти, ибо ответа на вопрос о ее освобождении нет.
что из фразы "тот кто вызывал функцию Pop" не понятно?

Добавлено через 3 минуты
и ДАЖЕ если я захочу переделать и сделать void Pop и соответственно какую нибудь T Peek, что вы предложите возвращать если стек пуст??? в этом весь вопрос...
0x10
2425 / 1597 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
17.07.2014, 19:23     Стек на шаблонах - оцените реализацию #68
Цитата Сообщение от GetHelp Посмотреть сообщение
что из фразы "тот кто вызывал функцию Pop" не понятно?
В общем случае объект может быть разделяемым между несколькими владельцами и его время жизни определяется временем жизни всех его владельцев.

Добавлено через 4 минуты
Цитата Сообщение от GetHelp Посмотреть сообщение
что вы предложите возвращать если стек пуст
Можно кинуть исключение или сказать, что это undefined behavior.
GetHelp
-8 / 60 / 6
Регистрация: 27.02.2013
Сообщений: 1,112
17.07.2014, 19:26  [ТС]     Стек на шаблонах - оцените реализацию #69
Цитата Сообщение от 0x10 Посмотреть сообщение
Можно кинуть исключение или сказать, что это undefined behaviour.
а что такое undefined behaviour.
0x10
2425 / 1597 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
17.07.2014, 19:29     Стек на шаблонах - оцените реализацию #70
GetHelp, неопределенное поведение. В частности: разыменование нулевого указателя, выход за границы массива. Один из этих вариантов возможен и при попытке снятия объекта с пустого стека в зависимости от реализации нижележащего контейнера.
GetHelp
-8 / 60 / 6
Регистрация: 27.02.2013
Сообщений: 1,112
17.07.2014, 19:40  [ТС]     Стек на шаблонах - оцените реализацию #71
0x10, вы имеете ввиду что то типа этого?

int32_t safe_div_int32_t (int32_t a, int32_t b)
или
int32_t unsafe_div_int32_t (int32_t a, int32_t b)

Добавлено через 27 секунд
вот тут нырыл http://blog.regehr.org/archives/213

Добавлено через 3 минуты
а исключение кинуть это что то типа throw(0)?
0x10
2425 / 1597 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
17.07.2014, 19:40     Стек на шаблонах - оцените реализацию #72
Я говорю о том, что получение доступа к элементу пустого контейнера есть исключительная ситуация, свидетельствующая о неправильном использовании библиотеки. Разработчик этой библиотеки может либо допускать такое использование и при попытке доступа тупо вылезать за границы памяти, либо генерировать исключение.
GetHelp
-8 / 60 / 6
Регистрация: 27.02.2013
Сообщений: 1,112
17.07.2014, 19:41  [ТС]     Стек на шаблонах - оцените реализацию #73
Цитата Сообщение от 0x10 Посмотреть сообщение
либо генерировать исключение
Цитата Сообщение от GetHelp Посмотреть сообщение
а исключение кинуть это что то типа throw(0)?
10 символов
0x10
2425 / 1597 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
17.07.2014, 19:41     Стек на шаблонах - оцените реализацию #74
Цитата Сообщение от GetHelp Посмотреть сообщение
а исключение кинуть это что то типа throw(0)?
Кинет объект типа int, по которому будет невозможно понять что произошло. Из стандартных исключений наиболее подходящим кажется http://www.cplusplus.com/reference/s.../out_of_range/
GetHelp
-8 / 60 / 6
Регистрация: 27.02.2013
Сообщений: 1,112
17.07.2014, 19:48  [ТС]     Стек на шаблонах - оцените реализацию #75
0x10, никак не пойму как его правильно заюзать, не подскажете?
0x10
2425 / 1597 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
17.07.2014, 19:51     Стек на шаблонах - оцените реализацию #76
Цитата Сообщение от GetHelp Посмотреть сообщение
никак не пойму как его правильно заюзать, не подскажете?
Если не хватает знаний по основам - не вижу смысла. Тем более, выше я говорил, что можно без исключений.

Нормальным вариантом кажется посмотреть на реализацию в стандартной библиотеке и сделать по образу и подобию. Для этого не обязательно лезть глубоко, достатоно посмотреть интерфейсы стандартных контейнеров.
GetHelp
-8 / 60 / 6
Регистрация: 27.02.2013
Сообщений: 1,112
17.07.2014, 19:58  [ТС]     Стек на шаблонах - оцените реализацию #77
Цитата Сообщение от 0x10 Посмотреть сообщение
Нормальным вариантом кажется посмотреть на реализацию в стандартной библиотеке и сделать по образу и подобию. Для этого не обязательно лезть глубоко, достатоно посмотреть интерфейсы стандартных контейнеров.
хотя бы тыкните пальцем что читать... ибо вот я открыл файл с объявлением этого стандартного стека... и нехрена не могу в нем понять вообще...
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
// stack standard header
#pragma once
#ifndef _STACK_
#define _STACK_
#ifndef RC_INVOKED
#include <deque>
 
 #pragma pack(push,_CRT_PACKING)
 #pragma warning(push,3)
_STD_BEGIN
        // TEMPLATE CLASS stack
template<class _Ty,
    class _Container = deque<_Ty> >
    class stack
    {   // LIFO queue implemented with a container
public:
    typedef stack<_Ty, _Container> _Myt;
    typedef _Container container_type;
    typedef typename _Container::value_type value_type;
    typedef typename _Container::size_type size_type;
    typedef typename _Container::reference reference;
    typedef typename _Container::const_reference const_reference;
 
    stack()
        : c()
        {   // construct with empty container
        }
 
    stack(const _Myt& _Right)
        : c(_Right.c)
        {   // construct by copying _Right
        }
 
    explicit stack(const _Container& _Cont)
        : c(_Cont)
        {   // construct by copying specified container
        }
 
    _Myt& operator=(const _Myt& _Right)
        {   // assign by copying _Right
        c = _Right.c;
        return (*this);
        }
 
    stack(_Myt&& _Right)
        : c(_STD move(_Right.c))
        {   // construct by moving _Right
        }
 
    explicit stack(_Container&& _Cont)
        : c(_STD move(_Cont))
        {   // construct by copying specified container
        }
 
    _Myt& operator=(_Myt&& _Right)
        {   // assign by moving _Right
        c = _STD move(_Right.c);
        return (*this);
        }
 
    void push(value_type&& _Val)
        {   // insert element at beginning
        c.push_back(_STD move(_Val));
        }
 
    template<class _Valty>
        void emplace(_Valty&& _Val)
        {   // insert element at beginning
        c.emplace_back(_STD forward<_Valty>(_Val));
        }
 
    void swap(_Myt&& _Right)
        {   // exchange contents with movable _Right
        c.swap(_STD move(_Right.c));
        }
 
    bool empty() const
        {   // test if stack is empty
        return (c.empty());
        }
 
    size_type size() const
        {   // test length of stack
        return (c.size());
        }
 
    reference top()
        {   // return last element of mutable stack
        return (c.back());
        }
 
    const_reference top() const
        {   // return last element of nonmutable stack
        return (c.back());
        }
 
    void push(const value_type& _Val)
        {   // insert element at end
        c.push_back(_Val);
        }
 
    void pop()
        {   // erase last element
        c.pop_back();
        }
 
    const _Container& _Get_container() const
        {   // get reference to container
        return (c);
        }
 
    void swap(_Myt& _Right)
        {   // exchange contents with _Right
        c.swap(_Right.c);
        }
 
protected:
    _Container c;   // the underlying container
    };
 
        // stack TEMPLATE FUNCTIONS
template<class _Ty,
    class _Container> inline
    void swap(stack<_Ty, _Container>& _Left,
        stack<_Ty, _Container>& _Right)
    {   // swap _Left and _Right stacks
    _Left.swap(_Right);
    }
 
template<class _Ty,
    class _Container> inline
    void swap(stack<_Ty, _Container>& _Left,
        stack<_Ty, _Container>&& _Right)
    {   // swap _Left and _Right stacks
    typedef stack<_Ty, _Container> _Myt;
    _Left.swap(_STD forward<_Myt>(_Right));
    }
 
template<class _Ty,
    class _Container> inline
    void swap(stack<_Ty, _Container>&& _Left,
        stack<_Ty, _Container>& _Right)
    {   // swap _Left and _Right stacks
    typedef stack<_Ty, _Container> _Myt;
    _Right.swap(_STD forward<_Myt>(_Left));
    }
 
template<class _Ty,
    class _Container> inline
    bool operator==(const stack<_Ty, _Container>& _Left,
        const stack<_Ty, _Container>& _Right)
    {   // test for stack equality
    return (_Left._Get_container() == _Right._Get_container());
    }
 
template<class _Ty,
    class _Container> inline
    bool operator!=(const stack<_Ty, _Container>& _Left,
        const stack<_Ty, _Container>& _Right)
    {   // test for stack inequality
    return (!(_Left == _Right));
    }
 
template<class _Ty,
    class _Container> inline
    bool operator<(const stack<_Ty, _Container>& _Left,
        const stack<_Ty, _Container>& _Right)
    {   // test if _Left < _Right for stacks
    return (_Left._Get_container() < _Right._Get_container());
    }
 
template<class _Ty,
    class _Container> inline
    bool operator>(const stack<_Ty, _Container>& _Left,
        const stack<_Ty, _Container>& _Right)
    {   // test if _Left > _Right for stacks
    return (_Right < _Left);
    }
 
template<class _Ty,
    class _Container> inline
    bool operator<=(const stack<_Ty, _Container>& _Left,
        const stack<_Ty, _Container>& _Right)
    {   // test if _Left <= _Right for stacks
    return (!(_Right < _Left));
    }
 
template<class _Ty,
    class _Container> inline
    bool operator>=(const stack<_Ty, _Container>& _Left,
        const stack<_Ty, _Container>& _Right)
    {   // test if _Left >= _Right for stacks
    return (!(_Left < _Right));
    }
_STD_END
 #pragma warning(pop)
 #pragma pack(pop)
 
#endif /* RC_INVOKED */
#endif /* _STACK_ */
 
/*
 * This file is derived from software bearing the following
 * restrictions:
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this
 * software and its documentation for any purpose is hereby
 * granted without fee, provided that the above copyright notice
 * appear in all copies and that both that copyright notice and
 * this permission notice appear in supporting documentation.
 * Hewlett-Packard Company makes no representations about the
 * suitability of this software for any purpose. It is provided
 * "as is" without express or implied warranty.
 */
 
/*
 * Copyright (c) 1992-2009 by P.J. Plauger.  ALL RIGHTS RESERVED.
 * Consult your license regarding permissions and restrictions.
V5.20:0009 */
0x10
2425 / 1597 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
17.07.2014, 20:07     Стек на шаблонах - оцените реализацию #78
Цитата Сообщение от GetHelp Посмотреть сообщение
хотя бы тыкните пальцем что читать
Любую книгу по плюсам, раздел - обработка исключений.
В данном случае реализация будет примерно такая (псевдокод):
C++
1
2
3
4
T& top() {
  if (container_.empty()) throw std::out_of_range("Access to element of empty container");
  return container.back();
}
Цитата Сообщение от GetHelp Посмотреть сообщение
и нехрена не могу в нем понять вообще
Не обязательно лезть в исходники, достаточно почитать доки по интерфейсам (cplusplus.com в помощь)

Оставим только функции pop и top, раз уж о них говорили, и все становится предельно ясно. Для краткости определения синонимов типов тоже удалены, предполагая, что из имена в контексте говорят за себя.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template<class _Ty,
    class _Container = deque<_Ty> >
    class stack
    {   // LIFO queue implemented with a container
public:
    reference top()
        {   // return last element of mutable stack
        return (c.back());
        }
 
    void pop()
        {   // erase last element
        c.pop_back();
        }
 
protected:
    _Container c;   // the underlying container
    };
GetHelp
-8 / 60 / 6
Регистрация: 27.02.2013
Сообщений: 1,112
17.07.2014, 20:18  [ТС]     Стек на шаблонах - оцените реализацию #79
ну короче как то так...
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
#include <stdexcept>
 
template <typename T>
class Stack
{
private:
    struct NODE
    {
        T data;
        NODE *prev;
    } *head;
public:
    Stack();
    ~Stack();
    void Push(T value);
    void Pop();
    T Peek();
};
 
template <typename T>
Stack<T>::Stack()
{
    head = nullptr;
}
 
template <typename T>
Stack<T>::~Stack()
{
    while (head)
    {
        NODE *tmp = head->prev;
        delete head;
        head = tmp;
    }
}
 
template <typename T>
void Stack<T>::Push(T value)
{
    NODE *tmp = new NODE;
    tmp->data = value;
    tmp->prev = head;
    head = tmp;
}
 
template <typename T>
void Stack<T>::Pop()
{
    if (!head) throw std::out_of_range("Access to element of empty container");
    T *value = new T;
    *value = head->data;
    NODE *tmp = head;
    head = head->prev;
    delete tmp;
}
 
template <typename T>
T Stack<T>::Peek()
{
    if (head)
        return head->data;
    else
        throw std::out_of_range("Access to element of empty container");
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.07.2014, 20:21     Стек на шаблонах - оцените реализацию
Еще ссылки по теме:

C++ Подстановка вычисляемого типа в шаблонах
Переменные в стеке. Где хранятся? Как обрабатываются? Есть ли программный стек или только стек процессора? C++
C++ Класс на шаблонах, менять аргументы шаблона

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

Или воспользуйтесь поиском по форуму:
0x10
2425 / 1597 / 232
Регистрация: 24.11.2012
Сообщений: 3,919
17.07.2014, 20:21     Стек на шаблонах - оцените реализацию #80
Теперь value в Pop не используется и 100% ведет к утечкам.
Yandex
Объявления
17.07.2014, 20:21     Стек на шаблонах - оцените реализацию
Закрытая тема Создать тему
Опции темы

Текущее время: 18:29. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru