167 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 K> pair<iterator, bool> insert(K&& x);14// template<class K> iterator insert(const_iterator hint, K&& x);15 16#include <algorithm>17#include <compare>18#include <concepts>19#include <deque>20#include <flat_set>21#include <functional>22#include <tuple>23 24#include "MinSequenceContainer.h"25#include "../helpers.h"26#include "test_macros.h"27#include "test_iterators.h"28#include "min_allocator.h"29 30// Constraints: The qualified-id Compare::is_transparent is valid and denotes a type. is_constructible_v<value_type, K> is true.31template <class M, class... Args>32concept CanInsert = requires(M m, Args&&... args) { m.insert(std::forward<Args>(args)...); };33 34using TransparentSet = std::flat_set<int, TransparentComparator>;35using TransparentSetIter = typename TransparentSet::iterator;36static_assert(CanInsert<TransparentSet, ExplicitlyConvertibleTransparent<int>>);37static_assert(CanInsert<TransparentSet, TransparentSetIter, ExplicitlyConvertibleTransparent<int>>);38static_assert(!CanInsert<TransparentSet, NonConvertibleTransparent<int>>);39static_assert(!CanInsert<TransparentSet, TransparentSetIter, NonConvertibleTransparent<int>>);40 41using NonTransparentSet = std::flat_set<int>;42using NonTransparentSetIter = typename NonTransparentSet::iterator;43static_assert(!CanInsert<NonTransparentSet, ExplicitlyConvertibleTransparent<int>>);44static_assert(!CanInsert<NonTransparentSet, NonTransparentSetIter, ExplicitlyConvertibleTransparent<int>>);45static_assert(!CanInsert<NonTransparentSet, NonConvertibleTransparent<int>>);46static_assert(!CanInsert<NonTransparentSet, NonTransparentSetIter, NonConvertibleTransparent<int>>);47 48template <class KeyContainer>49constexpr void test_one() {50 using Key = typename KeyContainer::value_type;51 using M = std::flat_set<Key, TransparentComparator, KeyContainer>;52 53 {54 const int expected[] = {1, 2, 3, 4, 5};55 56 {57 // insert(K&&)58 bool transparent_used = false;59 M m{{1, 2, 4, 5}, TransparentComparator{transparent_used}};60 assert(!transparent_used);61 std::same_as<std::pair<typename M::iterator, bool>> decltype(auto) r =62 m.insert(ExplicitlyConvertibleTransparent<Key>{3});63 assert(transparent_used);64 assert(r.first == m.begin() + 2);65 assert(r.second);66 assert(std::ranges::equal(m, expected));67 }68 {69 // insert(const_iterator, K&&)70 bool transparent_used = false;71 M m{{1, 2, 4, 5}, TransparentComparator{transparent_used}};72 assert(!transparent_used);73 std::same_as<typename M::iterator> auto it = m.insert(m.begin(), ExplicitlyConvertibleTransparent<Key>{3});74 assert(transparent_used);75 assert(it == m.begin() + 2);76 assert(std::ranges::equal(m, expected));77 }78 }79 80 {81 // was empty82 const int expected[] = {3};83 {84 // insert(K&&)85 bool transparent_used = false;86 M m{{}, TransparentComparator{transparent_used}};87 assert(!transparent_used);88 std::same_as<std::pair<typename M::iterator, bool>> decltype(auto) r =89 m.insert(ExplicitlyConvertibleTransparent<Key>{3});90 assert(!transparent_used); // no elements to compare against91 assert(r.first == m.begin());92 assert(r.second);93 assert(std::ranges::equal(m, expected));94 }95 {96 // insert(const_iterator, K&&)97 bool transparent_used = false;98 M m{{}, TransparentComparator{transparent_used}};99 assert(!transparent_used);100 std::same_as<typename M::iterator> auto it = m.insert(m.begin(), ExplicitlyConvertibleTransparent<Key>{3});101 assert(!transparent_used); // no elements to compare against102 assert(it == m.begin());103 assert(std::ranges::equal(m, expected));104 }105 }106}107 108constexpr bool test() {109 test_one<std::vector<int>>();110#ifndef __cpp_lib_constexpr_deque111 if (!TEST_IS_CONSTANT_EVALUATED)112#endif113 test_one<std::deque<int>>();114 test_one<MinSequenceContainer<int>>();115 test_one<std::vector<int, min_allocator<int>>>();116 117 {118 // no ambiguity between insert(pos, P&&) and insert(first, last)119 using M = std::flat_set<int>;120 struct Evil {121 operator M::value_type() const;122 operator M::const_iterator() const;123 };124 std::flat_set<int> m;125 ASSERT_SAME_TYPE(decltype(m.insert(Evil())), std::pair<M::iterator, bool>);126 ASSERT_SAME_TYPE(decltype(m.insert(m.begin(), Evil())), M::iterator);127 ASSERT_SAME_TYPE(decltype(m.insert(m.begin(), m.end())), void);128 }129 {130 // LWG4239 std::string and C string literal131 using M = std::flat_set<std::string, std::less<>>;132 M m{"alpha", "beta", "epsilon", "eta", "gamma"};133 auto [iter, inserted] = m.insert("beta");134 assert(!inserted);135 assert(iter == m.begin() + 1);136 }137 138 return true;139}140 141void test_exception() {142 {143 auto insert_func = [](auto& m, auto key_arg) {144 using FlatSet = std::decay_t<decltype(m)>;145 m.insert(ExplicitlyConvertibleTransparent<typename FlatSet::key_type>{key_arg});146 };147 test_emplace_exception_guarantee(insert_func);148 }149 {150 auto insert_func_iter = [](auto& m, auto key_arg) {151 using FlatSet = std::decay_t<decltype(m)>;152 m.insert(m.begin(), ExplicitlyConvertibleTransparent<typename FlatSet::key_type>{key_arg});153 };154 test_emplace_exception_guarantee(insert_func_iter);155 }156}157 158int main(int, char**) {159 test();160 test_exception();161#if TEST_STD_VER >= 26162 static_assert(test());163#endif164 165 return 0;166}167