1 | //===----------------------------------------------------------------------===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | |
9 | // UNSUPPORTED: c++03, c++11, c++14, c++17, c++20 |
10 | |
11 | // <flat_set> |
12 | |
13 | // size_type erase(K&& k); |
14 | |
15 | #include <compare> |
16 | #include <concepts> |
17 | #include <deque> |
18 | #include <flat_set> |
19 | #include <functional> |
20 | #include <string> |
21 | #include <utility> |
22 | #include <vector> |
23 | |
24 | #include "MinSequenceContainer.h" |
25 | #include "../helpers.h" |
26 | #include "test_macros.h" |
27 | #include "min_allocator.h" |
28 | |
29 | // Constraints: The qualified-id Compare::is_transparent is valid and denotes a type. |
30 | template <class M> |
31 | concept CanErase = requires(M m, Transparent<int> k) { m.erase(k); }; |
32 | using TransparentSet = std::flat_multiset<int, TransparentComparator>; |
33 | using NonTransparentSet = std::flat_multiset<int, NonTransparentComparator>; |
34 | static_assert(CanErase<TransparentSet>); |
35 | static_assert(!CanErase<const TransparentSet>); |
36 | static_assert(!CanErase<NonTransparentSet>); |
37 | static_assert(!CanErase<const NonTransparentSet>); |
38 | |
39 | template <class Key, class It> |
40 | struct HeterogeneousKey { |
41 | explicit HeterogeneousKey(Key key, It it) : key_(key), it_(it) {} |
42 | operator It() && { return it_; } |
43 | auto operator<=>(Key key) const { return key_ <=> key; } |
44 | friend bool operator<(const HeterogeneousKey&, const HeterogeneousKey&) { |
45 | assert(false); |
46 | return false; |
47 | } |
48 | Key key_; |
49 | It it_; |
50 | }; |
51 | |
52 | template <class KeyContainer> |
53 | void test_one() { |
54 | using Key = typename KeyContainer::value_type; |
55 | using M = std::flat_multiset<Key, std::less<Key>, KeyContainer>; |
56 | |
57 | M m = {1, 2, 3, 3, 4}; |
58 | ASSERT_SAME_TYPE(decltype(m.erase(9)), typename M::size_type); |
59 | auto n = m.erase(3); // erase(K&&) [with K=int] |
60 | assert(n == 2); |
61 | assert((m == M{1, 2, 4})); |
62 | typename M::key_type lvalue = 2; |
63 | n = m.erase(lvalue); // erase(K&&) [with K=int&] |
64 | assert(n == 1); |
65 | assert((m == M{1, 4})); |
66 | const typename M::key_type const_lvalue = 1; |
67 | n = m.erase(const_lvalue); // erase(const key_type&) |
68 | assert(n == 1); |
69 | assert((m == M{4})); |
70 | } |
71 | |
72 | template <class KeyContainer> |
73 | void test_transparent_comparator() { |
74 | using M = std::flat_multiset<std::string, TransparentComparator, KeyContainer>; |
75 | { |
76 | M m = {"alpha" , "beta" , "beta" , "epsilon" , "epsilon" , "epsilon" , "eta" , "eta" , "gamma" }; |
77 | ASSERT_SAME_TYPE(decltype(m.erase(Transparent<std::string>{"abc" })), typename M::size_type); |
78 | |
79 | auto n = m.erase(Transparent<std::string>{.t: "epsilon" }); |
80 | assert(n == 3); |
81 | |
82 | M expected = {"alpha" , "beta" , "beta" , "eta" , "eta" , "gamma" }; |
83 | assert(m == expected); |
84 | |
85 | auto n2 = m.erase(Transparent<std::string>{.t: "aaa" }); |
86 | assert(n2 == 0); |
87 | assert(m == expected); |
88 | } |
89 | { |
90 | // was empty |
91 | M m; |
92 | auto n = m.erase(Transparent<std::string>{.t: "epsilon" }); |
93 | assert(n == 0); |
94 | assert(m.empty()); |
95 | } |
96 | } |
97 | |
98 | void test() { |
99 | test_one<std::vector<int>>(); |
100 | test_one<std::deque<int>>(); |
101 | test_one<MinSequenceContainer<int>>(); |
102 | test_one<std::vector<int, min_allocator<int>>>(); |
103 | |
104 | test_transparent_comparator<std::vector<std::string>>(); |
105 | test_transparent_comparator<std::deque<std::string>>(); |
106 | test_transparent_comparator<MinSequenceContainer<std::string>>(); |
107 | test_transparent_comparator<std::vector<std::string, min_allocator<std::string>>>(); |
108 | |
109 | { |
110 | // P2077's HeterogeneousKey example |
111 | using M = std::flat_multiset<int, std::less<>>; |
112 | M m = {1, 2, 3, 4, 5, 6, 7, 8}; |
113 | auto h1 = HeterogeneousKey<int, M::iterator>(8, m.begin()); |
114 | std::same_as<M::size_type> auto n = m.erase(h1); // lvalue is not convertible to It; erase(K&&) is the best match |
115 | assert(n == 1); |
116 | assert((m == M{1, 2, 3, 4, 5, 6, 7})); |
117 | std::same_as<M::iterator> auto it = m.erase(std::move(h1)); // rvalue is convertible to It; erase(K&&) drops out |
118 | assert(it == m.begin()); |
119 | assert((m == M{2, 3, 4, 5, 6, 7})); |
120 | } |
121 | { |
122 | using M = std::flat_multiset<int, std::less<>>; |
123 | M m = {1, 2, 3, 4, 5, 6, 7, 8}; |
124 | auto h1 = HeterogeneousKey<int, M::const_iterator>(8, m.begin()); |
125 | std::same_as<M::size_type> auto n = m.erase(h1); // lvalue is not convertible to It; erase(K&&) is the best match |
126 | assert(n == 1); |
127 | assert((m == M{1, 2, 3, 4, 5, 6, 7})); |
128 | std::same_as<M::iterator> auto it = m.erase(std::move(h1)); // rvalue is convertible to It; erase(K&&) drops out |
129 | assert(it == m.begin()); |
130 | assert((m == M{2, 3, 4, 5, 6, 7})); |
131 | } |
132 | { |
133 | bool transparent_used = false; |
134 | TransparentComparator c(transparent_used); |
135 | std::flat_multiset<int, TransparentComparator> m(std::sorted_equivalent, {1, 2, 3}, c); |
136 | assert(!transparent_used); |
137 | auto n = m.erase(Transparent<int>{3}); |
138 | assert(n == 1); |
139 | assert(transparent_used); |
140 | } |
141 | { |
142 | // std::string and C string literal |
143 | using M = std::flat_multiset<std::string, std::less<>>; |
144 | M m = {"alpha" , "beta" , "beta" , "epsilon" , "eta" , "gamma" }; |
145 | auto n = m.erase("beta" ); |
146 | assert(n == 2); |
147 | assert((m == M{"alpha" , "epsilon" , "eta" , "gamma" })); |
148 | } |
149 | } |
150 | |
151 | void test_exception() { |
152 | auto erase_transparent = [](auto& m, auto key_arg) { |
153 | using Set = std::decay_t<decltype(m)>; |
154 | using Key = typename Set::key_type; |
155 | m.erase(Transparent<Key>{key_arg}); |
156 | }; |
157 | test_erase_exception_guarantee(erase_function&: erase_transparent); |
158 | } |
159 | |
160 | int main(int, char**) { |
161 | test(); |
162 | test_exception(); |
163 | |
164 | return 0; |
165 | } |
166 | |