diff options
Diffstat (limited to 'absl/container')
| -rw-r--r-- | absl/container/flat_hash_set.h | 6 | ||||
| -rw-r--r-- | absl/container/inlined_vector.h | 391 | ||||
| -rw-r--r-- | absl/container/internal/inlined_vector.h | 61 |
3 files changed, 223 insertions, 235 deletions
diff --git a/absl/container/flat_hash_set.h b/absl/container/flat_hash_set.h index 6bf51833fca6..2a51c3411d66 100644 --- a/absl/container/flat_hash_set.h +++ b/absl/container/flat_hash_set.h @@ -55,9 +55,9 @@ struct FlatHashSetPolicy; // following notable differences: // // * Requires keys that are CopyConstructible -// * Supports heterogeneous lookup, through `find()`, `operator[]()` and -// `insert()`, provided that the set is provided a compatible heterogeneous -// hashing function and equality operator. +// * Supports heterogeneous lookup, through `find()` and `insert()`, provided +// that the set is provided a compatible heterogeneous hashing function and +// equality operator. // * Invalidates any references and pointers to elements within the table after // `rehash()`. // * Contains a `capacity()` member function indicating the number of element diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h index 2381e65f51e9..25af1658914c 100644 --- a/absl/container/inlined_vector.h +++ b/absl/container/inlined_vector.h @@ -66,8 +66,7 @@ namespace absl { // designed to cover the same API footprint as covered by `std::vector`. template <typename T, size_t N, typename A = std::allocator<T>> class InlinedVector { - static_assert( - N > 0, "InlinedVector cannot be instantiated with `0` inlined elements."); + static_assert(N > 0, "`absl::InlinedVector` requires an inlined capacity."); using Storage = inlined_vector_internal::Storage<T, N, A>; using rvalue_reference = typename Storage::rvalue_reference; @@ -84,7 +83,6 @@ class InlinedVector { template <typename Iterator> using EnableIfAtLeastForwardIterator = absl::enable_if_t< inlined_vector_internal::IsAtLeastForwardIterator<Iterator>::value>; - template <typename Iterator> using DisableIfAtLeastForwardIterator = absl::enable_if_t< !inlined_vector_internal::IsAtLeastForwardIterator<Iterator>::value>; @@ -110,7 +108,7 @@ class InlinedVector { // Creates an empty inlined vector with a value-initialized allocator. InlinedVector() noexcept(noexcept(allocator_type())) : storage_() {} - // Creates an empty inlined vector with a specified allocator. + // Creates an empty inlined vector with a copy of `alloc`. explicit InlinedVector(const allocator_type& alloc) noexcept : storage_(alloc) {} @@ -128,7 +126,7 @@ class InlinedVector { storage_.Initialize(CopyValueAdapter(v), n); } - // Creates an inlined vector of copies of the values in `list`. + // Creates an inlined vector with copies of the elements of `list`. InlinedVector(std::initializer_list<value_type> list, const allocator_type& alloc = allocator_type()) : InlinedVector(list.begin(), list.end(), alloc) {} @@ -136,7 +134,7 @@ class InlinedVector { // Creates an inlined vector with elements constructed from the provided // forward iterator range [`first`, `last`). // - // NOTE: The `enable_if` prevents ambiguous interpretation between a call to + // NOTE: the `enable_if` prevents ambiguous interpretation between a call to // this constructor with two integral arguments and a call to the above // `InlinedVector(size_type, const_reference)` constructor. template <typename ForwardIterator, @@ -158,11 +156,12 @@ class InlinedVector { std::copy(first, last, std::back_inserter(*this)); } - // Creates a copy of an `other` inlined vector using `other`'s allocator. + // Creates an inlined vector by copying the contents of `other` using + // `other`'s allocator. InlinedVector(const InlinedVector& other) : InlinedVector(other, *other.storage_.GetAllocPtr()) {} - // Creates a copy of an `other` inlined vector using a specified allocator. + // Creates an inlined vector by copying the contents of `other` using `alloc`. InlinedVector(const InlinedVector& other, const allocator_type& alloc) : storage_(alloc) { if (IsMemcpyOk::value && !other.storage_.GetIsAllocated()) { @@ -173,67 +172,66 @@ class InlinedVector { } } - // Creates an inlined vector by moving in the contents of an `other` inlined - // vector without performing any allocations. If `other` contains allocated - // memory, the newly-created instance will take ownership of that memory - // (leaving `other` empty). However, if `other` does not contain allocated - // memory (i.e. is inlined), the new inlined vector will perform element-wise - // move construction of `other`'s elements. + // Creates an inlined vector by moving in the contents of `other` without + // allocating. If `other` contains allocated memory, the newly-created inlined + // vector will take ownership of that memory. However, if `other` does not + // contain allocated memory, the newly-created inlined vector will perform + // element-wise move construction of the contents of `other`. // // NOTE: since no allocation is performed for the inlined vector in either // case, the `noexcept(...)` specification depends on whether moving the - // underlying objects can throw. We assume: - // a) Move constructors should only throw due to allocation failure. - // b) If `value_type`'s move constructor allocates, it uses the same - // allocation function as the `InlinedVector`'s allocator. Thus, the move - // constructor is non-throwing if the allocator is non-throwing or - // `value_type`'s move constructor is specified as `noexcept`. + // underlying objects can throw. It is assumed assumed that... + // a) move constructors should only throw due to allocation failure. + // b) if `value_type`'s move constructor allocates, it uses the same + // allocation function as the inlined vector's allocator. + // Thus, the move constructor is non-throwing if the allocator is non-throwing + // or `value_type`'s move constructor is specified as `noexcept`. InlinedVector(InlinedVector&& other) noexcept( absl::allocator_is_nothrow<allocator_type>::value || std::is_nothrow_move_constructible<value_type>::value) : storage_(*other.storage_.GetAllocPtr()) { if (IsMemcpyOk::value) { storage_.MemcpyFrom(other.storage_); + other.storage_.SetInlinedSize(0); } else if (other.storage_.GetIsAllocated()) { storage_.SetAllocatedData(other.storage_.GetAllocatedData(), other.storage_.GetAllocatedCapacity()); storage_.SetAllocatedSize(other.storage_.GetSize()); + other.storage_.SetInlinedSize(0); } else { IteratorValueAdapter<MoveIterator> other_values( MoveIterator(other.storage_.GetInlinedData())); + inlined_vector_internal::ConstructElements( storage_.GetAllocPtr(), storage_.GetInlinedData(), &other_values, other.storage_.GetSize()); + storage_.SetInlinedSize(other.storage_.GetSize()); } } - // Creates an inlined vector by moving in the contents of an `other` inlined - // vector, performing allocations with the specified `alloc` allocator. If - // `other`'s allocator is not equal to `alloc` and `other` contains allocated - // memory, this move constructor will create a new allocation. + // Creates an inlined vector by moving in the contents of `other` with a copy + // of `alloc`. // - // NOTE: since allocation is performed in this case, this constructor can - // only be `noexcept` if the specified allocator is also `noexcept`. If this - // is the case, or if `other` contains allocated memory, this constructor - // performs element-wise move construction of its contents. - // - // Only in the case where `other`'s allocator is equal to `alloc` and `other` - // contains allocated memory will the newly created inlined vector take - // ownership of `other`'s allocated memory. + // NOTE: if `other`'s allocator is not equal to `alloc`, even if `other` + // contains allocated memory, this move constructor will still allocate. Since + // allocation is performed, this constructor can only be `noexcept` if the + // specified allocator is also `noexcept`. InlinedVector(InlinedVector&& other, const allocator_type& alloc) noexcept( absl::allocator_is_nothrow<allocator_type>::value) : storage_(alloc) { if (IsMemcpyOk::value) { storage_.MemcpyFrom(other.storage_); + other.storage_.SetInlinedSize(0); } else if ((*storage_.GetAllocPtr() == *other.storage_.GetAllocPtr()) && other.storage_.GetIsAllocated()) { storage_.SetAllocatedData(other.storage_.GetAllocatedData(), other.storage_.GetAllocatedCapacity()); storage_.SetAllocatedSize(other.storage_.GetSize()); + other.storage_.SetInlinedSize(0); } else { storage_.Initialize( @@ -250,7 +248,7 @@ class InlinedVector { // `InlinedVector::empty()` // - // Checks if the inlined vector has no elements. + // Returns whether the inlined vector contains no elements. bool empty() const noexcept { return !size(); } // `InlinedVector::size()` @@ -260,23 +258,23 @@ class InlinedVector { // `InlinedVector::max_size()` // - // Returns the maximum number of elements the vector can hold. + // Returns the maximum number of elements the inlined vector can hold. size_type max_size() const noexcept { // One bit of the size storage is used to indicate whether the inlined - // vector is allocated. As a result, the maximum size of the container that - // we can express is half of the max for `size_type`. + // vector contains allocated memory. As a result, the maximum size that the + // inlined vector can express is half of the max for `size_type`. return (std::numeric_limits<size_type>::max)() / 2; } // `InlinedVector::capacity()` // - // Returns the number of elements that can be stored in the inlined vector - // without requiring a reallocation of underlying memory. + // Returns the number of elements that could be stored in the inlined vector + // without requiring a reallocation. // - // NOTE: For most inlined vectors, `capacity()` should equal the template - // parameter `N`. For inlined vectors which exceed this capacity, they - // will no longer be inlined and `capacity()` will equal its capacity on the - // allocated heap. + // NOTE: for most inlined vectors, `capacity()` should be equal to the + // template parameter `N`. For inlined vectors which exceed this capacity, + // they will no longer be inlined and `capacity()` will equal the capactity of + // the allocated memory. size_type capacity() const noexcept { return storage_.GetIsAllocated() ? storage_.GetAllocatedCapacity() : storage_.GetInlinedCapacity(); @@ -284,56 +282,68 @@ class InlinedVector { // `InlinedVector::data()` // - // Returns a `pointer` to elements of the inlined vector. This pointer can be - // used to access and modify the contained elements. - // Only results within the range [`0`, `size()`) are defined. + // Returns a `pointer` to the elements of the inlined vector. This pointer + // can be used to access and modify the contained elements. + // + // NOTE: only elements within [`data()`, `data() + size()`) are valid. pointer data() noexcept { return storage_.GetIsAllocated() ? storage_.GetAllocatedData() : storage_.GetInlinedData(); } - // Overload of `InlinedVector::data()` to return a `const_pointer` to elements - // of the inlined vector. This pointer can be used to access (but not modify) - // the contained elements. + // Overload of `InlinedVector::data()` that returns a `const_pointer` to the + // elements of the inlined vector. This pointer can be used to access but not + // modify the contained elements. + // + // NOTE: only elements within [`data()`, `data() + size()`) are valid. const_pointer data() const noexcept { return storage_.GetIsAllocated() ? storage_.GetAllocatedData() : storage_.GetInlinedData(); } - // `InlinedVector::operator[]()` + // `InlinedVector::operator[](...)` // - // Returns a `reference` to the `i`th element of the inlined vector using the - // array operator. + // Returns a `reference` to the `i`th element of the inlined vector. reference operator[](size_type i) { assert(i < size()); + return data()[i]; } - // Overload of `InlinedVector::operator[]()` to return a `const_reference` to - // the `i`th element of the inlined vector. + // Overload of `InlinedVector::operator[](...)` that returns a + // `const_reference` to the `i`th element of the inlined vector. const_reference operator[](size_type i) const { assert(i < size()); + return data()[i]; } - // `InlinedVector::at()` + // `InlinedVector::at(...)` // // Returns a `reference` to the `i`th element of the inlined vector. + // + // NOTE: if `i` is not within the required range of `InlinedVector::at(...)`, + // in both debug and non-debug builds, `std::out_of_range` will be thrown. reference at(size_type i) { if (ABSL_PREDICT_FALSE(i >= size())) { base_internal::ThrowStdOutOfRange( "`InlinedVector::at(size_type)` failed bounds check"); } + return data()[i]; } - // Overload of `InlinedVector::at()` to return a `const_reference` to the - // `i`th element of the inlined vector. + // Overload of `InlinedVector::at(...)` that returns a `const_reference` to + // the `i`th element of the inlined vector. + // + // NOTE: if `i` is not within the required range of `InlinedVector::at(...)`, + // in both debug and non-debug builds, `std::out_of_range` will be thrown. const_reference at(size_type i) const { if (ABSL_PREDICT_FALSE(i >= size())) { base_internal::ThrowStdOutOfRange( "`InlinedVector::at(size_type) const` failed bounds check"); } + return data()[i]; } @@ -342,13 +352,15 @@ class InlinedVector { // Returns a `reference` to the first element of the inlined vector. reference front() { assert(!empty()); + return at(0); } - // Overload of `InlinedVector::front()` returns a `const_reference` to the - // first element of the inlined vector. + // Overload of `InlinedVector::front()` that returns a `const_reference` to + // the first element of the inlined vector. const_reference front() const { assert(!empty()); + return at(0); } @@ -357,13 +369,15 @@ class InlinedVector { // Returns a `reference` to the last element of the inlined vector. reference back() { assert(!empty()); + return at(size() - 1); } - // Overload of `InlinedVector::back()` to return a `const_reference` to the + // Overload of `InlinedVector::back()` that returns a `const_reference` to the // last element of the inlined vector. const_reference back() const { assert(!empty()); + return at(size() - 1); } @@ -372,7 +386,7 @@ class InlinedVector { // Returns an `iterator` to the beginning of the inlined vector. iterator begin() noexcept { return data(); } - // Overload of `InlinedVector::begin()` to return a `const_iterator` to + // Overload of `InlinedVector::begin()` that returns a `const_iterator` to // the beginning of the inlined vector. const_iterator begin() const noexcept { return data(); } @@ -381,7 +395,7 @@ class InlinedVector { // Returns an `iterator` to the end of the inlined vector. iterator end() noexcept { return data() + size(); } - // Overload of `InlinedVector::end()` to return a `const_iterator` to the + // Overload of `InlinedVector::end()` that returns a `const_iterator` to the // end of the inlined vector. const_iterator end() const noexcept { return data() + size(); } @@ -400,7 +414,7 @@ class InlinedVector { // Returns a `reverse_iterator` from the end of the inlined vector. reverse_iterator rbegin() noexcept { return reverse_iterator(end()); } - // Overload of `InlinedVector::rbegin()` to return a + // Overload of `InlinedVector::rbegin()` that returns a // `const_reverse_iterator` from the end of the inlined vector. const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); @@ -411,7 +425,7 @@ class InlinedVector { // Returns a `reverse_iterator` from the beginning of the inlined vector. reverse_iterator rend() noexcept { return reverse_iterator(begin()); } - // Overload of `InlinedVector::rend()` to return a `const_reverse_iterator` + // Overload of `InlinedVector::rend()` that returns a `const_reverse_iterator` // from the beginning of the inlined vector. const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); @@ -430,71 +444,75 @@ class InlinedVector { // `InlinedVector::get_allocator()` // - // Returns a copy of the allocator of the inlined vector. + // Returns a copy of the inlined vector's allocator. allocator_type get_allocator() const { return *storage_.GetAllocPtr(); } // --------------------------------------------------------------------------- // InlinedVector Member Mutators // --------------------------------------------------------------------------- - // `InlinedVector::operator=()` + // `InlinedVector::operator=(...)` // - // Replaces the contents of the inlined vector with copies of the elements in - // the provided `std::initializer_list`. + // Replaces the elements of the inlined vector with copies of the elements of + // `list`. InlinedVector& operator=(std::initializer_list<value_type> list) { assign(list.begin(), list.end()); + return *this; } - // Overload of `InlinedVector::operator=()` to replace the contents of the - // inlined vector with the contents of `other`. + // Overload of `InlinedVector::operator=(...)` that replaces the elements of + // the inlined vector with copies of the elements of `other`. InlinedVector& operator=(const InlinedVector& other) { if (ABSL_PREDICT_TRUE(this != std::addressof(other))) { const_pointer other_data = other.data(); assign(other_data, other_data + other.size()); } + return *this; } - // Overload of `InlinedVector::operator=()` to replace the contents of the - // inlined vector with the contents of `other`. + // Overload of `InlinedVector::operator=(...)` that moves the elements of + // `other` into the inlined vector. // - // NOTE: As a result of calling this overload, `other` may be empty or it's - // contents may be left in a moved-from state. + // NOTE: as a result of calling this overload, `other` is left in a valid but + // unspecified state. InlinedVector& operator=(InlinedVector&& other) { - if (ABSL_PREDICT_FALSE(this == std::addressof(other))) return *this; - - if (IsMemcpyOk::value || other.storage_.GetIsAllocated()) { - inlined_vector_internal::DestroyElements(storage_.GetAllocPtr(), data(), - size()); - storage_.DeallocateIfAllocated(); - storage_.MemcpyFrom(other.storage_); - other.storage_.SetInlinedSize(0); - } else { - storage_.Assign(IteratorValueAdapter<MoveIterator>( - MoveIterator(other.storage_.GetInlinedData())), - other.size()); + if (ABSL_PREDICT_TRUE(this != std::addressof(other))) { + if (IsMemcpyOk::value || other.storage_.GetIsAllocated()) { + inlined_vector_internal::DestroyElements(storage_.GetAllocPtr(), data(), + size()); + storage_.DeallocateIfAllocated(); + storage_.MemcpyFrom(other.storage_); + + other.storage_.SetInlinedSize(0); + } else { + storage_.Assign(IteratorValueAdapter<MoveIterator>( + MoveIterator(other.storage_.GetInlinedData())), + other.size()); + } } return *this; } - // `InlinedVector::assign()` + // `InlinedVector::assign(...)` // // Replaces the contents of the inlined vector with `n` copies of `v`. void assign(size_type n, const_reference v) { storage_.Assign(CopyValueAdapter(v), n); } - // Overload of `InlinedVector::assign()` to replace the contents of the - // inlined vector with copies of the values in the provided - // `std::initializer_list`. + // Overload of `InlinedVector::assign(...)` that replaces the contents of the + // inlined vector with copies of the elements of `list`. void assign(std::initializer_list<value_type> list) { assign(list.begin(), list.end()); } - // Overload of `InlinedVector::assign()` to replace the contents of the - // inlined vector with the forward iterator range [`first`, `last`). + // Overload of `InlinedVector::assign(...)` to replace the contents of the + // inlined vector with the range [`first`, `last`). + // + // NOTE: this overload is for iterators that are "forward" category or better. template <typename ForwardIterator, EnableIfAtLeastForwardIterator<ForwardIterator>* = nullptr> void assign(ForwardIterator first, ForwardIterator last) { @@ -502,8 +520,10 @@ class InlinedVector { std::distance(first, last)); } - // Overload of `InlinedVector::assign()` to replace the contents of the - // inlined vector with the input iterator range [`first`, `last`). + // Overload of `InlinedVector::assign(...)` to replace the contents of the + // inlined vector with the range [`first`, `last`). + // + // NOTE: this overload is for iterators that are "input" category. template <typename InputIterator, DisableIfAtLeastForwardIterator<InputIterator>* = nullptr> void assign(InputIterator first, InputIterator last) { @@ -517,36 +537,39 @@ class InlinedVector { std::copy(first, last, std::back_inserter(*this)); } - // `InlinedVector::resize()` + // `InlinedVector::resize(...)` // - // Resizes the inlined vector to contain `n` elements. If `n` is smaller than - // the inlined vector's current size, extra elements are destroyed. If `n` is - // larger than the initial size, new elements are value-initialized. + // Resizes the inlined vector to contain `n` elements. + // + // NOTE: if `n` is smaller than `size()`, extra elements are destroyed. If `n` + // is larger than `size()`, new elements are value-initialized. void resize(size_type n) { storage_.Resize(DefaultValueAdapter(), n); } - // Overload of `InlinedVector::resize()` to resize the inlined vector to - // contain `n` elements where, if `n` is larger than `size()`, the new values - // will be copy-constructed from `v`. + // Overload of `InlinedVector::resize(...)` that resizes the inlined vector to + // contain `n` elements. + // + // NOTE: if `n` is smaller than `size()`, extra elements are destroyed. If `n` + // is larger than `size()`, new elements are copied-constructed from `v`. void resize(size_type n, const_reference v) { storage_.Resize(CopyValueAdapter(v), n); } - // `InlinedVector::insert()` + // `InlinedVector::insert(...)` // - // Copies `v` into `pos`, returning an `iterator` pointing to the newly + // Inserts a copy of `v` at `pos`, returning an `iterator` to the newly // inserted element. iterator insert(const_iterator pos, const_reference v) { return emplace(pos, v); } - // Overload of `InlinedVector::insert()` for moving `v` into `pos`, returning - // an iterator pointing to the newly inserted element. + // Overload of `InlinedVector::insert(...)` that inserts `v` at `pos` using + // move semantics, returning an `iterator` to the newly inserted element. iterator insert(const_iterator pos, rvalue_reference v) { return emplace(pos, std::move(v)); } - // Overload of `InlinedVector::insert()` for inserting `n` contiguous copies - // of `v` starting at `pos`. Returns an `iterator` pointing to the first of + // Overload of `InlinedVector::insert(...)` that inserts `n` contiguous copies + // of `v` starting at `pos`, returning an `iterator` pointing to the first of // the newly inserted elements. iterator insert(const_iterator pos, size_type n, const_reference v) { assert(pos >= begin()); @@ -560,19 +583,18 @@ class InlinedVector { } } - // Overload of `InlinedVector::insert()` for copying the contents of the - // `std::initializer_list` into the vector starting at `pos`. Returns an - // `iterator` pointing to the first of the newly inserted elements. + // Overload of `InlinedVector::insert(...)` that inserts copies of the + // elements of `list` starting at `pos`, returning an `iterator` pointing to + // the first of the newly inserted elements. iterator insert(const_iterator pos, std::initializer_list<value_type> list) { return insert(pos, list.begin(), list.end()); } - // Overload of `InlinedVector::insert()` for inserting elements constructed - // from the forward iterator range [`first`, `last`). Returns an `iterator` - // pointing to the first of the newly inserted elements. + // Overload of `InlinedVector::insert(...)` that inserts the range [`first`, + // `last`) starting at `pos`, returning an `iterator` pointing to the first + // of the newly inserted elements. // - // NOTE: The `enable_if` is intended to disambiguate the two three-argument - // overloads of `insert()`. + // NOTE: this overload is for iterators that are "forward" category or better. template <typename ForwardIterator, EnableIfAtLeastForwardIterator<ForwardIterator>* = nullptr> iterator insert(const_iterator pos, ForwardIterator first, @@ -588,9 +610,11 @@ class InlinedVector { } } - // Overload of `InlinedVector::insert()` for inserting elements constructed - // from the input iterator range [`first`, `last`). Returns an `iterator` - // pointing to the first of the newly inserted elements. + // Overload of `InlinedVector::insert(...)` that inserts the range [`first`, + // `last`) starting at `pos`, returning an `iterator` pointing to the first + // of the newly inserted elements. + // + // NOTE: this overload is for iterators that are "input" category. template <typename InputIterator, DisableIfAtLeastForwardIterator<InputIterator>* = nullptr> iterator insert(const_iterator pos, InputIterator first, InputIterator last) { @@ -605,10 +629,10 @@ class InlinedVector { return iterator(data() + index); } - // `InlinedVector::emplace()` + // `InlinedVector::emplace(...)` // - // Constructs and inserts an object in the inlined vector at the given `pos`, - // returning an `iterator` pointing to the newly emplaced element. + // Constructs and inserts an element using `args...` in the inlined vector at + // `pos`, returning an `iterator` pointing to the newly emplaced element. template <typename... Args> iterator emplace(const_iterator pos, Args&&... args) { assert(pos >= begin()); @@ -621,30 +645,29 @@ class InlinedVector { 1); } - // `InlinedVector::emplace_back()` + // `InlinedVector::emplace_back(...)` // - // Constructs and appends a new element to the end of the inlined vector, - // returning a `reference` to the emplaced element. + // Constructs and inserts an element using `args...` in the inlined vector at + // `end()`, returning a `reference` to the newly emplaced element. template <typename... Args> reference emplace_back(Args&&... args) { return storage_.EmplaceBack(std::forward<Args>(args)...); } - // `InlinedVector::push_back()` + // `InlinedVector::push_back(...)` // - // Appends a copy of `v` to the end of the inlined vector. + // Inserts a copy of `v` in the inlined vector at `end()`. void push_back(const_reference v) { static_cast<void>(emplace_back(v)); } - // Overload of `InlinedVector::push_back()` for moving `v` into a newly - // appended element. + // Overload of `InlinedVector::push_back(...)` for inserting `v` at `end()` + // using move semantics. void push_back(rvalue_reference v) { static_cast<void>(emplace_back(std::move(v))); } // `InlinedVector::pop_back()` // - // Destroys the element at the end of the inlined vector and shrinks the size - // by `1` (unless the inlined vector is empty, in which case this is a no-op). + // Destroys the element at `back()`, reducing the size by `1`. void pop_back() noexcept { assert(!empty()); @@ -652,12 +675,12 @@ class InlinedVector { storage_.SubtractSize(1); } - // `InlinedVector::erase()` + // `InlinedVector::erase(...)` // - // Erases the element at `pos` of the inlined vector, returning an `iterator` - // pointing to the first element following the erased element. + // Erases the element at `pos`, returning an `iterator` pointing to where the + // erased element was located. // - // NOTE: May return the end iterator, which is not dereferencable. + // NOTE: may return `end()`, which is not dereferencable. iterator erase(const_iterator pos) { assert(pos >= begin()); assert(pos < end()); @@ -665,10 +688,11 @@ class InlinedVector { return storage_.Erase(pos, pos + 1); } - // Overload of `InlinedVector::erase()` for erasing all elements in the - // range [`from`, `to`) in the inlined vector. Returns an `iterator` pointing - // to the first element following the range erased or the end iterator if `to` - // was the end iterator. + // Overload of `InlinedVector::erase(...)` that erases every element in the + // range [`from`, `to`), returning an `iterator` pointing to where the first + // erased element was located. + // + // NOTE: may return `end()`, which is not dereferencable. iterator erase(const_iterator from, const_iterator to) { assert(from >= begin()); assert(from <= to); @@ -683,8 +707,8 @@ class InlinedVector { // `InlinedVector::clear()` // - // Destroys all elements in the inlined vector, sets the size of `0` and - // deallocates the heap allocation if the inlined vector was allocated. + // Destroys all elements in the inlined vector, setting the size to `0` and + // deallocating any held memory. void clear() noexcept { inlined_vector_internal::DestroyElements(storage_.GetAllocPtr(), data(), size()); @@ -692,37 +716,31 @@ class InlinedVector { storage_.SetInlinedSize(0); } - // `InlinedVector::reserve()` + // `InlinedVector::reserve(...)` // - // Enlarges the underlying representation of the inlined vector so it can hold - // at least `n` elements. This method does not change `size()` or the actual - // contents of the vector. - // - // NOTE: If `n` does not exceed `capacity()`, `reserve()` will have no - // effects. Otherwise, `reserve()` will reallocate, performing an n-time - // element-wise move of everything contained. + // Ensures that there is enough room for at least `n` elements. void reserve(size_type n) { storage_.Reserve(n); } // `InlinedVector::shrink_to_fit()` // - // Reduces memory usage by freeing unused memory. After this call, calls to + // Reduces memory usage by freeing unused memory. After being called, calls to // `capacity()` will be equal to `max(N, size())`. // - // If `size() <= N` and the elements are currently stored on the heap, they - // will be moved to the inlined storage and the heap memory will be - // deallocated. + // If `size() <= N` and the inlined vector contains allocated memory, the + // elements will all be moved to the inlined space and the allocated memory + // will be deallocated. // - // If `size() > N` and `size() < capacity()` the elements will be moved to a - // smaller heap allocation. + // If `size() > N` and `size() < capacity()`, the elements will be moved to a + // smaller allocation. void shrink_to_fit() { if (storage_.GetIsAllocated()) { storage_.ShrinkToFit(); } } - // `InlinedVector::swap()` + // `InlinedVector::swap(...)` // - // Swaps the contents of this inlined vector with the contents of `other`. + // Swaps the contents of the inlined vector with `other`. void swap(InlinedVector& other) { if (ABSL_PREDICT_TRUE(this != std::addressof(other))) { storage_.Swap(std::addressof(other.storage_)); @@ -740,93 +758,86 @@ class InlinedVector { // InlinedVector Non-Member Functions // ----------------------------------------------------------------------------- -// `swap()` +// `swap(...)` // -// Swaps the contents of two inlined vectors. This convenience function -// simply calls `InlinedVector::swap()`. +// Swaps the contents of two inlined vectors. template <typename T, size_t N, typename A> void swap(absl::InlinedVector<T, N, A>& a, absl::InlinedVector<T, N, A>& b) noexcept(noexcept(a.swap(b))) { a.swap(b); } -// `operator==()` +// `operator==(...)` // -// Tests the equivalency of the contents of two inlined vectors. +// Tests for value-equality of two inlined vectors. template <typename T, size_t N, typename A> bool operator==(const absl::InlinedVector<T, N, A>& a, const absl::InlinedVector<T, N, A>& b) { auto a_data = a.data(); - auto a_size = a.size(); auto b_data = b.data(); - auto b_size = b.size(); - return absl::equal(a_data, a_data + a_size, b_data, b_data + b_size); + return absl::equal(a_data, a_data + a.size(), b_data, b_data + b.size()); } -// `operator!=()` +// `operator!=(...)` // -// Tests the inequality of the contents of two inlined vectors. +// Tests for value-inequality of two inlined vectors. template <typename T, size_t N, typename A> bool operator!=(const absl::InlinedVector<T, N, A>& a, const absl::InlinedVector<T, N, A>& b) { return !(a == b); } -// `operator<()` +// `operator<(...)` // -// Tests whether the contents of one inlined vector are less than the contents -// of another through a lexicographical comparison operation. +// Tests whether the value of an inlined vector is less than the value of +// another inlined vector using a lexicographical comparison algorithm. template <typename T, size_t N, typename A> bool operator<(const absl::InlinedVector<T, N, A>& a, const absl::InlinedVector<T, N, A>& b) { auto a_data = a.data(); - auto a_size = a.size(); auto b_data = b.data(); - auto b_size = b.size(); - return std::lexicographical_compare(a_data, a_data + a_size, b_data, - b_data + b_size); + return std::lexicographical_compare(a_data, a_data + a.size(), b_data, + b_data + b.size()); } -// `operator>()` +// `operator>(...)` // -// Tests whether the contents of one inlined vector are greater than the -// contents of another through a lexicographical comparison operation. +// Tests whether the value of an inlined vector is greater than the value of +// another inlined vector using a lexicographical comparison algorithm. template <typename T, size_t N, typename A> bool operator>(const absl::InlinedVector<T, N, A>& a, const absl::InlinedVector<T, N, A>& b) { return b < a; } -// `operator<=()` +// `operator<=(...)` // -// Tests whether the contents of one inlined vector are less than or equal to -// the contents of another through a lexicographical comparison operation. +// Tests whether the value of an inlined vector is less than or equal to the +// value of another inlined vector using a lexicographical comparison algorithm. template <typename T, size_t N, typename A> bool operator<=(const absl::InlinedVector<T, N, A>& a, const absl::InlinedVector<T, N, A>& b) { return !(b < a); } -// `operator>=()` +// `operator>=(...)` // -// Tests whether the contents of one inlined vector are greater than or equal to -// the contents of another through a lexicographical comparison operation. +// Tests whether the value of an inlined vector is greater than or equal to the +// value of another inlined vector using a lexicographical comparison algorithm. template <typename T, size_t N, typename A> bool operator>=(const absl::InlinedVector<T, N, A>& a, const absl::InlinedVector<T, N, A>& b) { return !(a < b); } -// `AbslHashValue()` +// `AbslHashValue(...)` // -// Provides `absl::Hash` support for `absl::InlinedVector`. You do not normally -// call this function directly. -template <typename H, typename TheT, size_t TheN, typename TheA> -H AbslHashValue(H h, const absl::InlinedVector<TheT, TheN, TheA>& a) { - auto a_data = a.data(); - auto a_size = a.size(); - return H::combine(H::combine_contiguous(std::move(h), a_data, a_size), - a_size); +// Provides `absl::Hash` support for `absl::InlinedVector`. It is uncommon to +// call this directly. +template <typename H, typename T, size_t N, typename A> +H AbslHashValue(H h, const absl::InlinedVector<T, N, A>& a) { + auto size = a.size(); + return H::combine(H::combine_contiguous(std::move(h), a.data(), size), size); } } // namespace absl diff --git a/absl/container/internal/inlined_vector.h b/absl/container/internal/inlined_vector.h index b241d0e086de..17e203e51f5e 100644 --- a/absl/container/internal/inlined_vector.h +++ b/absl/container/internal/inlined_vector.h @@ -71,14 +71,12 @@ template <typename AllocatorType, typename ValueType, typename ValueAdapter, typename SizeType> void ConstructElements(AllocatorType* alloc_ptr, ValueType* construct_first, ValueAdapter* values_ptr, SizeType construct_size) { - // If any construction fails, all completed constructions are rolled back. for (SizeType i = 0; i < construct_size; ++i) { ABSL_INTERNAL_TRY { values_ptr->ConstructNext(alloc_ptr, construct_first + i); } ABSL_INTERNAL_CATCH_ANY { inlined_vector_internal::DestroyElements(alloc_ptr, construct_first, i); - ABSL_INTERNAL_RETHROW; } } @@ -171,6 +169,12 @@ class AllocationTransaction { explicit AllocationTransaction(AllocatorType* alloc_ptr) : alloc_data_(*alloc_ptr, nullptr) {} + ~AllocationTransaction() { + if (DidAllocate()) { + AllocatorTraits::deallocate(GetAllocator(), GetData(), GetCapacity()); + } + } + AllocationTransaction(const AllocationTransaction&) = delete; void operator=(const AllocationTransaction&) = delete; @@ -185,12 +189,6 @@ class AllocationTransaction { return GetData(); } - ~AllocationTransaction() { - if (DidAllocate()) { - AllocatorTraits::deallocate(GetAllocator(), GetData(), GetCapacity()); - } - } - private: container_internal::CompressedTuple<AllocatorType, pointer> alloc_data_; size_type capacity_ = 0; @@ -205,9 +203,21 @@ class ConstructionTransaction { explicit ConstructionTransaction(AllocatorType* alloc_ptr) : alloc_data_(*alloc_ptr, nullptr) {} + ~ConstructionTransaction() { + if (DidConstruct()) { + inlined_vector_internal::DestroyElements(std::addressof(GetAllocator()), + GetData(), GetSize()); + } + } + ConstructionTransaction(const ConstructionTransaction&) = delete; void operator=(const ConstructionTransaction&) = delete; + AllocatorType& GetAllocator() { return alloc_data_.template get<0>(); } + pointer& GetData() { return alloc_data_.template get<1>(); } + size_type& GetSize() { return size_; } + + bool DidConstruct() { return GetData() != nullptr; } template <typename ValueAdapter> void Construct(pointer data, ValueAdapter* values_ptr, size_type size) { inlined_vector_internal::ConstructElements(std::addressof(GetAllocator()), @@ -220,18 +230,7 @@ class ConstructionTransaction { GetSize() = 0; } - ~ConstructionTransaction() { - if (GetData() != nullptr) { - inlined_vector_internal::DestroyElements(std::addressof(GetAllocator()), - GetData(), GetSize()); - } - } - private: - AllocatorType& GetAllocator() { return alloc_data_.template get<0>(); } - pointer& GetData() { return alloc_data_.template get<1>(); } - size_type& GetSize() { return size_; } - container_internal::CompressedTuple<AllocatorType, pointer> alloc_data_; size_type size_ = 0; }; @@ -345,6 +344,7 @@ class Storage { void SubtractSize(size_type count) { assert(count <= GetSize()); + GetSizeAndIsAllocated() -= count << 1; } @@ -533,22 +533,14 @@ auto Storage<T, N, A>::Resize(ValueAdapter values, size_type new_size) -> void { if (new_size > storage_view.capacity) { size_type new_capacity = ComputeCapacity(storage_view.capacity, new_size); pointer new_data = allocation_tx.Allocate(new_capacity); - - // Construct new objects in `new_data` construct_loop = {new_data + storage_view.size, new_size - storage_view.size}; - - // Move all existing objects into `new_data` move_construct_loop = {new_data, storage_view.size}; - - // Destroy all existing objects in `storage_view.data` destroy_loop = {storage_view.data, storage_view.size}; } else if (new_size > storage_view.size) { - // Construct new objects in `storage_view.data` construct_loop = {storage_view.data + storage_view.size, new_size - storage_view.size}; } else { - // Destroy end `storage_view.size - new_size` objects in `storage_view.data` destroy_loop = {storage_view.data + new_size, storage_view.size - new_size}; } @@ -797,8 +789,6 @@ auto Storage<T, N, A>::ShrinkToFit() -> void { &move_values, storage_view.size); } ABSL_INTERNAL_CATCH_ANY { - // Writing to inlined data will trample on the existing state, thus it needs - // to be restored when a construction fails. SetAllocatedData(storage_view.data, storage_view.capacity); ABSL_INTERNAL_RETHROW; } @@ -822,13 +812,8 @@ auto Storage<T, N, A>::Swap(Storage* other_storage_ptr) -> void { assert(this != other_storage_ptr); if (GetIsAllocated() && other_storage_ptr->GetIsAllocated()) { - // Both are allocated, thus we can swap the allocations at the top level. - swap(data_.allocated, other_storage_ptr->data_.allocated); } else if (!GetIsAllocated() && !other_storage_ptr->GetIsAllocated()) { - // Both are inlined, thus element-wise swap up to smaller size, then move - // the remaining elements. - Storage* small_ptr = this; Storage* large_ptr = other_storage_ptr; if (small_ptr->GetSize() > large_ptr->GetSize()) swap(small_ptr, large_ptr); @@ -850,11 +835,6 @@ auto Storage<T, N, A>::Swap(Storage* other_storage_ptr) -> void { large_ptr->GetInlinedData() + small_ptr->GetSize(), large_ptr->GetSize() - small_ptr->GetSize()); } else { - // One is allocated and the other is inlined, thus we first move the - // elements from the inlined instance to the inlined space in the allocated - // instance and then we can finish by having the other vector take on the - // allocation. - Storage* allocated_ptr = this; Storage* inlined_ptr = other_storage_ptr; if (!allocated_ptr->GetIsAllocated()) swap(allocated_ptr, inlined_ptr); @@ -872,8 +852,6 @@ auto Storage<T, N, A>::Swap(Storage* other_storage_ptr) -> void { &move_values, inlined_ptr->GetSize()); } ABSL_INTERNAL_CATCH_ANY { - // Writing to inlined data will trample on the existing state, thus it - // needs to be restored when a construction fails. allocated_ptr->SetAllocatedData(allocated_storage_view.data, allocated_storage_view.capacity); ABSL_INTERNAL_RETHROW; @@ -887,7 +865,6 @@ auto Storage<T, N, A>::Swap(Storage* other_storage_ptr) -> void { allocated_storage_view.capacity); } - // All cases swap the size, `is_allocated` boolean and the allocator. swap(GetSizeAndIsAllocated(), other_storage_ptr->GetSizeAndIsAllocated()); swap(*GetAllocPtr(), *other_storage_ptr->GetAllocPtr()); } |