Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.59/27: Рейтинг темы: голосов - 27, средняя оценка - 4.59
63 / 64 / 11
Регистрация: 27.02.2013
Сообщений: 1,116
1

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

17.07.2014, 00:21. Показов 5630. Ответов 101
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
просто хочу узнать чужое мнение, написал стек через шаблоны, оцените реализацию
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 (т.е. предыдущий и следующий элементы) потом забил, толку с них никакого, все равно по смещению ищу значение
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
17.07.2014, 00:21
Ответы с готовыми решениями:

Сделать реализацию list (классы node и list) на шаблонах
Помогите написать прогу Необходимо: Сделать реализацию list (классы node и list) на шаблонах....

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

Оцените реализацию Угадывателя чисел
И вопрос на засыпку, можно ли как то максимально оптимизировать данный процесс? Если да, то как....

Оцените реализацию вертикального списка
Сделал вертикальный список с навигацией по стрелкам клавиатуры. ...

101
63 / 64 / 11
Регистрация: 27.02.2013
Сообщений: 1,116
17.07.2014, 19:05  [ТС] 61
Author24 — интернет-сервис помощи студентам
Цитата Сообщение от 0x10 Посмотреть сообщение
Сам же уперся в то, что не знаешь что возвращать из функции pop. Ссылку нельзя - поскольку объект с вершины должен быть удален. Указатель - тоже нельзя, потенциальные утечки. Копию - необоснованные накладные расходы.
я не говорил что не знаю... я возвращаю указатель на копию я не понимаю о каких накладных речь выделяется всего лишь память на 1 элемент, который и возвращается функцией, а там уже что с ним будут делать не моя забота...
0
3257 / 2059 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
17.07.2014, 19:06 62
Цитата Сообщение от GetHelp Посмотреть сообщение
я не говорил что не знаю... я возвращаю указатель на копию
Про утечки памяти уже сказали.
0
63 / 64 / 11
Регистрация: 27.02.2013
Сообщений: 1,116
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;
}
а других утечек я не вижу...
0
3257 / 2059 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
17.07.2014, 19:10 64
Цитата Сообщение от GetHelp Посмотреть сообщение
а других утечек я не вижу...
Кто должен освобождать память, выделенную под value?
0
63 / 64 / 11
Регистрация: 27.02.2013
Сообщений: 1,116
17.07.2014, 19:10  [ТС] 65
Цитата Сообщение от 0x10 Посмотреть сообщение
Кто должен освобождать память, выделенную под value?
Цитата Сообщение от GetHelp Посмотреть сообщение
выделяется всего лишь память на 1 элемент, который и возвращается функцией, а там уже что с ним будут делать не моя забота...
тот кто вызывал функцию Pop очевидно
0
3257 / 2059 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
17.07.2014, 19:12 66
Цитата Сообщение от GetHelp Посмотреть сообщение
а там уже что с ним будут делать не моя забота
Значит, у библиотеки хреновый интрфейс, котороый провоцирует утечки памяти, ибо ответа на вопрос о ее освобождении нет.
0
63 / 64 / 11
Регистрация: 27.02.2013
Сообщений: 1,116
17.07.2014, 19:16  [ТС] 67
Цитата Сообщение от 0x10 Посмотреть сообщение
Значит, у библиотеки хреновый интрфейс, котороый провоцирует утечки памяти, ибо ответа на вопрос о ее освобождении нет.
что из фразы "тот кто вызывал функцию Pop" не понятно?

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

Добавлено через 4 минуты
Цитата Сообщение от GetHelp Посмотреть сообщение
что вы предложите возвращать если стек пуст
Можно кинуть исключение или сказать, что это undefined behavior.
0
63 / 64 / 11
Регистрация: 27.02.2013
Сообщений: 1,116
17.07.2014, 19:26  [ТС] 69
Цитата Сообщение от 0x10 Посмотреть сообщение
Можно кинуть исключение или сказать, что это undefined behaviour.
а что такое undefined behaviour.
0
3257 / 2059 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
17.07.2014, 19:29 70
GetHelp, неопределенное поведение. В частности: разыменование нулевого указателя, выход за границы массива. Один из этих вариантов возможен и при попытке снятия объекта с пустого стека в зависимости от реализации нижележащего контейнера.
0
63 / 64 / 11
Регистрация: 27.02.2013
Сообщений: 1,116
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)?
0
3257 / 2059 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
17.07.2014, 19:40 72
Я говорю о том, что получение доступа к элементу пустого контейнера есть исключительная ситуация, свидетельствующая о неправильном использовании библиотеки. Разработчик этой библиотеки может либо допускать такое использование и при попытке доступа тупо вылезать за границы памяти, либо генерировать исключение.
0
63 / 64 / 11
Регистрация: 27.02.2013
Сообщений: 1,116
17.07.2014, 19:41  [ТС] 73
Цитата Сообщение от 0x10 Посмотреть сообщение
либо генерировать исключение
Цитата Сообщение от GetHelp Посмотреть сообщение
а исключение кинуть это что то типа throw(0)?
10 символов
0
3257 / 2059 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
17.07.2014, 19:41 74
Цитата Сообщение от GetHelp Посмотреть сообщение
а исключение кинуть это что то типа throw(0)?
Кинет объект типа int, по которому будет невозможно понять что произошло. Из стандартных исключений наиболее подходящим кажется http://www.cplusplus.com/refer... _of_range/
0
63 / 64 / 11
Регистрация: 27.02.2013
Сообщений: 1,116
17.07.2014, 19:48  [ТС] 75
0x10, никак не пойму как его правильно заюзать, не подскажете?
0
3257 / 2059 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
17.07.2014, 19:51 76
Цитата Сообщение от GetHelp Посмотреть сообщение
никак не пойму как его правильно заюзать, не подскажете?
Если не хватает знаний по основам - не вижу смысла. Тем более, выше я говорил, что можно без исключений.

Нормальным вариантом кажется посмотреть на реализацию в стандартной библиотеке и сделать по образу и подобию. Для этого не обязательно лезть глубоко, достатоно посмотреть интерфейсы стандартных контейнеров.
0
63 / 64 / 11
Регистрация: 27.02.2013
Сообщений: 1,116
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 */
0
3257 / 2059 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
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
    };
0
63 / 64 / 11
Регистрация: 27.02.2013
Сообщений: 1,116
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");
}
0
3257 / 2059 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
17.07.2014, 20:21 80
Теперь value в Pop не используется и 100% ведет к утечкам.
0
17.07.2014, 20:21
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.07.2014, 20:21
Помогаю со студенческими работами здесь

Оцените реализацию классов с использованием наследования
Программируя, я никогда раньше не пользовался наследованием классов и всем, что к этому относится и...

Программа для шифрования файлов в один контейнер. Оцените реализацию
Приветствую. Написал свою первую программу. Суть такая: Выбираются файлы, добавляются в...

пытаюсь сделать реализацию через считывание из файла кол-ва чисел, i,но незнаю как сделать реализацию из файла в массив и сортировки.
В файле input.txt находится неизвестное количество вещественных чисел в интервале . Выцапарать их...

Ошыбка на шаблонах
Простая проблемка, но никак не могу понять почему оно не работет. Выдает ошибку: Notice:...


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

Или воспользуйтесь поиском по форуму:
80
Закрытая тема Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru