200 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// template <class... Args>14// iterator emplace_hint(const_iterator position, Args&&... args);15 16#include <flat_map>17#include <cassert>18#include <deque>19#include <functional>20#include <type_traits>21#include <vector>22 23#include "MinSequenceContainer.h"24#include "test_macros.h"25#include "../../../Emplaceable.h"26#include "DefaultOnly.h"27#include "min_allocator.h"28#include "../helpers.h"29 30#if defined(_LIBCPP_VERSION)31// spec only specifies `emplace(Args&&...)` is_constructible_v<pair<key_type, mapped_type>, Args...> is true.32// nothing mentioned for emplace_hint33template <class M, class... Args>34concept CanEmplaceHint =35 requires(M m, typename M::const_iterator i, Args&&... args) { m.emplace_hint(i, std::forward<Args>(args)...); };36 37using Map = std::flat_map<Emplaceable, Emplaceable>;38static_assert(CanEmplaceHint<Map>);39static_assert(CanEmplaceHint<Map, Emplaceable, Emplaceable>);40static_assert(CanEmplaceHint<Map, std::piecewise_construct_t, std::tuple<int, double>, std::tuple<int, double>>);41static_assert(!CanEmplaceHint<Map, Emplaceable>);42static_assert(!CanEmplaceHint<Map, int, double>);43#endif44 45template <class KeyContainer, class ValueContainer>46constexpr void test() {47 using Key = typename KeyContainer::value_type;48 using Value = typename ValueContainer::value_type;49 using M = std::flat_map<Key, Value, std::less<Key>, KeyContainer, ValueContainer>;50 using R = M::iterator;51 {52 // was empty53 M m;54 std::same_as<R> decltype(auto) r = m.emplace_hint(m.end(), typename M::value_type(2, 3.5));55 assert(r == m.begin());56 assert(m.size() == 1);57 assert(r->first == 2);58 assert(r->second == 3.5);59 }60 {61 // hints correct at the begin62 M m = {{3, 3.0}, {4, 4.0}};63 auto hint = m.begin();64 std::same_as<R> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(2, 2.0));65 assert(r == m.begin());66 assert(m.size() == 3);67 assert(r->first == 2);68 assert(r->second == 2.0);69 }70 {71 // hints correct in the middle72 M m = {{0, 0.0}, {1, 1.0}, {3, 3.0}, {4, 4.0}};73 auto hint = m.begin() + 2;74 std::same_as<R> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(2, 2.0));75 assert(r == m.begin() + 2);76 assert(m.size() == 5);77 assert(r->first == 2);78 assert(r->second == 2.0);79 }80 {81 // hints correct at the end82 M m = {{0, 0.0}, {1, 1.0}};83 auto hint = m.end();84 std::same_as<R> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(2, 2.0));85 assert(r == m.begin() + 2);86 assert(m.size() == 3);87 assert(r->first == 2);88 assert(r->second == 2.0);89 }90 {91 // hints correct but key already exists92 M m = {{0, 0.0}, {1, 1.0}, {2, 1.9}, {3, 3.0}, {4, 4.0}};93 auto hint = m.begin() + 2;94 std::same_as<R> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(2, 2.0));95 assert(r == m.begin() + 2);96 assert(m.size() == 5);97 assert(r->first == 2);98 assert(r->second == 1.9);99 }100 {101 // hints incorrectly at the begin102 M m = {{1, 1.0}, {4, 4.0}};103 auto hint = m.begin();104 std::same_as<R> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(2, 2.0));105 assert(r == m.begin() + 1);106 assert(m.size() == 3);107 assert(r->first == 2);108 assert(r->second == 2.0);109 }110 {111 // hints incorrectly in the middle112 M m = {{0, 0.0}, {1, 1.0}, {3, 3.0}, {4, 4.0}};113 auto hint = m.begin() + 1;114 std::same_as<R> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(2, 2.0));115 assert(r == m.begin() + 2);116 assert(m.size() == 5);117 assert(r->first == 2);118 assert(r->second == 2.0);119 }120 {121 // hints incorrectly at the end122 M m = {{0, 0.0}, {3, 3.0}};123 auto hint = m.end();124 std::same_as<R> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(2, 2.0));125 assert(r == m.begin() + 1);126 assert(m.size() == 3);127 assert(r->first == 2);128 assert(r->second == 2.0);129 }130 {131 // hints incorrect and key already exists132 M m = {{0, 0.0}, {1, 1.0}, {2, 1.9}, {3, 3.0}, {4, 4.0}};133 auto hint = m.begin();134 std::same_as<R> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(2, 2.0));135 assert(r == m.begin() + 2);136 assert(m.size() == 5);137 assert(r->first == 2);138 assert(r->second == 1.9);139 }140}141 142template <class KeyContainer, class ValueContainer>143constexpr void test_emplaceable() {144 using M = std::flat_map<int, Emplaceable, std::less<int>, KeyContainer, ValueContainer>;145 using R = M::iterator;146 147 M m;148 ASSERT_SAME_TYPE(decltype(m.emplace_hint(m.cbegin())), R);149 R r = m.emplace_hint(m.end(), std::piecewise_construct, std::forward_as_tuple(2), std::forward_as_tuple());150 assert(r == m.begin());151 assert(m.size() == 1);152 assert(m.begin()->first == 2);153 assert(m.begin()->second == Emplaceable());154 r = m.emplace_hint(m.end(), std::piecewise_construct, std::forward_as_tuple(1), std::forward_as_tuple(2, 3.5));155 assert(r == m.begin());156 assert(m.size() == 2);157 assert(m.begin()->first == 1);158 assert(m.begin()->second == Emplaceable(2, 3.5));159 r = m.emplace_hint(m.end(), std::piecewise_construct, std::forward_as_tuple(1), std::forward_as_tuple(2, 3.5));160 assert(r == m.begin());161 assert(m.size() == 2);162 assert(m.begin()->first == 1);163 assert(m.begin()->second == Emplaceable(2, 3.5));164}165 166constexpr bool test() {167 test<std::vector<int>, std::vector<double>>();168#ifndef __cpp_lib_constexpr_deque169 if (!TEST_IS_CONSTANT_EVALUATED)170#endif171 {172 test<std::deque<int>, std::vector<double>>();173 test_emplaceable<std::deque<int>, std::vector<Emplaceable>>();174 }175 test<MinSequenceContainer<int>, MinSequenceContainer<double>>();176 test<std::vector<int, min_allocator<int>>, std::vector<double, min_allocator<double>>>();177 178 test_emplaceable<std::vector<int>, std::vector<Emplaceable>>();179 test_emplaceable<MinSequenceContainer<int>, MinSequenceContainer<Emplaceable>>();180 test_emplaceable<std::vector<int, min_allocator<int>>, std::vector<Emplaceable, min_allocator<Emplaceable>>>();181 182 if (!TEST_IS_CONSTANT_EVALUATED) {183 auto emplace_func = [](auto& m, auto key_arg, auto value_arg) {184 m.emplace_hint(m.begin(), std::piecewise_construct, std::tuple(key_arg), std::tuple(value_arg));185 };186 test_emplace_exception_guarantee(emplace_func);187 }188 189 return true;190}191 192int main(int, char**) {193 test();194#if TEST_STD_VER >= 26195 static_assert(test());196#endif197 198 return 0;199}200