third_party/pigweed/repo/pw_containers/public/pw_containers/vector.h

   1 // Copyright 2020 The Pigweed Authors
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
   4 // use this file except in compliance with the License. You may obtain a copy of
   5 // the License at
   6 //
   7 //     https://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
  11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
  12 // License for the specific language governing permissions and limitations under
  13 // the License.
  14 #pragma once
  15
  16 #include <algorithm>
  17 #include <array>
  18 #include <cstddef>
  19 #include <initializer_list>
  20 #include <iterator>
  21 #include <limits>
  22 #include <new>
  23 #include <type_traits>
  24 #include <utility>
  25
  26 #include "pw_polyfill/language_feature_macros.h"
  27
  28 namespace pw {
  29 namespace vector_impl {
  30
  31 template <typename I>
  32 using IsIterator = std::negation<
  33     std::is_same<typename std::iterator_traits<I>::value_type, void>>;
  34
  35 // Used as kMaxSize in the generic-size Vector<T> interface.
  36 PW_INLINE_VARIABLE constexpr size_t kGeneric = size_t(-1);
  37
  38 }  // namespace vector_impl
  39
  40 // The Vector class is similar to std::vector, except it is backed by a
  41 // fixed-size buffer. Vectors must be declared with an explicit maximum size
  42 // (e.g. Vector<int, 10>) but vectors can be used and referred to without the
  43 // max size template parameter (e.g. Vector<int>).
  44 //
  45 // To allow referring to a pw::Vector without an explicit maximum size, all
  46 // Vector classes inherit from Vector<T, vector_impl::kGeneric>, which stores
  47 // the maximum size in a variable. This allows Vectors to be used without having
  48 // to know their maximum size at compile time. It also keeps code size small
  49 // since function implementations are shared for all maximum sizes.
  50 template <typename T, size_t kMaxSize = vector_impl::kGeneric>
  51 class Vector : public Vector<T, vector_impl::kGeneric> {
  52  public:
  53   using typename Vector<T, vector_impl::kGeneric>::value_type;
  54   using typename Vector<T, vector_impl::kGeneric>::size_type;
  55   using typename Vector<T, vector_impl::kGeneric>::difference_type;
  56   using typename Vector<T, vector_impl::kGeneric>::reference;
  57   using typename Vector<T, vector_impl::kGeneric>::const_reference;
  58   using typename Vector<T, vector_impl::kGeneric>::pointer;
  59   using typename Vector<T, vector_impl::kGeneric>::const_pointer;
  60   using typename Vector<T, vector_impl::kGeneric>::iterator;
  61   using typename Vector<T, vector_impl::kGeneric>::const_iterator;
  62   using typename Vector<T, vector_impl::kGeneric>::reverse_iterator;
  63   using typename Vector<T, vector_impl::kGeneric>::const_reverse_iterator;
  64
  65   // Construct
  66   Vector() noexcept : Vector<T, vector_impl::kGeneric>(kMaxSize) {}
  67
  68   Vector(size_type count, const T& value)
  69       : Vector<T, vector_impl::kGeneric>(kMaxSize, count, value) {}
  70
  71   explicit Vector(size_type count)
  72       : Vector<T, vector_impl::kGeneric>(kMaxSize, count, T()) {}
  73
  74   template <
  75       typename Iterator,
  76       typename...,
  77       typename = std::enable_if_t<vector_impl::IsIterator<Iterator>::value>>
  78   Vector(Iterator first, Iterator last)
  79       : Vector<T, vector_impl::kGeneric>(kMaxSize, first, last) {}
  80
  81   Vector(const Vector& other)
  82       : Vector<T, vector_impl::kGeneric>(kMaxSize, other) {}
  83
  84   template <size_t kOtherMaxSize>
  85   Vector(const Vector<T, kOtherMaxSize>& other)
  86       : Vector<T, vector_impl::kGeneric>(kMaxSize, other) {}
  87
  88   Vector(Vector&& other) noexcept
  89       : Vector<T, vector_impl::kGeneric>(kMaxSize, std::move(other)) {}
  90
  91   template <size_t kOtherMaxSize>
  92   Vector(Vector<T, kOtherMaxSize>&& other) noexcept
  93       : Vector<T, vector_impl::kGeneric>(kMaxSize, std::move(other)) {}
  94
  95   Vector(std::initializer_list<T> list)
  96       : Vector<T, vector_impl::kGeneric>(kMaxSize, list) {}
  97
  98   Vector& operator=(const Vector& other) {
  99     Vector<T>::assign(other.begin(), other.end());
 100     return *this;
 101   }
 102
 103   template <size_t kOtherMaxSize>
 104   Vector& operator=(const Vector<T, kOtherMaxSize>& other) noexcept {
 105     Vector<T>::assign(other.begin(), other.end());
 106     return *this;
 107   }
 108
 109   Vector& operator=(Vector&& other) noexcept {
 110     Vector<T>::operator=(std::move(other));
 111     return *this;
 112   }
 113
 114   template <size_t kOtherMaxSize>
 115   Vector& operator=(Vector<T, kOtherMaxSize>&& other) noexcept {
 116     Vector<T>::operator=(std::move(other));
 117     return *this;
 118   }
 119
 120   Vector& operator=(std::initializer_list<T> list) {
 121     this->assign(list.begin(), list.end());
 122     return *this;
 123   }
 124
 125   // All other vector methods are implemented on the Vector<T> base class.
 126
 127  private:
 128   friend class Vector<T, vector_impl::kGeneric>;
 129
 130   static_assert(kMaxSize <= std::numeric_limits<size_type>::max());
 131
 132   // Provides access to the underlying array as an array of T.
 133 #ifdef __cpp_lib_launder
 134   pointer array() { return std::launder(reinterpret_cast<T*>(&array_)); }
 135   const_pointer array() const {
 136     return std::launder(reinterpret_cast<const T*>(&array_));
 137   }
 138 #else
 139   pointer array() { return reinterpret_cast<T*>(&array_); }
 140   const_pointer array() const { return reinterpret_cast<const T*>(&array_); }
 141 #endif  // __cpp_lib_launder
 142
 143   // Vector entries are stored as uninitialized memory blocks aligned correctly
 144   // for the type. Elements are initialized on demand with placement new.
 145   //
 146   // This uses std::array instead of a C array to support zero-length Vectors.
 147   // Zero-length C arrays are non-standard, but std::array<T, 0> is valid.
 148   // The alignas specifier is required ensure that a zero-length array is
 149   // aligned the same as an array with elements.
 150   alignas(T) std::array<std::aligned_storage_t<sizeof(T), alignof(T)>,
 151                         kMaxSize> array_;
 152 };
 153
 154 // Defines the generic-sized Vector<T> specialization, which serves as the base
 155 // class for Vector<T> of any maximum size. Except for constructors, all Vector
 156 // methods are implemented on this class.
 157 template <typename T>
 158 class Vector<T, vector_impl::kGeneric> {
 159  public:
 160   using value_type = T;
 161
 162   // Use unsigned short instead of size_t. Since Vectors are statically
 163   // allocated, 65535 entries is a reasonable upper limit. This reduces Vector's
 164   // overhead by packing the size and capacity into 32 bits.
 165   using size_type = unsigned short;
 166
 167   using difference_type = ptrdiff_t;
 168   using reference = value_type&;
 169   using const_reference = const value_type&;
 170   using pointer = T*;
 171   using const_pointer = const T*;
 172   using iterator = T*;
 173   using const_iterator = const T*;
 174   using reverse_iterator = std::reverse_iterator<iterator>;
 175   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 176
 177   // A vector without an explicit maximum size (Vector<T>) cannot be constructed
 178   // directly. Instead, construct a Vector<T, max_size>. Vectors of any max size
 179   // can be used through a Vector<T> pointer or reference.
 180
 181   ~Vector() { clear(); }
 182
 183   // Assign
 184
 185   Vector& operator=(const Vector& other) {
 186     assign(other.begin(), other.end());
 187     return *this;
 188   }
 189
 190   Vector& operator=(Vector&& other) noexcept {
 191     clear();
 192     MoveFrom(other);
 193     return *this;
 194   }
 195
 196   Vector& operator=(std::initializer_list<T> list) {
 197     assign(list);
 198     return *this;
 199   }
 200
 201   void assign(size_type count, const T& value) {
 202     clear();
 203     Append(count, value);
 204   }
 205
 206   template <
 207       typename Iterator,
 208       typename...,
 209       typename = std::enable_if_t<vector_impl::IsIterator<Iterator>::value>>
 210   void assign(Iterator first, Iterator last) {
 211     clear();
 212     CopyFrom(first, last);
 213   }
 214
 215   void assign(std::initializer_list<T> list) {
 216     assign(list.begin(), list.end());
 217   }
 218
 219   // Access
 220
 221   // TODO(hepler): Add an assert for bounds checking in at.
 222   reference at(size_type index) { return data()[index]; }
 223   const_reference at(size_type index) const { return data()[index]; }
 224
 225   reference operator[](size_type index) { return data()[index]; }
 226   const_reference operator[](size_type index) const { return data()[index]; }
 227
 228   reference front() { return data()[0]; }
 229   const_reference front() const { return data()[0]; }
 230
 231   reference back() { return data()[size() - 1]; }
 232   const_reference back() const { return data()[size() - 1]; }
 233
 234   // The underlying data is not part of the generic-length vector class. It is
 235   // provided in the derived class from which this instance was constructed. To
 236   // access the data, down-cast this to a Vector with a known max size, and
 237   // return a pointer to the start of the array, which is the same for all
 238   // vectors with explicit max size.
 239   T* data() noexcept { return static_cast<Vector<T, 0>*>(this)->array(); }
 240   const T* data() const noexcept {
 241     return static_cast<const Vector<T, 0>*>(this)->array();
 242   }
 243
 244   // Iterate
 245
 246   iterator begin() noexcept { return &data()[0]; }
 247   const_iterator begin() const noexcept { return &data()[0]; }
 248   const_iterator cbegin() const noexcept { return &data()[0]; }
 249
 250   iterator end() noexcept { return &data()[size()]; }
 251   const_iterator end() const noexcept { return &data()[size()]; }
 252   const_iterator cend() const noexcept { return &data()[size()]; }
 253
 254   reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
 255   const_reverse_iterator rbegin() const { return reverse_iterator(end()); }
 256   const_reverse_iterator crbegin() const noexcept {
 257     return reverse_iterator(cend());
 258   }
 259
 260   reverse_iterator rend() noexcept { return reverse_iterator(begin()); }
 261   const_reverse_iterator rend() const { return reverse_iterator(begin()); }
 262   const_reverse_iterator crend() const noexcept {
 263     return reverse_iterator(cbegin());
 264   }
 265
 266   // Size
 267
 268   [[nodiscard]] bool empty() const noexcept { return size() == 0u; }
 269
 270   // True if there is no free space in the vector. Operations that add elements
 271   // (push_back, insert, etc.) will fail if full() is true.
 272   [[nodiscard]] bool full() const noexcept { return size() == max_size(); }
 273
 274   // Returns the number of elements in the Vector. Uses size_t instead of
 275   // size_type for consistency with other containers.
 276   size_t size() const noexcept { return size_; }
 277
 278   // Returns the maximum number of elements in this Vector.
 279   size_t max_size() const noexcept { return max_size_; }
 280
 281   size_t capacity() const noexcept { return max_size(); }
 282
 283   // Modify
 284
 285   void clear() noexcept;
 286
 287   // TODO(hepler): insert, emplace, and erase are not yet implemented.
 288   //    Currently, items can only be added to or removed from the end.
 289   iterator insert(const_iterator index, const T& value);
 290
 291   iterator insert(const_iterator index, T&& value);
 292
 293   iterator insert(const_iterator index, size_type count, const T& value);
 294
 295   template <typename Iterator>
 296   iterator insert(const_iterator index, Iterator first, Iterator last);
 297
 298   iterator insert(const_iterator index, std::initializer_list<T> list);
 299
 300   template <typename... Args>
 301   iterator emplace(const_iterator index, Args&&... args);
 302
 303   iterator erase(const_iterator index);
 304
 305   iterator erase(const_iterator first, const_iterator last);
 306
 307   void push_back(const T& value) { emplace_back(value); }
 308
 309   void push_back(T&& value) { emplace_back(std::move(value)); }
 310
 311   template <typename... Args>
 312   void emplace_back(Args&&... args);
 313
 314   void pop_back();
 315
 316   void resize(size_type new_size) { resize(new_size, T()); }
 317
 318   void resize(size_type new_size, const T& value);
 319
 320  protected:
 321   // Vectors without an explicit size cannot be constructed directly. Instead,
 322   // the maximum size must be provided.
 323   explicit Vector(size_type max_size) noexcept : max_size_(max_size) {}
 324
 325   Vector(size_type max_size, size_type count, const T& value)
 326       : Vector(max_size) {
 327     Append(count, value);
 328   }
 329
 330   Vector(size_type max_size, size_type count) : Vector(max_size, count, T()) {}
 331
 332   template <
 333       typename Iterator,
 334       typename...,
 335       typename = std::enable_if_t<vector_impl::IsIterator<Iterator>::value>>
 336   Vector(size_type max_size, Iterator first, Iterator last) : Vector(max_size) {
 337     CopyFrom(first, last);
 338   }
 339
 340   Vector(size_type max_size, const Vector& other) : Vector(max_size) {
 341     CopyFrom(other.begin(), other.end());
 342   }
 343
 344   Vector(size_type max_size, Vector&& other) noexcept : Vector(max_size) {
 345     MoveFrom(other);
 346   }
 347
 348   Vector(size_type max_size, std::initializer_list<T> list) : Vector(max_size) {
 349     CopyFrom(list.begin(), list.end());
 350   }
 351
 352  private:
 353   template <typename Iterator>
 354   void CopyFrom(Iterator first, Iterator last);
 355
 356   void MoveFrom(Vector& other) noexcept;
 357
 358   void Append(size_type count, const T& value);
 359
 360   const size_type max_size_;
 361   size_type size_ = 0;
 362 };
 363
 364 // Compare
 365
 366 template <typename T, size_t kLhsSize, size_t kRhsSize>
 367 bool operator==(const Vector<T, kLhsSize>& lhs,
 368                 const Vector<T, kRhsSize>& rhs) {
 369   return std::equal(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
 370 }
 371
 372 template <typename T, size_t kLhsSize, size_t kRhsSize>
 373 bool operator!=(const Vector<T, kLhsSize>& lhs,
 374                 const Vector<T, kRhsSize>& rhs) {
 375   return !(lhs == rhs);
 376 }
 377
 378 template <typename T, size_t kLhsSize, size_t kRhsSize>
 379 bool operator<(const Vector<T, kLhsSize>& lhs, const Vector<T, kRhsSize>& rhs) {
 380   return std::lexicographical_compare(
 381       lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
 382 }
 383
 384 template <typename T, size_t kLhsSize, size_t kRhsSize>
 385 bool operator<=(const Vector<T, kLhsSize>& lhs,
 386                 const Vector<T, kRhsSize>& rhs) {
 387   return !(rhs < lhs);
 388 }
 389
 390 template <typename T, size_t kLhsSize, size_t kRhsSize>
 391 bool operator>(const Vector<T, kLhsSize>& lhs, const Vector<T, kRhsSize>& rhs) {
 392   return rhs < lhs;
 393 }
 394
 395 template <typename T, size_t kLhsSize, size_t kRhsSize>
 396 bool operator>=(const Vector<T, kLhsSize>& lhs,
 397                 const Vector<T, kRhsSize>& rhs) {
 398   return !(lhs < rhs);
 399 }
 400
 401 // Function implementations
 402
 403 template <typename T>
 404 void Vector<T, vector_impl::kGeneric>::clear() noexcept {
 405   for (auto& item : *this) {
 406     item.~T();
 407   }
 408   size_ = 0;
 409 }
 410
 411 template <typename T>
 412 template <typename... Args>
 413 void Vector<T, vector_impl::kGeneric>::emplace_back(Args&&... args) {
 414   if (!full()) {
 415     new (&data()[size_]) T(std::forward<Args>(args)...);
 416     size_ += 1;
 417   }
 418 }
 419
 420 template <typename T>
 421 void Vector<T, vector_impl::kGeneric>::pop_back() {
 422   if (!empty()) {
 423     back().~T();
 424     size_ -= 1;
 425   }
 426 }
 427
 428 template <typename T>
 429 void Vector<T, vector_impl::kGeneric>::resize(size_type new_size,
 430                                               const T& value) {
 431   if (size() < new_size) {
 432     Append(std::min(max_size(), size_t(new_size)) - size(), value);
 433   } else {
 434     while (size() > new_size) {
 435       pop_back();
 436     }
 437   }
 438 }
 439
 440 template <typename T>
 441 template <typename Iterator>
 442 void Vector<T, vector_impl::kGeneric>::CopyFrom(Iterator first, Iterator last) {
 443   while (first != last) {
 444     push_back(*first++);
 445   }
 446 }
 447
 448 template <typename T>
 449 void Vector<T, vector_impl::kGeneric>::MoveFrom(Vector& other) noexcept {
 450   for (auto&& item : other) {
 451     emplace_back(std::move(item));
 452   }
 453   other.clear();
 454 }
 455
 456 template <typename T>
 457 void Vector<T, vector_impl::kGeneric>::Append(size_type count, const T& value) {
 458   for (size_t i = 0; i < count; ++i) {
 459     push_back(value);
 460   }
 461 }
 462
 463 }  // namespace pw