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

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