inlined_vector.h 34 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914
  1. // Copyright 2019 The Abseil Authors.
  2. //
  3. // Licensed under the Apache License, Version 2.0 (the "License");
  4. // you may not use this file except in compliance with the License.
  5. // You may obtain a copy of 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,
  11. // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12. // See the License for the specific language governing permissions and
  13. // limitations under the License.
  14. //
  15. // -----------------------------------------------------------------------------
  16. // File: inlined_vector.h
  17. // -----------------------------------------------------------------------------
  18. //
  19. // This header file contains the declaration and definition of an "inlined
  20. // vector" which behaves in an equivalent fashion to a `std::vector`, except
  21. // that storage for small sequences of the vector are provided inline without
  22. // requiring any heap allocation.
  23. //
  24. // An `absl::InlinedVector<T, N>` specifies the default capacity `N` as one of
  25. // its template parameters. Instances where `size() <= N` hold contained
  26. // elements in inline space. Typically `N` is very small so that sequences that
  27. // are expected to be short do not require allocations.
  28. //
  29. // An `absl::InlinedVector` does not usually require a specific allocator. If
  30. // the inlined vector grows beyond its initial constraints, it will need to
  31. // allocate (as any normal `std::vector` would). This is usually performed with
  32. // the default allocator (defined as `std::allocator<T>`). Optionally, a custom
  33. // allocator type may be specified as `A` in `absl::InlinedVector<T, N, A>`.
  34. #ifndef ABSL_CONTAINER_INLINED_VECTOR_H_
  35. #define ABSL_CONTAINER_INLINED_VECTOR_H_
  36. #include <algorithm>
  37. #include <cstddef>
  38. #include <cstdlib>
  39. #include <cstring>
  40. #include <initializer_list>
  41. #include <iterator>
  42. #include <memory>
  43. #include <type_traits>
  44. #include <utility>
  45. #include "absl/algorithm/algorithm.h"
  46. #include "absl/base/internal/throw_delegate.h"
  47. #include "absl/base/macros.h"
  48. #include "absl/base/optimization.h"
  49. #include "absl/base/port.h"
  50. #include "absl/container/internal/inlined_vector.h"
  51. #include "absl/memory/memory.h"
  52. #include "absl/meta/type_traits.h"
  53. namespace absl {
  54. ABSL_NAMESPACE_BEGIN
  55. // -----------------------------------------------------------------------------
  56. // InlinedVector
  57. // -----------------------------------------------------------------------------
  58. //
  59. // An `absl::InlinedVector` is designed to be a drop-in replacement for
  60. // `std::vector` for use cases where the vector's size is sufficiently small
  61. // that it can be inlined. If the inlined vector does grow beyond its estimated
  62. // capacity, it will trigger an initial allocation on the heap, and will behave
  63. // as a `std::vector`. The API of the `absl::InlinedVector` within this file is
  64. // designed to cover the same API footprint as covered by `std::vector`.
  65. template <typename T, size_t N, typename A = std::allocator<T>>
  66. class InlinedVector {
  67. static_assert(N > 0, "`absl::InlinedVector` requires an inlined capacity.");
  68. using Storage = inlined_vector_internal::Storage<T, N, A>;
  69. template <typename TheA>
  70. using AllocatorTraits = inlined_vector_internal::AllocatorTraits<TheA>;
  71. template <typename TheA>
  72. using MoveIterator = inlined_vector_internal::MoveIterator<TheA>;
  73. template <typename TheA>
  74. using IsMemcpyOk = inlined_vector_internal::IsMemcpyOk<TheA>;
  75. template <typename TheA>
  76. using IsMoveAssignOk = inlined_vector_internal::IsMoveAssignOk<TheA>;
  77. template <typename TheA, typename Iterator>
  78. using IteratorValueAdapter =
  79. inlined_vector_internal::IteratorValueAdapter<TheA, Iterator>;
  80. template <typename TheA>
  81. using CopyValueAdapter = inlined_vector_internal::CopyValueAdapter<TheA>;
  82. template <typename TheA>
  83. using DefaultValueAdapter =
  84. inlined_vector_internal::DefaultValueAdapter<TheA>;
  85. template <typename Iterator>
  86. using EnableIfAtLeastForwardIterator = absl::enable_if_t<
  87. inlined_vector_internal::IsAtLeastForwardIterator<Iterator>::value, int>;
  88. template <typename Iterator>
  89. using DisableIfAtLeastForwardIterator = absl::enable_if_t<
  90. !inlined_vector_internal::IsAtLeastForwardIterator<Iterator>::value, int>;
  91. using MemcpyPolicy = typename Storage::MemcpyPolicy;
  92. using ElementwiseAssignPolicy = typename Storage::ElementwiseAssignPolicy;
  93. using ElementwiseConstructPolicy =
  94. typename Storage::ElementwiseConstructPolicy;
  95. using MoveAssignmentPolicy = typename Storage::MoveAssignmentPolicy;
  96. public:
  97. using allocator_type = A;
  98. using value_type = inlined_vector_internal::ValueType<A>;
  99. using pointer = inlined_vector_internal::Pointer<A>;
  100. using const_pointer = inlined_vector_internal::ConstPointer<A>;
  101. using size_type = inlined_vector_internal::SizeType<A>;
  102. using difference_type = inlined_vector_internal::DifferenceType<A>;
  103. using reference = inlined_vector_internal::Reference<A>;
  104. using const_reference = inlined_vector_internal::ConstReference<A>;
  105. using iterator = inlined_vector_internal::Iterator<A>;
  106. using const_iterator = inlined_vector_internal::ConstIterator<A>;
  107. using reverse_iterator = inlined_vector_internal::ReverseIterator<A>;
  108. using const_reverse_iterator =
  109. inlined_vector_internal::ConstReverseIterator<A>;
  110. // ---------------------------------------------------------------------------
  111. // InlinedVector Constructors and Destructor
  112. // ---------------------------------------------------------------------------
  113. // Creates an empty inlined vector with a value-initialized allocator.
  114. InlinedVector() noexcept(noexcept(allocator_type())) : storage_() {}
  115. // Creates an empty inlined vector with a copy of `allocator`.
  116. explicit InlinedVector(const allocator_type& allocator) noexcept
  117. : storage_(allocator) {}
  118. // Creates an inlined vector with `n` copies of `value_type()`.
  119. explicit InlinedVector(size_type n,
  120. const allocator_type& allocator = allocator_type())
  121. : storage_(allocator) {
  122. storage_.Initialize(DefaultValueAdapter<A>(), n);
  123. }
  124. // Creates an inlined vector with `n` copies of `v`.
  125. InlinedVector(size_type n, const_reference v,
  126. const allocator_type& allocator = allocator_type())
  127. : storage_(allocator) {
  128. storage_.Initialize(CopyValueAdapter<A>(std::addressof(v)), n);
  129. }
  130. // Creates an inlined vector with copies of the elements of `list`.
  131. InlinedVector(std::initializer_list<value_type> list,
  132. const allocator_type& allocator = allocator_type())
  133. : InlinedVector(list.begin(), list.end(), allocator) {}
  134. // Creates an inlined vector with elements constructed from the provided
  135. // forward iterator range [`first`, `last`).
  136. //
  137. // NOTE: the `enable_if` prevents ambiguous interpretation between a call to
  138. // this constructor with two integral arguments and a call to the above
  139. // `InlinedVector(size_type, const_reference)` constructor.
  140. template <typename ForwardIterator,
  141. EnableIfAtLeastForwardIterator<ForwardIterator> = 0>
  142. InlinedVector(ForwardIterator first, ForwardIterator last,
  143. const allocator_type& allocator = allocator_type())
  144. : storage_(allocator) {
  145. storage_.Initialize(IteratorValueAdapter<A, ForwardIterator>(first),
  146. static_cast<size_t>(std::distance(first, last)));
  147. }
  148. // Creates an inlined vector with elements constructed from the provided input
  149. // iterator range [`first`, `last`).
  150. template <typename InputIterator,
  151. DisableIfAtLeastForwardIterator<InputIterator> = 0>
  152. InlinedVector(InputIterator first, InputIterator last,
  153. const allocator_type& allocator = allocator_type())
  154. : storage_(allocator) {
  155. std::copy(first, last, std::back_inserter(*this));
  156. }
  157. // Creates an inlined vector by copying the contents of `other` using
  158. // `other`'s allocator.
  159. InlinedVector(const InlinedVector& other)
  160. : InlinedVector(other, other.storage_.GetAllocator()) {}
  161. // Creates an inlined vector by copying the contents of `other` using the
  162. // provided `allocator`.
  163. InlinedVector(const InlinedVector& other, const allocator_type& allocator)
  164. : storage_(allocator) {
  165. if (other.empty()) {
  166. // Empty; nothing to do.
  167. } else if (IsMemcpyOk<A>::value && !other.storage_.GetIsAllocated()) {
  168. // Memcpy-able and do not need allocation.
  169. storage_.MemcpyFrom(other.storage_);
  170. } else {
  171. storage_.InitFrom(other.storage_);
  172. }
  173. }
  174. // Creates an inlined vector by moving in the contents of `other` without
  175. // allocating. If `other` contains allocated memory, the newly-created inlined
  176. // vector will take ownership of that memory. However, if `other` does not
  177. // contain allocated memory, the newly-created inlined vector will perform
  178. // element-wise move construction of the contents of `other`.
  179. //
  180. // NOTE: since no allocation is performed for the inlined vector in either
  181. // case, the `noexcept(...)` specification depends on whether moving the
  182. // underlying objects can throw. It is assumed assumed that...
  183. // a) move constructors should only throw due to allocation failure.
  184. // b) if `value_type`'s move constructor allocates, it uses the same
  185. // allocation function as the inlined vector's allocator.
  186. // Thus, the move constructor is non-throwing if the allocator is non-throwing
  187. // or `value_type`'s move constructor is specified as `noexcept`.
  188. InlinedVector(InlinedVector&& other) noexcept(
  189. absl::allocator_is_nothrow<allocator_type>::value ||
  190. std::is_nothrow_move_constructible<value_type>::value)
  191. : storage_(other.storage_.GetAllocator()) {
  192. if (IsMemcpyOk<A>::value) {
  193. storage_.MemcpyFrom(other.storage_);
  194. other.storage_.SetInlinedSize(0);
  195. } else if (other.storage_.GetIsAllocated()) {
  196. storage_.SetAllocation({other.storage_.GetAllocatedData(),
  197. other.storage_.GetAllocatedCapacity()});
  198. storage_.SetAllocatedSize(other.storage_.GetSize());
  199. other.storage_.SetInlinedSize(0);
  200. } else {
  201. IteratorValueAdapter<A, MoveIterator<A>> other_values(
  202. MoveIterator<A>(other.storage_.GetInlinedData()));
  203. inlined_vector_internal::ConstructElements<A>(
  204. storage_.GetAllocator(), storage_.GetInlinedData(), other_values,
  205. other.storage_.GetSize());
  206. storage_.SetInlinedSize(other.storage_.GetSize());
  207. }
  208. }
  209. // Creates an inlined vector by moving in the contents of `other` with a copy
  210. // of `allocator`.
  211. //
  212. // NOTE: if `other`'s allocator is not equal to `allocator`, even if `other`
  213. // contains allocated memory, this move constructor will still allocate. Since
  214. // allocation is performed, this constructor can only be `noexcept` if the
  215. // specified allocator is also `noexcept`.
  216. InlinedVector(
  217. InlinedVector&& other,
  218. const allocator_type&
  219. allocator) noexcept(absl::allocator_is_nothrow<allocator_type>::value)
  220. : storage_(allocator) {
  221. if (IsMemcpyOk<A>::value) {
  222. storage_.MemcpyFrom(other.storage_);
  223. other.storage_.SetInlinedSize(0);
  224. } else if ((storage_.GetAllocator() == other.storage_.GetAllocator()) &&
  225. other.storage_.GetIsAllocated()) {
  226. storage_.SetAllocation({other.storage_.GetAllocatedData(),
  227. other.storage_.GetAllocatedCapacity()});
  228. storage_.SetAllocatedSize(other.storage_.GetSize());
  229. other.storage_.SetInlinedSize(0);
  230. } else {
  231. storage_.Initialize(IteratorValueAdapter<A, MoveIterator<A>>(
  232. MoveIterator<A>(other.data())),
  233. other.size());
  234. }
  235. }
  236. ~InlinedVector() {}
  237. // ---------------------------------------------------------------------------
  238. // InlinedVector Member Accessors
  239. // ---------------------------------------------------------------------------
  240. // `InlinedVector::empty()`
  241. //
  242. // Returns whether the inlined vector contains no elements.
  243. bool empty() const noexcept { return !size(); }
  244. // `InlinedVector::size()`
  245. //
  246. // Returns the number of elements in the inlined vector.
  247. size_type size() const noexcept { return storage_.GetSize(); }
  248. // `InlinedVector::max_size()`
  249. //
  250. // Returns the maximum number of elements the inlined vector can hold.
  251. size_type max_size() const noexcept {
  252. // One bit of the size storage is used to indicate whether the inlined
  253. // vector contains allocated memory. As a result, the maximum size that the
  254. // inlined vector can express is the minimum of the limit of how many
  255. // objects we can allocate and std::numeric_limits<size_type>::max() / 2.
  256. return (std::min)(AllocatorTraits<A>::max_size(storage_.GetAllocator()),
  257. (std::numeric_limits<size_type>::max)() / 2);
  258. }
  259. // `InlinedVector::capacity()`
  260. //
  261. // Returns the number of elements that could be stored in the inlined vector
  262. // without requiring a reallocation.
  263. //
  264. // NOTE: for most inlined vectors, `capacity()` should be equal to the
  265. // template parameter `N`. For inlined vectors which exceed this capacity,
  266. // they will no longer be inlined and `capacity()` will equal the capactity of
  267. // the allocated memory.
  268. size_type capacity() const noexcept {
  269. return storage_.GetIsAllocated() ? storage_.GetAllocatedCapacity()
  270. : storage_.GetInlinedCapacity();
  271. }
  272. // `InlinedVector::data()`
  273. //
  274. // Returns a `pointer` to the elements of the inlined vector. This pointer
  275. // can be used to access and modify the contained elements.
  276. //
  277. // NOTE: only elements within [`data()`, `data() + size()`) are valid.
  278. pointer data() noexcept {
  279. return storage_.GetIsAllocated() ? storage_.GetAllocatedData()
  280. : storage_.GetInlinedData();
  281. }
  282. // Overload of `InlinedVector::data()` that returns a `const_pointer` to the
  283. // elements of the inlined vector. This pointer can be used to access but not
  284. // modify the contained elements.
  285. //
  286. // NOTE: only elements within [`data()`, `data() + size()`) are valid.
  287. const_pointer data() const noexcept {
  288. return storage_.GetIsAllocated() ? storage_.GetAllocatedData()
  289. : storage_.GetInlinedData();
  290. }
  291. // `InlinedVector::operator[](...)`
  292. //
  293. // Returns a `reference` to the `i`th element of the inlined vector.
  294. reference operator[](size_type i) {
  295. ABSL_HARDENING_ASSERT(i < size());
  296. return data()[i];
  297. }
  298. // Overload of `InlinedVector::operator[](...)` that returns a
  299. // `const_reference` to the `i`th element of the inlined vector.
  300. const_reference operator[](size_type i) const {
  301. ABSL_HARDENING_ASSERT(i < size());
  302. return data()[i];
  303. }
  304. // `InlinedVector::at(...)`
  305. //
  306. // Returns a `reference` to the `i`th element of the inlined vector.
  307. //
  308. // NOTE: if `i` is not within the required range of `InlinedVector::at(...)`,
  309. // in both debug and non-debug builds, `std::out_of_range` will be thrown.
  310. reference at(size_type i) {
  311. if (ABSL_PREDICT_FALSE(i >= size())) {
  312. base_internal::ThrowStdOutOfRange(
  313. "`InlinedVector::at(size_type)` failed bounds check");
  314. }
  315. return data()[i];
  316. }
  317. // Overload of `InlinedVector::at(...)` that returns a `const_reference` to
  318. // the `i`th element of the inlined vector.
  319. //
  320. // NOTE: if `i` is not within the required range of `InlinedVector::at(...)`,
  321. // in both debug and non-debug builds, `std::out_of_range` will be thrown.
  322. const_reference at(size_type i) const {
  323. if (ABSL_PREDICT_FALSE(i >= size())) {
  324. base_internal::ThrowStdOutOfRange(
  325. "`InlinedVector::at(size_type) const` failed bounds check");
  326. }
  327. return data()[i];
  328. }
  329. // `InlinedVector::front()`
  330. //
  331. // Returns a `reference` to the first element of the inlined vector.
  332. reference front() {
  333. ABSL_HARDENING_ASSERT(!empty());
  334. return data()[0];
  335. }
  336. // Overload of `InlinedVector::front()` that returns a `const_reference` to
  337. // the first element of the inlined vector.
  338. const_reference front() const {
  339. ABSL_HARDENING_ASSERT(!empty());
  340. return data()[0];
  341. }
  342. // `InlinedVector::back()`
  343. //
  344. // Returns a `reference` to the last element of the inlined vector.
  345. reference back() {
  346. ABSL_HARDENING_ASSERT(!empty());
  347. return data()[size() - 1];
  348. }
  349. // Overload of `InlinedVector::back()` that returns a `const_reference` to the
  350. // last element of the inlined vector.
  351. const_reference back() const {
  352. ABSL_HARDENING_ASSERT(!empty());
  353. return data()[size() - 1];
  354. }
  355. // `InlinedVector::begin()`
  356. //
  357. // Returns an `iterator` to the beginning of the inlined vector.
  358. iterator begin() noexcept { return data(); }
  359. // Overload of `InlinedVector::begin()` that returns a `const_iterator` to
  360. // the beginning of the inlined vector.
  361. const_iterator begin() const noexcept { return data(); }
  362. // `InlinedVector::end()`
  363. //
  364. // Returns an `iterator` to the end of the inlined vector.
  365. iterator end() noexcept { return data() + size(); }
  366. // Overload of `InlinedVector::end()` that returns a `const_iterator` to the
  367. // end of the inlined vector.
  368. const_iterator end() const noexcept { return data() + size(); }
  369. // `InlinedVector::cbegin()`
  370. //
  371. // Returns a `const_iterator` to the beginning of the inlined vector.
  372. const_iterator cbegin() const noexcept { return begin(); }
  373. // `InlinedVector::cend()`
  374. //
  375. // Returns a `const_iterator` to the end of the inlined vector.
  376. const_iterator cend() const noexcept { return end(); }
  377. // `InlinedVector::rbegin()`
  378. //
  379. // Returns a `reverse_iterator` from the end of the inlined vector.
  380. reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
  381. // Overload of `InlinedVector::rbegin()` that returns a
  382. // `const_reverse_iterator` from the end of the inlined vector.
  383. const_reverse_iterator rbegin() const noexcept {
  384. return const_reverse_iterator(end());
  385. }
  386. // `InlinedVector::rend()`
  387. //
  388. // Returns a `reverse_iterator` from the beginning of the inlined vector.
  389. reverse_iterator rend() noexcept { return reverse_iterator(begin()); }
  390. // Overload of `InlinedVector::rend()` that returns a `const_reverse_iterator`
  391. // from the beginning of the inlined vector.
  392. const_reverse_iterator rend() const noexcept {
  393. return const_reverse_iterator(begin());
  394. }
  395. // `InlinedVector::crbegin()`
  396. //
  397. // Returns a `const_reverse_iterator` from the end of the inlined vector.
  398. const_reverse_iterator crbegin() const noexcept { return rbegin(); }
  399. // `InlinedVector::crend()`
  400. //
  401. // Returns a `const_reverse_iterator` from the beginning of the inlined
  402. // vector.
  403. const_reverse_iterator crend() const noexcept { return rend(); }
  404. // `InlinedVector::get_allocator()`
  405. //
  406. // Returns a copy of the inlined vector's allocator.
  407. allocator_type get_allocator() const { return storage_.GetAllocator(); }
  408. // ---------------------------------------------------------------------------
  409. // InlinedVector Member Mutators
  410. // ---------------------------------------------------------------------------
  411. // `InlinedVector::operator=(...)`
  412. //
  413. // Replaces the elements of the inlined vector with copies of the elements of
  414. // `list`.
  415. InlinedVector& operator=(std::initializer_list<value_type> list) {
  416. assign(list.begin(), list.end());
  417. return *this;
  418. }
  419. // Overload of `InlinedVector::operator=(...)` that replaces the elements of
  420. // the inlined vector with copies of the elements of `other`.
  421. InlinedVector& operator=(const InlinedVector& other) {
  422. if (ABSL_PREDICT_TRUE(this != std::addressof(other))) {
  423. const_pointer other_data = other.data();
  424. assign(other_data, other_data + other.size());
  425. }
  426. return *this;
  427. }
  428. // Overload of `InlinedVector::operator=(...)` that moves the elements of
  429. // `other` into the inlined vector.
  430. //
  431. // NOTE: as a result of calling this overload, `other` is left in a valid but
  432. // unspecified state.
  433. InlinedVector& operator=(InlinedVector&& other) {
  434. if (ABSL_PREDICT_TRUE(this != std::addressof(other))) {
  435. MoveAssignment(MoveAssignmentPolicy{}, std::move(other));
  436. }
  437. return *this;
  438. }
  439. // `InlinedVector::assign(...)`
  440. //
  441. // Replaces the contents of the inlined vector with `n` copies of `v`.
  442. void assign(size_type n, const_reference v) {
  443. storage_.Assign(CopyValueAdapter<A>(std::addressof(v)), n);
  444. }
  445. // Overload of `InlinedVector::assign(...)` that replaces the contents of the
  446. // inlined vector with copies of the elements of `list`.
  447. void assign(std::initializer_list<value_type> list) {
  448. assign(list.begin(), list.end());
  449. }
  450. // Overload of `InlinedVector::assign(...)` to replace the contents of the
  451. // inlined vector with the range [`first`, `last`).
  452. //
  453. // NOTE: this overload is for iterators that are "forward" category or better.
  454. template <typename ForwardIterator,
  455. EnableIfAtLeastForwardIterator<ForwardIterator> = 0>
  456. void assign(ForwardIterator first, ForwardIterator last) {
  457. storage_.Assign(IteratorValueAdapter<A, ForwardIterator>(first),
  458. static_cast<size_t>(std::distance(first, last)));
  459. }
  460. // Overload of `InlinedVector::assign(...)` to replace the contents of the
  461. // inlined vector with the range [`first`, `last`).
  462. //
  463. // NOTE: this overload is for iterators that are "input" category.
  464. template <typename InputIterator,
  465. DisableIfAtLeastForwardIterator<InputIterator> = 0>
  466. void assign(InputIterator first, InputIterator last) {
  467. size_type i = 0;
  468. for (; i < size() && first != last; ++i, static_cast<void>(++first)) {
  469. data()[i] = *first;
  470. }
  471. erase(data() + i, data() + size());
  472. std::copy(first, last, std::back_inserter(*this));
  473. }
  474. // `InlinedVector::resize(...)`
  475. //
  476. // Resizes the inlined vector to contain `n` elements.
  477. //
  478. // NOTE: If `n` is smaller than `size()`, extra elements are destroyed. If `n`
  479. // is larger than `size()`, new elements are value-initialized.
  480. void resize(size_type n) {
  481. ABSL_HARDENING_ASSERT(n <= max_size());
  482. storage_.Resize(DefaultValueAdapter<A>(), n);
  483. }
  484. // Overload of `InlinedVector::resize(...)` that resizes the inlined vector to
  485. // contain `n` elements.
  486. //
  487. // NOTE: if `n` is smaller than `size()`, extra elements are destroyed. If `n`
  488. // is larger than `size()`, new elements are copied-constructed from `v`.
  489. void resize(size_type n, const_reference v) {
  490. ABSL_HARDENING_ASSERT(n <= max_size());
  491. storage_.Resize(CopyValueAdapter<A>(std::addressof(v)), n);
  492. }
  493. // `InlinedVector::insert(...)`
  494. //
  495. // Inserts a copy of `v` at `pos`, returning an `iterator` to the newly
  496. // inserted element.
  497. iterator insert(const_iterator pos, const_reference v) {
  498. return emplace(pos, v);
  499. }
  500. // Overload of `InlinedVector::insert(...)` that inserts `v` at `pos` using
  501. // move semantics, returning an `iterator` to the newly inserted element.
  502. iterator insert(const_iterator pos, value_type&& v) {
  503. return emplace(pos, std::move(v));
  504. }
  505. // Overload of `InlinedVector::insert(...)` that inserts `n` contiguous copies
  506. // of `v` starting at `pos`, returning an `iterator` pointing to the first of
  507. // the newly inserted elements.
  508. iterator insert(const_iterator pos, size_type n, const_reference v) {
  509. ABSL_HARDENING_ASSERT(pos >= begin());
  510. ABSL_HARDENING_ASSERT(pos <= end());
  511. if (ABSL_PREDICT_TRUE(n != 0)) {
  512. value_type dealias = v;
  513. // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102329#c2
  514. // It appears that GCC thinks that since `pos` is a const pointer and may
  515. // point to uninitialized memory at this point, a warning should be
  516. // issued. But `pos` is actually only used to compute an array index to
  517. // write to.
  518. #if !defined(__clang__) && defined(__GNUC__)
  519. #pragma GCC diagnostic push
  520. #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
  521. #endif
  522. return storage_.Insert(pos, CopyValueAdapter<A>(std::addressof(dealias)),
  523. n);
  524. #if !defined(__clang__) && defined(__GNUC__)
  525. #pragma GCC diagnostic pop
  526. #endif
  527. } else {
  528. return const_cast<iterator>(pos);
  529. }
  530. }
  531. // Overload of `InlinedVector::insert(...)` that inserts copies of the
  532. // elements of `list` starting at `pos`, returning an `iterator` pointing to
  533. // the first of the newly inserted elements.
  534. iterator insert(const_iterator pos, std::initializer_list<value_type> list) {
  535. return insert(pos, list.begin(), list.end());
  536. }
  537. // Overload of `InlinedVector::insert(...)` that inserts the range [`first`,
  538. // `last`) starting at `pos`, returning an `iterator` pointing to the first
  539. // of the newly inserted elements.
  540. //
  541. // NOTE: this overload is for iterators that are "forward" category or better.
  542. template <typename ForwardIterator,
  543. EnableIfAtLeastForwardIterator<ForwardIterator> = 0>
  544. iterator insert(const_iterator pos, ForwardIterator first,
  545. ForwardIterator last) {
  546. ABSL_HARDENING_ASSERT(pos >= begin());
  547. ABSL_HARDENING_ASSERT(pos <= end());
  548. if (ABSL_PREDICT_TRUE(first != last)) {
  549. return storage_.Insert(
  550. pos, IteratorValueAdapter<A, ForwardIterator>(first),
  551. static_cast<size_type>(std::distance(first, last)));
  552. } else {
  553. return const_cast<iterator>(pos);
  554. }
  555. }
  556. // Overload of `InlinedVector::insert(...)` that inserts the range [`first`,
  557. // `last`) starting at `pos`, returning an `iterator` pointing to the first
  558. // of the newly inserted elements.
  559. //
  560. // NOTE: this overload is for iterators that are "input" category.
  561. template <typename InputIterator,
  562. DisableIfAtLeastForwardIterator<InputIterator> = 0>
  563. iterator insert(const_iterator pos, InputIterator first, InputIterator last) {
  564. ABSL_HARDENING_ASSERT(pos >= begin());
  565. ABSL_HARDENING_ASSERT(pos <= end());
  566. size_type index = static_cast<size_type>(std::distance(cbegin(), pos));
  567. for (size_type i = index; first != last; ++i, static_cast<void>(++first)) {
  568. insert(data() + i, *first);
  569. }
  570. return iterator(data() + index);
  571. }
  572. // `InlinedVector::emplace(...)`
  573. //
  574. // Constructs and inserts an element using `args...` in the inlined vector at
  575. // `pos`, returning an `iterator` pointing to the newly emplaced element.
  576. template <typename... Args>
  577. iterator emplace(const_iterator pos, Args&&... args) {
  578. ABSL_HARDENING_ASSERT(pos >= begin());
  579. ABSL_HARDENING_ASSERT(pos <= end());
  580. value_type dealias(std::forward<Args>(args)...);
  581. // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102329#c2
  582. // It appears that GCC thinks that since `pos` is a const pointer and may
  583. // point to uninitialized memory at this point, a warning should be
  584. // issued. But `pos` is actually only used to compute an array index to
  585. // write to.
  586. #if !defined(__clang__) && defined(__GNUC__)
  587. #pragma GCC diagnostic push
  588. #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
  589. #endif
  590. return storage_.Insert(pos,
  591. IteratorValueAdapter<A, MoveIterator<A>>(
  592. MoveIterator<A>(std::addressof(dealias))),
  593. 1);
  594. #if !defined(__clang__) && defined(__GNUC__)
  595. #pragma GCC diagnostic pop
  596. #endif
  597. }
  598. // `InlinedVector::emplace_back(...)`
  599. //
  600. // Constructs and inserts an element using `args...` in the inlined vector at
  601. // `end()`, returning a `reference` to the newly emplaced element.
  602. template <typename... Args>
  603. reference emplace_back(Args&&... args) {
  604. return storage_.EmplaceBack(std::forward<Args>(args)...);
  605. }
  606. // `InlinedVector::push_back(...)`
  607. //
  608. // Inserts a copy of `v` in the inlined vector at `end()`.
  609. void push_back(const_reference v) { static_cast<void>(emplace_back(v)); }
  610. // Overload of `InlinedVector::push_back(...)` for inserting `v` at `end()`
  611. // using move semantics.
  612. void push_back(value_type&& v) {
  613. static_cast<void>(emplace_back(std::move(v)));
  614. }
  615. // `InlinedVector::pop_back()`
  616. //
  617. // Destroys the element at `back()`, reducing the size by `1`.
  618. void pop_back() noexcept {
  619. ABSL_HARDENING_ASSERT(!empty());
  620. AllocatorTraits<A>::destroy(storage_.GetAllocator(), data() + (size() - 1));
  621. storage_.SubtractSize(1);
  622. }
  623. // `InlinedVector::erase(...)`
  624. //
  625. // Erases the element at `pos`, returning an `iterator` pointing to where the
  626. // erased element was located.
  627. //
  628. // NOTE: may return `end()`, which is not dereferencable.
  629. iterator erase(const_iterator pos) {
  630. ABSL_HARDENING_ASSERT(pos >= begin());
  631. ABSL_HARDENING_ASSERT(pos < end());
  632. return storage_.Erase(pos, pos + 1);
  633. }
  634. // Overload of `InlinedVector::erase(...)` that erases every element in the
  635. // range [`from`, `to`), returning an `iterator` pointing to where the first
  636. // erased element was located.
  637. //
  638. // NOTE: may return `end()`, which is not dereferencable.
  639. iterator erase(const_iterator from, const_iterator to) {
  640. ABSL_HARDENING_ASSERT(from >= begin());
  641. ABSL_HARDENING_ASSERT(from <= to);
  642. ABSL_HARDENING_ASSERT(to <= end());
  643. if (ABSL_PREDICT_TRUE(from != to)) {
  644. return storage_.Erase(from, to);
  645. } else {
  646. return const_cast<iterator>(from);
  647. }
  648. }
  649. // `InlinedVector::clear()`
  650. //
  651. // Destroys all elements in the inlined vector, setting the size to `0` and
  652. // deallocating any held memory.
  653. void clear() noexcept {
  654. inlined_vector_internal::DestroyAdapter<A>::DestroyElements(
  655. storage_.GetAllocator(), data(), size());
  656. storage_.DeallocateIfAllocated();
  657. storage_.SetInlinedSize(0);
  658. }
  659. // `InlinedVector::reserve(...)`
  660. //
  661. // Ensures that there is enough room for at least `n` elements.
  662. void reserve(size_type n) { storage_.Reserve(n); }
  663. // `InlinedVector::shrink_to_fit()`
  664. //
  665. // Attempts to reduce memory usage by moving elements to (or keeping elements
  666. // in) the smallest available buffer sufficient for containing `size()`
  667. // elements.
  668. //
  669. // If `size()` is sufficiently small, the elements will be moved into (or kept
  670. // in) the inlined space.
  671. void shrink_to_fit() {
  672. if (storage_.GetIsAllocated()) {
  673. storage_.ShrinkToFit();
  674. }
  675. }
  676. // `InlinedVector::swap(...)`
  677. //
  678. // Swaps the contents of the inlined vector with `other`.
  679. void swap(InlinedVector& other) {
  680. if (ABSL_PREDICT_TRUE(this != std::addressof(other))) {
  681. storage_.Swap(std::addressof(other.storage_));
  682. }
  683. }
  684. private:
  685. template <typename H, typename TheT, size_t TheN, typename TheA>
  686. friend H AbslHashValue(H h, const absl::InlinedVector<TheT, TheN, TheA>& a);
  687. void MoveAssignment(MemcpyPolicy, InlinedVector&& other) {
  688. inlined_vector_internal::DestroyAdapter<A>::DestroyElements(
  689. storage_.GetAllocator(), data(), size());
  690. storage_.DeallocateIfAllocated();
  691. storage_.MemcpyFrom(other.storage_);
  692. other.storage_.SetInlinedSize(0);
  693. }
  694. void MoveAssignment(ElementwiseAssignPolicy, InlinedVector&& other) {
  695. if (other.storage_.GetIsAllocated()) {
  696. MoveAssignment(MemcpyPolicy{}, std::move(other));
  697. } else {
  698. storage_.Assign(IteratorValueAdapter<A, MoveIterator<A>>(
  699. MoveIterator<A>(other.storage_.GetInlinedData())),
  700. other.size());
  701. }
  702. }
  703. void MoveAssignment(ElementwiseConstructPolicy, InlinedVector&& other) {
  704. if (other.storage_.GetIsAllocated()) {
  705. MoveAssignment(MemcpyPolicy{}, std::move(other));
  706. } else {
  707. inlined_vector_internal::DestroyAdapter<A>::DestroyElements(
  708. storage_.GetAllocator(), data(), size());
  709. storage_.DeallocateIfAllocated();
  710. IteratorValueAdapter<A, MoveIterator<A>> other_values(
  711. MoveIterator<A>(other.storage_.GetInlinedData()));
  712. inlined_vector_internal::ConstructElements<A>(
  713. storage_.GetAllocator(), storage_.GetInlinedData(), other_values,
  714. other.storage_.GetSize());
  715. storage_.SetInlinedSize(other.storage_.GetSize());
  716. }
  717. }
  718. Storage storage_;
  719. };
  720. // -----------------------------------------------------------------------------
  721. // InlinedVector Non-Member Functions
  722. // -----------------------------------------------------------------------------
  723. // `swap(...)`
  724. //
  725. // Swaps the contents of two inlined vectors.
  726. template <typename T, size_t N, typename A>
  727. void swap(absl::InlinedVector<T, N, A>& a,
  728. absl::InlinedVector<T, N, A>& b) noexcept(noexcept(a.swap(b))) {
  729. a.swap(b);
  730. }
  731. // `operator==(...)`
  732. //
  733. // Tests for value-equality of two inlined vectors.
  734. template <typename T, size_t N, typename A>
  735. bool operator==(const absl::InlinedVector<T, N, A>& a,
  736. const absl::InlinedVector<T, N, A>& b) {
  737. auto a_data = a.data();
  738. auto b_data = b.data();
  739. return absl::equal(a_data, a_data + a.size(), b_data, b_data + b.size());
  740. }
  741. // `operator!=(...)`
  742. //
  743. // Tests for value-inequality of two inlined vectors.
  744. template <typename T, size_t N, typename A>
  745. bool operator!=(const absl::InlinedVector<T, N, A>& a,
  746. const absl::InlinedVector<T, N, A>& b) {
  747. return !(a == b);
  748. }
  749. // `operator<(...)`
  750. //
  751. // Tests whether the value of an inlined vector is less than the value of
  752. // another inlined vector using a lexicographical comparison algorithm.
  753. template <typename T, size_t N, typename A>
  754. bool operator<(const absl::InlinedVector<T, N, A>& a,
  755. const absl::InlinedVector<T, N, A>& b) {
  756. auto a_data = a.data();
  757. auto b_data = b.data();
  758. return std::lexicographical_compare(a_data, a_data + a.size(), b_data,
  759. b_data + b.size());
  760. }
  761. // `operator>(...)`
  762. //
  763. // Tests whether the value of an inlined vector is greater than the value of
  764. // another inlined vector using a lexicographical comparison algorithm.
  765. template <typename T, size_t N, typename A>
  766. bool operator>(const absl::InlinedVector<T, N, A>& a,
  767. const absl::InlinedVector<T, N, A>& b) {
  768. return b < a;
  769. }
  770. // `operator<=(...)`
  771. //
  772. // Tests whether the value of an inlined vector is less than or equal to the
  773. // value of another inlined vector using a lexicographical comparison algorithm.
  774. template <typename T, size_t N, typename A>
  775. bool operator<=(const absl::InlinedVector<T, N, A>& a,
  776. const absl::InlinedVector<T, N, A>& b) {
  777. return !(b < a);
  778. }
  779. // `operator>=(...)`
  780. //
  781. // Tests whether the value of an inlined vector is greater than or equal to the
  782. // value of another inlined vector using a lexicographical comparison algorithm.
  783. template <typename T, size_t N, typename A>
  784. bool operator>=(const absl::InlinedVector<T, N, A>& a,
  785. const absl::InlinedVector<T, N, A>& b) {
  786. return !(a < b);
  787. }
  788. // `AbslHashValue(...)`
  789. //
  790. // Provides `absl::Hash` support for `absl::InlinedVector`. It is uncommon to
  791. // call this directly.
  792. template <typename H, typename T, size_t N, typename A>
  793. H AbslHashValue(H h, const absl::InlinedVector<T, N, A>& a) {
  794. auto size = a.size();
  795. return H::combine(H::combine_contiguous(std::move(h), a.data(), size), size);
  796. }
  797. ABSL_NAMESPACE_END
  798. } // namespace absl
  799. #endif // ABSL_CONTAINER_INLINED_VECTOR_H_