147 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// <unordered_map>10 11// template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,12// class Alloc = allocator<pair<const Key, T>>>13// class unordered_multimap14 15// void rehash(size_type n);16 17#include <unordered_map>18#include <string>19#include <set>20#include <cassert>21#include <cfloat>22#include <cmath>23#include <cstddef>24 25#include "test_macros.h"26#include "min_allocator.h"27 28template <class C>29void rehash_postcondition(const C& c, std::size_t n) {30 assert(c.bucket_count() >= c.size() / c.max_load_factor() && c.bucket_count() >= n);31}32 33template <class C>34void test(const C& c) {35 assert(c.size() == 6);36 typedef std::pair<typename C::const_iterator, typename C::const_iterator> Eq;37 Eq eq = c.equal_range(1);38 assert(std::distance(eq.first, eq.second) == 2);39 typename C::const_iterator i = eq.first;40 {41 std::set<std::string> s;42 s.insert("one");43 s.insert("four");44 for (int n = 0; n < 2; ++n) {45 assert(i->first == 1);46 assert(s.find(i->second) != s.end());47 s.erase(s.find(i->second));48 ++i;49 }50 }51 eq = c.equal_range(2);52 assert(std::distance(eq.first, eq.second) == 2);53 i = eq.first;54 {55 std::set<std::string> s;56 s.insert("two");57 s.insert("four");58 for (int n = 0; n < 2; ++n) {59 assert(i->first == 2);60 assert(s.find(i->second) != s.end());61 s.erase(s.find(i->second));62 ++i;63 }64 }65 eq = c.equal_range(3);66 assert(std::distance(eq.first, eq.second) == 1);67 i = eq.first;68 assert(i->first == 3);69 assert(i->second == "three");70 eq = c.equal_range(4);71 assert(std::distance(eq.first, eq.second) == 1);72 i = eq.first;73 assert(i->first == 4);74 assert(i->second == "four");75 assert(static_cast<std::size_t>(std::distance(c.begin(), c.end())) == c.size());76 assert(static_cast<std::size_t>(std::distance(c.cbegin(), c.cend())) == c.size());77 assert(std::fabs(c.load_factor() - (float)c.size() / c.bucket_count()) < FLT_EPSILON);78}79 80int main(int, char**) {81 {82 typedef std::unordered_multimap<int, std::string> C;83 typedef std::pair<int, std::string> P;84 P a[] = {85 P(1, "one"),86 P(2, "two"),87 P(3, "three"),88 P(4, "four"),89 P(1, "four"),90 P(2, "four"),91 };92 C c(a, a + sizeof(a) / sizeof(a[0]));93 test(c);94 assert(c.bucket_count() >= 7);95 c.rehash(3);96 rehash_postcondition(c, 3);97 LIBCPP_ASSERT(c.bucket_count() == 7);98 test(c);99 c.max_load_factor(2);100 c.rehash(3);101 rehash_postcondition(c, 3);102 LIBCPP_ASSERT(c.bucket_count() == 3);103 test(c);104 c.rehash(31);105 rehash_postcondition(c, 31);106 LIBCPP_ASSERT(c.bucket_count() == 31);107 test(c);108 }109#if TEST_STD_VER >= 11110 {111 typedef std::unordered_multimap<int,112 std::string,113 std::hash<int>,114 std::equal_to<int>,115 min_allocator<std::pair<const int, std::string>>>116 C;117 typedef std::pair<int, std::string> P;118 P a[] = {119 P(1, "one"),120 P(2, "two"),121 P(3, "three"),122 P(4, "four"),123 P(1, "four"),124 P(2, "four"),125 };126 C c(a, a + sizeof(a) / sizeof(a[0]));127 test(c);128 assert(c.bucket_count() >= 7);129 c.rehash(3);130 rehash_postcondition(c, 3);131 LIBCPP_ASSERT(c.bucket_count() == 7);132 test(c);133 c.max_load_factor(2);134 c.rehash(3);135 rehash_postcondition(c, 3);136 LIBCPP_ASSERT(c.bucket_count() == 3);137 test(c);138 c.rehash(31);139 rehash_postcondition(c, 31);140 LIBCPP_ASSERT(c.bucket_count() == 31);141 test(c);142 }143#endif144 145 return 0;146}147