261 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9// UNSUPPORTED: c++03, c++11, c++14, c++17, c++2010 11// <flat_map>12 13// flat_multimap(key_container_type key_cont, mapped_container_type mapped_cont,14// const key_compare& comp = key_compare());15// template<class Allocator>16// flat_multimap(const key_container_type& key_cont, const mapped_container_type& mapped_cont,17// const Allocator& a);18// template<class Alloc>19// flat_multimap(const key_container_type& key_cont, const mapped_container_type& mapped_cont,20// const key_compare& comp, const Alloc& a);21 22#include <algorithm>23#include <deque>24#include <flat_map>25#include <functional>26#include <vector>27 28#include "min_allocator.h"29#include "MoveOnly.h"30#include "test_allocator.h"31#include "test_iterators.h"32#include "test_macros.h"33#include "../helpers.h"34#include "../../../test_compare.h"35 36struct P {37 int first;38 int second;39 template <class T, class U>40 constexpr bool operator==(const std::pair<T, U>& rhs) const {41 return MoveOnly(first) == rhs.first && MoveOnly(second) == rhs.second;42 }43};44 45template <template <class...> class KeyContainer, template <class...> class ValueContainer>46constexpr void test() {47 {48 // flat_multimap(key_container_type , mapped_container_type)49 using M = std::flat_multimap<int, short, std::less<int>, KeyContainer<int>, ValueContainer<short>>;50 KeyContainer<int> ks = {1, 1, 1, 2, 2, 3, 2, 3, 3};51 ValueContainer<short> vs = {1, 2, 3, 4, 5, 6, 7, 8, 9};52 auto m = M(ks, vs);53 assert((m.keys() == KeyContainer<int>{1, 1, 1, 2, 2, 2, 3, 3, 3}));54 check_possible_values(55 m.values(),56 std::vector<std::vector<short>>{57 {1, 2, 3},58 {1, 2, 3},59 {1, 2, 3},60 {4, 5, 7},61 {4, 5, 7},62 {4, 5, 7},63 {6, 8, 9},64 {6, 8, 9},65 {6, 8, 9},66 });67 68 // explicit(false)69 M m2 = {ks, vs};70 assert(m2 == m);71 72 m = M(std::move(ks), std::move(vs));73 assert(ks.empty()); // it was moved-from74 assert(vs.empty()); // it was moved-from75 assert((m.keys() == KeyContainer<int>{1, 1, 1, 2, 2, 2, 3, 3, 3}));76 check_possible_values(77 m.values(),78 std::vector<std::vector<short>>{79 {1, 2, 3},80 {1, 2, 3},81 {1, 2, 3},82 {4, 5, 7},83 {4, 5, 7},84 {4, 5, 7},85 {6, 8, 9},86 {6, 8, 9},87 {6, 8, 9},88 });89 }90 {91 // flat_multimap(key_container_type , mapped_container_type)92 // move-only93 P expected[] = {{3, 2}, {2, 1}, {1, 3}};94 using Ks = KeyContainer<int, min_allocator<int>>;95 using Vs = ValueContainer<MoveOnly, min_allocator<MoveOnly>>;96 using M = std::flat_multimap<int, MoveOnly, std::greater<int>, Ks, Vs>;97 Ks ks = {1, 3, 2};98 Vs vs;99 vs.push_back(3);100 vs.push_back(2);101 vs.push_back(1);102 auto m = M(std::move(ks), std::move(vs));103 assert(ks.empty()); // it was moved-from104 assert(vs.empty()); // it was moved-from105 assert(std::ranges::equal(m, expected, std::equal_to<>()));106 }107 {108 // flat_multimap(key_container_type , mapped_container_type)109 // container's allocators are used110 using A = test_allocator<int>;111 using M = std::flat_multimap<int, int, std::less<int>, KeyContainer<int, A>, ValueContainer<int, A>>;112 auto ks = KeyContainer<int, A>({1, 1, 1, 2, 2, 3, 2, 3, 3}, A(5));113 auto vs = ValueContainer<int, A>({1, 1, 1, 2, 2, 3, 2, 3, 3}, A(6));114 auto m = M(std::move(ks), std::move(vs));115 assert(ks.empty()); // it was moved-from116 assert(vs.empty()); // it was moved-from117 assert(std::ranges::equal(m.keys(), std::vector{1, 1, 1, 2, 2, 2, 3, 3, 3}));118 assert(std::ranges::equal(m.values(), std::vector{1, 1, 1, 2, 2, 2, 3, 3, 3}));119 assert(m.keys().get_allocator() == A(5));120 assert(m.values().get_allocator() == A(6));121 }122 {123 // flat_multimap(key_container_type , mapped_container_type, key_compare)124 using C = test_less<int>;125 using M = std::flat_multimap<int, char, C, KeyContainer<int>, ValueContainer<char>>;126 KeyContainer<int> ks = {1, 1, 1, 2, 2, 3, 2, 3, 3};127 ValueContainer<char> vs = {1, 2, 3, 4, 5, 6, 7, 8, 9};128 auto m = M(ks, vs, C(4));129 assert((m.keys() == KeyContainer<int>{1, 1, 1, 2, 2, 2, 3, 3, 3}));130 check_possible_values(131 m.values(),132 std::vector<std::vector<char>>{133 {1, 2, 3},134 {1, 2, 3},135 {1, 2, 3},136 {4, 5, 7},137 {4, 5, 7},138 {4, 5, 7},139 {6, 8, 9},140 {6, 8, 9},141 {6, 8, 9},142 });143 assert(m.key_comp() == C(4));144 145 // explicit(false)146 M m2 = {ks, vs, C(4)};147 assert(m2 == m);148 assert(m2.key_comp() == C(4));149 }150 {151 // flat_multimap(key_container_type , mapped_container_type, const Allocator&)152 using A = test_allocator<int>;153 using M = std::flat_multimap<int, int, std::less<int>, KeyContainer<int, A>, ValueContainer<int, A>>;154 auto ks = KeyContainer<int, A>({1, 1, 1, 2, 2, 3, 2, 3, 3}, A(5));155 auto vs = ValueContainer<int, A>({1, 1, 1, 2, 2, 3, 2, 3, 3}, A(6));156 auto m = M(ks, vs, A(4)); // replaces the allocators157 assert(!ks.empty()); // it was an lvalue above158 assert(!vs.empty()); // it was an lvalue above159 assert(std::ranges::equal(m.keys(), std::vector{1, 1, 1, 2, 2, 2, 3, 3, 3}));160 assert(std::ranges::equal(m.values(), std::vector{1, 1, 1, 2, 2, 2, 3, 3, 3}));161 assert(m.keys().get_allocator() == A(4));162 assert(m.values().get_allocator() == A(4));163 }164 {165 // flat_multimap(key_container_type , mapped_container_type, const Allocator&)166 // explicit(false)167 using A = test_allocator<int>;168 using M = std::flat_multimap<int, int, std::less<int>, KeyContainer<int, A>, ValueContainer<int, A>>;169 auto ks = KeyContainer<int, A>({1, 1, 1, 2, 2, 3, 2, 3, 3}, A(5));170 auto vs = ValueContainer<int, A>({1, 1, 1, 2, 2, 3, 2, 3, 3}, A(6));171 M m = {ks, vs, A(4)}; // implicit ctor172 assert(!ks.empty()); // it was an lvalue above173 assert(!vs.empty()); // it was an lvalue above174 assert(std::ranges::equal(m.keys(), std::vector{1, 1, 1, 2, 2, 2, 3, 3, 3}));175 assert(std::ranges::equal(m.values(), std::vector{1, 1, 1, 2, 2, 2, 3, 3, 3}));176 assert(m.keys().get_allocator() == A(4));177 assert(m.values().get_allocator() == A(4));178 }179 180 {181 // flat_multimap(key_container_type , mapped_container_type, key_compare, const Allocator&)182 using C = test_less<int>;183 using A = test_allocator<int>;184 using M = std::flat_multimap<int, int, C, std::vector<int, A>, std::vector<int, A>>;185 std::vector<int, A> ks = {1, 1, 1, 2, 2, 3, 2, 3, 3};186 std::vector<int, A> vs = {1, 2, 3, 4, 5, 6, 7, 8, 9};187 auto m = M(ks, vs, C(4), A(5));188 assert(std::ranges::equal(m.keys(), std::vector{1, 1, 1, 2, 2, 2, 3, 3, 3}));189 check_possible_values(190 m.values(),191 std::vector<std::vector<int>>{192 {1, 2, 3},193 {1, 2, 3},194 {1, 2, 3},195 {4, 5, 7},196 {4, 5, 7},197 {4, 5, 7},198 {6, 8, 9},199 {6, 8, 9},200 {6, 8, 9},201 });202 assert(m.key_comp() == C(4));203 assert(m.keys().get_allocator() == A(5));204 assert(m.values().get_allocator() == A(5));205 206 // explicit(false)207 M m2 = {ks, vs, C(4), A(5)};208 assert(m2 == m);209 assert(m2.key_comp() == C(4));210 assert(m2.keys().get_allocator() == A(5));211 assert(m2.values().get_allocator() == A(5));212 }213}214 215bool constexpr test() {216 {217 // The constructors in this subclause shall not participate in overload218 // resolution unless uses_allocator_v<key_container_type, Alloc> is true219 // and uses_allocator_v<mapped_container_type, Alloc> is true.220 221 using C = test_less<int>;222 using A1 = test_allocator<int>;223 using A2 = other_allocator<int>;224 using V1 = std::vector<int, A1>;225 using V2 = std::vector<int, A2>;226 using M1 = std::flat_multimap<int, int, C, V1, V1>;227 using M2 = std::flat_multimap<int, int, C, V1, V2>;228 using M3 = std::flat_multimap<int, int, C, V2, V1>;229 static_assert(std::is_constructible_v<M1, const V1&, const V1&, const A1&>);230 static_assert(!std::is_constructible_v<M1, const V1&, const V1&, const A2&>);231 static_assert(!std::is_constructible_v<M2, const V1&, const V2&, const A2&>);232 static_assert(!std::is_constructible_v<M3, const V2&, const V1&, const A2&>);233 234 static_assert(std::is_constructible_v<M1, const V1&, const V1&, const C&, const A1&>);235 static_assert(!std::is_constructible_v<M1, const V1&, const V1&, const C&, const A2&>);236 static_assert(!std::is_constructible_v<M2, const V1&, const V2&, const C&, const A2&>);237 static_assert(!std::is_constructible_v<M3, const V2&, const V1&, const C&, const A2&>);238 }239 240 test<std::vector, std::vector>();241 242#ifndef __cpp_lib_constexpr_deque243 if (!TEST_IS_CONSTANT_EVALUATED)244#endif245 {246 test<std::deque, std::vector>();247 test<std::deque, std::deque>();248 }249 250 return true;251}252 253int main(int, char**) {254 test();255#if TEST_STD_VER >= 26256 static_assert(test());257#endif258 259 return 0;260}261