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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.88
GetHelp
-7 / 61 / 6
Регистрация: 27.02.2013
Сообщений: 1,112
#1

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

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

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

ошибка в шаблонах функций - C++
Есть у меня программа из нескольких файлов . с шаблонами для функций ... компилятор выдает следующий ошибку -&gt; &quot;/main.cpp:17: undefined...

Дружественные функции в шаблонах - C++
Как использовать дружественные функции в шаблонах? ( C++ Builder)

Typename в шаблонах класса - C++
В таком шаблоне: template &lt;typename T, int n, bool islong=???&gt; class CounterA{... требуется распознать тип, то есть переменная islong...

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

Доступ к элементам tuple в шаблонах - C++
Собственно, не могу понять как работать с элементами кортежа в цикле, не получается получить к ним доступ. Подскажите, кто знает, как это...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
0x10
2460 / 1632 / 238
Регистрация: 24.11.2012
Сообщений: 4,015
17.07.2014, 19:51 #76
Цитата Сообщение от GetHelp Посмотреть сообщение
никак не пойму как его правильно заюзать, не подскажете?
Если не хватает знаний по основам - не вижу смысла. Тем более, выше я говорил, что можно без исключений.

Нормальным вариантом кажется посмотреть на реализацию в стандартной библиотеке и сделать по образу и подобию. Для этого не обязательно лезть глубоко, достатоно посмотреть интерфейсы стандартных контейнеров.
GetHelp
-7 / 61 / 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
2460 / 1632 / 238
Регистрация: 24.11.2012
Сообщений: 4,015
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
-7 / 61 / 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");
}
0x10
2460 / 1632 / 238
Регистрация: 24.11.2012
Сообщений: 4,015
17.07.2014, 20:21 #80
Теперь value в Pop не используется и 100% ведет к утечкам.
GetHelp
-7 / 61 / 6
Регистрация: 27.02.2013
Сообщений: 1,112
17.07.2014, 20:25  [ТС] #81
Цитата Сообщение от 0x10 Посмотреть сообщение
Теперь value в Pop не используется и 100% ведет к утечкам.
тьфу забыл
C++
1
2
3
4
5
6
7
8
template <typename T>
void Stack<T>::Pop()
{
    if (!head) throw std::out_of_range("Access to element of empty container");
    NODE *tmp = head;
    head = head->prev;
    delete tmp;
}

Не по теме:

а нехило мы развернулись на 9 страниц



Добавлено через 2 минуты
з.ы. вроде теперь все ок уже? итоговая оценка =)
Jupiter
Каратель
Эксперт С++
6553 / 3973 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
17.07.2014, 20:57 #82
Цитата Сообщение от GetHelp Посмотреть сообщение
C++
1
2
template <typename T>
void Stack<T>::Push(T value)
а push все так же принимает value по значениею

Цитата Сообщение от GetHelp Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
template <typename T>
T Stack<T>::Peek()
{
    if (head)
        return head->data;
    else
        throw std::out_of_range("Access to element of empty container");
}
код в стиле кодогенератора...какой может быть else после return
GetHelp
-7 / 61 / 6
Регистрация: 27.02.2013
Сообщений: 1,112
17.07.2014, 21:12  [ТС] #83
Цитата Сообщение от Jupiter Посмотреть сообщение
а push все так же принимает value по значениею
эмм а с этим то какие проблемы? как вы еще собираетесь добавлять элемент в стек как не через параметр функции?
Цитата Сообщение от Jupiter Посмотреть сообщение
код в стиле кодогенератора...какой может быть else после return
а какие с этим проблемы? по мне так все нормально...
0x10
2460 / 1632 / 238
Регистрация: 24.11.2012
Сообщений: 4,015
17.07.2014, 21:16 #84
Цитата Сообщение от GetHelp Посмотреть сообщение
эмм а с этим то какие проблемы? как вы еще собираетесь добавлять элемент в стек как не через параметр функции?
Передать по константной ссылке. Сейчас при добавлении объекта в стек происходит два копиросания. Первое - при передаче параметра, второе - парой строк ниже, при присваивании.

Цитата Сообщение от GetHelp Посмотреть сообщение
а какие с этим проблемы? по мне так все нормально...
Проблема стилистическая, противоречит логичности кода. После return последующие инструкции не будут выполняться, следовательно, else и дополнительный уровень вложенности - избыточность.

