首页 > 编程语言 >并发编程数据结构-栈

并发编程数据结构-栈

时间：2024-09-08 16:06:00浏览次数：5  
标签：std mtx lock 编程 pop 并发 other 数据结构 stack

并发编程数据结构-栈

有锁栈

Stack1 - 基础线程安全栈

Stack1 是一个简单的线程安全栈实现，使用了 std::mutex 来保证 push 和 pop 操作的原子性。主要特点包括：

  • 使用 std::lock_guard 确保操作期间栈的线程安全。
  • 提供了两种 push 操作（左值引用和右值引用），优化了性能。
  • pop 操作抛出自定义的 EmptyStackError 异常，以处理栈为空的情况。
  • 提供了 pop(T& v) 和 pop() 两种接口，方便用户选择直接传引用或返回 shared_ptr。
  • 问题：用户需要不断检查 empty() 并手动处理栈空的情况，这在多线程环境下并不高效。
template <typename T>
class Stack1
{
public:
    Stack1() = default;
    ~Stack1() = default;
    Stack1(const Stack1&) = delete;
    Stack1& operator=(const Stack1&) = delete;
    Stack1(Stack1&& other) noexcept{
        std::scoped_lock lock(_mtx, other._mtx);
        _stack = std::move(other._stack);
    }

    Stack1& operator=(Stack1&& other) noexcept
    {
        if(this != &other)
        {
            std::scoped_lock lock(_mtx, other._mtx);
            _stack = std::move(other._stack);
        }
        return *this;
    }


    void push(const T&v)
    {
        std::lock_guard<std::mutex> lock(_mtx);
        _stack.emplace(v);
    }

    void push(T &&v)
    {
        std::lock_guard<std::mutex> lock(_mtx);
        _stack.emplace(std::move(v));
    }

    void pop(T &v)
    {
        std::lock_guard<std::mutex> lock(_mtx);
        if(_stack.empty()) throw EmptyStackError();
        v = std::move(_stack.top());
        _stack.pop();
    }

    std::shared_ptr<T> pop()
    {
        std::lock_guard<std::mutex> lock(_mtx);
        if(_stack.empty()) throw EmptyStackError();
        auto res = std::make_shared<T>(std::move(_stack.top()));
        _stack.pop();
        return res;
    }

    bool empty() const
    {
        std::lock_guard<std::mutex> lock(_mtx);
        return _stack.empty();
    }
private:
    std::stack<T> _stack;
    mutable std::mutex _mtx;
};

Stack2 - 引入条件变量的栈

Stack2 在 Stack1 的基础上，通过引入条件变量 std::condition_variable 改进了 pop 操作，使得线程在栈为空时可以阻塞等待，直到有数据入栈时才唤醒。

  • 使用 wait_pop 代替普通的 pop，在栈为空时阻塞线程，避免繁琐的轮询检查。
  • 每次 push 操作后，会通知阻塞的线程，解除等待状态。
  • 问题：在wait_pop中，如果在获得了cv的通知之后抛出异常，导致其他的线程无法获得该notify，因此全部阻塞。
template<typename T>
class Stack2
{
public:
    Stack2() = default;
    ~Stack2() = default;
    Stack2(const Stack2&) = delete;
    Stack2& operator=(const Stack2&) = delete;
    Stack2(Stack2&& other) noexcept
    {
        std::scoped_lock lock(_mtx, other._mtx);
        _stack = std::move(other._stack);
    }

    Stack2& operator=(Stack2&& other) noexcept
    {
        if(this != &other)
        {
            std::scoped_lock lock(_mtx, other._mtx);
            _stack = std::move(other._stack);
        }
        return *this;
    }

    void push(const T& v)   // 入栈，唤醒阻塞的线程
    {
        std::unique_lock<std::mutex> lock(_mtx);
        _stack.emplace(v);
        _cv.notify_one();
    }

    void push(T&& v)   // 入栈，唤醒阻塞的线程
    {
        std::unique_lock<std::mutex> lock(_mtx);
        _stack.emplace(std::move(v));
        _cv.notify_one();
    }

    void wait_pop(T& v)
    {
        std::unique_lock<std::mutex> lock(_mtx);
        _cv.wait(lock, [this]()->bool{return !_stack.empty();});
        v = std::move(_stack.top());
        _stack.pop();
    }

