63 / 64 / 11
Регистрация: 27.02.2013
Сообщений: 1,116

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

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

Студворк — интернет-сервис помощи студентам
просто хочу узнать чужое мнение, написал стек через шаблоны, оцените реализацию
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
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
17.07.2014, 00:21
Ответы с готовыми решениями:

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

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

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

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

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

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

Нормальным вариантом кажется посмотреть на реализацию в стандартной библиотеке и сделать по образу и подобию. Для этого не обязательно лезть глубоко, достатоно посмотреть интерфейсы стандартных контейнеров.
0
63 / 64 / 11
Регистрация: 27.02.2013
Сообщений: 1,116
17.07.2014, 19:58  [ТС]
Цитата Сообщение от 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
3258 / 2060 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
17.07.2014, 20:07
Цитата Сообщение от 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  [ТС]
ну короче как то так...
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
3258 / 2060 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
17.07.2014, 20:21
Теперь value в Pop не используется и 100% ведет к утечкам.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
17.07.2014, 20:21

Оцените реализацию вертикального списка
Сделал вертикальный список с навигацией по стрелкам клавиатуры. https://jsfiddle.net/Ucorp/cuhkmxe0/9/ Буду рад услышать ваше...

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

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

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

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


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

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

Новые блоги и статьи
Кредитный калькулятор
Maks 05.08.2026
Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .
У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35".
kumehtar 04.08.2026
С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .
Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники).
Hrethgir 04.08.2026
Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .
Термопринтер QR701
Argus19 03.08.2026
Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .
Создание формы заимствованного документа
Maks 03.08.2026
Задача: Необходимо создать собственную форму заимствованного документа. На форме должен быть реквизит "Покупатель", а также табличная часть со следующими реквизитами: - Расчетный счет покупателя. . .
Задача предоставления скидок покупателям
Maks 03.08.2026
Задача: В документе "Продажи" необходимо реализовать функционал предоставления скидок покупателям. Скидка должна автоматически рассчитываться и подставляться в соответствующее поле при выборе. . .
Почему SEO не начинается с ключевых слов: что проверить до написания текстов
Neotwalker 01.08.2026
Когда владельцу сайта предлагают заняться SEO, первым шагом часто становится сбор запросов и написание текстов. Логика кажется понятной: 1. Находим ключевые слова. 2. Добавляем их на. . .
Знание — сила: Доктрина интенциональности знаний, углубление в формулу
Hrethgir 01.08.2026
https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11957&stc=1&d=1785567302 Знаменитый афоризм Фрэнсиса Бэкона «Знание — сила» (Scientia potentia est) в массовой культуре принято понимать. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru