版權(quán)聲明：本文為博主原創(chuàng)文章，轉(zhuǎn)載請注明源地址。 https://blog.csdn.net/10km/article/details/52072061
前一篇博客《C++11:基于std::queue和std::mutex構(gòu)建一個線程安全的隊列》中，實現(xiàn)了一個線程安全的隊列，本文說說如何實現(xiàn)一個線程安全的map。
在上一篇博客中，實現(xiàn)threadsafe_queue主要是依賴std::mutex信號量來實現(xiàn)線程對threadsafe_queue的獨占訪問,不論是只讀的函數(shù)還是寫函數(shù)對threadsafe_queue都是獨占訪問,因為對threadsafe_queue中的操作相對較少，而且主要操作push/pop都是寫操作,所以這樣做是沒問題的。
但對于map,除了insert/erase這樣的寫操作之外還有find這樣的讀取操作,如果每個線程都是獨占訪問，無疑是會影響效率的。
所以在實現(xiàn)線程安全的map時,我沒有選擇使用std::mutex控制所有的操作為獨占訪問，而是用RWLock來控制map對象的訪問，RWLock是我以前自己寫的一個類，將線程對資源的訪問分為讀取操作和寫入操作兩類，這兩類操作是獨占的，但允許多個線程讀取操作，允許一個線程寫訪問。也就是說多個線程在讀取操作的時候，要寫入的線程是阻塞的，直到所讀取操作線程執(zhí)行完讀取操作釋放讀取鎖，反之亦然，如果有一個線程在執(zhí)行寫入操作，所有要讀取操作的線程就得等著，直到寫入操作結(jié)束。
關(guān)于RWLock的源碼及更詳細的說明參見我的博客《無鎖編程:c++11基于atomic實現(xiàn)共享讀寫鎖(寫優(yōu)先)》
有了RWLock,基于std::unordered_map實現(xiàn)線程安全的map就比較簡單了，基本上是把unordered_map的源碼抄了一遍，對于unordered_map中的每個函數(shù)入口加一個RWLock的讀取鎖或?qū)懭腈i。
實現(xiàn)的基本原則很簡單:
對于const函數(shù)加讀取鎖，允許共享讀取，
對于非const函數(shù)，加寫入鎖，允許獨占寫入。
下面是完整的源碼:
/*
* 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實現(xiàn)線程安全map
* 禁止復制構(gòu)造函數(shù)
* 禁止復制賦值操作符
* 允許移動構(gòu)造函數(shù)
* 禁止移動賦值操作符
* */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);
} /*
* 新增加函數(shù),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;
} /*
* 新增加函數(shù),返回讀取鎖的RAII對象
* 在對map進行讀取操作時應(yīng)該先調(diào)用此函數(shù)
* */raii read_guard()const noexcept{ return lock.read_guard();
} /*
* 新增加函數(shù),返回寫入鎖的RAII對象
* 在對map進行寫入操作時應(yīng)該先調(diào)用此函數(shù)
* */raii write_guard()noexcept{ return lock.write_guard();
} /*
* 新增加函數(shù)
* 如果指定的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;
} /*
* 新增加函數(shù)
* 如果指定的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>();
} /*
* 新增加函數(shù)
* 如果存在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禁止復制構(gòu)造函數(shù)和賦值操作符,所以threadsafe_unordered_map也禁止復制構(gòu)造函數(shù)和賦值操作符。
另外在類中增加幾個用于多線程環(huán)境的函數(shù)(見源碼中的中文注釋),
當你需要對map加鎖時需要用到raii write_guard()noexcept和raii read_guard()const noexcept。關(guān)于這兩個函數(shù)返回的raii類參見我另一篇博客《C++11實現(xiàn)模板化(通用化)RAII機制》
而bool find(const key_type& __x, mapped_type &value) const則用于多線程環(huán)境查找__x對應(yīng)的值。
下面三個新增加函數(shù)是參照java中ConcurrentMap<K,V>接口實現(xiàn)的
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)
