1 // *****************************************************************************
2 // * This file is part of the FreeFileSync project. It is distributed under *
3 // * GNU General Public License: http://www.gnu.org/licenses/gpl-3.0 *
4 // * Copyright (C) Zenju (zenju AT freefilesync DOT org) - All Rights Reserved *
5 // *****************************************************************************
6
7 #ifndef STL_TOOLS_H_84567184321434
8 #define STL_TOOLS_H_84567184321434
9
10 #include <set>
11 #include <map>
12 #include <vector>
13 #include <memory>
14 #include <algorithm>
15 #include "type_tools.h"
16 #include "build_info.h"
17
18
19 //enhancements for <algorithm>
20 namespace zen
21 {
22 //erase selected elements from any container:
23 template <class T, class Alloc, class Predicate>
24 void erase_if(std::vector<T, Alloc>& v, Predicate p);
25
26 template <class T, class LessType, class Alloc, class Predicate>
27 void erase_if(std::set<T, LessType, Alloc>& s, Predicate p);
28
29 template <class KeyType, class ValueType, class LessType, class Alloc, class Predicate>
30 void erase_if(std::map<KeyType, ValueType, LessType, Alloc>& m, Predicate p);
31
32 //append STL containers
33 template <class T, class Alloc, class C>
34 void append(std::vector<T, Alloc>& v, const C& c);
35
36 template <class T, class LessType, class Alloc, class C>
37 void append(std::set<T, LessType, Alloc>& s, const C& c);
38
39 template <class KeyType, class ValueType, class LessType, class Alloc, class C>
40 void append(std::map<KeyType, ValueType, LessType, Alloc>& m, const C& c);
41
42 template <class M, class K, class V>
43 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)
44
45 template <class T, class Alloc>
46 void removeDuplicates(std::vector<T, Alloc>& v);
47
48 //binary search returning an iterator
49 template <class ForwardIterator, class T, typename CompLess>
50 ForwardIterator binary_search(ForwardIterator first, ForwardIterator last, const T& value, CompLess less);
51
52 template <class BidirectionalIterator, class T>
53 BidirectionalIterator find_last(BidirectionalIterator first, BidirectionalIterator last, const T& value);
54
55 //replacement for std::find_end taking advantage of bidirectional iterators (and giving the algorithm a reasonable name)
56 template <class BidirectionalIterator1, class BidirectionalIterator2>
57 BidirectionalIterator1 search_last(BidirectionalIterator1 first1, BidirectionalIterator1 last1,
58 BidirectionalIterator2 first2, BidirectionalIterator2 last2);
59
60 template <class InputIterator1, class InputIterator2>
61 bool equal(InputIterator1 first1, InputIterator1 last1,
62 InputIterator2 first2, InputIterator2 last2);
63
64 template <class ByteIterator> size_t hashBytes (ByteIterator first, ByteIterator last);
65 template <class ByteIterator> size_t hashBytesAppend(size_t hashVal, ByteIterator first, ByteIterator last);
66
67
68 //support for custom string classes in std::unordered_set/map
69 struct StringHash
70 {
71 template <class String>
operatorStringHash72 size_t operator()(const String& str) const
73 {
74 const auto* strFirst = strBegin(str);
75 return hashBytes(reinterpret_cast<const char*>(strFirst),
76 reinterpret_cast<const char*>(strFirst + strLength(str)));
77 }
78 };
79
80
81
82
83
84
85 //######################## implementation ########################
86
87 template <class T, class Alloc, class Predicate> inline
erase_if(std::vector<T,Alloc> & v,Predicate p)88 void erase_if(std::vector<T, Alloc>& v, Predicate p)
89 {
90 v.erase(std::remove_if(v.begin(), v.end(), p), v.end());
91 }
92
93
94 namespace impl
95 {
96 template <class S, class Predicate> inline
set_or_map_erase_if(S & s,Predicate p)97 void set_or_map_erase_if(S& s, Predicate p)
98 {
99 for (auto it = s.begin(); it != s.end();)
100 if (p(*it))
101 s.erase(it++);
102 else
103 ++it;
104 }
105 }
106
107
108 template <class T, class LessType, class Alloc, class Predicate> inline
erase_if(std::set<T,LessType,Alloc> & s,Predicate p)109 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!!!
110
111
112 template <class KeyType, class ValueType, class LessType, class Alloc, class Predicate> inline
erase_if(std::map<KeyType,ValueType,LessType,Alloc> & m,Predicate p)113 void erase_if(std::map<KeyType, ValueType, LessType, Alloc>& m, Predicate p) { impl::set_or_map_erase_if(m, p); }
114
115
116 template <class T, class Alloc, class C> inline
append(std::vector<T,Alloc> & v,const C & c)117 void append(std::vector<T, Alloc>& v, const C& c) { v.insert(v.end(), c.begin(), c.end()); }
118
119
120 template <class T, class LessType, class Alloc, class C> inline
append(std::set<T,LessType,Alloc> & s,const C & c)121 void append(std::set<T, LessType, Alloc>& s, const C& c) { s.insert(c.begin(), c.end()); }
122
123
124 template <class KeyType, class ValueType, class LessType, class Alloc, class C> inline
append(std::map<KeyType,ValueType,LessType,Alloc> & m,const C & c)125 void append(std::map<KeyType, ValueType, LessType, Alloc>& m, const C& c) { m.insert(c.begin(), c.end()); }
126
127
128 template <class M, class K, class V> inline
map_add_or_update(M & map,const K & key,const V & value)129 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)
130 {
131 auto it = map.lower_bound(key);
132 if (it != map.end() && !(map.key_comp()(key, it->first)))
133 {
134 it->second = value;
135 return it->second;
136 }
137 else
138 return map.insert(it, typename M::value_type(key, value))->second;
139 }
140
141
142 template <class T, class Alloc> inline
removeDuplicates(std::vector<T,Alloc> & v)143 void removeDuplicates(std::vector<T, Alloc>& v)
144 {
145 std::sort(v.begin(), v.end());
146 v.erase(std::unique(v.begin(), v.end()), v.end());
147 }
148
149
150 template <class ForwardIterator, class T, typename CompLess> inline
binary_search(ForwardIterator first,ForwardIterator last,const T & value,CompLess less)151 ForwardIterator binary_search(ForwardIterator first, ForwardIterator last, const T& value, CompLess less)
152 {
153 first = std::lower_bound(first, last, value, less);
154 if (first != last && !less(value, *first))
155 return first;
156 else
157 return last;
158 }
159
160
161 template <class BidirectionalIterator, class T> inline
find_last(const BidirectionalIterator first,const BidirectionalIterator last,const T & value)162 BidirectionalIterator find_last(const BidirectionalIterator first, const BidirectionalIterator last, const T& value)
163 {
164 for (BidirectionalIterator it = last; it != first;) //reverse iteration: 1. check 2. decrement 3. evaluate
165 {
166 --it; //
167
168 if (*it == value)
169 return it;
170 }
171 return last;
172 }
173
174
175 template <class BidirectionalIterator1, class BidirectionalIterator2> inline
search_last(const BidirectionalIterator1 first1,BidirectionalIterator1 last1,const BidirectionalIterator2 first2,const BidirectionalIterator2 last2)176 BidirectionalIterator1 search_last(const BidirectionalIterator1 first1, BidirectionalIterator1 last1,
177 const BidirectionalIterator2 first2, const BidirectionalIterator2 last2)
178 {
179 const BidirectionalIterator1 itNotFound = last1;
180
181 //reverse iteration: 1. check 2. decrement 3. evaluate
182 for (;;)
183 {
184 BidirectionalIterator1 it1 = last1;
185 BidirectionalIterator2 it2 = last2;
186
187 for (;;)
188 {
189 if (it2 == first2) return it1;
190 if (it1 == first1) return itNotFound;
191
192 --it1;
193 --it2;
194
195 if (*it1 != *it2) break;
196 }
197 --last1;
198 }
199 }
200
201
202 template <class InputIterator1, class InputIterator2> inline
equal(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2,InputIterator2 last2)203 bool equal(InputIterator1 first1, InputIterator1 last1,
204 InputIterator2 first2, InputIterator2 last2)
205 {
206 return last1 - first1 == last2 - first2 && std::equal(first1, last1, first2);
207 }
208
209
210 #if defined _MSC_VER && _MSC_VER <= 1600
211 static_assert(false, "VS2010 performance bug in std::unordered_set<>: http://drdobbs.com/blogs/cpp/232200410 -> should be fixed in VS11");
212 #endif
213
214
215 template <class ByteIterator> inline
hashBytes(ByteIterator first,ByteIterator last)216 size_t hashBytes(ByteIterator first, ByteIterator last)
217 {
218 //FNV-1a: http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
219 #ifdef ZEN_BUILD_32BIT
220 const size_t basis = 2166136261U;
221 #elif defined ZEN_BUILD_64BIT
222 const size_t basis = 14695981039346656037ULL;
223 #endif
224 return hashBytesAppend(basis, first, last);
225 }
226
227
228 template <class ByteIterator> inline
hashBytesAppend(size_t hashVal,ByteIterator first,ByteIterator last)229 size_t hashBytesAppend(size_t hashVal, ByteIterator first, ByteIterator last)
230 {
231 #ifdef ZEN_BUILD_32BIT
232 const size_t prime = 16777619U;
233 #elif defined ZEN_BUILD_64BIT
234 const size_t prime = 1099511628211ULL;
235 #endif
236 static_assert(sizeof(typename std::iterator_traits<ByteIterator>::value_type) == 1, "");
237
238 for (; first != last; ++first)
239 {
240 hashVal ^= static_cast<size_t>(*first);
241 hashVal *= prime;
242 }
243 return hashVal;
244 }
245 }
246
247 #endif //STL_TOOLS_H_84567184321434
248