C++ STL rope 可持久化平衡树 (可持久化数组)
2024-10-07 16:33:31
官方文档好像 GG 了。
rope 不属于标准 STL,属于扩展 STL,来自 pb_ds 库 (Policy-Based Data Structures)。
基本操作:
#include <ext/rope> // 头文件
using namespace __gnu_cxx; // 注意名称空间
rope<int> rp;
int main() {
rp.push_back(x); // 在末尾插入 x
rp.insert(pos, x); // 在 pos 处插入 x
rp.erase(pos, x); // 在 pos 处删除 x 个元素
rp.length(); // 返回 rp 的大小
rp.size(); // 同上
rp.replace(pos, x); // 将 pos 处的元素替换成 x
rp.substr(pos, x); // 从 pos 处开始提取 x 个元素
rp.copy(pos, x, s); // 从 pos 处开始复制 x 个元素到 s 中
rp[x]; // 访问第 x 个元素
rp.at(x); // 同上
return 0;
}
rope 内部是块状链表实现的,黑科技是支持 \(O(1)\) 复制,而且不会空间爆炸 (rope 是平衡树,拷贝时只拷贝根节点就行)。因此可以用来做可持久化数组。
拷贝历史版本的方式:
rope<int> *his[100000];
his[i] = new rope<int> (*his[i - 1]);
缺点是常数大 (C++ STL 的通病)。
还有一个叫 crope 的东西,crope 即 rope,可以用 cin/cout 直接输入输出,常用于字符串操作。
最新文章
- Solr Facet 默认值
- 商业智能BI
- java实现删除文件以及文件夹
- JAVA基础知识之JDBC——JDBC数据库连接池
- [IOS swift对比oc]
- linux安装桌面环境(GNOME)VNC连接Linux
- Codeforces Round #131 (Div. 2) B. Hometask dp
- 【转】网络中的AS自治域
- 如果使用得当,MySQL 也可以化身 NoSQL
- ios开发入门篇(二):Objective-C的简单语法介绍
- UIScrollView的属性总结
- centos 6.3 编译安装 nginx +mysql + php
- Windows系统如何使用sqlmap
- java.io与网络通信
- Django模型操作常用方法
- 深入理解jQuery中的each方法
- Spring Boot初识(4)- Spring Boot整合JWT
- C++基类的析构函数定义为虚函数的原因
- DDD领域模型数据访问权限之用户权限(十)
- 2017-2018-2 1723《程序设计与数据结构》第三周作业 &; 实验一 总结
热门文章
- git设置忽略文件.gitignore
- apt-cyg for Cygwin(setup-x86_64 .exe )在win10下的安装
- python3 装饰器修复技术@wraps到底是什么?
- mybatis的一些小细节
- *arg,**kwargs的参数作用的疑惑
- W3C、MDN及html常用标签介绍
- 【目录】linux 编程
- SpringMVC学习(12):基于Hibernate+Spring+Spring MVC+Bootstrap的管理系统实现
- Java面试宝典(6)混合(前端 + 数据库)
- 深入Spring:自定义IOC