Ну и я не перевариваю объект head, у которого есть поле prev. Либо это хвост, у которого есть предыдущий элемент, либо это голова, у которой есть следующий.
uglyPinokkio
326 / 229 / 41
Регистрация: 30.05.2014
Сообщений: 682
17.07.2014, 21:16 #85
Цитата Сообщение от GetHelp Посмотреть сообщение
как вы еще собираетесь добавлять элемент в стек как не через параметр функции?
Через параметр, только передаваемый по константной ссылке.

Цитата Сообщение от GetHelp Посмотреть сообщение
а какие с этим проблемы? по мне так все нормально...
Что изменится, если else убрать?
Jupiter
Каратель
Эксперт С++
6553 / 3973 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
17.07.2014, 21:18 #86
Цитата Сообщение от GetHelp Посмотреть сообщение
эмм а с этим то какие проблемы? как вы еще собираетесь добавлять элемент в стек как не через параметр функции?
через параметр, но по ссылке на константу
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private:
    struct NODE
    {
        NODE(const T& data, NODE* prev)
        : data(data), prev(prev)
        {}
 
        T data;
        NODE *prev;
    } *head;
//...
template <typename T>
void Stack<T>::Push(const T& value)
{
    head  = new NODE(value, head);
}
Добавлено через 1 минуту
Цитата Сообщение от GetHelp Посмотреть сообщение
а какие с этим проблемы? по мне так все нормально...
а по мне те кто так пишут(я про else) просто боты
0x10
17.07.2014, 21:35
  #87

Не по теме:

Цитата Сообщение от Jupiter Посмотреть сообщение
а по мне те кто так пишут(я про else) просто боты
Туда же, видел как-то:
C++
1
2
3
4
5
6
switch (...) {
// ...
default:
  return foo;
  break;
}

GetHelp
-7 / 61 / 6
Регистрация: 27.02.2013
Сообщений: 1,112
17.07.2014, 22:24  [ТС] #88
Цитата Сообщение от 0x10 Посмотреть сообщение
Передать по константной ссылке. Сейчас при добавлении объекта в стек происходит два копиросания. Первое - при передаче параметра, второе - парой строк ниже, при присваивании.
че за ссылка? не понимаю к чему усложнять... вы еще скажите что вообще передавать параметры в функциях это плохо и надо писать функции без параметров
Цитата Сообщение от 0x10 Посмотреть сообщение
Проблема стилистическая, противоречит логичности кода. После return последующие инструкции не будут выполняться, следовательно, else и дополнительный уровень вложенности - избыточность.
бред какой то вы пишите, все нормально будет выполняться... потому что просто напросто в случае когда !head код просто не пойдет по ветке с return....

Добавлено через 2 минуты
Цитата Сообщение от 0x10 Посмотреть сообщение
Ну и я не перевариваю объект head, у которого есть поле prev. Либо это хвост, у которого есть предыдущий элемент, либо это голова, у которой есть следующий.
брал за образец такой список http://learnc.info/adt/linked_list.html, там было это объявлено как next, но по сути это является не следующим, а именно предыдущим значением... меня лично это сбивало с толку
Jupiter
Каратель
Эксперт С++
6553 / 3973 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
17.07.2014, 22:26 #89
Цитата Сообщение от GetHelp Посмотреть сообщение
че за ссылка? не понимаю к чему усложнять..
или учи матчасть или иди
Vourhey
Почетный модератор
6478 / 2253 / 123
Регистрация: 29.07.2006
Сообщений: 12,635
17.07.2014, 22:26 #90
Цитата Сообщение от GetHelp Посмотреть сообщение
че за ссылка? не понимаю к чему усложнять...
Это не усложнение, а нужна оптимизация. В противном случае, при большом кол-ве данных твоя программа будет работать медленнее, чем программа с передачей параметров через ссылки.
Цитата Сообщение от GetHelp Посмотреть сообщение
вы еще скажите что вообще передавать параметры в функциях это плохо и надо писать функции без параметров
Без причины передавать, например, структуру с набором данных не по ссылке - да, плохо.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.07.2014, 22:26
Привет! Вот еще темы с ответами:

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

Тип, зависимый от условия в шаблонах - C++
Возможно ли реализовать подобное: template &lt;uint8_t bits&gt; class test { // если bits &lt;= 8 typedef uint8_t storageType; //...

Используя стек, описать функцию проверяющую, является ли стек пустым - C++
Используя стек, описать функцию проверяющую, является ли стек пустым

Программа добавляет введенный массив 5*5 в стек и выводит полученный стек двумя столбцами - C++
Программа добавляет введенный массив 5*5 в стек и выводит полученный стек двумя столбцами #include &lt;iostream&gt; #include &lt;stdlib.h&gt; ...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
17.07.2014, 22:26
Закрытая тема Создать тему
Опции темы

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