153 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, class Pred, class Alloc>12// bool13// operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x,14// const unordered_map<Key, T, Hash, Pred, Alloc>& y);15//16// template <class Key, class T, class Hash, class Pred, class Alloc>17// bool18// operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x,19// const unordered_map<Key, T, Hash, Pred, Alloc>& y);20 21// Implements paper: http://wg21.link/p080922 23#include <unordered_map>24#include <cstddef>25#include <limits>26#include <cassert>27#include <functional>28 29template <class T>30std::size_t hash_identity(T val) {31 return val;32}33template <class T>34std::size_t hash_neg(T val) {35 return std::numeric_limits<T>::max() - val;36}37template <class T>38std::size_t hash_scale(T val) {39 return static_cast<std::size_t>(val << 1);40}41template <class T>42std::size_t hash_even(T val) {43 return val & 1 ? 1 : 0;44}45template <class T>46std::size_t hash_same(T /*val*/) {47 return 1;48}49 50template <class T>51std::size_t hash_identity(T* val) {52 return *val;53}54template <class T>55std::size_t hash_neg(T* val) {56 return std::numeric_limits<T>::max() - *val;57}58template <class T>59std::size_t hash_scale(T* val) {60 return static_cast<std::size_t>(*val << 1);61}62template <class T>63std::size_t hash_even(T* val) {64 return *val & 1 ? 1 : 0;65}66 67template <class Map, class Ittr>68void populate(Map& m, Ittr start, Ittr end) {69 for (auto *p1 = start, *p2 = end - 1; p1 != end; ++p1, --p2) {70 m.insert(std::make_pair(*p1, *p2));71 }72}73 74template <class T, std::size_t N>75void test(T (&vals)[N]) {76 using Hash = std::size_t (*)(T);77 using C = std::unordered_map<T, T, Hash, std::equal_to<T> >;78 79 C c1(0, hash_identity);80 C c2(0, hash_neg);81 C c3(0, hash_scale);82 C c4(0, hash_even);83 C c5(0, hash_same);84 85 populate(c1, std::begin(vals), std::end(vals));86 populate(c2, std::begin(vals), std::end(vals));87 populate(c3, std::begin(vals), std::end(vals));88 populate(c4, std::begin(vals), std::end(vals));89 populate(c5, std::begin(vals), std::end(vals));90 91 assert(c1 == c1);92 assert(c1 == c2);93 assert(c1 == c3);94 assert(c1 == c4);95 assert(c1 == c5);96 97 assert(c2 == c1);98 assert(c2 == c2);99 assert(c2 == c3);100 assert(c2 == c4);101 assert(c2 == c5);102 103 assert(c3 == c1);104 assert(c3 == c2);105 assert(c3 == c3);106 assert(c3 == c4);107 assert(c3 == c5);108 109 assert(c4 == c1);110 assert(c4 == c2);111 assert(c4 == c3);112 assert(c4 == c4);113 assert(c4 == c5);114 115 assert(c5 == c1);116 assert(c5 == c2);117 assert(c5 == c3);118 assert(c5 == c4);119 assert(c5 == c5);120}121 122int main(int, char**) {123 {124 std::size_t vals[] = {125 // clang-format off126 1,127 2, 2,128 3, 3, 3,129 4, 4, 4, 4,130 5, 5, 5, 5, 5,131 6, 6, 6, 6, 6, 6,132 7, 7, 7, 7, 7, 7, 7,133 8, 8, 8, 8, 8, 8, 8, 8,134 9, 9, 9, 9, 9, 9, 9, 9, 9,135 10136 // clang-format on137 };138 test(vals);139 }140 141 {142 bool vals[] = {true, false};143 test(vals);144 }145 146 {147 char* vals[] = {(char*)("a"), (char*)("b"), (char*)("cde")};148 test(vals);149 }150 151 return 0;152}153