前一篇博客《C++11:基于std::queue和std::mutex构建一个线程安全的队列》中，实现了一个线程安全的队列，本文说说如何实现一个线程安全的map。
在上一篇博客中，实现threadsafe_queue主要是依赖std::mutex信号量来实现线程对threadsafe_queue的独占访问,不论是只读的函数还是写函数对threadsafe_queue都是独占访问,因为对threadsafe_queue中的操作相对较少，而且主要操作push/pop都是写操作,所以这样做是没问题的。
但对于map,除了insert/erase这样的写操作之外还有find这样的读取操作,如果每个线程都是独占访问，无疑是会影响效率的。
所以在实现线程安全的map时,我没有选择使用std::mutex控制所有的操作为独占访问，而是用RWLock来控制map对象的访问，RWLock是我以前自己写的一个类，将线程对资源的访问分为读取操作和写入操作两类，这两类操作是独占的，但允许多个线程读取操作，允许一个线程写访问。也就是说多个线程在读取操作的时候，要写入的线程是阻塞的，直到所读取操作线程执行完读取操作释放读取锁，反之亦然，如果有一个线程在执行写入操作，所有要读取操作的线程就得等着，直到写入操作结束。
关于RWLock的源码及更详细的说明参见我的博客《无锁编程:c++11基于atomic实现共享读写锁(写优先)》
有了RWLock,基于std::unordered_map实现线程安全的map就比较简单了，基本上是把unordered_map的源码抄了一遍，对于unordered_map中的每个函数入口加一个RWLock的读取锁或写入锁。
实现的基本原则很简单:
对于const函数加读取锁，允许共享读取，
对于非const函数，加写入锁，允许独占写入。
下面是完整的源码:
/*
* threadsafe_unordered_map.h
*
* Created on: 2016年7月26日
* Author: guyadong
*/#ifndef COMMON_SOURCE_CPP_THREADSAFE_UNORDERED_MAP_H_#define COMMON_SOURCE_CPP_THREADSAFE_UNORDERED_MAP_H_#include <unordered_map>#include <memory>#include <utility>#include "RWLock.h"namespace gdface {inline namespace mt{/*
* 基于std::unordered_map实现线程安全map
* 禁止复制构造函数
* 禁止复制赋值操作符
* 允许移动构造函数
* 禁止移动赋值操作符
* */template<typename _Key, typename _Tp, typename _Hash = hash<_Key>, typename _Pred = std::equal_to<_Key>, typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >class threadsafe_unordered_map{private: std::unordered_map<_Key,_Tp,_Hash,_Pred,_Alloc> map; // 用于控制读写访问的锁对象mutable RWLock lock;public: using map_type=std::unordered_map<_Key,_Tp,_Hash,_Pred,_Alloc>; using key_type=typename map_type::key_type; using mapped_type=typename map_type::mapped_type; using value_type=typename map_type::value_type; using hasher=typename map_type::hasher; using key_equal=typename map_type::key_equal; using allocator_type=typename map_type::allocator_type; using reference=typename map_type::reference; using const_reference=typename map_type::const_reference; using pointer=typename map_type::pointer; using const_pointer=typename map_type::const_pointer; using iterator=typename map_type::iterator; using const_iterator=typename map_type::const_iterator; using local_iterator=typename map_type::local_iterator; using const_local_iterator=typename map_type::const_local_iterator; using size_type=typename map_type::size_type; using difference_type=typename map_type::difference_type;
threadsafe_unordered_map()=default;
threadsafe_unordered_map(const threadsafe_unordered_map&)=delete;
threadsafe_unordered_map(threadsafe_unordered_map&&)=default;
threadsafe_unordered_map& operator=(const threadsafe_unordered_map&)=delete;
threadsafe_unordered_map& operator=(threadsafe_unordered_map&&)=delete; explicit threadsafe_unordered_map(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal(), const allocator_type& __a = allocator_type()):map(__n,__hf,__eql,__a){} template<typename _InputIterator>
threadsafe_unordered_map(_InputIterator __first, _InputIterator __last,
size_type __n = 0, const hasher& __hf = hasher(), const key_equal& __eql = key_equal(), const allocator_type& __a = allocator_type()):map(__first,__last,__n,__hf,__eql,__a){}
threadsafe_unordered_map(const map_type&v): map(v){}
threadsafe_unordered_map(map_type&&rv):map(std::move(rv)){} explicitthreadsafe_unordered_map(const allocator_type& __a):map(__a){}
threadsafe_unordered_map(const map_type& __umap, const allocator_type& __a):map(__umap,__a){}
threadsafe_unordered_map(map_type&& __umap, const allocator_type& __a):map(std::move(__umap),__a){}
threadsafe_unordered_map(initializer_list<value_type> __l,
size_type __n = 0, const hasher& __hf = hasher(), const key_equal& __eql = key_equal(), const allocator_type& __a = allocator_type()):map(__l,__n,__hf,__eql,__a){}
threadsafe_unordered_map(size_type __n, const allocator_type& __a)
: threadsafe_unordered_map(__n, hasher(), key_equal(), __a){}
threadsafe_unordered_map(size_type __n, const hasher& __hf, const allocator_type& __a)
: threadsafe_unordered_map(__n, __hf, key_equal(), __a){} template<typename _InputIterator>
threadsafe_unordered_map(_InputIterator __first, _InputIterator __last,
size_type __n, const allocator_type& __a):map(__first,__last,__n,__a){} template<typename _InputIterator>
threadsafe_unordered_map(_InputIterator __first, _InputIterator __last,
size_type __n, const hasher& __hf, const allocator_type& __a)
: threadsafe_unordered_map(__first, __last, __n, __hf, key_equal(), __a){}
threadsafe_unordered_map(initializer_list<value_type> __l,
size_type __n, const allocator_type& __a)
: threadsafe_unordered_map(__l, __n, hasher(), key_equal(), __a){}
threadsafe_unordered_map(initializer_list<value_type> __l,
size_type __n, const hasher& __hf, const allocator_type& __a)
: threadsafe_unordered_map(__l, __n, __hf, key_equal(), __a){} bool empty() const noexcept{ auto guard=lock.read_guard(); return map.empty();
}
size_type size() const noexcept{ auto guard=lock.read_guard(); return map.size();
}
size_type max_size() const noexcept{ auto guard=lock.read_guard(); return map.max_size();
}
iterator begin() noexcept{ auto guard=lock.write_guard(); return map.begin();
}
const_iterator begin() const noexcept{ auto guard=lock.read_guard(); return map.begin();
}
const_iterator cbegin() const noexcept{ auto guard=lock.read_guard(); return map.cbegin();
}
iterator end() noexcept{ auto guard=lock.write_guard(); return map.end();
}
const_iterator end() const noexcept{ auto guard=lock.read_guard(); return map.end();
}
const_iterator cend() const noexcept{ auto guard=lock.read_guard(); return map.cend();
} template<typename... _Args> std::pair<iterator, bool>
emplace(_Args&&... __args){ auto guard=lock.write_guard(); return map.emplace(std::forward<_Args>(__args)...);
} template<typename... _Args>
iterator
emplace_hint(const_iterator __pos, _Args&&... __args){ auto guard=lock.write_guard(); return map.emplace_hint(__pos, std::forward<_Args>(__args)...);
} std::pair<iterator, bool> insert(const value_type& __x){ auto guard=lock.write_guard(); return map.insert(__x);
} template<typename _Pair, typename = typename std::enable_if<std::is_constructible<value_type,
_Pair&&>::value>::type> std::pair<iterator, bool>
insert(_Pair&& __x){ auto guard=lock.write_guard(); return map.insert(std::forward<_Pair>(__x));
}
iterator
insert(const_iterator __hint, const value_type& __x) { auto guard=lock.write_guard(); return map.insert(__hint, __x);
} template<typename _Pair, typename = typename std::enable_if<std::is_constructible<value_type,
_Pair&&>::value>::type>
iterator
insert(const_iterator __hint, _Pair&& __x){ auto guard=lock.write_guard(); return map.insert(__hint, std::forward<_Pair>(__x));
} template<typename _InputIterator> voidinsert(_InputIterator __first, _InputIterator __last){ auto guard=lock.write_guard(); map.insert(__first, __last);
} void insert(initializer_list<value_type> __l){ auto guard=lock.write_guard(); map.insert(__l);
}
iterator erase(const_iterator __position){ auto guard=lock.write_guard(); return map.erase(__position);
}
iterator erase(iterator __position){ auto guard=lock.write_guard(); return map.erase(__position);
}
size_type erase(const key_type& __x){ auto guard=lock.write_guard(); return map.erase(__x);
}
iterator erase(const_iterator __first, const_iterator __last){ auto guard=lock.write_guard(); return map.erase(__first, __last);
} void clear() noexcept{ auto guard=lock.write_guard(); map.clear();
} void swap(map_type& __x) noexcept( noexcept(map.swap(__x._M_h)) ){ auto guard=lock.write_guard(); map.swap(__x._M_h);
}
hasher hash_function() const{ auto guard=lock.read_guard(); return map.hash_function();
}
key_equal key_eq() const{ auto guard=lock.read_guard(); return map.key_eq();
}
iterator find(const key_type& __x){ auto guard=lock.write_guard(); return map.find(__x);
}
const_iterator find(const key_type& __x) const{ auto guard=lock.read_guard(); return map.find(__x);
}
size_type count(const key_type& __x) const { auto guard=lock.read_guard(); return map.count(__x);
} std::pair<iterator, iterator> equal_range(const key_type& __x){ auto guard=lock.write_guard(); return map.equal_range(__x);
} std::pair<const_iterator, const_iterator>
equal_range(const key_type& __x) const{ auto guard=lock.read_guard(); return map.equal_range(__x);
}
mapped_type& operator[](const key_type& __k){ auto guard=lock.write_guard(); return map[__k];
}
mapped_type& operator[](key_type&& __k){ auto guard=lock.write_guard(); return map[std::move(__k)];
}
mapped_type& at(const key_type& __k){ auto guard=lock.write_guard(); return map.at(__k);
} const mapped_type& at(const key_type& __k) const{ auto guard=lock.read_guard(); return map.at(__k);
}
size_type bucket_count() const noexcept{ auto guard=lock.read_guard(); return map.bucket_count();
}
size_type max_bucket_count() const noexcept{ auto guard=lock.read_guard(); return map.max_bucket_count();
}
size_type bucket_size(size_type __n) const{ auto guard=lock.read_guard(); return map.bucket_size(__n);
}
size_type bucket(const key_type& __key) const{ auto guard=lock.read_guard(); return map.bucket(__key);
}
local_iterator begin(size_type __n) { auto guard=lock.write_guard(); return map.begin(__n);
}
const_local_iterator begin(size_type __n) const { auto guard=lock.read_guard(); return map.begin(__n);
}
const_local_iterator cbegin(size_type __n) const{ auto guard=lock.read_guard(); return map.cbegin(__n);
}
local_iterator end(size_type __n) { auto guard=lock.write_guard(); return map.end(__n);
}
const_local_iterator end(size_type __n) const{ auto guard=lock.read_guard(); return map.end(__n);
}
const_local_iterator cend(size_type __n) const{ auto guard=lock.read_guard(); return map.cend(__n);
} float load_factor() const noexcept{ auto guard=lock.read_guard(); return map.load_factor();
} float max_load_factor() const noexcept{ auto guard=lock.read_guard(); return map.max_load_factor();
} void max_load_factor(float __z){ auto guard=lock.write_guard(); map.max_load_factor(__z);
} void rehash(size_type __n){ auto guard=lock.write_guard(); map.rehash(__n);
} void reserve(size_type __n){ auto guard=lock.write_guard(); map.reserve(__n);
} /*
* 新增加函数,bool值返回是否找到
* 返回true时,将value中置为找到的值
* */bool find(const key_type& __x, mapped_type &value) const{ auto guard=lock.read_guard(); auto itor=map.find(__x); auto found=itor!=map.end(); if(found)
value=itor->second; return found;
} /*
* 新增加函数,返回读取锁的RAII对象
* 在对map进行读取操作时应该先调用此函数
* */raii read_guard()const noexcept{ return lock.read_guard();
} /*
* 新增加函数,返回写入锁的RAII对象
* 在对map进行写入操作时应该先调用此函数
* */raii write_guard()noexcept{ return lock.write_guard();
} /*
* 新增加函数
* 如果指定的key不存在，则增加key->value映射
* 如果指定的key存在返回key映射的值,否则返回value
* */mapped_type insertIfAbsent(const key_type& key,const mapped_type &value){ auto guard=lock.write_guard(); auto itor=map.find(key); if (itor==map.end()){ map.insert(value_type(key, value)); return value;
} return itor->second;
} /*
* 新增加函数
* 如果指定的key存在，则用value替换key映射的值,返回key原来映射的值
* 否则返回nullptr
* */std::shared_ptr<mapped_type> replace(const key_type& key,const mapped_type &value){ auto guard=lock.write_guard(); if (map.find(key)!=map.end()){ map.insert(value_type(key, value)); return std::make_shared<mapped_type>(value);
} return std::shared_ptr<mapped_type>();
} /*
* 新增加函数
* 如果存在key->value映射，则用newValue替换key映射的值,返回true
* 否则返回false
* */bool replace(const key_type& key,const mapped_type &value,const mapped_type &newValue){ auto guard=lock.write_guard(); auto itor=map.find(key); if (itor!=map.end()&&itor->second==value){ map.insert(value_type(key, newValue)); return true;
} return false;
} template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1, typename _Alloc1> friend booloperator==(const threadsafe_unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&, const threadsafe_unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&);
};template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>inline booloperator==(const threadsafe_unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, const threadsafe_unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
{ auto guardx=__x.lock.read_guard(); auto guardy=__y.lock.read_guard(); return __x.map._M_equal(__y.map);
}template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>inline booloperator!=(const threadsafe_unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, const threadsafe_unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
{ auto guardx=__x.lock.read_guard(); auto guardy=__y.lock.read_guard(); return !(__x == __y);
}
}/* namespace mt */}/* namespace gdface */#endif /* COMMON_SOURCE_CPP_THREADSAFE_UNORDERED_MAP_H_ */
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
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
说明:
因为RWLock禁止复制构造函数和赋值操作符,所以threadsafe_unordered_map也禁止复制构造函数和赋值操作符。
另外在类中增加几个用于多线程环境的函数(见源码中的中文注释),
当你需要对map加锁时需要用到raii write_guard()noexcept和raii read_guard()const noexcept。关于这两个函数返回的raii类参见我另一篇博客《C++11实现模板化(通用化)RAII机制》
而bool find(const key_type& __x, mapped_type &value) const则用于多线程环境查找__x对应的值。
下面三个新增加函数是参照java中ConcurrentMap<K,V>接口实现的
mapped_type insertIfAbsent(const key_type& key,const mapped_type &value);
std::shared_ptr<mapped_type> replace(const key_type& key,const mapped_type &value);bool replace(const key_type& key,const mapped_type &value,const mapped_type &newValue)
