1//===----------------------------------------------------------------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is dual licensed under the MIT and the University of Illinois Open
6// Source Licenses. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10// <unordered_map>
11
12// template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
13//           class Alloc = allocator<pair<const Key, T>>>
14// class unordered_multimap
15
16// void rehash(size_type n);
17
18#include <unordered_map>
19#include <string>
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, size_t n)
30{
31	assert(c.bucket_count() >= c.size() / c.max_load_factor() && c.bucket_count() >= n);
32}
33
34template <class C>
35void test(const C& c)
36{
37    assert(c.size() == 6);
38    typedef std::pair<typename C::const_iterator, typename C::const_iterator> Eq;
39    Eq eq = c.equal_range(1);
40    assert(std::distance(eq.first, eq.second) == 2);
41    typename C::const_iterator i = eq.first;
42    assert(i->first == 1);
43    assert(i->second == "one");
44    ++i;
45    assert(i->first == 1);
46    assert(i->second == "four");
47    eq = c.equal_range(2);
48    assert(std::distance(eq.first, eq.second) == 2);
49    i = eq.first;
50    assert(i->first == 2);
51    assert(i->second == "two");
52    ++i;
53    assert(i->first == 2);
54    assert(i->second == "four");
55
56    eq = c.equal_range(3);
57    assert(std::distance(eq.first, eq.second) == 1);
58    i = eq.first;
59    assert(i->first == 3);
60    assert(i->second == "three");
61    eq = c.equal_range(4);
62    assert(std::distance(eq.first, eq.second) == 1);
63    i = eq.first;
64    assert(i->first == 4);
65    assert(i->second == "four");
66    assert(static_cast<std::size_t>(std::distance(c.begin(), c.end())) == c.size());
67    assert(static_cast<std::size_t>(std::distance(c.cbegin(), c.cend())) == c.size());
68    assert(std::fabs(c.load_factor() - (float)c.size()/c.bucket_count()) < FLT_EPSILON);
69}
70
71int main()
72{
73    {
74        typedef std::unordered_multimap<int, std::string> C;
75        typedef std::pair<int, std::string> P;
76        P a[] =
77        {
78            P(1, "one"),
79            P(2, "two"),
80            P(3, "three"),
81            P(4, "four"),
82            P(1, "four"),
83            P(2, "four"),
84        };
85        C c(a, a + sizeof(a)/sizeof(a[0]));
86        test(c);
87        assert(c.bucket_count() >= 7);
88        c.rehash(3);
89        rehash_postcondition(c, 3);
90        LIBCPP_ASSERT(c.bucket_count() == 7);
91        test(c);
92        c.max_load_factor(2);
93        c.rehash(3);
94        rehash_postcondition(c, 3);
95        LIBCPP_ASSERT(c.bucket_count() == 3);
96        test(c);
97        c.rehash(31);
98        rehash_postcondition(c, 31);
99        LIBCPP_ASSERT(c.bucket_count() == 31);
100        test(c);
101    }
102#if TEST_STD_VER >= 11
103    {
104        typedef std::unordered_multimap<int, std::string, std::hash<int>, std::equal_to<int>,
105                            min_allocator<std::pair<const int, std::string>>> C;
106        typedef std::pair<int, std::string> P;
107        P a[] =
108        {
109            P(1, "one"),
110            P(2, "two"),
111            P(3, "three"),
112            P(4, "four"),
113            P(1, "four"),
114            P(2, "four"),
115        };
116        C c(a, a + sizeof(a)/sizeof(a[0]));
117        test(c);
118        assert(c.bucket_count() >= 7);
119        c.rehash(3);
120        rehash_postcondition(c, 3);
121        LIBCPP_ASSERT(c.bucket_count() == 7);
122        test(c);
123        c.max_load_factor(2);
124        c.rehash(3);
125        rehash_postcondition(c, 3);
126        LIBCPP_ASSERT(c.bucket_count() == 3);
127        test(c);
128        c.rehash(31);
129        rehash_postcondition(c, 31);
130        LIBCPP_ASSERT(c.bucket_count() == 31);
131        test(c);
132    }
133#endif
134}
135