364 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#include <algorithm>14#include <array>15#include <cassert>16#include <climits>17#include <deque>18#include <initializer_list>19#include <list>20#include <flat_map>21#include <functional>22#include <ranges>23#include <type_traits>24#include <utility>25#include <vector>26 27#include "deduction_guides_sfinae_checks.h"28#include "test_allocator.h"29 30using P = std::pair<int, long>;31using PC = std::pair<const int, long>;32 33void test_copy() {34 {35 std::flat_multimap<long, short> source = {{1, 2}, {1, 3}};36 std::flat_multimap s(source);37 ASSERT_SAME_TYPE(decltype(s), decltype(source));38 assert(s == source);39 }40 {41 std::flat_multimap<long, short, std::greater<long>> source = {{1, 2}, {1, 3}};42 std::flat_multimap s{source}; // braces instead of parens43 ASSERT_SAME_TYPE(decltype(s), decltype(source));44 assert(s == source);45 }46 {47 std::flat_multimap<long, short, std::greater<long>> source = {{1, 2}, {1, 3}};48 std::flat_multimap s(source, std::allocator<int>());49 ASSERT_SAME_TYPE(decltype(s), decltype(source));50 assert(s == source);51 }52}53 54void test_containers() {55 std::deque<int, test_allocator<int>> ks({1, 2, 1, 2, 2, INT_MAX, 3}, test_allocator<int>(0, 42));56 std::deque<short, test_allocator<short>> vs({1, 2, 3, 4, 5, 3, 4}, test_allocator<int>(0, 43));57 std::deque<int, test_allocator<int>> sorted_ks({1, 1, 2, 2, 2, 3, INT_MAX}, test_allocator<int>(0, 42));58 std::deque<short, test_allocator<short>> sorted_vs({1, 3, 2, 4, 5, 4, 3}, test_allocator<int>(0, 43));59 const std::pair<int, short> expected[] = {{1, 1}, {1, 3}, {2, 2}, {2, 4}, {2, 5}, {3, 4}, {INT_MAX, 3}};60 {61 std::flat_multimap s(ks, vs);62 63 ASSERT_SAME_TYPE(decltype(s), std::flat_multimap<int, short, std::less<int>, decltype(ks), decltype(vs)>);64 assert(std::ranges::equal(s, expected));65 assert(s.keys().get_allocator().get_id() == 42);66 assert(s.values().get_allocator().get_id() == 43);67 }68 {69 std::flat_multimap s(std::sorted_equivalent, sorted_ks, sorted_vs);70 71 ASSERT_SAME_TYPE(decltype(s), std::flat_multimap<int, short, std::less<int>, decltype(ks), decltype(vs)>);72 assert(std::ranges::equal(s, expected));73 assert(s.keys().get_allocator().get_id() == 42);74 assert(s.values().get_allocator().get_id() == 43);75 }76 {77 std::flat_multimap s(ks, vs, test_allocator<long>(0, 44));78 79 ASSERT_SAME_TYPE(decltype(s), std::flat_multimap<int, short, std::less<int>, decltype(ks), decltype(vs)>);80 assert(std::ranges::equal(s, expected));81 assert(s.keys().get_allocator().get_id() == 44);82 assert(s.values().get_allocator().get_id() == 44);83 }84 {85 std::flat_multimap s(std::sorted_equivalent, sorted_ks, sorted_vs, test_allocator<long>(0, 44));86 87 ASSERT_SAME_TYPE(decltype(s), std::flat_multimap<int, short, std::less<int>, decltype(ks), decltype(vs)>);88 assert(std::ranges::equal(s, expected));89 assert(s.keys().get_allocator().get_id() == 44);90 assert(s.values().get_allocator().get_id() == 44);91 }92}93 94void test_containers_compare() {95 std::deque<int, test_allocator<int>> ks({1, 2, 1, 2, 2, INT_MAX, 3}, test_allocator<int>(0, 42));96 std::deque<short, test_allocator<short>> vs({1, 2, 3, 4, 5, 3, 4}, test_allocator<int>(0, 43));97 std::deque<int, test_allocator<int>> sorted_ks({INT_MAX, 3, 2, 2, 2, 1, 1}, test_allocator<int>(0, 42));98 std::deque<short, test_allocator<short>> sorted_vs({3, 4, 2, 4, 5, 1, 3}, test_allocator<int>(0, 43));99 const std::pair<int, short> expected[] = {{INT_MAX, 3}, {3, 4}, {2, 2}, {2, 4}, {2, 5}, {1, 1}, {1, 3}};100 {101 std::flat_multimap s(ks, vs, std::greater<int>());102 103 ASSERT_SAME_TYPE(decltype(s), std::flat_multimap<int, short, std::greater<int>, decltype(ks), decltype(vs)>);104 assert(std::ranges::equal(s, expected));105 assert(s.keys().get_allocator().get_id() == 42);106 assert(s.values().get_allocator().get_id() == 43);107 }108 {109 std::flat_multimap s(std::sorted_equivalent, sorted_ks, sorted_vs, std::greater<int>());110 111 ASSERT_SAME_TYPE(decltype(s), std::flat_multimap<int, short, std::greater<int>, decltype(ks), decltype(vs)>);112 assert(std::ranges::equal(s, expected));113 assert(s.keys().get_allocator().get_id() == 42);114 assert(s.values().get_allocator().get_id() == 43);115 }116 {117 std::flat_multimap s(ks, vs, std::greater<int>(), test_allocator<long>(0, 44));118 119 ASSERT_SAME_TYPE(decltype(s), std::flat_multimap<int, short, std::greater<int>, decltype(ks), decltype(vs)>);120 assert(std::ranges::equal(s, expected));121 assert(s.keys().get_allocator().get_id() == 44);122 assert(s.values().get_allocator().get_id() == 44);123 }124 {125 std::flat_multimap s(126 std::sorted_equivalent, sorted_ks, sorted_vs, std::greater<int>(), test_allocator<long>(0, 44));127 128 ASSERT_SAME_TYPE(decltype(s), std::flat_multimap<int, short, std::greater<int>, decltype(ks), decltype(vs)>);129 assert(std::ranges::equal(s, expected));130 assert(s.keys().get_allocator().get_id() == 44);131 assert(s.values().get_allocator().get_id() == 44);132 }133}134 135void test_iter_iter() {136 const P arr[] = {{1, 1L}, {2, 2L}, {1, 1L}, {INT_MAX, 1L}, {3, 1L}};137 const P sorted_arr[] = {{1, 1L}, {1, 1L}, {2, 2L}, {3, 1L}, {INT_MAX, 1L}};138 const PC arrc[] = {{1, 1L}, {2, 2L}, {1, 1L}, {INT_MAX, 1L}, {3, 1L}};139 const PC sorted_arrc[] = {{1, 1L}, {1, 1L}, {2, 2L}, {3, 1L}, {INT_MAX, 1L}};140 {141 std::flat_multimap m(std::begin(arr), std::end(arr));142 143 ASSERT_SAME_TYPE(decltype(m), std::flat_multimap<int, long>);144 assert(std::ranges::equal(m, sorted_arr));145 }146 {147 std::flat_multimap m(std::begin(arrc), std::end(arrc));148 149 ASSERT_SAME_TYPE(decltype(m), std::flat_multimap<int, long>);150 assert(std::ranges::equal(m, sorted_arr));151 }152 {153 std::flat_multimap m(std::sorted_equivalent, std::begin(sorted_arr), std::end(sorted_arr));154 155 ASSERT_SAME_TYPE(decltype(m), std::flat_multimap<int, long>);156 assert(std::ranges::equal(m, sorted_arr));157 }158 {159 std::flat_multimap m(std::sorted_equivalent, std::begin(sorted_arrc), std::end(sorted_arrc));160 161 ASSERT_SAME_TYPE(decltype(m), std::flat_multimap<int, long>);162 assert(std::ranges::equal(m, sorted_arr));163 }164 {165 std::flat_multimap<int, short> mo;166 std::flat_multimap m(mo.begin(), mo.end());167 ASSERT_SAME_TYPE(decltype(m), decltype(mo));168 }169 {170 std::flat_multimap<int, short> mo;171 std::flat_multimap m(mo.cbegin(), mo.cend());172 ASSERT_SAME_TYPE(decltype(m), decltype(mo));173 }174 {175 std::pair<int, int> source[3] = {{1, 1}, {1, 1}, {3, 3}};176 std::flat_multimap s = {source, source + 3}; // flat_multimap(InputIterator, InputIterator)177 ASSERT_SAME_TYPE(decltype(s), std::flat_multimap<int, int>);178 assert(s.size() == 3);179 }180 {181 std::pair<int, int> source[3] = {{1, 1}, {1, 1}, {3, 3}};182 std::flat_multimap s{source, source + 3}; // flat_multimap(InputIterator, InputIterator)183 ASSERT_SAME_TYPE(decltype(s), std::flat_multimap<int, int>);184 assert(s.size() == 3);185 }186 {187 std::pair<int, int> source[3] = {{1, 1}, {1, 2}, {3, 3}};188 std::flat_multimap s{189 std::sorted_equivalent, source, source + 3}; // flat_multimap(sorted_equivalent_t, InputIterator, InputIterator)190 static_assert(std::is_same_v<decltype(s), std::flat_multimap<int, int>>);191 assert(s.size() == 3);192 }193}194 195void test_iter_iter_compare() {196 const P arr[] = {{1, 1L}, {2, 2L}, {1, 1L}, {INT_MAX, 1L}, {3, 1L}};197 const P sorted_arr[] = {{INT_MAX, 1L}, {3, 1L}, {2, 2L}, {1, 1L}, {1, 1L}};198 const PC arrc[] = {{1, 1L}, {2, 2L}, {1, 1L}, {INT_MAX, 1L}, {3, 1L}};199 const PC sorted_arrc[] = {{INT_MAX, 1L}, {3, 1L}, {2, 2L}, {1, 1L}, {1, 1L}};200 using C = std::greater<long long>;201 {202 std::flat_multimap m(std::begin(arr), std::end(arr), C());203 204 ASSERT_SAME_TYPE(decltype(m), std::flat_multimap<int, long, C>);205 assert(std::ranges::equal(m, sorted_arr));206 }207 {208 std::flat_multimap m(std::begin(arrc), std::end(arrc), C());209 210 ASSERT_SAME_TYPE(decltype(m), std::flat_multimap<int, long, C>);211 assert(std::ranges::equal(m, sorted_arr));212 }213 {214 std::flat_multimap m(std::sorted_equivalent, std::begin(sorted_arr), std::end(sorted_arr), C());215 216 ASSERT_SAME_TYPE(decltype(m), std::flat_multimap<int, long, C>);217 assert(std::ranges::equal(m, sorted_arr));218 }219 {220 std::flat_multimap m(std::sorted_equivalent, std::begin(sorted_arrc), std::end(sorted_arrc), C());221 222 ASSERT_SAME_TYPE(decltype(m), std::flat_multimap<int, long, C>);223 assert(std::ranges::equal(m, sorted_arr));224 }225 {226 std::flat_multimap<int, short> mo;227 std::flat_multimap m(mo.begin(), mo.end(), C());228 ASSERT_SAME_TYPE(decltype(m), std::flat_multimap<int, short, C>);229 }230 {231 std::flat_multimap<int, short> mo;232 std::flat_multimap m(mo.cbegin(), mo.cend(), C());233 ASSERT_SAME_TYPE(decltype(m), std::flat_multimap<int, short, C>);234 }235}236 237void test_initializer_list() {238 const P sorted_arr[] = {{1, 1L}, {1, 1L}, {2, 2L}, {3, 1L}, {INT_MAX, 1L}};239 {240 std::flat_multimap m{std::pair{1, 1L}, {2, 2L}, {1, 1L}, {INT_MAX, 1L}, {3, 1L}};241 242 ASSERT_SAME_TYPE(decltype(m), std::flat_multimap<int, long>);243 assert(std::ranges::equal(m, sorted_arr));244 }245 {246 std::flat_multimap m(std::sorted_equivalent, {std::pair{1, 1L}, {1, 1L}, {2, 2L}, {3, 1L}, {INT_MAX, 1L}});247 248 ASSERT_SAME_TYPE(decltype(m), std::flat_multimap<int, long>);249 assert(std::ranges::equal(m, sorted_arr));250 }251 {252 std::flat_multimap s = {std::make_pair(1, 'a')}; // flat_multimap(initializer_list<pair<int, char>>)253 ASSERT_SAME_TYPE(decltype(s), std::flat_multimap<int, char>);254 assert(s.size() == 1);255 }256 {257 using M = std::flat_multimap<int, short>;258 M m;259 std::flat_multimap s = {std::make_pair(m, m)}; // flat_multimap(initializer_list<pair<M, M>>)260 ASSERT_SAME_TYPE(decltype(s), std::flat_multimap<M, M>);261 assert(s.size() == 1);262 assert(s.find(m)->second == m);263 }264}265 266void test_initializer_list_compare() {267 const P sorted_arr[] = {{INT_MAX, 1L}, {3, 1L}, {2, 2L}, {1, 1L}, {1, 1L}};268 using C = std::greater<long long>;269 {270 std::flat_multimap m({std::pair{1, 1L}, {2, 2L}, {1, 1L}, {INT_MAX, 1L}, {3, 1L}}, C());271 272 ASSERT_SAME_TYPE(decltype(m), std::flat_multimap<int, long, C>);273 assert(std::ranges::equal(m, sorted_arr));274 }275 {276 std::flat_multimap m(std::sorted_equivalent, {std::pair{INT_MAX, 1L}, {3, 1L}, {2, 2L}, {1, 1L}, {1, 1L}}, C());277 278 ASSERT_SAME_TYPE(decltype(m), std::flat_multimap<int, long, C>);279 assert(std::ranges::equal(m, sorted_arr));280 }281}282 283void test_from_range() {284 std::list<std::pair<int, short>> r = {{1, 1}, {2, 2}, {1, 1}, {INT_MAX, 4}, {3, 5}};285 const std::pair<int, short> expected[] = {{1, 1}, {1, 1}, {2, 2}, {3, 5}, {INT_MAX, 4}};286 {287 std::flat_multimap s(std::from_range, r);288 ASSERT_SAME_TYPE(decltype(s), std::flat_multimap<int, short, std::less<int>>);289 assert(std::ranges::equal(s, expected));290 }291 {292 std::flat_multimap s(std::from_range, r, test_allocator<long>(0, 42));293 ASSERT_SAME_TYPE(294 decltype(s),295 std::flat_multimap<int,296 short,297 std::less<int>,298 std::vector<int, test_allocator<int>>,299 std::vector<short, test_allocator<short>>>);300 assert(std::ranges::equal(s, expected));301 assert(s.keys().get_allocator().get_id() == 42);302 assert(s.values().get_allocator().get_id() == 42);303 }304}305 306void test_from_range_compare() {307 std::list<std::pair<int, short>> r = {{1, 1}, {2, 2}, {1, 1}, {INT_MAX, 4}, {3, 5}};308 const std::pair<int, short> expected[] = {{INT_MAX, 4}, {3, 5}, {2, 2}, {1, 1}, {1, 1}};309 {310 std::flat_multimap s(std::from_range, r, std::greater<int>());311 ASSERT_SAME_TYPE(decltype(s), std::flat_multimap<int, short, std::greater<int>>);312 assert(std::ranges::equal(s, expected));313 }314 {315 std::flat_multimap s(std::from_range, r, std::greater<int>(), test_allocator<long>(0, 42));316 ASSERT_SAME_TYPE(317 decltype(s),318 std::flat_multimap<int,319 short,320 std::greater<int>,321 std::vector<int, test_allocator<int>>,322 std::vector<short, test_allocator<short>>>);323 assert(std::ranges::equal(s, expected));324 assert(s.keys().get_allocator().get_id() == 42);325 assert(s.values().get_allocator().get_id() == 42);326 }327}328 329void test_tuple_like_deduction() {330 std::vector<std::pair<const int, float>> pair_vec = {{1, 1.1f}, {2, 2.2f}, {3, 3.3f}};331 std::flat_multimap fmm1(pair_vec.begin(), pair_vec.end());332 ASSERT_SAME_TYPE(decltype(fmm1), std::flat_multimap<int, float>);333 334 std::vector<std::tuple<int, double>> tuple_vec = {{10, 1.1}, {20, 2.2}, {30, 3.3}};335 std::flat_multimap fmm2(tuple_vec.begin(), tuple_vec.end());336 ASSERT_SAME_TYPE(decltype(fmm2), std::flat_multimap<int, double>);337 338 std::vector<std::array<long, 2>> array_vec = {{100L, 101L}, {200L, 201L}, {300L, 301L}};339 std::flat_multimap fmm3(array_vec.begin(), array_vec.end());340 ASSERT_SAME_TYPE(decltype(fmm3), std::flat_multimap<long, long>);341 342 std::vector<std::pair<int, char>> non_const_key_pair_vec = {{5, 'a'}, {6, 'b'}};343 std::flat_multimap fmm4(non_const_key_pair_vec.begin(), non_const_key_pair_vec.end());344 ASSERT_SAME_TYPE(decltype(fmm4), std::flat_multimap<int, char>);345}346 347int main(int, char**) {348 // Each test function also tests the sorted_equivalent-prefixed and allocator-suffixed overloads.349 test_copy();350 test_containers();351 test_containers_compare();352 test_iter_iter();353 test_iter_iter_compare();354 test_initializer_list();355 test_initializer_list_compare();356 test_from_range();357 test_from_range_compare();358 test_tuple_like_deduction();359 360 AssociativeContainerDeductionGuidesSfinaeAway<std::flat_multimap, std::flat_multimap<int, short>>();361 362 return 0;363}364