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 | // template <class... Args> |
14 | // iterator emplace_hint(const_iterator position, Args&&... args); |
15 | |
16 | #include <flat_set> |
17 | #include <cassert> |
18 | #include <deque> |
19 | #include <functional> |
20 | #include <vector> |
21 | |
22 | #include "MinSequenceContainer.h" |
23 | #include "test_macros.h" |
24 | #include "../../../Emplaceable.h" |
25 | #include "DefaultOnly.h" |
26 | #include "min_allocator.h" |
27 | #include "../helpers.h" |
28 | |
29 | struct CompareTensDigit { |
30 | bool operator()(auto lhs, auto rhs) const { return (lhs / 10) < (rhs / 10); } |
31 | }; |
32 | |
33 | template <class KeyContainer> |
34 | void test_one() { |
35 | using Key = typename KeyContainer::value_type; |
36 | using M = std::flat_multiset<Key, std::less<Key>, KeyContainer>; |
37 | using R = M::iterator; |
38 | |
39 | { |
40 | // was empty |
41 | M m; |
42 | std::same_as<R> decltype(auto) r = m.emplace_hint(m.end(), typename M::value_type(2)); |
43 | assert(r == m.begin()); |
44 | assert(m.size() == 1); |
45 | assert(*r == 2); |
46 | } |
47 | { |
48 | // hints correct and no duplicates |
49 | M m = {0, 1, 3}; |
50 | auto hint = m.begin() + 2; |
51 | std::same_as<R> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(2)); |
52 | assert(r == m.begin() + 2); |
53 | assert(m.size() == 4); |
54 | assert(*r == 2); |
55 | } |
56 | { |
57 | // hints correct at the begin |
58 | M m = {3, 4}; |
59 | auto hint = m.begin(); |
60 | std::same_as<R> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(2)); |
61 | assert(r == m.begin()); |
62 | assert(m.size() == 3); |
63 | assert(*r == 2); |
64 | } |
65 | { |
66 | // hints correct in the middle |
67 | M m = {0, 1, 3, 4}; |
68 | auto hint = m.begin() + 2; |
69 | std::same_as<R> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(2)); |
70 | assert(r == m.begin() + 2); |
71 | assert(m.size() == 5); |
72 | assert(*r == 2); |
73 | } |
74 | { |
75 | // hints correct at the end |
76 | M m = {0, 1}; |
77 | auto hint = m.end(); |
78 | std::same_as<R> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(2)); |
79 | assert(r == m.begin() + 2); |
80 | assert(m.size() == 3); |
81 | assert(*r == 2); |
82 | } |
83 | { |
84 | // hints correct but key already exists |
85 | M m = {0, 1, 2, 3, 4}; |
86 | auto hint = m.begin() + 2; |
87 | std::same_as<R> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(2)); |
88 | assert(r == m.begin() + 2); |
89 | assert(m.size() == 6); |
90 | assert(*r == 2); |
91 | } |
92 | { |
93 | // hint correct and at the first duplicate |
94 | using M2 = std::flat_multiset<Key, CompareTensDigit, KeyContainer>; |
95 | using R2 = M2::iterator; |
96 | M2 m{0, 10, 20, 25, 30}; |
97 | auto hint = m.begin() + 2; |
98 | std::same_as<R2> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(21)); |
99 | assert(r == m.begin() + 2); |
100 | assert(m.size() == 6); |
101 | assert(*r == 21); |
102 | } |
103 | { |
104 | // hint correct and in-between duplicates |
105 | using M2 = std::flat_multiset<Key, CompareTensDigit, KeyContainer>; |
106 | using R2 = M2::iterator; |
107 | M2 m{0, 10, 20, 21, 22, 30}; |
108 | auto hint = m.begin() + 4; |
109 | std::same_as<R2> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(23)); |
110 | assert(r == m.begin() + 4); |
111 | assert(m.size() == 7); |
112 | assert(*r == 23); |
113 | assert(*std::next(r) == 22); |
114 | } |
115 | { |
116 | // hint correct and after duplicates |
117 | using M2 = std::flat_multiset<Key, CompareTensDigit, KeyContainer>; |
118 | using R2 = M2::iterator; |
119 | M2 m{0, 10, 20, 21, 22, 30}; |
120 | auto hint = m.begin() + 5; |
121 | std::same_as<R2> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(23)); |
122 | assert(r == m.begin() + 5); |
123 | assert(m.size() == 7); |
124 | assert(*r == 23); |
125 | assert(*std::next(r) == 30); |
126 | } |
127 | { |
128 | // hints incorrect and no duplicates |
129 | M m = {0, 1, 3}; |
130 | auto hint = m.begin() + 1; |
131 | std::same_as<R> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(2)); |
132 | assert(r == m.begin() + 2); |
133 | assert(m.size() == 4); |
134 | assert(*r == 2); |
135 | } |
136 | { |
137 | // hints incorrectly at the begin |
138 | M m = {1, 4}; |
139 | auto hint = m.begin(); |
140 | std::same_as<R> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(2)); |
141 | assert(r == m.begin() + 1); |
142 | assert(m.size() == 3); |
143 | assert(*r == 2); |
144 | } |
145 | { |
146 | // hints incorrectly in the middle |
147 | M m = {0, 1, 3, 4}; |
148 | auto hint = m.begin() + 1; |
149 | std::same_as<R> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(2)); |
150 | assert(r == m.begin() + 2); |
151 | assert(m.size() == 5); |
152 | assert(*r == 2); |
153 | } |
154 | { |
155 | // hints incorrectly at the end |
156 | M m = {0, 3}; |
157 | auto hint = m.end(); |
158 | std::same_as<R> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(2)); |
159 | assert(r == m.begin() + 1); |
160 | assert(m.size() == 3); |
161 | assert(*r == 2); |
162 | } |
163 | { |
164 | // hints incorrect and key already exists |
165 | M m = {0, 1, 2, 3, 4}; |
166 | auto hint = m.begin(); |
167 | std::same_as<R> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(2)); |
168 | assert(r == m.begin() + 2); |
169 | assert(m.size() == 6); |
170 | assert(*r == 2); |
171 | } |
172 | { |
173 | // hint incorrect and before the first duplicate |
174 | using M2 = std::flat_multiset<Key, CompareTensDigit, KeyContainer>; |
175 | using R2 = M2::iterator; |
176 | M2 m{0, 10, 20, 21, 22, 30}; |
177 | auto hint = m.begin(); |
178 | std::same_as<R2> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(23)); |
179 | assert(r == m.begin() + 2); |
180 | assert(m.size() == 7); |
181 | assert(*r == 23); |
182 | assert(*std::next(r) == 20); |
183 | } |
184 | { |
185 | // hint incorrect and after the last duplicate |
186 | using M2 = std::flat_multiset<Key, CompareTensDigit, KeyContainer>; |
187 | using R2 = M2::iterator; |
188 | M2 m{0, 10, 20, 21, 22, 30, 40}; |
189 | auto hint = m.begin() + 6; |
190 | std::same_as<R2> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(23)); |
191 | assert(r == m.begin() + 5); |
192 | assert(m.size() == 8); |
193 | assert(*r == 23); |
194 | assert(*std::next(r) == 30); |
195 | } |
196 | } |
197 | |
198 | template <class KeyContainer> |
199 | void test_emplaceable() { |
200 | using M = std::flat_multiset<Emplaceable, std::less<Emplaceable>, KeyContainer>; |
201 | using R = M::iterator; |
202 | |
203 | M m; |
204 | ASSERT_SAME_TYPE(decltype(m.emplace_hint(m.cbegin())), R); |
205 | R r = m.emplace_hint(m.end(), 2, 0.0); |
206 | assert(r == m.begin()); |
207 | assert(m.size() == 1); |
208 | assert(*m.begin() == Emplaceable(2, 0.0)); |
209 | r = m.emplace_hint(m.end(), 1, 3.5); |
210 | assert(r == m.begin()); |
211 | assert(m.size() == 2); |
212 | assert(*m.begin() == Emplaceable(1, 3.5)); |
213 | r = m.emplace_hint(m.end(), 1, 3.5); |
214 | assert(r == m.begin() + 1); |
215 | assert(m.size() == 3); |
216 | assert(*r == Emplaceable(1, 3.5)); |
217 | } |
218 | |
219 | void test() { |
220 | test_one<std::vector<int>>(); |
221 | test_one<std::deque<int>>(); |
222 | test_one<MinSequenceContainer<int>>(); |
223 | test_one<std::vector<int, min_allocator<int>>>(); |
224 | |
225 | test_emplaceable<std::vector<Emplaceable>>(); |
226 | test_emplaceable<std::vector<Emplaceable>>(); |
227 | test_emplaceable<MinSequenceContainer<Emplaceable>>(); |
228 | test_emplaceable<std::vector<Emplaceable, min_allocator<Emplaceable>>>(); |
229 | } |
230 | |
231 | void test_exception() { |
232 | auto emplace_func = [](auto& m, auto key_arg) { m.emplace_hint(m.begin(), key_arg); }; |
233 | test_emplace_exception_guarantee(emplace_function&: emplace_func); |
234 | } |
235 | |
236 | int main(int, char**) { |
237 | test(); |
238 | test_exception(); |
239 | |
240 | return 0; |
241 | } |
242 | |