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,
50 class SimpleVector
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
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)
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;
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
110  ~SimpleVector() {
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  //! return the i-th position of the vector
154  reference operator [] (size_type i) noexcept {
155  return *(begin() + i);
156  }
157  //! return constant reference to the i-th position of the vector
158  const_reference operator [] (size_type i) const noexcept {
159  return *(begin() + i);
160  }
161 
162  //! resize the array to contain exactly new_size items
163  void resize(size_type new_size) {
164  if (array_) {
165  value_type* tmp = array_;
166  array_ = create_array(new_size);
167  std::move(tmp, tmp + std::min(size_, new_size), array_);
168  destroy_array(tmp, size_);
169  size_ = new_size;
170  }
171  else {
172  array_ = create_array(new_size);
173  size_ = new_size;
174  }
175  }
176 
177  //! deallocate contained array
178  void destroy() {
180  array_ = nullptr;
181  size_ = 0;
182  }
183 
184  //! Zero the whole array content.
185  void fill(const value_type& v = value_type()) noexcept {
186  std::fill(array_, array_ + size_, v);
187  }
188 
189 private:
190  static ValueType * create_array(size_t size) {
191  switch (Mode)
192  {
194  // with normal object construction
195  return new value_type[size];
198  // operator new allocates bytes
199  return static_cast<ValueType*>(
200  operator new (size * sizeof(ValueType)));
201  }
202  abort();
203  }
204 
205  static void destroy_array(ValueType* array, size_t size) {
206  switch (Mode)
207  {
209  // with normal object destruction
210  delete[] array;
211  return;
213  // destroy objects and deallocate memory
214  for (size_t i = 0; i < size; ++i)
215  array[i].~ValueType();
216  operator delete (array);
217  return;
219  // only deallocate memory
220  operator delete (array);
221  return;
222  }
223  abort();
224  }
225 };
226 
227 //! make template alias due to similarity with std::vector
228 template <typename T>
229 using simple_vector = SimpleVector<T>;
230 
231 //! \}
232 
233 } // namespace tlx
234 
235 #endif // !TLX_CONTAINER_SIMPLE_VECTOR_HEADER
236 
237 /******************************************************************************/
tlx::digest_detail::min
static uint32_t min(uint32_t x, uint32_t y)
Definition: md5.cpp:54
tlx::SimpleVector::value_type
ValueType value_type
Definition: simple_vector.hpp:65
tlx::SimpleVector::~SimpleVector
~SimpleVector()
delete vector
Definition: simple_vector.hpp:122
tlx::SimpleVector::size_
size_type size_
size of allocated memory
Definition: simple_vector.hpp:70
tlx::SimpleVector::size
size_type size() const noexcept
return number of items in vector
Definition: simple_vector.hpp:135
tlx::SimpleVector::destroy
void destroy()
deallocate contained array
Definition: simple_vector.hpp:190
tlx::SimpleVector::SimpleVector
SimpleVector()
allocate empty simple vector
Definition: simple_vector.hpp:85
tlx::SimpleVectorMode::NoInitNoDestroy
@ NoInitNoDestroy
Do not initialize objects at allocation and do not destroy them.
tlx::SimpleVector::array_
value_type * array_
pointer to allocated memory area
Definition: simple_vector.hpp:73
tlx::SimpleVector
Simpler non-growing vector without initialization.
Definition: simple_vector.hpp:62
tlx::SimpleVector::operator=
SimpleVector & operator=(const SimpleVector &)=delete
non-copyable: delete assignment operator
tlx::SimpleVector< std::thread >::iterator
value_type * iterator
Definition: simple_vector.hpp:78
tlx::SimpleVector::resize
void resize(size_type new_size)
resize the array to contain exactly new_size items
Definition: simple_vector.hpp:175
tlx::SimpleVectorMode::Normal
@ Normal
Initialize objects at allocation and destroy on deallocation.
tlx::SimpleVector::end
iterator end() noexcept
return mutable iterator beyond last element
Definition: simple_vector.hpp:153
tlx
Definition: exclusive_scan.hpp:17
tlx::SimpleVector::SimpleVector
SimpleVector(const size_type &sz)
allocate vector's memory
Definition: simple_vector.hpp:90
tlx::SimpleVector::size_type
size_t size_type
Definition: simple_vector.hpp:66
tlx::SimpleVector< std::thread >::const_iterator
const value_type * const_iterator
Definition: simple_vector.hpp:79
tlx::SimpleVectorMode::NoInitButDestroy
@ NoInitButDestroy
Do not initialize objects at allocation, but destroy on deallocation.
tlx::SimpleVector::data
iterator data() noexcept
return iterator to beginning of vector
Definition: simple_vector.hpp:127
tlx::SimpleVector::destroy_array
static void destroy_array(ValueType *array, size_t size)
Definition: simple_vector.hpp:217
tlx::SimpleVector::cend
const_iterator cend() const noexcept
return constant iterator beyond last element
Definition: simple_vector.hpp:161
tlx::SimpleVector::fill
void fill(const value_type &v=value_type()) noexcept
Zero the whole array content.
Definition: simple_vector.hpp:197
tlx::swap
void swap(CountingPtr< A, D > &a1, CountingPtr< A, D > &a2) noexcept
swap enclosed object with another counting pointer (no reference counts need change)
Definition: counting_ptr.hpp:328
tlx::SimpleVectorMode
SimpleVectorMode
enum class to select SimpleVector object initialization
Definition: simple_vector.hpp:40
tlx::SimpleVector::cbegin
const_iterator cbegin() const noexcept
return constant iterator to first element
Definition: simple_vector.hpp:148
tlx::SimpleVector::begin
iterator begin() noexcept
return mutable iterator to first element
Definition: simple_vector.hpp:140
tlx::SimpleVector::operator[]
reference operator[](size_type i) noexcept
return the i-th position of the vector
Definition: simple_vector.hpp:166
tlx::SimpleVector< std::thread >::reference
value_type & reference
Definition: simple_vector.hpp:80
tlx::SimpleVector::create_array
static ValueType * create_array(size_t size)
Definition: simple_vector.hpp:202
tlx::SimpleVector::swap
void swap(SimpleVector &obj) noexcept
swap vector with another one
Definition: simple_vector.hpp:116
tlx::SimpleVector< std::thread >::const_reference
const value_type & const_reference
Definition: simple_vector.hpp:81
tlx::simple_vector
SimpleVector< T > simple_vector
make template alias due to similarity with std::vector
Definition: simple_vector.hpp:241