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// template<class K> pair<iterator, bool> insert(P&& x);
14// template<class K> iterator insert(const_iterator hint, P&& x);
15
16#include <algorithm>
17#include <compare>
18#include <concepts>
19#include <deque>
20#include <flat_map>
21#include <functional>
22#include <tuple>
23
24#include "MinSequenceContainer.h"
25#include "../helpers.h"
26#include "test_macros.h"
27#include "test_iterators.h"
28#include "min_allocator.h"
29
30// Constraints: is_constructible_v<pair<key_type, mapped_type>, P> is true.
31template <class M, class... Args>
32concept CanInsert = requires(M m, Args&&... args) { m.insert(std::forward<Args>(args)...); };
33
34using Map = std::flat_map<int, double>;
35using Iter = Map::const_iterator;
36
37static_assert(CanInsert<Map, std::pair<short, double>&&>);
38static_assert(CanInsert<Map, Iter, std::pair<short, double>&&>);
39static_assert(CanInsert<Map, std::tuple<short, double>&&>);
40static_assert(CanInsert<Map, Iter, std::tuple<short, double>&&>);
41static_assert(!CanInsert<Map, int>);
42static_assert(!CanInsert<Map, Iter, int>);
43
44static int expensive_comparisons = 0;
45static int cheap_comparisons = 0;
46
47struct CompareCounter {
48 int i_ = 0;
49 CompareCounter(int i) : i_(i) {}
50 friend auto operator<=>(const CompareCounter& x, const CompareCounter& y) {
51 expensive_comparisons += 1;
52 return x.i_ <=> y.i_;
53 }
54 bool operator==(const CompareCounter&) const = default;
55 friend auto operator<=>(const CompareCounter& x, int y) {
56 cheap_comparisons += 1;
57 return x.i_ <=> y;
58 }
59};
60
61template <class KeyContainer, class ValueContainer>
62void test() {
63 using Key = typename KeyContainer::value_type;
64 using Value = typename ValueContainer::value_type;
65 using M = std::flat_map<Key, Value, std::less<Key>, KeyContainer, ValueContainer>;
66
67 const std::pair<int, int> expected[] = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}};
68 {
69 // insert(P&&)
70 // Unlike flat_set, here we can't use key_compare to compare value_type versus P,
71 // so we must eagerly convert to value_type.
72 M m = {{1, 1}, {2, 2}, {4, 4}, {5, 5}};
73 expensive_comparisons = 0;
74 cheap_comparisons = 0;
75 std::same_as<std::pair<typename M::iterator, bool>> auto p =
76 m.insert(std::make_pair(3, 3)); // conversion happens first
77 assert(expensive_comparisons >= 2);
78 assert(cheap_comparisons == 0);
79 assert(p == std::make_pair(m.begin() + 2, true));
80 assert(std::ranges::equal(m, expected));
81 }
82 {
83 // insert(const_iterator, P&&)
84 M m = {{1, 1}, {2, 2}, {4, 4}, {5, 5}};
85 expensive_comparisons = 0;
86 cheap_comparisons = 0;
87 std::same_as<typename M::iterator> auto it = m.insert(m.begin(), std::make_pair(3, 3));
88 assert(expensive_comparisons >= 2);
89 assert(cheap_comparisons == 0);
90 assert(it == m.begin() + 2);
91 assert(std::ranges::equal(m, expected));
92 }
93 {
94 // insert(value_type&&)
95 M m = {{1, 1}, {2, 2}, {4, 4}, {5, 5}};
96 expensive_comparisons = 0;
97 cheap_comparisons = 0;
98 std::same_as<std::pair<typename M::iterator, bool>> auto p =
99 m.insert(std::make_pair(3, 3)); // conversion happens last
100 assert(expensive_comparisons >= 2);
101 assert(cheap_comparisons == 0);
102 assert(p == std::make_pair(m.begin() + 2, true));
103 assert(std::ranges::equal(m, expected));
104 }
105 {
106 // insert(const_iterator, value_type&&)
107 M m = {{1, 1}, {2, 2}, {4, 4}, {5, 5}};
108 expensive_comparisons = 0;
109 cheap_comparisons = 0;
110 std::same_as<typename M::iterator> auto it = m.insert(m.begin(), std::make_pair(3, 3));
111 assert(expensive_comparisons >= 2);
112 assert(cheap_comparisons == 0);
113 assert(it == m.begin() + 2);
114 assert(std::ranges::equal(m, expected));
115 }
116 {
117 // emplace(Args&&...)
118 M m = {{1, 1}, {2, 2}, {4, 4}, {5, 5}};
119 expensive_comparisons = 0;
120 cheap_comparisons = 0;
121 std::same_as<std::pair<typename M::iterator, bool>> auto p =
122 m.emplace(std::make_pair(3, 3)); // conversion happens first
123 assert(expensive_comparisons >= 2);
124 assert(cheap_comparisons == 0);
125 assert(p == std::make_pair(m.begin() + 2, true));
126 assert(std::ranges::equal(m, expected));
127 }
128}
129
130int main(int, char**) {
131 test<std::vector<CompareCounter>, std::vector<double>>();
132 test<std::deque<CompareCounter>, std::vector<double>>();
133 test<MinSequenceContainer<CompareCounter>, MinSequenceContainer<double>>();
134 test<std::vector<CompareCounter, min_allocator<CompareCounter>>, std::vector<double, min_allocator<double>>>();
135
136 {
137 // no ambiguity between insert(pos, P&&) and insert(first, last)
138 using M = std::flat_map<int, int>;
139 struct Evil {
140 operator M::value_type() const;
141 operator M::const_iterator() const;
142 };
143 std::flat_map<int, int> m;
144 ASSERT_SAME_TYPE(decltype(m.insert(Evil())), std::pair<M::iterator, bool>);
145 ASSERT_SAME_TYPE(decltype(m.insert(m.begin(), Evil())), M::iterator);
146 ASSERT_SAME_TYPE(decltype(m.insert(m.begin(), m.end())), void);
147 }
148 {
149 auto insert_func = [](auto& m, auto key_arg, auto value_arg) {
150 using FlatMap = std::decay_t<decltype(m)>;
151 using tuple_type = std::tuple<typename FlatMap::key_type, typename FlatMap::mapped_type>;
152 tuple_type t(key_arg, value_arg);
153 m.insert(t);
154 };
155 test_emplace_exception_guarantee(emplace_function&: insert_func);
156 }
157 {
158 auto insert_func_iter = [](auto& m, auto key_arg, auto value_arg) {
159 using FlatMap = std::decay_t<decltype(m)>;
160 using tuple_type = std::tuple<typename FlatMap::key_type, typename FlatMap::mapped_type>;
161 tuple_type t(key_arg, value_arg);
162 m.insert(m.begin(), t);
163 };
164 test_emplace_exception_guarantee(emplace_function&: insert_func_iter);
165 }
166 {
167 // LWG4239 std::string and C string literal
168 using M = std::flat_map<std::string, int, std::less<>>;
169 M m{{"alpha", 1}, {"beta", 2}, {"epsilon", 1}, {"eta", 3}, {"gamma", 3}};
170 auto [it, inserted] = m.insert({"alpha", 1});
171 assert(!inserted);
172 assert(it == m.begin());
173 auto it2 = m.insert(m.begin(), {"beta2", 2});
174 assert(it2 == m.begin() + 2);
175 }
176 return 0;
177}
178

source code of libcxx/test/std/containers/container.adaptors/flat.map/flat.map.modifiers/insert_transparent.pass.cpp