1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
// Copyright (c) 2020 GeometryFactory Sarl (France)
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org)
//
// $URL: https://github.com/CGAL/cgal/blob/v6.1/STL_Extension/include/CGAL/Small_unordered_set.h $
// $Id: include/CGAL/Small_unordered_set.h b26b07a1242 $
// SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial
//
// Author(s) : Simon Giraudot
#ifndef CGAL_SMALL_UNORDERED_SET_H
#define CGAL_SMALL_UNORDERED_SET_H
#include <array>
#include <unordered_set>
namespace CGAL
{
/*
This is a very rudimentary structure. It is far from being a full
"small unordered set", but it is a starting point.
For the moment, its only feature is the insertion of elements +
check that they were indeed inserted, while avoiding instantiating a
`std::unordered_set` as long as the number of elements remain small.
In practice:
- if the number of elements in the set is lower than MaxSize,
elements are just appended to a `std::array<Key, MaxSize>` and the
unicity test is done element by element, in linear time
- when the number of elements exceed MaxSize, a
`std::unordered_set<Key>` is instantiated, all the elements of the
array are inserted in it and from that point the container behaves
like a `std::unordered_set`
For this structure to be a true "small unordered set", special
iterators should be created to make the switch from array to
unordered set completely transparent to the user, and all other
usual member functions should be introduced. So far, this is not
needed and thus not done.
*/
template<typename Key, std::size_t MaxSize>
class Small_unordered_set
{
using Array = std::array<Key, MaxSize>;
using Set = std::unordered_set<Key>;
Array m_array;
std::unique_ptr<Set> m_set;
std::size_t m_size = 0;
public:
Small_unordered_set() { }
Small_unordered_set (const Small_unordered_set& other)
: m_size (other.m_size)
{
if (other.m_set)
m_set = std::make_unique<Set>(*other.m_set);
else
m_array = other.m_array;
}
Small_unordered_set (Small_unordered_set&& other)
: m_size (other.m_size)
{
if (other.m_set)
m_set = std::move(other.m_set);
else
m_array = std::move(other.m_array);
}
Small_unordered_set& operator= (const Small_unordered_set& other)
{
m_size = other.m_size;
if (other.m_set)
m_set = std::make_unique<Set>(*other.m_set);
else
m_array = other.m_array;
}
Small_unordered_set& operator= (Small_unordered_set&& other)
{
m_size = other.m_size;
if (other.m_set)
m_set = std::move(other.m_set);
else
m_array = std::move(other.m_array);
}
bool insert (const Key& key)
{
if (m_size != MaxSize)
{
for (std::size_t i = 0; i < m_size; ++ i)
if (m_array[i] == key)
return false;
m_array[m_size ++] = key;
return true;
}
if (!m_set)
{
m_set = std::make_unique<Set>();
m_set->reserve (MaxSize + 1);
for (const Key& a : m_array)
m_set->insert(a);
}
return m_set->insert(key).second;
}
};
}
#endif // CGAL_SMALL_UNORDERED_SET_H
|
