242 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// class flat_multimap14 15// template <class... Args>16// iterator emplace_hint(const_iterator position, Args&&... args);17 18#include <flat_map>19#include <cassert>20#include <deque>21#include <functional>22#include <vector>23 24#include "MinSequenceContainer.h"25#include "test_macros.h"26#include "../../../Emplaceable.h"27#include "DefaultOnly.h"28#include "min_allocator.h"29#include "../helpers.h"30 31#if defined(_LIBCPP_VERSION)32// spec only specifies `emplace(Args&&...)` is_constructible_v<pair<key_type, mapped_type>, Args...> is true.33// nothing mentioned for emplace_hint34template <class M, class... Args>35concept CanEmplaceHint =36 requires(M m, typename M::const_iterator i, Args&&... args) { m.emplace_hint(i, std::forward<Args>(args)...); };37 38using Map = std::flat_multimap<Emplaceable, Emplaceable>;39static_assert(CanEmplaceHint<Map>);40static_assert(CanEmplaceHint<Map, Emplaceable, Emplaceable>);41static_assert(CanEmplaceHint<Map, std::piecewise_construct_t, std::tuple<int, double>, std::tuple<int, double>>);42static_assert(!CanEmplaceHint<Map, Emplaceable>);43static_assert(!CanEmplaceHint<Map, int, double>);44#endif45 46template <class KeyContainer, class ValueContainer>47constexpr void test() {48 using Key = typename KeyContainer::value_type;49 using Value = typename ValueContainer::value_type;50 using M = std::flat_multimap<Key, Value, std::less<Key>, KeyContainer, ValueContainer>;51 using R = M::iterator;52 {53 // was empty54 M m;55 std::same_as<R> decltype(auto) r = m.emplace_hint(m.end(), typename M::value_type(2, 3.5));56 assert(r == m.begin());57 assert(m.size() == 1);58 assert(m.begin()->first == 2);59 assert(m.begin()->second == 3.5);60 }61 {62 // hint correct and no duplicates63 M m = {{0, 0.0}, {1, 1.0}, {3, 3.0}};64 auto it = m.begin() + 2;65 std::same_as<R> decltype(auto) r = m.emplace_hint(it, typename M::value_type(2, 2.0));66 assert(r == m.begin() + 2);67 assert(m.size() == 4);68 assert(r->first == 2);69 assert(r->second == 2.0);70 }71 {72 // hint correct and at the begin73 M m = {{3, 3.0}, {4, 4.0}};74 auto it = m.begin();75 std::same_as<R> decltype(auto) r = m.emplace_hint(it, typename M::value_type(2, 2.0));76 assert(r == m.begin());77 assert(m.size() == 3);78 assert(r->first == 2);79 assert(r->second == 2.0);80 }81 {82 // hint correct and at the end83 M m = {{0, 0.0}, {1, 1.0}};84 auto it = m.end();85 std::same_as<R> decltype(auto) r = m.emplace_hint(it, typename M::value_type(2, 2.0));86 assert(r == m.begin() + 2);87 assert(m.size() == 3);88 assert(r->first == 2);89 assert(r->second == 2.0);90 }91 {92 // hint correct and at first duplicate93 M m = {{0, 0.0}, {1, 1.0}, {2, 1.9}, {2, 2.1}, {3, 3.0}};94 auto it = m.begin() + 2;95 std::same_as<R> decltype(auto) r = m.emplace_hint(it, typename M::value_type(2, 2.0));96 assert(r == m.begin() + 2);97 assert(m.size() == 6);98 assert(r->first == 2);99 assert(r->second == 2.0);100 assert(std::next(r)->first == 2);101 assert(std::next(r)->second == 1.9);102 }103 {104 // hint correct and in-between duplicates105 M m = {{0, 0.0}, {1, 1.0}, {2, 1.8}, {2, 1.9}, {2, 2.1}, {3, 3.0}};106 auto it = m.begin() + 4;107 std::same_as<R> decltype(auto) r = m.emplace_hint(it, typename M::value_type(2, 2.0));108 assert(r == m.begin() + 4);109 assert(m.size() == 7);110 assert(r->first == 2);111 assert(r->second == 2.0);112 assert(std::next(r)->first == 2);113 assert(std::next(r)->second == 2.1 || std::next(r)->second == 1.9);114 }115 {116 // hint correct and after duplicates117 M m = {{0, 0.0}, {1, 1.0}, {2, 1.8}, {2, 1.9}, {2, 2.1}, {3, 3.0}};118 auto it = m.begin() + 5;119 std::same_as<R> decltype(auto) r = m.emplace_hint(it, typename M::value_type(2, 2.0));120 assert(r == m.begin() + 5);121 assert(m.size() == 7);122 assert(r->first == 2);123 assert(r->second == 2.0);124 assert(std::next(r)->first == 3);125 assert(std::next(r)->second == 3.0);126 }127 {128 // hint incorrect and no duplicates129 M m = {{0, 0.0}, {1, 1.0}, {3, 3.0}};130 auto it = m.begin() + 1;131 std::same_as<R> decltype(auto) r = m.emplace_hint(it, typename M::value_type(2, 2.0));132 assert(r == m.begin() + 2);133 assert(m.size() == 4);134 assert(r->first == 2);135 assert(r->second == 2.0);136 }137 {138 // hint incorrect and at the begin139 M m = {{0, 0.0}, {1, 1.0}};140 auto it = m.begin();141 std::same_as<R> decltype(auto) r = m.emplace_hint(it, typename M::value_type(2, 2.0));142 assert(r == m.begin() + 2);143 assert(m.size() == 3);144 assert(r->first == 2);145 assert(r->second == 2.0);146 }147 {148 // hint incorrect and at the end149 M m = {{3, 3.0}, {4, 4.0}};150 auto it = m.end();151 std::same_as<R> decltype(auto) r = m.emplace_hint(it, typename M::value_type(2, 2.0));152 assert(r == m.begin());153 assert(m.size() == 3);154 assert(r->first == 2);155 assert(r->second == 2.0);156 }157 {158 // hint incorrect and before the first duplicate159 M m = {{0, 0.0}, {1, 1.0}, {2, 1.8}, {2, 1.9}, {2, 2.1}, {3, 3.0}};160 auto it = m.begin();161 std::same_as<R> decltype(auto) r = m.emplace_hint(it, typename M::value_type(2, 2.0));162 // the result is as left as possible163 assert(r == m.begin() + 2);164 assert(m.size() == 7);165 assert(r->first == 2);166 assert(r->second == 2.0);167 assert(std::next(r)->first == 2);168 assert(std::next(r)->second == 1.8);169 }170 {171 // hint incorrect and after the last duplicate172 M m = {{0, 0.0}, {1, 1.0}, {2, 1.8}, {2, 1.9}, {2, 2.1}, {3, 3.0}, {4, 4.0}};173 auto it = m.begin() + 6;174 std::same_as<R> decltype(auto) r = m.emplace_hint(it, typename M::value_type(2, 2.0));175 // the result is as right as possible176 assert(r == m.begin() + 5);177 assert(m.size() == 8);178 assert(r->first == 2);179 assert(r->second == 2.0);180 assert(std::next(r)->first == 3);181 assert(std::next(r)->second == 3.0);182 }183}184 185template <class KeyContainer, class ValueContainer>186constexpr void test_emplaceable() {187 using M = std::flat_multimap<int, Emplaceable, std::less<int>, KeyContainer, ValueContainer>;188 using R = M::iterator;189 190 M m;191 ASSERT_SAME_TYPE(decltype(m.emplace_hint(m.cbegin())), R);192 R r = m.emplace_hint(m.end(), std::piecewise_construct, std::forward_as_tuple(2), std::forward_as_tuple());193 assert(r == m.begin());194 assert(m.size() == 1);195 assert(r->first == 2);196 assert(r->second == Emplaceable());197 r = m.emplace_hint(m.end(), std::piecewise_construct, std::forward_as_tuple(1), std::forward_as_tuple(2, 3.5));198 assert(r == m.begin());199 assert(m.size() == 2);200 assert(r->first == 1);201 assert(r->second == Emplaceable(2, 3.5));202 r = m.emplace_hint(m.end(), std::piecewise_construct, std::forward_as_tuple(1), std::forward_as_tuple(2, 3.6));203 assert(r == m.begin() + 1);204 assert(m.size() == 3);205 assert(r->first == 1);206 assert(r->second == Emplaceable(2, 3.6));207}208 209constexpr bool test() {210 test<std::vector<int>, std::vector<double>>();211#ifndef __cpp_lib_constexpr_deque212 if (!TEST_IS_CONSTANT_EVALUATED)213#endif214 test<std::deque<int>, std::vector<double>>();215 test<MinSequenceContainer<int>, MinSequenceContainer<double>>();216 test<std::vector<int, min_allocator<int>>, std::vector<double, min_allocator<double>>>();217 218 test_emplaceable<std::vector<int>, std::vector<Emplaceable>>();219#ifndef __cpp_lib_constexpr_deque220 if (!TEST_IS_CONSTANT_EVALUATED)221#endif222 test_emplaceable<std::deque<int>, std::vector<Emplaceable>>();223 test_emplaceable<MinSequenceContainer<int>, MinSequenceContainer<Emplaceable>>();224 test_emplaceable<std::vector<int, min_allocator<int>>, std::vector<Emplaceable, min_allocator<Emplaceable>>>();225 if (!TEST_IS_CONSTANT_EVALUATED) {226 auto emplace_func = [](auto& m, auto key_arg, auto value_arg) {227 m.emplace_hint(m.begin(), std::piecewise_construct, std::tuple(key_arg), std::tuple(value_arg));228 };229 test_emplace_exception_guarantee(emplace_func);230 }231 return true;232}233 234int main(int, char**) {235 test();236#if TEST_STD_VER >= 26237 static_assert(test());238#endif239 240 return 0;241}242