tlx
simple_vector.hpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * tlx/container/simple_vector.hpp
3  *
4  * Copied and modified from STXXL, see http://stxxl.org
5  *
6  * Part of tlx - http://panthema.net/tlx
7  *
8  * Copyright (C) 2002 Roman Dementiev <dementiev@mpi-sb.mpg.de>
9  * Copyright (C) 2008, 2011 Andreas Beckmann <beckmann@cs.uni-frankfurt.de>
10  * Copyright (C) 2013-2017 Timo Bingmann <tb@panthema.net>
11  *
12  * All rights reserved. Published under the Boost Software License, Version 1.0
13  ******************************************************************************/
14 
15 #ifndef TLX_CONTAINER_SIMPLE_VECTOR_HEADER
16 #define TLX_CONTAINER_SIMPLE_VECTOR_HEADER
17 
18 #include <algorithm>
19 #include <cstdlib>
20 #include <utility>
21 
22 namespace tlx {
23 
24 //! \addtogroup tlx_container
25 //! \{
26 
27 //! enum class to select SimpleVector object initialization
28 enum class SimpleVectorMode {
29  //! Initialize objects at allocation and destroy on deallocation
30  Normal,
31  //! Do not initialize objects at allocation, but destroy on
32  //! deallocation. Thus, all objects must be constructed from outside.
34  //! Do not initialize objects at allocation and do not destroy them.
36 };
37 
38 /*!
39  * Simpler non-growing vector without initialization.
40  *
41  * SimpleVector can be used a replacement for std::vector when only a
42  * non-growing array of simple types is needed. The advantages of SimpleVector
43  * are that it does not initilize memory for POD types (-> faster), while normal
44  * structs are supported as well if default-contractible. The simple pointer
45  * types allow faster compilation and is less error prone to copying and other
46  * problems.
47  */
48 template <typename ValueType,
51 {
52 public:
53  using value_type = ValueType;
54  using size_type = size_t;
55 
56 protected:
57  //! size of allocated memory
59 
60  //! pointer to allocated memory area
61  value_type* array_;
62 
63 public:
64  // *** simple pointer iterators
65 
66  using iterator = value_type *;
67  using const_iterator = const value_type *;
68  using reference = value_type&;
69  using const_reference = const value_type&;
70 
71 public:
72  //! allocate empty simple vector
74  : size_(0), array_(nullptr)
75  { }
76 
77  //! allocate vector's memory
78  explicit SimpleVector(const size_type& sz)
79  : size_(sz), array_(nullptr) {
80  if (size_ > 0)
81  array_ = create_array(size_);
82  }
83 
84  //! non-copyable: delete copy-constructor
85  SimpleVector(const SimpleVector&) = delete;
86  //! non-copyable: delete assignment operator
87  SimpleVector& operator = (const SimpleVector&) = delete;
88 
89  //! move-constructor
90  SimpleVector(SimpleVector&& v) noexcept
91  : size_(v.size_), array_(v.array_)
92  { v.size_ = 0, v.array_ = nullptr; }
93 
94  //! move-assignment
95  SimpleVector& operator = (SimpleVector&& v) noexcept {
96  if (&v == this) return *this;
97  destroy_array(array_, size_);
98  size_ = v.size_, array_ = v.array_;
99  v.size_ = 0, v.array_ = nullptr;
100  return *this;
101  }
102 
103  //! swap vector with another one
104  void swap(SimpleVector& obj) noexcept {
105  std::swap(size_, obj.size_);
106  std::swap(array_, obj.array_);
107  }
108 
109  //! delete vector
111  destroy_array(array_, size_);
112  }
113 
114  //! return iterator to beginning of vector
115  iterator data() noexcept {
116  return array_;
117  }
118  //! return iterator to beginning of vector
119  const_iterator data() const noexcept {
120  return array_;
121  }
122  //! return number of items in vector
123  size_type size() const noexcept {
124  return size_;
125  }
126 
127  //! return mutable iterator to first element
128  iterator begin() noexcept {
129  return array_;
130  }
131  //! return constant iterator to first element
132  const_iterator begin() const noexcept {
133  return array_;
134  }
135  //! return constant iterator to first element
136  const_iterator cbegin() const noexcept {
137  return begin();
138  }
139 
140  //! return mutable iterator beyond last element
141  iterator end() noexcept {
142  return array_ + size_;
143  }
144  //! return constant iterator beyond last element
145  const_iterator end() const noexcept {
146  return array_ + size_;
147  }
148  //! return constant iterator beyond last element
149  const_iterator cend() const noexcept {
150  return end();
151  }
152 
153  //! returns reference to the last element in the container
154  reference front() noexcept {
155  return array_[0];
156  }
157  //! returns reference to the first element in the container
158  const_reference front() const noexcept {
159  return array_[0];
160  }
161  //! returns reference to the first element in the container
162  reference back() noexcept {
163  return array_[size_ - 1];
164  }
165  //! returns reference to the last element in the container
166  const_reference back() const noexcept {
167  return array_[size_ - 1];
168  }
169 
170  //! return the i-th position of the vector
171  reference operator [] (size_type i) noexcept {
172  return *(begin() + i);
173  }
174  //! return constant reference to the i-th position of the vector
175  const_reference operator [] (size_type i) const noexcept {
176  return *(begin() + i);
177  }
178 
179  //! return the i-th position of the vector
180  reference at(size_type i) noexcept {
181  return *(begin() + i);
182  }
183  //! return constant reference to the i-th position of the vector
184  const_reference at(size_type i) const noexcept {
185  return *(begin() + i);
186  }
187 
188  //! resize the array to contain exactly new_size items
189  void resize(size_type new_size) {
190  if (array_) {
191  value_type* tmp = array_;
192  array_ = create_array(new_size);
193  std::move(tmp, tmp + std::min(size_, new_size), array_);
194  destroy_array(tmp, size_);
195  size_ = new_size;
196  }
197  else {
198  array_ = create_array(new_size);
199  size_ = new_size;
200  }
201  }
202 
203  //! deallocate contained array
204  void destroy() {
205  destroy_array(array_, size_);
206  array_ = nullptr;
207  size_ = 0;
208  }
209 
210  //! Zero the whole array content.
211  void fill(const value_type& v = value_type()) noexcept {
212  std::fill(array_, array_ + size_, v);
213  }
214 
215 private:
216  static ValueType * create_array(size_t size) {
217  switch (Mode)
218  {
220  // with normal object construction
221  return new value_type[size];
224  // operator new allocates bytes
225  return static_cast<ValueType*>(
226  operator new (size * sizeof(ValueType)));
227  }
228  abort();
229  }
230 
231  static void destroy_array(ValueType* array, size_t size) {
232  switch (Mode)
233  {
235  // with normal object destruction
236  delete[] array;
237  return;
239  // destroy objects and deallocate memory
240  for (size_t i = 0; i < size; ++i)
241  array[i].~ValueType();
242  operator delete (array);
243  return;
245  // only deallocate memory
246  operator delete (array);
247  return;
248  }
249  abort();
250  }
251 };
252 
253 //! make template alias due to similarity with std::vector
254 template <typename T>
256 
257 //! \}
258 
259 } // namespace tlx
260 
261 #endif // !TLX_CONTAINER_SIMPLE_VECTOR_HEADER
262 
263 /******************************************************************************/
iterator end() noexcept
return mutable iterator beyond last element
Do not initialize objects at allocation and do not destroy them.
const_reference front() const noexcept
returns reference to the first element in the container
Do not initialize objects at allocation, but destroy on deallocation.
void resize(size_type new_size)
resize the array to contain exactly new_size items
SimpleVector(const size_type &sz)
allocate vector&#39;s memory
const_iterator begin() const noexcept
return constant iterator to first element
const_reference back() const noexcept
returns reference to the last element in the container
static void destroy_array(ValueType *array, size_t size)
Simpler non-growing vector without initialization.
reference front() noexcept
returns reference to the last element in the container
reference at(size_type i) noexcept
return the i-th position of the vector
const_iterator cbegin() const noexcept
return constant iterator to first element
Initialize objects at allocation and destroy on deallocation.
iterator data() noexcept
return iterator to beginning of vector
const_iterator cend() const noexcept
return constant iterator beyond last element
void fill(const value_type &v=value_type()) noexcept
Zero the whole array content.
const_iterator data() const noexcept
return iterator to beginning of vector
void swap(SimpleVector &obj) noexcept
swap vector with another one
const value_type & const_reference
static uint32_t min(uint32_t x, uint32_t y)
Definition: md5.cpp:32
iterator begin() noexcept
return mutable iterator to first element
void swap(CountingPtr< A, D > &a1, CountingPtr< A, D > &a2) noexcept
swap enclosed object with another counting pointer (no reference counts need change) ...
reference back() noexcept
returns reference to the first element in the container
static ValueType * create_array(size_t size)
size_type size() const noexcept
return number of items in vector
const_iterator end() const noexcept
return constant iterator beyond last element
SimpleVector(SimpleVector &&v) noexcept
move-constructor
value_type * array_
pointer to allocated memory area
void destroy()
deallocate contained array
~SimpleVector()
delete vector
SimpleVectorMode
enum class to select SimpleVector object initialization
size_type size_
size of allocated memory
const_reference at(size_type i) const noexcept
return constant reference to the i-th position of the vector
SimpleVector()
allocate empty simple vector