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_map>
12
13// class flat_multimap
14
15// template <class... Args>
16// iterator emplace_hint(const_iterator position, Args&&... args);
17
18#include <flat_map>
19#include <cassert>
20#include <deque>
21#include <functional>
22#include <vector>
23
24#include "MinSequenceContainer.h"
25#include "test_macros.h"
26#include "../../../Emplaceable.h"
27#include "DefaultOnly.h"
28#include "min_allocator.h"
29#include "../helpers.h"
30
31#if defined(_LIBCPP_VERSION)
32// spec only specifies `emplace(Args&&...)` is_constructible_v<pair<key_type, mapped_type>, Args...> is true.
33// nothing mentioned for emplace_hint
34template <class M, class... Args>
35concept CanEmplaceHint =
36 requires(M m, typename M::const_iterator i, Args&&... args) { m.emplace_hint(i, std::forward<Args>(args)...); };
37
38using Map = std::flat_multimap<Emplaceable, Emplaceable>;
39static_assert(CanEmplaceHint<Map>);
40static_assert(CanEmplaceHint<Map, Emplaceable, Emplaceable>);
41static_assert(CanEmplaceHint<Map, std::piecewise_construct_t, std::tuple<int, double>, std::tuple<int, double>>);
42static_assert(!CanEmplaceHint<Map, Emplaceable>);
43static_assert(!CanEmplaceHint<Map, int, double>);
44#endif
45
46template <class KeyContainer, class ValueContainer>
47void test() {
48 using Key = typename KeyContainer::value_type;
49 using Value = typename ValueContainer::value_type;
50 using M = std::flat_multimap<Key, Value, std::less<Key>, KeyContainer, ValueContainer>;
51 using R = M::iterator;
52 {
53 // was empty
54 M m;
55 std::same_as<R> decltype(auto) r = m.emplace_hint(m.end(), typename M::value_type(2, 3.5));
56 assert(r == m.begin());
57 assert(m.size() == 1);
58 assert(m.begin()->first == 2);
59 assert(m.begin()->second == 3.5);
60 }
61 {
62 // hint correct and no duplicates
63 M m = {{0, 0.0}, {1, 1.0}, {3, 3.0}};
64 auto it = m.begin() + 2;
65 std::same_as<R> decltype(auto) r = m.emplace_hint(it, typename M::value_type(2, 2.0));
66 assert(r == m.begin() + 2);
67 assert(m.size() == 4);
68 assert(r->first == 2);
69 assert(r->second == 2.0);
70 }
71 {
72 // hint correct and at the begin
73 M m = {{3, 3.0}, {4, 4.0}};
74 auto it = m.begin();
75 std::same_as<R> decltype(auto) r = m.emplace_hint(it, typename M::value_type(2, 2.0));
76 assert(r == m.begin());
77 assert(m.size() == 3);
78 assert(r->first == 2);
79 assert(r->second == 2.0);
80 }
81 {
82 // hint correct and at the end
83 M m = {{0, 0.0}, {1, 1.0}};
84 auto it = m.end();
85 std::same_as<R> decltype(auto) r = m.emplace_hint(it, typename M::value_type(2, 2.0));
86 assert(r == m.begin() + 2);
87 assert(m.size() == 3);
88 assert(r->first == 2);
89 assert(r->second == 2.0);
90 }
91 {
92 // hint correct and at first duplicate
93 M m = {{0, 0.0}, {1, 1.0}, {2, 1.9}, {2, 2.1}, {3, 3.0}};
94 auto it = m.begin() + 2;
95 std::same_as<R> decltype(auto) r = m.emplace_hint(it, typename M::value_type(2, 2.0));
96 assert(r == m.begin() + 2);
97 assert(m.size() == 6);
98 assert(r->first == 2);
99 assert(r->second == 2.0);
100 assert(std::next(r)->first == 2);
101 assert(std::next(r)->second == 1.9);
102 }
103 {
104 // hint correct and in-between duplicates
105 M m = {{0, 0.0}, {1, 1.0}, {2, 1.8}, {2, 1.9}, {2, 2.1}, {3, 3.0}};
106 auto it = m.begin() + 4;
107 std::same_as<R> decltype(auto) r = m.emplace_hint(it, typename M::value_type(2, 2.0));
108 assert(r == m.begin() + 4);
109 assert(m.size() == 7);
110 assert(r->first == 2);
111 assert(r->second == 2.0);
112 assert(std::next(r)->first == 2);
113 assert(std::next(r)->second == 2.1);
114 }
115 {
116 // hint correct and after duplicates
117 M m = {{0, 0.0}, {1, 1.0}, {2, 1.8}, {2, 1.9}, {2, 2.1}, {3, 3.0}};
118 auto it = m.begin() + 5;
119 std::same_as<R> decltype(auto) r = m.emplace_hint(it, typename M::value_type(2, 2.0));
120 assert(r == m.begin() + 5);
121 assert(m.size() == 7);
122 assert(r->first == 2);
123 assert(r->second == 2.0);
124 assert(std::next(r)->first == 3);
125 assert(std::next(r)->second == 3.0);
126 }
127 {
128 // hint incorrect and no duplicates
129 M m = {{0, 0.0}, {1, 1.0}, {3, 3.0}};
130 auto it = m.begin() + 1;
131 std::same_as<R> decltype(auto) r = m.emplace_hint(it, typename M::value_type(2, 2.0));
132 assert(r == m.begin() + 2);
133 assert(m.size() == 4);
134 assert(r->first == 2);
135 assert(r->second == 2.0);
136 }
137 {
138 // hint incorrect and at the begin
139 M m = {{0, 0.0}, {1, 1.0}};
140 auto it = m.begin();
141 std::same_as<R> decltype(auto) r = m.emplace_hint(it, typename M::value_type(2, 2.0));
142 assert(r == m.begin() + 2);
143 assert(m.size() == 3);
144 assert(r->first == 2);
145 assert(r->second == 2.0);
146 }
147 {
148 // hint incorrect and at the end
149 M m = {{3, 3.0}, {4, 4.0}};
150 auto it = m.end();
151 std::same_as<R> decltype(auto) r = m.emplace_hint(it, typename M::value_type(2, 2.0));
152 assert(r == m.begin());
153 assert(m.size() == 3);
154 assert(r->first == 2);
155 assert(r->second == 2.0);
156 }
157 {
158 // hint incorrect and before the first duplicate
159 M m = {{0, 0.0}, {1, 1.0}, {2, 1.8}, {2, 1.9}, {2, 2.1}, {3, 3.0}};
160 auto it = m.begin();
161 std::same_as<R> decltype(auto) r = m.emplace_hint(it, typename M::value_type(2, 2.0));
162 // the result is as left as possible
163 assert(r == m.begin() + 2);
164 assert(m.size() == 7);
165 assert(r->first == 2);
166 assert(r->second == 2.0);
167 assert(std::next(r)->first == 2);
168 assert(std::next(r)->second == 1.8);
169 }
170 {
171 // hint incorrect and after the last duplicate
172 M m = {{0, 0.0}, {1, 1.0}, {2, 1.8}, {2, 1.9}, {2, 2.1}, {3, 3.0}, {4, 4.0}};
173 auto it = m.begin() + 6;
174 std::same_as<R> decltype(auto) r = m.emplace_hint(it, typename M::value_type(2, 2.0));
175 // the result is as right as possible
176 assert(r == m.begin() + 5);
177 assert(m.size() == 8);
178 assert(r->first == 2);
179 assert(r->second == 2.0);
180 assert(std::next(r)->first == 3);
181 assert(std::next(r)->second == 3.0);
182 }
183}
184
185template <class KeyContainer, class ValueContainer>
186void test_emplaceable() {
187 using M = std::flat_multimap<int, Emplaceable, std::less<int>, KeyContainer, ValueContainer>;
188 using R = M::iterator;
189
190 M m;
191 ASSERT_SAME_TYPE(decltype(m.emplace_hint(m.cbegin())), R);
192 R r = m.emplace_hint(m.end(), std::piecewise_construct, std::forward_as_tuple(2), std::forward_as_tuple());
193 assert(r == m.begin());
194 assert(m.size() == 1);
195 assert(r->first == 2);
196 assert(r->second == Emplaceable());
197 r = m.emplace_hint(m.end(), std::piecewise_construct, std::forward_as_tuple(args: 1), std::forward_as_tuple(args: 2, args: 3.5));
198 assert(r == m.begin());
199 assert(m.size() == 2);
200 assert(r->first == 1);
201 assert(r->second == Emplaceable(2, 3.5));
202 r = m.emplace_hint(m.end(), std::piecewise_construct, std::forward_as_tuple(args: 1), std::forward_as_tuple(args: 2, args: 3.6));
203 assert(r == m.begin() + 1);
204 assert(m.size() == 3);
205 assert(r->first == 1);
206 assert(r->second == Emplaceable(2, 3.6));
207}
208
209int main(int, char**) {
210 test<std::vector<int>, std::vector<double>>();
211 test<std::deque<int>, std::vector<double>>();
212 test<MinSequenceContainer<int>, MinSequenceContainer<double>>();
213 test<std::vector<int, min_allocator<int>>, std::vector<double, min_allocator<double>>>();
214
215 test_emplaceable<std::vector<int>, std::vector<Emplaceable>>();
216 test_emplaceable<std::deque<int>, std::vector<Emplaceable>>();
217 test_emplaceable<MinSequenceContainer<int>, MinSequenceContainer<Emplaceable>>();
218 test_emplaceable<std::vector<int, min_allocator<int>>, std::vector<Emplaceable, min_allocator<Emplaceable>>>();
219
220 {
221 auto emplace_func = [](auto& m, auto key_arg, auto value_arg) {
222 m.emplace_hint(m.begin(), std::piecewise_construct, std::tuple(key_arg), std::tuple(value_arg));
223 };
224 test_emplace_exception_guarantee(emplace_function&: emplace_func);
225 }
226
227 return 0;
228}
229

source code of libcxx/test/std/containers/container.adaptors/flat.multimap/flat.multimap.modifiers/emplace_hint.pass.cpp