libcxx/include/vector

   1 // -*- C++ -*-
   2 //===----------------------------------------------------------------------===//
   3 //
   4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   5 // See https://llvm.org/LICENSE.txt for license information.
   6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #ifndef _LIBCPP_VECTOR
  11 #define _LIBCPP_VECTOR
  12
  13 // clang-format off
  14
  15 /*
  16     vector synopsis
  17
  18 namespace std
  19 {
  20
  21 template <class T, class Allocator = allocator<T> >
  22 class vector
  23 {
  24 public:
  25     typedef T                                        value_type;
  26     typedef Allocator                                allocator_type;
  27     typedef typename allocator_type::reference       reference;
  28     typedef typename allocator_type::const_reference const_reference;
  29     typedef implementation-defined                   iterator;
  30     typedef implementation-defined                   const_iterator;
  31     typedef typename allocator_type::size_type       size_type;
  32     typedef typename allocator_type::difference_type difference_type;
  33     typedef typename allocator_type::pointer         pointer;
  34     typedef typename allocator_type::const_pointer   const_pointer;
  35     typedef std::reverse_iterator<iterator>          reverse_iterator;
  36     typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
  37
  38     vector()
  39         noexcept(is_nothrow_default_constructible<allocator_type>::value);
  40     explicit vector(const allocator_type&);
  41     explicit vector(size_type n);
  42     explicit vector(size_type n, const allocator_type&); // C++14
  43     vector(size_type n, const value_type& value, const allocator_type& = allocator_type());
  44     template <class InputIterator>
  45         vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type());
  46     template<container-compatible-range<T> R>
  47       constexpr vector(from_range_t, R&& rg, const Allocator& = Allocator()); // C++23
  48     vector(const vector& x);
  49     vector(vector&& x)
  50         noexcept(is_nothrow_move_constructible<allocator_type>::value);
  51     vector(initializer_list<value_type> il);
  52     vector(initializer_list<value_type> il, const allocator_type& a);
  53     ~vector();
  54     vector& operator=(const vector& x);
  55     vector& operator=(vector&& x)
  56         noexcept(
  57              allocator_type::propagate_on_container_move_assignment::value ||
  58              allocator_type::is_always_equal::value); // C++17
  59     vector& operator=(initializer_list<value_type> il);
  60     template <class InputIterator>
  61         void assign(InputIterator first, InputIterator last);
  62     template<container-compatible-range<T> R>
  63       constexpr void assign_range(R&& rg); // C++23
  64     void assign(size_type n, const value_type& u);
  65     void assign(initializer_list<value_type> il);
  66
  67     allocator_type get_allocator() const noexcept;
  68
  69     iterator               begin() noexcept;
  70     const_iterator         begin()   const noexcept;
  71     iterator               end() noexcept;
  72     const_iterator         end()     const noexcept;
  73
  74     reverse_iterator       rbegin() noexcept;
  75     const_reverse_iterator rbegin()  const noexcept;
  76     reverse_iterator       rend() noexcept;
  77     const_reverse_iterator rend()    const noexcept;
  78
  79     const_iterator         cbegin()  const noexcept;
  80     const_iterator         cend()    const noexcept;
  81     const_reverse_iterator crbegin() const noexcept;
  82     const_reverse_iterator crend()   const noexcept;
  83
  84     size_type size() const noexcept;
  85     size_type max_size() const noexcept;
  86     size_type capacity() const noexcept;
  87     bool empty() const noexcept;
  88     void reserve(size_type n);
  89     void shrink_to_fit() noexcept;
  90
  91     reference       operator[](size_type n);
  92     const_reference operator[](size_type n) const;
  93     reference       at(size_type n);
  94     const_reference at(size_type n) const;
  95
  96     reference       front();
  97     const_reference front() const;
  98     reference       back();
  99     const_reference back() const;
 100
 101     value_type*       data() noexcept;
 102     const value_type* data() const noexcept;
 103
 104     void push_back(const value_type& x);
 105     void push_back(value_type&& x);
 106     template <class... Args>
 107         reference emplace_back(Args&&... args); // reference in C++17
 108     template<container-compatible-range<T> R>
 109       constexpr void append_range(R&& rg); // C++23
 110     void pop_back();
 111
 112     template <class... Args> iterator emplace(const_iterator position, Args&&... args);
 113     iterator insert(const_iterator position, const value_type& x);
 114     iterator insert(const_iterator position, value_type&& x);
 115     iterator insert(const_iterator position, size_type n, const value_type& x);
 116     template <class InputIterator>
 117         iterator insert(const_iterator position, InputIterator first, InputIterator last);
 118     template<container-compatible-range<T> R>
 119       constexpr iterator insert_range(const_iterator position, R&& rg); // C++23
 120     iterator insert(const_iterator position, initializer_list<value_type> il);
 121
 122     iterator erase(const_iterator position);
 123     iterator erase(const_iterator first, const_iterator last);
 124
 125     void clear() noexcept;
 126
 127     void resize(size_type sz);
 128     void resize(size_type sz, const value_type& c);
 129
 130     void swap(vector&)
 131         noexcept(allocator_traits<allocator_type>::propagate_on_container_swap::value ||
 132                  allocator_traits<allocator_type>::is_always_equal::value);  // C++17
 133
 134     bool __invariants() const;
 135 };
 136
 137 template <class Allocator = allocator<T> >
 138 class vector<bool, Allocator>
 139 {
 140 public:
 141     typedef bool                                     value_type;
 142     typedef Allocator                                allocator_type;
 143     typedef implementation-defined                   iterator;
 144     typedef implementation-defined                   const_iterator;
 145     typedef typename allocator_type::size_type       size_type;
 146     typedef typename allocator_type::difference_type difference_type;
 147     typedef iterator                                 pointer;
 148     typedef const_iterator                           const_pointer;
 149     typedef std::reverse_iterator<iterator>          reverse_iterator;
 150     typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
 151
 152     class reference
 153     {
 154     public:
 155         reference(const reference&) noexcept;
 156         operator bool() const noexcept;
 157         reference& operator=(bool x) noexcept;
 158         reference& operator=(const reference& x) noexcept;
 159         iterator operator&() const noexcept;
 160         void flip() noexcept;
 161     };
 162
 163     class const_reference
 164     {
 165     public:
 166         const_reference(const reference&) noexcept;
 167         operator bool() const noexcept;
 168         const_iterator operator&() const noexcept;
 169     };
 170
 171     vector()
 172         noexcept(is_nothrow_default_constructible<allocator_type>::value);
 173     explicit vector(const allocator_type&) noexcept;
 174     explicit vector(size_type n, const allocator_type& a = allocator_type()); // C++14
 175     vector(size_type n, const value_type& value, const allocator_type& = allocator_type());
 176     template <class InputIterator>
 177         vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type());
 178     template<container-compatible-range<bool> R>
 179       constexpr vector(from_range_t, R&& rg, const Allocator& = Allocator());
 180     vector(const vector& x);
 181     vector(vector&& x) noexcept;
 182     vector(initializer_list<value_type> il);
 183     vector(initializer_list<value_type> il, const allocator_type& a);
 184     ~vector();
 185     vector& operator=(const vector& x);
 186     vector& operator=(vector&& x)
 187         noexcept(
 188              allocator_type::propagate_on_container_move_assignment::value ||
 189              allocator_type::is_always_equal::value); // C++17
 190     vector& operator=(initializer_list<value_type> il);
 191     template <class InputIterator>
 192         void assign(InputIterator first, InputIterator last);
 193     template<container-compatible-range<T> R>
 194       constexpr void assign_range(R&& rg); // C++23
 195     void assign(size_type n, const value_type& u);
 196     void assign(initializer_list<value_type> il);
 197
 198     allocator_type get_allocator() const noexcept;
 199
 200     iterator               begin() noexcept;
 201     const_iterator         begin()   const noexcept;
 202     iterator               end() noexcept;
 203     const_iterator         end()     const noexcept;
 204
 205     reverse_iterator       rbegin() noexcept;
 206     const_reverse_iterator rbegin()  const noexcept;
 207     reverse_iterator       rend() noexcept;
 208     const_reverse_iterator rend()    const noexcept;
 209
 210     const_iterator         cbegin()  const noexcept;
 211     const_iterator         cend()    const noexcept;
 212     const_reverse_iterator crbegin() const noexcept;
 213     const_reverse_iterator crend()   const noexcept;
 214
 215     size_type size() const noexcept;
 216     size_type max_size() const noexcept;
 217     size_type capacity() const noexcept;
 218     bool empty() const noexcept;
 219     void reserve(size_type n);
 220     void shrink_to_fit() noexcept;
 221
 222     reference       operator[](size_type n);
 223     const_reference operator[](size_type n) const;
 224     reference       at(size_type n);
 225     const_reference at(size_type n) const;
 226
 227     reference       front();
 228     const_reference front() const;
 229     reference       back();
 230     const_reference back() const;
 231
 232     void push_back(const value_type& x);
 233     template <class... Args> reference emplace_back(Args&&... args);  // C++14; reference in C++17
 234     template<container-compatible-range<T> R>
 235       constexpr void append_range(R&& rg); // C++23
 236     void pop_back();
 237
 238     template <class... Args> iterator emplace(const_iterator position, Args&&... args);  // C++14
 239     iterator insert(const_iterator position, const value_type& x);
 240     iterator insert(const_iterator position, size_type n, const value_type& x);
 241     template <class InputIterator>
 242         iterator insert(const_iterator position, InputIterator first, InputIterator last);
 243     template<container-compatible-range<T> R>
 244       constexpr iterator insert_range(const_iterator position, R&& rg); // C++23
 245     iterator insert(const_iterator position, initializer_list<value_type> il);
 246
 247     iterator erase(const_iterator position);
 248     iterator erase(const_iterator first, const_iterator last);
 249
 250     void clear() noexcept;
 251
 252     void resize(size_type sz);
 253     void resize(size_type sz, value_type x);
 254
 255     void swap(vector&)
 256         noexcept(allocator_traits<allocator_type>::propagate_on_container_swap::value ||
 257                  allocator_traits<allocator_type>::is_always_equal::value);  // C++17
 258     void flip() noexcept;
 259
 260     bool __invariants() const;
 261 };
 262
 263 template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
 264    vector(InputIterator, InputIterator, Allocator = Allocator())
 265    -> vector<typename iterator_traits<InputIterator>::value_type, Allocator>; // C++17
 266
 267 template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>>
 268   vector(from_range_t, R&&, Allocator = Allocator())
 269     -> vector<ranges::range_value_t<R>, Allocator>; // C++23
 270
 271 template <class Allocator> struct hash<std::vector<bool, Allocator>>;
 272
 273 template <class T, class Allocator> bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y);   // constexpr since C++20
 274 template <class T, class Allocator> bool operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);   // removed in C++20
 275 template <class T, class Allocator> bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y);   // removed in C++20
 276 template <class T, class Allocator> bool operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y);   // removed in C++20
 277 template <class T, class Allocator> bool operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);   // removed in C++20
 278 template <class T, class Allocator> bool operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);   // removed in C++20
 279 template <class T, class Allocator> constexpr
 280   constexpr synth-three-way-result<T> operator<=>(const vector<T, Allocator>& x,
 281                                                   const vector<T, Allocator>& y);                                  // since C++20
 282
 283 template <class T, class Allocator>
 284 void swap(vector<T,Allocator>& x, vector<T,Allocator>& y)
 285     noexcept(noexcept(x.swap(y)));
 286
 287 template <class T, class Allocator, class U>
 288 typename vector<T, Allocator>::size_type
 289 erase(vector<T, Allocator>& c, const U& value);       // since C++20
 290 template <class T, class Allocator, class Predicate>
 291 typename vector<T, Allocator>::size_type
 292 erase_if(vector<T, Allocator>& c, Predicate pred);    // since C++20
 293
 294
 295 template<class T>
 296  inline constexpr bool is-vector-bool-reference = see below;        // exposition only, since C++23
 297
 298 template<class T, class charT> requires is-vector-bool-reference<T> // Since C++23
 299  struct formatter<T, charT>;
 300
 301 }  // std
 302
 303 */
 304
 305 // clang-format on
 306
 307 #include <__config>
 308
 309 #include <__vector/comparison.h>
 310 #include <__vector/swap.h>
 311 #include <__vector/vector.h>
 312 #include <__vector/vector_bool.h>
 313
 314 #if _LIBCPP_STD_VER >= 17
 315 #  include <__vector/pmr.h>
 316 #endif
 317
 318 #if _LIBCPP_STD_VER >= 20
 319 #  include <__vector/erase.h>
 320 #endif
 321
 322 #if _LIBCPP_STD_VER >= 23
 323 #  include <__vector/vector_bool_formatter.h>
 324 #endif
 325
 326 #include <version>
 327
 328 // standard-mandated includes
 329
 330 // [iterator.range]
 331 #include <__iterator/access.h>
 332 #include <__iterator/data.h>
 333 #include <__iterator/empty.h>
 334 #include <__iterator/reverse_access.h>
 335 #include <__iterator/size.h>
 336
 337 // [vector.syn]
 338 #include <compare>
 339 #include <initializer_list>
 340
 341 // [vector.syn], [unord.hash]
 342 #include <__functional/hash.h>
 343
 344 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 345 #  pragma GCC system_header
 346 #endif
 347
 348 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
 349 #  include <algorithm>
 350 #  include <array>
 351 #  include <atomic>
 352 #  include <cctype>
 353 #  include <cerrno>
 354 #  include <clocale>
 355 #  include <concepts>
 356 #  include <cstdint>
 357 #  include <cstdlib>
 358 #  include <iosfwd>
 359 #  if _LIBCPP_HAS_LOCALIZATION
 360 #    include <locale>
 361 #  endif
 362 #  include <string>
 363 #  include <string_view>
 364 #  include <tuple>
 365 #  include <type_traits>
 366 #  include <typeinfo>
 367 #  include <utility>
 368 #endif
 369
 370 #endif // _LIBCPP_VECTOR