首页 > 其他分享 >链表

链表

时间:2024-04-02 18:01:41浏览次数:21  
标签:std current head node lk next 链表

template<typename T>
class threadsafe_list
{
  struct node  // 1
  {
    std::mutex m;
    std::shared_ptr<T> data;
    std::unique_ptr<node> next;
    node():  // 2
      next()
    {}

    node(T const& value):  // 3
      data(std::make_shared<T>(value))
    {}
  };

  node head;

public:
  threadsafe_list()
  {}

  ~threadsafe_list()
  {
    remove_if([](node const&){return true;});
  }

  threadsafe_list(threadsafe_list const& other)=delete;
  threadsafe_list& operator=(threadsafe_list const& other)=delete;

  void push_front(T const& value)
  {
    std::unique_ptr<node> new_node(new node(value));  // 4
    std::lock_guard<std::mutex> lk(head.m);
    new_node->next=std::move(head.next);  // 5
    head.next=std::move(new_node);  // 6
  }

  template<typename Function>
  void for_each(Function f)  // 7
  {
    node* current=&head;
    std::unique_lock<std::mutex> lk(head.m);  // 8
    while(node* const next=current->next.get())  // 9
    {
      std::unique_lock<std::mutex> next_lk(next->m);  // 10
      lk.unlock();  // 11
      f(*next->data);  // 12
      current=next;
      lk=std::move(next_lk);  // 13
    }
  }

  template<typename Predicate>
  std::shared_ptr<T> find_first_if(Predicate p)  // 14
  {
    node* current=&head;
    std::unique_lock<std::mutex> lk(head.m);
    while(node* const next=current->next.get())
    {
      std::unique_lock<std::mutex> next_lk(next->m);
      lk.unlock();
      if(p(*next->data))  // 15
      {
         return next->data;  // 16
      }
      current=next;
      lk=std::move(next_lk);
    }
    return std::shared_ptr<T>();
  }

  template<typename Predicate>
  void remove_if(Predicate p)  // 17
  {
    node* current=&head;
    std::unique_lock<std::mutex> lk(head.m);
    while(node* const next=current->next.get())
    {
      std::unique_lock<std::mutex> next_lk(next->m);
      if(p(*next->data))  // 18
      {
        std::unique_ptr<node> old_next=std::move(current->next);
        current->next=std::move(next->next);
        next_lk.unlock();
      }  // 20
      else
      {
        lk.unlock();  // 21
        current=next;
        lk=std::move(next_lk);
      }
    }
  }
};

  

标签:std,current,head,node,lk,next,链表
From: https://www.cnblogs.com/fchy822/p/18111198

相关文章

  • [LeetCode]12. K 个一组翻转链表 C语言实现
    Problem:25.K个一组翻转链表目录思路解题方法复杂度Code思路官方思路多指针+翻转链表+结构体解题方法定义多指针用来查找的头节点每一组的头节点每一组的尾节点,用来找到下一组头节点复杂度时间复杂度:添加时间复杂度,示例:$O(n)$空间复杂度:添加空......
  • 【leetcode】链表篇刷题 --
    //删除指定value节点classSolution{public:ListNode*removeElements(ListNode*head,intval){//单独处理headwhile(head!=NULL&&head->val==val){ListNode*temp=head;head=head->next;......
  • C语言链表:链式魔法,数据之美
    导入链表,作为C语言中一种基础且重要的数据结构,以其独特的方式组织和存储数据,成为了解决许多复杂问题的关键。下面,我们将更具体地探讨C语言链表的各个方面。一、链表的基本结构链表由一系列节点组成,每个节点通常包含两部分:数据域和指针域。数据域用于存储实际的数据,而指针域......
  • 排序链表
    1、非递归//递归的归并排序classSolution{public:ListNode*sortList(ListNode*head){if(head==nullptr)returnhead;intlength=0;ListNode*node=head;while(node!=nullptr){length++;......
  • Python数据结构与算法——数据结构(链表、哈希表、树)
    目录链表  链表介绍  创建和遍历链表  链表节点插入和删除  双链表  链表总结——复杂度分析哈希表(散列表)哈希表介绍哈希冲突哈希表实现哈希表应用树树树的示例——模拟文件系统二叉树二叉树的链式存储 二叉树的遍历二叉搜索树插入......
  • 【数据结构】线性表-单链表
    编程语言:C++前言:节点:节点是链表的一个基本单元,包含两部分——数据域和指针域,数据域用于存储数据,指针域存储下一个节点的地址,形成链结。什么是单链表:n个节点链结成一个链表,即为线性表(a1,a2,a3……)的链式存储结构,每个节点只包含一个指针域的链表叫做单链表。链表组成:头节点、......
  • 数据结构-C语言描述(队列的链表实现)
    概述在日常生活中,先进先出似乎更加符合我们的日常认知。 排队的人群中,队首的人总是先离开,而队尾的人总是后离开。1.队列的基本原理和操作我们知道队列也是一种线性表,而今天我们就用非顺序储存结构(链表)来实现它。首先我们先明确队列的基本操作原理:因为同时涉及到队首和队......
  • 算法复习:链表
    链表定义structListNode{intval;ListNode*next;ListNode(intx):val(x),next(nullptr){}};链表的遍历:ListNodep=head; while(p!=null)p=p.next; 找到链表的尾结点:p=head; while(p.next!=null)p=p.next;链表节点的个数:     p=head......
  • 6-92 链表基本操作(Python语言描述)
    本题要求在给出的链节点类、和单链表类部分代码的情况下,编写好基本操作的各种python3代码实现,最后调用测试代码检验。函数接口定义:已实现的链节点类、和单链表类部分代码。如下:classSingleNode(object):"""单链表的结点"""def__init__(self,item):#_i......
  • 数据结构 —— 线性表的链式存储(链表)(C++)
    目录单链表(有头结点)定义初始化判空销毁清空求表长取值查找插入删除创建头部创建尾部创建本文相关知识:以链式存储结构来实现线性表(C++)如有错误请指正~~谢谢~后面更新循环链表和双向链表单链表(有头结点)以带头结点的单链表为例,操作更加简便!定义首先,为了增强程序的可读性,做出以......