249 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_set>12 13// template <class... Args>14// iterator emplace_hint(const_iterator position, Args&&... args);15 16#include <flat_set>17#include <cassert>18#include <deque>19#include <functional>20#include <vector>21 22#include "MinSequenceContainer.h"23#include "test_macros.h"24#include "../../../Emplaceable.h"25#include "DefaultOnly.h"26#include "min_allocator.h"27#include "../helpers.h"28 29struct CompareTensDigit {30 constexpr bool operator()(auto lhs, auto rhs) const { return (lhs / 10) < (rhs / 10); }31};32 33template <class KeyContainer>34constexpr void test_one() {35 using Key = typename KeyContainer::value_type;36 using M = std::flat_multiset<Key, std::less<Key>, KeyContainer>;37 using R = M::iterator;38 39 {40 // was empty41 M m;42 std::same_as<R> decltype(auto) r = m.emplace_hint(m.end(), typename M::value_type(2));43 assert(r == m.begin());44 assert(m.size() == 1);45 assert(*r == 2);46 }47 {48 // hints correct and no duplicates49 M m = {0, 1, 3};50 auto hint = m.begin() + 2;51 std::same_as<R> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(2));52 assert(r == m.begin() + 2);53 assert(m.size() == 4);54 assert(*r == 2);55 }56 {57 // hints correct at the begin58 M m = {3, 4};59 auto hint = m.begin();60 std::same_as<R> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(2));61 assert(r == m.begin());62 assert(m.size() == 3);63 assert(*r == 2);64 }65 {66 // hints correct in the middle67 M m = {0, 1, 3, 4};68 auto hint = m.begin() + 2;69 std::same_as<R> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(2));70 assert(r == m.begin() + 2);71 assert(m.size() == 5);72 assert(*r == 2);73 }74 {75 // hints correct at the end76 M m = {0, 1};77 auto hint = m.end();78 std::same_as<R> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(2));79 assert(r == m.begin() + 2);80 assert(m.size() == 3);81 assert(*r == 2);82 }83 {84 // hints correct but key already exists85 M m = {0, 1, 2, 3, 4};86 auto hint = m.begin() + 2;87 std::same_as<R> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(2));88 assert(r == m.begin() + 2);89 assert(m.size() == 6);90 assert(*r == 2);91 }92 {93 // hint correct and at the first duplicate94 using M2 = std::flat_multiset<Key, CompareTensDigit, KeyContainer>;95 using R2 = M2::iterator;96 M2 m{0, 10, 20, 25, 30};97 auto hint = m.begin() + 2;98 std::same_as<R2> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(21));99 assert(r == m.begin() + 2);100 assert(m.size() == 6);101 assert(*r == 21);102 }103 {104 // hint correct and in-between duplicates105 using M2 = std::flat_multiset<Key, CompareTensDigit, KeyContainer>;106 using R2 = M2::iterator;107 M2 m{0, 10, 20, 21, 22, 30};108 auto hint = m.begin() + 4;109 std::same_as<R2> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(23));110 assert(r == m.begin() + 4);111 assert(m.size() == 7);112 assert(*r == 23);113 assert(*std::next(r) == 22);114 }115 {116 // hint correct and after duplicates117 using M2 = std::flat_multiset<Key, CompareTensDigit, KeyContainer>;118 using R2 = M2::iterator;119 M2 m{0, 10, 20, 21, 22, 30};120 auto hint = m.begin() + 5;121 std::same_as<R2> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(23));122 assert(r == m.begin() + 5);123 assert(m.size() == 7);124 assert(*r == 23);125 assert(*std::next(r) == 30);126 }127 {128 // hints incorrect and no duplicates129 M m = {0, 1, 3};130 auto hint = m.begin() + 1;131 std::same_as<R> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(2));132 assert(r == m.begin() + 2);133 assert(m.size() == 4);134 assert(*r == 2);135 }136 {137 // hints incorrectly at the begin138 M m = {1, 4};139 auto hint = m.begin();140 std::same_as<R> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(2));141 assert(r == m.begin() + 1);142 assert(m.size() == 3);143 assert(*r == 2);144 }145 {146 // hints incorrectly in the middle147 M m = {0, 1, 3, 4};148 auto hint = m.begin() + 1;149 std::same_as<R> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(2));150 assert(r == m.begin() + 2);151 assert(m.size() == 5);152 assert(*r == 2);153 }154 {155 // hints incorrectly at the end156 M m = {0, 3};157 auto hint = m.end();158 std::same_as<R> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(2));159 assert(r == m.begin() + 1);160 assert(m.size() == 3);161 assert(*r == 2);162 }163 {164 // hints incorrect and key already exists165 M m = {0, 1, 2, 3, 4};166 auto hint = m.begin();167 std::same_as<R> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(2));168 assert(r == m.begin() + 2);169 assert(m.size() == 6);170 assert(*r == 2);171 }172 {173 // hint incorrect and before the first duplicate174 using M2 = std::flat_multiset<Key, CompareTensDigit, KeyContainer>;175 using R2 = M2::iterator;176 M2 m{0, 10, 20, 21, 22, 30};177 auto hint = m.begin();178 std::same_as<R2> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(23));179 assert(r == m.begin() + 2);180 assert(m.size() == 7);181 assert(*r == 23);182 }183 {184 // hint incorrect and after the last duplicate185 using M2 = std::flat_multiset<Key, CompareTensDigit, KeyContainer>;186 using R2 = M2::iterator;187 M2 m{0, 10, 20, 21, 22, 30, 40};188 auto hint = m.begin() + 6;189 std::same_as<R2> decltype(auto) r = m.emplace_hint(hint, typename M::value_type(23));190 assert(r == m.begin() + 5);191 assert(m.size() == 8);192 assert(*r == 23);193 assert(*std::next(r) == 30);194 }195}196 197template <class KeyContainer>198constexpr void test_emplaceable() {199 using M = std::flat_multiset<Emplaceable, std::less<Emplaceable>, KeyContainer>;200 using R = M::iterator;201 202 M m;203 ASSERT_SAME_TYPE(decltype(m.emplace_hint(m.cbegin())), R);204 R r = m.emplace_hint(m.end(), 2, 0.0);205 assert(r == m.begin());206 assert(m.size() == 1);207 assert(*m.begin() == Emplaceable(2, 0.0));208 r = m.emplace_hint(m.end(), 1, 3.5);209 assert(r == m.begin());210 assert(m.size() == 2);211 assert(*m.begin() == Emplaceable(1, 3.5));212 r = m.emplace_hint(m.end(), 1, 3.5);213 assert(r == m.begin() + 1);214 assert(m.size() == 3);215 assert(*r == Emplaceable(1, 3.5));216}217 218constexpr bool test() {219 test_one<std::vector<int>>();220#ifndef __cpp_lib_constexpr_deque221 if (!TEST_IS_CONSTANT_EVALUATED)222#endif223 test_one<std::deque<int>>();224 test_one<MinSequenceContainer<int>>();225 test_one<std::vector<int, min_allocator<int>>>();226 227 test_emplaceable<std::vector<Emplaceable>>();228 test_emplaceable<std::vector<Emplaceable>>();229 test_emplaceable<MinSequenceContainer<Emplaceable>>();230 test_emplaceable<std::vector<Emplaceable, min_allocator<Emplaceable>>>();231 232 return true;233}234 235void test_exception() {236 auto emplace_func = [](auto& m, auto key_arg) { m.emplace_hint(m.begin(), key_arg); };237 test_emplace_exception_guarantee(emplace_func);238}239 240int main(int, char**) {241 test();242#if TEST_STD_VER >= 26243 static_assert(test());244#endif245 test_exception();246 247 return 0;248}249