专栏首页10km的专栏C++11:基于std::unordered_map和共享锁构建线程安全的map

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

版权声明:本文为博主原创文章,转载请注明源地址。 https://blog.csdn.net/10km/article/details/52072061

前一篇博客《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_ */

说明: 因为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)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • c/c++:for each遍历 __VA_ARGS__ 中的每一个元素

    版权声明:本文为博主原创文章,转载请注明源地址。 https://blog.csdn.net...

    用户1148648
  • thrift/swift:对swift2thrift-generator-cli IDL生成工具的改进

    版权声明:本文为博主原创文章,转载请注明源地址。 https://blog.csdn.net...

    用户1148648
  • java:commons pool2 在android下的使用

    版权声明:本文为博主原创文章,转载请注明源地址。 https://blog.csdn.net...

    用户1148648
  • Python编程技巧:如何用Map, Filter, Reduce代替For循环?

    for 循环就像是一把瑞士军刀,它可以解决很多问题,但是,当你需要扫视代码,快速搞清楚代码所做的事情时,它们可能会让人不知所措。

    AI研习社
  • 再谈Newtonsoft.Json高级用法

      上一篇Newtonsoft.Json高级用法发布以后收到挺多回复的,本篇将分享几点挺有用的知识点和最近项目中用到的一个新点进行说明,做为对上篇文章的补充。 ...

    用户1168362
  • Spring Cloud Stream使用细节

    上篇文章我们看了Spring Cloud Stream的基本使用,小伙伴们对Spring Cloud Stream应该也有了一个基本的了解,但是上篇文章中的消息...

    江南一点雨
  • 结合ABP源码实现邮件发送功能

    1. 前言 最近pm临时提出了多种邮件验证操作的需求,因为一时间也没有找到好的邮件收发组件,也抱着研究ABP的心态,就花了几小时时间探究了一下ABP中关于Em...

    潘成涛
  • 接口思考小笔记

    Qt君
  • asp.net web api 下载之断点续传

    一、基本思想 利用 HTTP 请求的Range标头值,来向服务端传递请求数据的开始位置和结束位置。服务端获得这两个参数后,将指定范围内的数据传递给客户端。当客户...

    甜橙很酸
  • 力扣题目汇总(转换成小写字母,唯一摩尔斯密码,有序数组平方)

    实现函数 ToLowerCase(),该函数接收一个字符串参数 str,并将该字符串中的大写字母转换成小写字母,之后返回新的字符串。

    小小咸鱼YwY

扫码关注云+社区

领取腾讯云代金券