    std::shared_ptr<T> wait_pop()
    {
        std::unique_lock<std::mutex> lock(_mtx);
        _cv.wait(lock, [this]()->bool{return !_stack.empty();});
        auto res = std::make_shared<T>(std::move(_stack.top()));  // 当此处抛出异常，由于本线程获得了cv的通知，导致其他的线程无法获得改notify，因此全部阻塞
        _stack.pop();
        return res;
    }

    void pop(T &v)
    {
        std::lock_guard<std::mutex> lock(_mtx);
        if(_stack.empty()) throw EmptyStackError();
        v = std::move(_stack.top());
        _stack.pop();
    }

    std::shared_ptr<T> pop()
    {
        std::lock_guard<std::mutex> lock(_mtx);
        if(_stack.empty()) throw EmptyStackError();
        auto res = std::make_shared<T>(std::move(_stack.top()));
        _stack.pop();
        return res;
    }

    bool empty() const
    {
        std::lock_guard<std::mutex> lock(_mtx);
        return _stack.empty();
    }

private:
    mutable std::mutex _mtx;
    std::condition_variable _cv;
    std::stack<T> _stack;
};

Stack3 - 内存提前分配的优化栈

Stack3 进一步优化了 Stack2 中的潜在问题，通过提前在 push 时进行内存分配，避免在 wait_pop 中由于内存分配失败而抛出异常。内部栈_stack中直接存储数据的shared_ptr而不是数据本身，这样在pop时避免了构造返回值shared_ptr抛出异常的问题。

将数据分配内存的时间提前到push的过程中，这样wait_pop就不会因为无法分配内存抛出异常了

template<typename T>
class Stack3
{
public:
    Stack3() = default;
    ~Stack3() = default;
    Stack3(const Stack3&) = delete;
    Stack3& operator=(const Stack3&) = delete;
    Stack3(Stack3&& other) noexcept
    {
        std::scoped_lock lock(_mtx, other._mtx);
        _stack = std::move(other._stack);
    }

    Stack3& operator=(Stack3&& other) noexcept
    {
        if(this != &other)
        {
            std::scoped_lock lock(_mtx, other._mtx);
            _stack = std::move(other._stack);
        }
        return *this;
    }
    
    void push(const T& v)   // 入栈，唤醒阻塞的线程
    {
        auto t = std::make_shared<T>(v);
        std::unique_lock<std::mutex> lock(_mtx);
        _stack.push(t);
        _cv.notify_one();
    }

    void push(T&& v)   // 入栈，唤醒阻塞的线程
    {
        auto t = std::make_shared<T>(std::move(v));
        std::unique_lock<std::mutex> lock(_mtx);
        _stack.push(t);
        _cv.notify_one();
    }

    void wait_pop(T& v)
    {
        std::unique_lock<std::mutex> lock(_mtx);
        _cv.wait(lock, [this]()->bool{return !_stack.empty();});
        v = std::move(*_stack.top());
        _stack.pop();
    }

    std::shared_ptr<T> wait_pop()
    {
        std::unique_lock<std::mutex> lock(_mtx);
        _cv.wait(lock, [this]()->bool{return !_stack.empty();});
        auto res = _stack.top();  // 当此处抛出异常，由于本线程获得了cv的通知，导致其他的线程无法获得改notify，因此全部阻塞
        _stack.pop();
        return res;
    }

    void pop(T &v)
    {
        std::lock_guard<std::mutex> lock(_mtx);
        if(_stack.empty()) throw EmptyStackError();
        v = std::move(*_stack.top());
        _stack.pop();
    }

    std::shared_ptr<T> pop()
    {
        std::lock_guard<std::mutex> lock(_mtx);
        if(_stack.empty()) throw EmptyStackError();
        auto res = _stack.top();
        _stack.pop();
        return res;
    }

    bool empty() const
    {
        std::lock_guard<std::mutex> lock(_mtx);
        return _stack.empty();
    }

private:
    mutable std::mutex _mtx;
    std::condition_variable _cv;
    std::stack<std::shared_ptr<T>> _stack;
};

