当前位置:   article > 正文

C++11:基于std::unordered_map和共享锁构建线程安全的map_std::unordered_map 现成安全

std::unordered_map 现成安全

前一篇博客《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)){}
	explicit
	threadsafe_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>
    void
    insert(_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 bool
    operator==(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 bool
operator==(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 bool
operator!=(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()noexceptraii 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)
  • 1
  • 2
  • 3

完整代码参见码云git仓库:

https://gitee.com/l0km/common_source_cpp/blob/master/threadsafe_unordered_map.h

本文内容由网友自发贡献,转载请注明出处:https://www.wpsshop.cn/w/Cpp五条/article/detail/452267
推荐阅读
相关标签
  

闽ICP备14008679号