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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
|
// **************************************************************************
// * This file is part of the FreeFileSync project. It is distributed under *
// * GNU General Public License: http://www.gnu.org/licenses/gpl-3.0 *
// * Copyright (C) Zenju (zenju AT gmx DOT de) - All Rights Reserved *
// **************************************************************************
#ifndef STL_TOOLS_H_84567184321434
#define STL_TOOLS_H_84567184321434
#include <set>
#include <map>
#include <vector>
#include <memory>
#include <algorithm>
#include "type_tools.h"
#include "build_info.h"
//enhancements for <algorithm>
namespace zen
{
//erase selected elements from any container:
template <class T, class Alloc, class Predicate>
void erase_if(std::vector<T, Alloc>& v, Predicate p);
template <class T, class LessType, class Alloc, class Predicate>
void erase_if(std::set<T, LessType, Alloc>& s, Predicate p);
template <class KeyType, class ValueType, class LessType, class Alloc, class Predicate>
void erase_if(std::map<KeyType, ValueType, LessType, Alloc>& m, Predicate p);
//append STL containers
template <class T, class Alloc, class C>
void append(std::vector<T, Alloc>& v, const C& c);
template <class T, class LessType, class Alloc, class C>
void append(std::set<T, LessType, Alloc>& s, const C& c);
template <class KeyType, class ValueType, class LessType, class Alloc, class C>
void append(std::map<KeyType, ValueType, LessType, Alloc>& m, const C& c);
template <class M, class K, class V>
V& map_add_or_update(M& map, const K& key, const V& value); //efficient add or update without "default-constructible" requirement (Effective STL, item 24)
template <class T, class Alloc>
void removeDuplicates(std::vector<T, Alloc>& v);
//binary search returning an iterator
template <class ForwardIterator, class T, typename CompLess>
ForwardIterator binary_search(ForwardIterator first, ForwardIterator last, const T& value, CompLess less);
template <class BidirectionalIterator, class T>
BidirectionalIterator find_last(BidirectionalIterator first, BidirectionalIterator last, const T& value);
//replacement for std::find_end taking advantage of bidirectional iterators (and giving the algorithm a reasonable name)
template <class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator1 search_last(BidirectionalIterator1 first1, BidirectionalIterator1 last1,
BidirectionalIterator2 first2, BidirectionalIterator2 last2);
template <class InputIterator1, class InputIterator2>
bool equal(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2);
size_t hashBytes(const unsigned char* ptr, size_t len);
size_t hashBytesAppend(size_t hashVal, const unsigned char* ptr, size_t len);
//support for custom string classes in std::unordered_set/map
struct StringHash
{
template <class String>
size_t operator()(const String& str) const
{
const auto* strFirst = strBegin(str);
return hashBytes(reinterpret_cast<const unsigned char*>(strFirst), strLength(str) * sizeof(strFirst[0]));
}
};
//######################## implementation ########################
template <class T, class Alloc, class Predicate> inline
void erase_if(std::vector<T, Alloc>& v, Predicate p)
{
v.erase(std::remove_if(v.begin(), v.end(), p), v.end());
}
namespace impl
{
template <class S, class Predicate> inline
void set_or_map_erase_if(S& s, Predicate p)
{
for (auto it = s.begin(); it != s.end();)
if (p(*it))
s.erase(it++);
else
++it;
}
}
template <class T, class LessType, class Alloc, class Predicate> inline
void erase_if(std::set<T, LessType, Alloc>& s, Predicate p) { impl::set_or_map_erase_if(s, p); } //don't make this any more generic! e.g. must not compile for std::vector!!!
template <class KeyType, class ValueType, class LessType, class Alloc, class Predicate> inline
void erase_if(std::map<KeyType, ValueType, LessType, Alloc>& m, Predicate p) { impl::set_or_map_erase_if(m, p); }
template <class T, class Alloc, class C> inline
void append(std::vector<T, Alloc>& v, const C& c) { v.insert(v.end(), c.begin(), c.end()); }
template <class T, class LessType, class Alloc, class C> inline
void append(std::set<T, LessType, Alloc>& s, const C& c) { s.insert(c.begin(), c.end()); }
template <class KeyType, class ValueType, class LessType, class Alloc, class C> inline
void append(std::map<KeyType, ValueType, LessType, Alloc>& m, const C& c) { m.insert(c.begin(), c.end()); }
template <class M, class K, class V> inline
V& map_add_or_update(M& map, const K& key, const V& value) //efficient add or update without "default-constructible" requirement (Effective STL, item 24)
{
auto it = map.lower_bound(key);
if (it != map.end() && !(map.key_comp()(key, it->first)))
{
it->second = value;
return it->second;
}
else
return map.insert(it, typename M::value_type(key, value))->second;
}
template <class T, class Alloc> inline
void removeDuplicates(std::vector<T, Alloc>& v)
{
std::sort(v.begin(), v.end());
v.erase(std::unique(v.begin(), v.end()), v.end());
}
template <class ForwardIterator, class T, typename CompLess> inline
ForwardIterator binary_search(ForwardIterator first, ForwardIterator last, const T& value, CompLess less)
{
first = std::lower_bound(first, last, value, less);
if (first != last && !less(value, *first))
return first;
else
return last;
}
template <class BidirectionalIterator, class T> inline
BidirectionalIterator find_last(const BidirectionalIterator first, const BidirectionalIterator last, const T& value)
{
for (BidirectionalIterator it = last; it != first;) //reverse iteration: 1. check 2. decrement 3. evaluate
{
--it; //
if (*it == value)
return it;
}
return last;
}
template <class BidirectionalIterator1, class BidirectionalIterator2> inline
BidirectionalIterator1 search_last(const BidirectionalIterator1 first1, BidirectionalIterator1 last1,
const BidirectionalIterator2 first2, const BidirectionalIterator2 last2)
{
const BidirectionalIterator1 itNotFound = last1;
//reverse iteration: 1. check 2. decrement 3. evaluate
for (;;)
{
BidirectionalIterator1 it1 = last1;
BidirectionalIterator2 it2 = last2;
for (;;)
{
if (it2 == first2) return it1;
if (it1 == first1) return itNotFound;
--it1;
--it2;
if (*it1 != *it2) break;
}
--last1;
}
}
template <class InputIterator1, class InputIterator2> inline
bool equal(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2)
{
return last1 - first1 == last2 - first2 && std::equal(first1, last1, first2);
}
#if defined _MSC_VER && _MSC_VER <= 1600
static_assert(false, "VS2010 performance bug in std::unordered_set<>: http://drdobbs.com/blogs/cpp/232200410 -> should be fixed in VS11");
#endif
inline
size_t hashBytes(const unsigned char* ptr, size_t len)
{
//http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
#ifdef ZEN_BUILD_32BIT
const size_t basis = 2166136261U;
#elif defined ZEN_BUILD_64BIT
const size_t basis = 14695981039346656037ULL;
#endif
return hashBytesAppend(basis, ptr, len);
}
inline
size_t hashBytesAppend(size_t hashVal, const unsigned char* ptr, size_t len)
{
#ifdef ZEN_BUILD_32BIT
const size_t prime = 16777619U;
#elif defined ZEN_BUILD_64BIT
const size_t prime = 1099511628211ULL;
#endif
for (size_t i = 0; i < len; ++i)
{
hashVal ^= static_cast<size_t>(ptr[i]);
hashVal *= prime;
}
return hashVal;
}
}
#endif //STL_TOOLS_H_84567184321434
|
