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
|
#ifndef KSTD_STACK_HPP
#define KSTD_STACK_HPP
#include "kstd/vector"
#include <initializer_list>
#include <utility>
namespace kstd
{
/**
* @brief Custom stack implementation mirroring the std::stack to allow for the usage of STL functionality with our
* custom memory management.
*
* @tparam T Element the stack instance should contain.
* @tparam Container Actual underlying container that should be wrapped to provide stack functionality. Requires
* access to pop_back(), push_back(), back(), size(), empty() and emplace_back()
*/
template<typename T, typename Container = kstd::vector<T>>
struct stack
{
using container_type = Container; ///< Type of the underlying container used to implement stack-like interface.
using value_type = Container::value_type; ///< Type of the elements contained in the underlying container.
using size_type = Container::size_type; ///< Type of the size in the underlying container.
using reference = Container::reference; ///< Type of reference to the elements.
using const_reference = Container::const_reference; ///< Type of constant reference to the elements.
/**
* @brief Default Constructor.
*/
stack() = default;
stack(stack const &) = delete;
stack(stack &&) = delete;
auto operator=(stack const &) -> stack & = delete;
auto operator=(stack &&) -> stack & = delete;
/**
* @brief Constructs data with the given amount of elements containing the given value or alternatively the default
* constructed value.
*
* @param n Amount of elements we want to create and set the given value for.
* @param initial Inital value of all elements in the underlying data array.
*/
explicit stack(size_type n, value_type initial = value_type{})
: _container(n, initial)
{
// Nothing to do.
}
/**
* @brief Constructs data by copying all element from the given exclusive range.
*
* @tparam InputIterator Template that should have atleast input iterator characteristics.
* @param first Input iterator to the first element in the range we want to copy from.
* @param last Input iterator to one past the last element in the range we want to copy from.
*/
template<typename InputIterator>
explicit stack(InputIterator first, InputIterator last)
: _container(first, last)
{
// Nothing to do.
}
/**
* @brief Construct data by copying all elements from the initializer list.
*
* @param elements List we want to copy all elements from.
*/
explicit stack(std::initializer_list<T> elements)
: _container(elements)
{
// Nothing to do.
}
/**
* @brief Copy constructor.
*
* @note Allocates underlying data container with the same capacity as stack we are copying from and copies all
* elements from it.
*
* @param other Other instance of stack we want to copy the data from.
*/
stack(stack<T> const & other)
: _container(other)
{
// Nothing to do.
}
/**
* @brief Destructor.
*/
~stack() = default;
/**
* @brief Amount of elements currently contained in this vector, will fill up until we have reached the capacity. If
* that is the case the capacity is increased automatically.
*
* @return Current amount of elements.
*/
auto size() const -> size_type
{
return _container.size();
}
/**
* @brief Returns a reference to the last element in the container. Calling back on an empty container causes
* undefined behavior.
*
* @return Reference to the last element.
*/
auto top() -> reference
{
return _container.back();
}
/**
* @brief Returns a reference to the last element in the container. Calling back on an empty container causes
* undefined behavior.
*
* @return Reference to the last element.
*/
auto top() const -> const_reference
{
return _container.back();
}
/**
* @brief Appends the given element value to the end of the container. The element is assigned through the
* assignment operator of the template type. The value is forwarded to the constructor as
* std::forward<U>(value), meaning it is either moved (rvalue) or copied (lvalue).
*
* @note If after the operation the new size() is greater than old capacity() a reallocation takes place,
* in which case all iterators (including the end() iterator) and all references to the elements are invalidated.
* Otherwise only the end() iterator is invalidated. Uses a forward reference for the actual value passed, which
* allows the template method to be used by both lvalue and rvalues and compile a different implementation.
*
* @param value The value of the element to append.
*/
template<class U>
auto push(U && value) -> void
{
_container.push_back(std::forward<U>(value));
}
/**
* @brief Appends a new element to the end of the container. The element is constructed through a constructor of the
* template type. The arguments args... are forwarded to the constructor as std::forward<Args>(args)....
*
* If after the operation the new size() is greater than old capacity() a reallocation takes place, in which case
* all iterators (including the end() iterator) and all references to the elements are invalidated. Otherwise only
* the end() iterator is invalidated. Uses a forward reference for the actual value passed, which
* allows the template method to be used by both lvalue and rvalues and compile a different implementation.
*
* @tparam Args
* @param args Arguments to forward to the constructor of the element
* @return value_type&
*/
template<class... Args>
auto emplace(Args &&... args) -> reference
{
_container.emplace_back(std::forward<Args>(args)...);
}
/**
* @brief Removes the last element of the container.
*
* @note Calling pop_back on an empty container results in halting the
* further execution. Iterators and references to the last element are invalidated. The end()
* iterator is also invalidated.
*/
auto pop() -> void
{
_container.pop_back();
}
/**
* @brief Whether there are currently any items this container or not.
*
* @return True if there are no elements, false if there are.
*/
auto empty() const -> bool
{
return _container.empty();
}
private:
container_type _container = {}; ///< Underlying container used by the stack to actually save the data.
};
} // namespace kstd
#endif
|