标签：std,mtx,lock,编程,pop,并发,other,数据结构,stack
From： https://www.cnblogs.com/sfbslover/p/18402978

相关文章

  • 数据结构基础讲解（三）——线性表之循环链表专项练习
    本文数据结构讲解参考书目：通过网盘分享的文件：数据结构 C语言版.pdf链接: https://pan.baidu.com/s/159y_QTbXqpMhNCNP_Fls9g?pwd=ze8e 提取码:ze8e数据结构基础讲解（二）——线性表之单链表专项练习-CSDN博客 个人主页：樱娆π-CSDN博客目录循环链表双向链表......
  • 【数据结构】单链表专题
    链表的概念及结构概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表的结构跟火车车厢相似，淡季时车次的车厢会相应减少，旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上，不会影响其他车......
  • Python 语法糖：让编程更简单（续）
    Python语法糖：让编程更简单（续）6.SlicenotationSlicenotation是Python中的一种语法糖，用于从列表或字符串中获取子串或子列表。例如：numbers=[1,2,3,4,5]print(numbers[1:3])#Output:[2,3]这段代码将从numbers列表中获取索引为1到3的子列表。7.f-string......
  • 数据结构基础讲解（二）——线性表之单链表专项练习
    本文数据结构讲解参考书目：通过网盘分享的文件：数据结构 C语言版.pdf链接: https://pan.baidu.com/s/159y_QTbXqpMhNCNP_Fls9g?pwd=ze8e 提取码:ze8e 上一节我讲了线性表中顺序表的定义以及常用的算法，那么这节我将继续讲解顺序表中的链式结构以及常见的算法。数据......
  • 数据结构基础讲解（一）——线性表之顺序表专项练习
     本文数据结构讲解参考书目：通过网盘分享的文件：数据结构 C语言版.pdf链接:https://pan.baidu.com/s/159y_QTbXqpMhNCNP_Fls9g?pwd=ze8e提取码:ze8e目录前言一.线性表的定义二.线性表的基本操作三.线性表的顺序存储和表示四.顺序表中基本操作的实现1.顺序表......
  • 常见并发工具类的使用场景
    常见并发工具类的使用场景ReentrantLockReentrantLock是一种可重入的独占锁，它允许同一个线程多次获取同一把锁而不会被阻塞。它的功能类似于synchronized是一种互斥锁，可以保证线程安全。可中断可以设置超时时间可以设置为公平锁支持多个条件变量与synchronized一样，都支......
  • Python编程：探索有趣的代码设计模式
    Python编程是一门广泛应用的技术，无论是在数据分析、人工智能，还是在Web开发中，都扮演着不可或缺的角色。而在编写Python代码的过程中，掌握一些经典的代码设计模式，不仅能够提升编程效率，还能帮助我们更好地理解代码背后的逻辑。今天我们就来聊一聊一些有趣的Python代码设计模式，看看它们......
  • 马老师浑元十三刀本质是DDD程序=算法+数据结构：浑元形意太极的本质是领域驱动设计（02）
    浑元形意太极的本质是领域驱动设计（01）在软件开发的旅程中，领域驱动设计就是我们的指路明灯。它照亮了我们前进的道路，驱散了迷茫的阴霾。有了领域驱动设计的指引，我们不再畏惧未知，不再害怕挑战。我们知道，无论前方有多么艰难的障碍，都有领域驱动设计为我们指明方向。领域驱动设计就......
  • 【数据结构】18.图（Graph）
    一、图的基本概念图是由顶点集合及顶点间的关系组成的一种数据结构：G=(V，E)，其中：V={x|x属于某个数据对象集}是有穷非空集合；E={(x,y)|x,y属于V}或者E={<x,y>|x,y属于V&&Path(x,y)}是顶点间关系的有穷集合，也叫做边的集合。注意:线性表可以是空表，树可以是空树，但图......
  • JAVA(十四)类和对象之面向对象编程
    编程的分类按编程风格分类面向过程编程和面向对象编程和面向接口编程1.1面向过程编程过程式编程，也称为命令式编程，是一种编程范式，它依赖于过程调用来实现逻辑。代码按照一定的顺序执行，从而实现功能。在过程式编程中，程序被组织成一系列的过程或函数调用，每个过程都负责执行特......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99