summaryrefslogtreecommitdiff
path: root/absl/container
diff options
context:
space:
mode:
Diffstat (limited to 'absl/container')
-rw-r--r--absl/container/flat_hash_map.h8
-rw-r--r--absl/container/flat_hash_set.h8
-rw-r--r--absl/container/inlined_vector.h28
-rw-r--r--absl/container/inlined_vector_benchmark.cc118
-rw-r--r--absl/container/internal/inlined_vector.h16
-rw-r--r--absl/container/internal/raw_hash_set_test.cc19
6 files changed, 107 insertions, 90 deletions
diff --git a/absl/container/flat_hash_map.h b/absl/container/flat_hash_map.h
index dfc497b5..00cc4dcf 100644
--- a/absl/container/flat_hash_map.h
+++ b/absl/container/flat_hash_map.h
@@ -219,8 +219,12 @@ class flat_hash_map : public absl::container_internal::raw_hash_map<
// Erases the element at `position` of the `flat_hash_map`, returning
// `void`.
//
- // NOTE: this return behavior is different than that of STL containers in
- // general and `std::unordered_map` in particular.
+ // NOTE: returning `void` in this case is different than that of STL
+ // containers in general and `std::unordered_map` in particular (which
+ // return an iterator to the element following the erased element). If that
+ // iterator is needed, simply post increment the iterator:
+ //
+ // map.erase(it++);
//
// iterator erase(const_iterator first, const_iterator last):
//
diff --git a/absl/container/flat_hash_set.h b/absl/container/flat_hash_set.h
index f27f174c..6bf51833 100644
--- a/absl/container/flat_hash_set.h
+++ b/absl/container/flat_hash_set.h
@@ -212,8 +212,12 @@ class flat_hash_set
// Erases the element at `position` of the `flat_hash_set`, returning
// `void`.
//
- // NOTE: this return behavior is different than that of STL containers in
- // general and `std::unordered_map` in particular.
+ // NOTE: returning `void` in this case is different than that of STL
+ // containers in general and `std::unordered_set` in particular (which
+ // return an iterator to the element following the erased element). If that
+ // iterator is needed, simply post increment the iterator:
+ //
+ // set.erase(it++);
//
// iterator erase(const_iterator first, const_iterator last):
//
diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h
index 68308750..77988058 100644
--- a/absl/container/inlined_vector.h
+++ b/absl/container/inlined_vector.h
@@ -66,7 +66,10 @@ 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 {
- using Storage = inlined_vector_internal::InlinedVectorStorage<T, N, A>;
+ static_assert(
+ N > 0, "InlinedVector cannot be instantiated with `0` inlined elements.");
+
+ using Storage = inlined_vector_internal::Storage<InlinedVector>;
using Tag = typename Storage::Tag;
using AllocatorAndTag = typename Storage::AllocatorAndTag;
using Allocation = typename Storage::Allocation;
@@ -283,8 +286,7 @@ class InlinedVector {
// will no longer be inlined and `capacity()` will equal its capacity on the
// allocated heap.
size_type capacity() const noexcept {
- return allocated() ? allocation().capacity()
- : Storage::GetInlinedCapacity();
+ return allocated() ? allocation().capacity() : static_cast<size_type>(N);
}
// `InlinedVector::data()`
@@ -802,19 +804,19 @@ class InlinedVector {
// `InlinedVector::shrink_to_fit()`
//
// Reduces memory usage by freeing unused memory. After this call, calls to
- // `capacity()` will be equal to `max(Storage::GetInlinedCapacity(), size())`.
+ // `capacity()` will be equal to `max(N, size())`.
//
- // If `size() <= Storage::GetInlinedCapacity()` 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 elements are currently stored on the heap, they
+ // will be moved to the inlined storage and the heap memory will be
+ // deallocated.
//
- // If `size() > Storage::GetInlinedCapacity()` 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 heap allocation.
void shrink_to_fit() {
const auto s = size();
if (ABSL_PREDICT_FALSE(!allocated() || s == capacity())) return;
- if (s <= Storage::GetInlinedCapacity()) {
+ if (s <= N) {
// Move the elements to the inlined storage.
// We have to do this using a temporary, because `inlined_storage` and
// `allocation_storage` are in a union field.
@@ -943,7 +945,7 @@ class InlinedVector {
const size_type s = size();
assert(s <= capacity());
- size_type target = (std::max)(Storage::GetInlinedCapacity(), s + delta);
+ size_type target = (std::max)(N, s + delta);
// Compute new capacity by repeatedly doubling current capacity
// TODO(psrc): Check and avoid overflow?
@@ -1046,7 +1048,7 @@ class InlinedVector {
}
void InitAssign(size_type n) {
- if (n > Storage::GetInlinedCapacity()) {
+ if (n > N) {
Allocation new_allocation(allocator(), n);
init_allocation(new_allocation);
UninitializedFill(allocated_space(), allocated_space() + n);
@@ -1058,7 +1060,7 @@ class InlinedVector {
}
void InitAssign(size_type n, const_reference v) {
- if (n > Storage::GetInlinedCapacity()) {
+ if (n > N) {
Allocation new_allocation(allocator(), n);
init_allocation(new_allocation);
UninitializedFill(allocated_space(), allocated_space() + n, v);
diff --git a/absl/container/inlined_vector_benchmark.cc b/absl/container/inlined_vector_benchmark.cc
index fc928afe..867a29ea 100644
--- a/absl/container/inlined_vector_benchmark.cc
+++ b/absl/container/inlined_vector_benchmark.cc
@@ -23,17 +23,13 @@
namespace {
-using IntVec = absl::InlinedVector<int, 8>;
-
void BM_InlinedVectorFill(benchmark::State& state) {
- const int len = state.range(0);
+ absl::InlinedVector<int, 8> v;
+ int val = 10;
for (auto _ : state) {
- IntVec v;
- for (int i = 0; i < len; i++) {
- v.push_back(i);
- }
+ benchmark::DoNotOptimize(v);
+ v.push_back(val);
}
- state.SetItemsProcessed(static_cast<int64_t>(state.iterations()) * len);
}
BENCHMARK(BM_InlinedVectorFill)->Range(0, 1024);
@@ -43,23 +39,25 @@ void BM_InlinedVectorFillRange(benchmark::State& state) {
for (int i = 0; i < len; i++) {
ia[i] = i;
}
+ auto* from = ia.get();
+ auto* to = from + len;
for (auto _ : state) {
- IntVec v(ia.get(), ia.get() + len);
+ benchmark::DoNotOptimize(from);
+ benchmark::DoNotOptimize(to);
+ absl::InlinedVector<int, 8> v(from, to);
benchmark::DoNotOptimize(v);
}
- state.SetItemsProcessed(static_cast<int64_t>(state.iterations()) * len);
}
BENCHMARK(BM_InlinedVectorFillRange)->Range(0, 1024);
void BM_StdVectorFill(benchmark::State& state) {
- const int len = state.range(0);
+ std::vector<int> v;
+ int val = 10;
for (auto _ : state) {
- std::vector<int> v;
- for (int i = 0; i < len; i++) {
- v.push_back(i);
- }
+ benchmark::DoNotOptimize(v);
+ benchmark::DoNotOptimize(val);
+ v.push_back(val);
}
- state.SetItemsProcessed(static_cast<int64_t>(state.iterations()) * len);
}
BENCHMARK(BM_StdVectorFill)->Range(0, 1024);
@@ -124,7 +122,7 @@ struct Buffer { // some arbitrary structure for benchmarking.
void* user_data;
};
-void BM_InlinedVectorTenAssignments(benchmark::State& state) {
+void BM_InlinedVectorAssignments(benchmark::State& state) {
const int len = state.range(0);
using BufferVec = absl::InlinedVector<Buffer, 2>;
@@ -133,18 +131,25 @@ void BM_InlinedVectorTenAssignments(benchmark::State& state) {
BufferVec dst;
for (auto _ : state) {
- for (int i = 0; i < 10; ++i) {
- dst = src;
- }
+ benchmark::DoNotOptimize(dst);
+ benchmark::DoNotOptimize(src);
+ dst = src;
}
}
-BENCHMARK(BM_InlinedVectorTenAssignments)
- ->Arg(0)->Arg(1)->Arg(2)->Arg(3)->Arg(4)->Arg(20);
+BENCHMARK(BM_InlinedVectorAssignments)
+ ->Arg(0)
+ ->Arg(1)
+ ->Arg(2)
+ ->Arg(3)
+ ->Arg(4)
+ ->Arg(20);
void BM_CreateFromContainer(benchmark::State& state) {
for (auto _ : state) {
- absl::InlinedVector<int, 4> x(absl::InlinedVector<int, 4>{1, 2, 3});
- benchmark::DoNotOptimize(x);
+ absl::InlinedVector<int, 4> src{1, 2, 3};
+ benchmark::DoNotOptimize(src);
+ absl::InlinedVector<int, 4> dst(std::move(src));
+ benchmark::DoNotOptimize(dst);
}
}
BENCHMARK(BM_CreateFromContainer);
@@ -214,6 +219,8 @@ void BM_SwapElements(benchmark::State& state) {
Vec b;
for (auto _ : state) {
using std::swap;
+ benchmark::DoNotOptimize(a);
+ benchmark::DoNotOptimize(b);
swap(a, b);
}
}
@@ -259,60 +266,44 @@ BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<std::string, 8>);
void BM_InlinedVectorIndexInlined(benchmark::State& state) {
absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7};
for (auto _ : state) {
- for (int i = 0; i < 1000; ++i) {
- benchmark::DoNotOptimize(v);
- benchmark::DoNotOptimize(v[4]);
- }
+ benchmark::DoNotOptimize(v);
+ benchmark::DoNotOptimize(v[4]);
}
- state.SetItemsProcessed(1000 * static_cast<int64_t>(state.iterations()));
}
BENCHMARK(BM_InlinedVectorIndexInlined);
void BM_InlinedVectorIndexExternal(benchmark::State& state) {
absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
for (auto _ : state) {
- for (int i = 0; i < 1000; ++i) {
- benchmark::DoNotOptimize(v);
- benchmark::DoNotOptimize(v[4]);
- }
+ benchmark::DoNotOptimize(v);
+ benchmark::DoNotOptimize(v[4]);
}
- state.SetItemsProcessed(1000 * static_cast<int64_t>(state.iterations()));
}
BENCHMARK(BM_InlinedVectorIndexExternal);
void BM_StdVectorIndex(benchmark::State& state) {
std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
for (auto _ : state) {
- for (int i = 0; i < 1000; ++i) {
- benchmark::DoNotOptimize(v);
- benchmark::DoNotOptimize(v[4]);
- }
+ benchmark::DoNotOptimize(v);
+ benchmark::DoNotOptimize(v[4]);
}
- state.SetItemsProcessed(1000 * static_cast<int64_t>(state.iterations()));
}
BENCHMARK(BM_StdVectorIndex);
-#define UNROLL_2(x) \
- benchmark::DoNotOptimize(x); \
- benchmark::DoNotOptimize(x);
-
-#define UNROLL_4(x) UNROLL_2(x) UNROLL_2(x)
-#define UNROLL_8(x) UNROLL_4(x) UNROLL_4(x)
-#define UNROLL_16(x) UNROLL_8(x) UNROLL_8(x);
-
void BM_InlinedVectorDataInlined(benchmark::State& state) {
absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7};
for (auto _ : state) {
- UNROLL_16(v.data());
+ benchmark::DoNotOptimize(v);
+ benchmark::DoNotOptimize(v.data());
}
- state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
}
BENCHMARK(BM_InlinedVectorDataInlined);
void BM_InlinedVectorDataExternal(benchmark::State& state) {
absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
for (auto _ : state) {
- UNROLL_16(v.data());
+ benchmark::DoNotOptimize(v);
+ benchmark::DoNotOptimize(v.data());
}
state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
}
@@ -321,7 +312,8 @@ BENCHMARK(BM_InlinedVectorDataExternal);
void BM_StdVectorData(benchmark::State& state) {
std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
for (auto _ : state) {
- UNROLL_16(v.data());
+ benchmark::DoNotOptimize(v);
+ benchmark::DoNotOptimize(v.data());
}
state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
}
@@ -330,54 +322,54 @@ BENCHMARK(BM_StdVectorData);
void BM_InlinedVectorSizeInlined(benchmark::State& state) {
absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7};
for (auto _ : state) {
- UNROLL_16(v.size());
+ benchmark::DoNotOptimize(v);
+ benchmark::DoNotOptimize(v.size());
}
- state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
}
BENCHMARK(BM_InlinedVectorSizeInlined);
void BM_InlinedVectorSizeExternal(benchmark::State& state) {
absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
for (auto _ : state) {
- UNROLL_16(v.size());
+ benchmark::DoNotOptimize(v);
+ benchmark::DoNotOptimize(v.size());
}
- state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
}
BENCHMARK(BM_InlinedVectorSizeExternal);
void BM_StdVectorSize(benchmark::State& state) {
std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
for (auto _ : state) {
- UNROLL_16(v.size());
+ benchmark::DoNotOptimize(v);
+ benchmark::DoNotOptimize(v.size());
}
- state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
}
BENCHMARK(BM_StdVectorSize);
void BM_InlinedVectorEmptyInlined(benchmark::State& state) {
absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7};
for (auto _ : state) {
- UNROLL_16(v.empty());
+ benchmark::DoNotOptimize(v);
+ benchmark::DoNotOptimize(v.empty());
}
- state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
}
BENCHMARK(BM_InlinedVectorEmptyInlined);
void BM_InlinedVectorEmptyExternal(benchmark::State& state) {
absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
for (auto _ : state) {
- UNROLL_16(v.empty());
+ benchmark::DoNotOptimize(v);
+ benchmark::DoNotOptimize(v.empty());
}
- state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
}
BENCHMARK(BM_InlinedVectorEmptyExternal);
void BM_StdVectorEmpty(benchmark::State& state) {
std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
for (auto _ : state) {
- UNROLL_16(v.empty());
+ benchmark::DoNotOptimize(v);
+ benchmark::DoNotOptimize(v.empty());
}
- state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
}
BENCHMARK(BM_StdVectorEmpty);
diff --git a/absl/container/internal/inlined_vector.h b/absl/container/internal/inlined_vector.h
index 30850609..24059d94 100644
--- a/absl/container/internal/inlined_vector.h
+++ b/absl/container/internal/inlined_vector.h
@@ -24,11 +24,12 @@
namespace absl {
namespace inlined_vector_internal {
-template <typename T, size_t N, typename A>
-class InlinedVectorStorage {
- static_assert(
- N > 0, "InlinedVector cannot be instantiated with `0` inline elements.");
+template <typename InlinedVector>
+class Storage;
+template <template <typename, size_t, typename> class InlinedVector, typename T,
+ size_t N, typename A>
+class Storage<InlinedVector<T, N, A>> {
public:
using allocator_type = A;
using value_type = typename allocator_type::value_type;
@@ -44,12 +45,7 @@ class InlinedVectorStorage {
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
- constexpr static size_type GetInlinedCapacity() {
- return static_cast<size_type>(N);
- }
-
- explicit InlinedVectorStorage(const allocator_type& a)
- : allocator_and_tag_(a) {}
+ explicit Storage(const allocator_type& a) : allocator_and_tag_(a) {}
// TODO(johnsoncj): Make the below types and members private after migration
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc
index 87511148..02fd0bfa 100644
--- a/absl/container/internal/raw_hash_set_test.cc
+++ b/absl/container/internal/raw_hash_set_test.cc
@@ -845,6 +845,25 @@ TEST(Table, Erase) {
EXPECT_TRUE(t.find(0) == t.end());
}
+TEST(Table, EraseMaintainsValidIterator) {
+ IntTable t;
+ const int kNumElements = 100;
+ for (int i = 0; i < kNumElements; i ++) {
+ EXPECT_TRUE(t.emplace(i).second);
+ }
+ EXPECT_EQ(t.size(), kNumElements);
+
+ int num_erase_calls = 0;
+ auto it = t.begin();
+ while (it != t.end()) {
+ t.erase(it++);
+ num_erase_calls++;
+ }
+
+ EXPECT_TRUE(t.empty());
+ EXPECT_EQ(num_erase_calls, kNumElements);
+}
+
// Collect N bad keys by following algorithm:
// 1. Create an empty table and reserve it to 2 * N.
// 2. Insert N random elements.
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-07 02:04:07 +0000