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

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