关于学到的一些新东西

758 字

4 分钟

关于学到的一些新东西

2022-06-05

算法

刚刚结束了这次的周赛，最后一题还是没有写出来，但是学到了关于字符串的一些新知识：

这是原题：https://leetcode.cn/problems/design-a-text-editor/

现在大概知道怎么做了，通过两个双端队列模拟即可，根本不需要维护光标的位置，这样思考量大大减少了。

1.c++的string也有insert和erase函数，用法和vector等容器一样，这个我以前居然不知道…

2.还有一种做法就是利用双向链表模拟，这个我就是这样做的，但是debug把自己绕糊涂了，自己对这个数据结构感觉还是比较生疏，但是学到了几个比较有用的api：next()和prev()还有advance(), 这些都是对迭代器操作的一些函数，具体用法为

advance()的函数原型

1
templatevoid advance( InputIt& it, Distance n );
2

3
templateconstexpr void advance( InputIt& it, Distance n );

advance()的含义：表示将输入迭代器it移动n个单位的步长，其中n可为正数与负数。注意：这里的输入迭代器为双向迭代器，即迭代器即可右移，也可左移。若移动n个单位的步长后，超出迭代器范围[begin,end)，则此行为未定义。

advance()函数返回值：函数返回值为void，也就是将传入的迭代器用引用的方式移动n个单位了。

next()的函数原型：

1
templateForwardIt next(
2
  ForwardIt it,
3
  typename std::iterator_traits::difference_type n = 1 );
4

5
templateconstexpr InputIt next(
6
  InputIt it,
7
  typename std::iterator_traits::difference_type n = 1 );

next()的含义：表示迭代器右移n个单位的步长，即迭代器+n。若移动n个单位的步长后，超出迭代器范围[begin,end)，则此行为未定义。

next()函数返回值：函数的返回值为一个迭代器，也就是传入迭代器右移n个单位后，返回这个移动后的新迭代器，其中n=1，可以省略第二个参数。

prev()的函数原型：

1
templateBidirIt prev(
2
  BidirIt it,
3
  typename std::iterator_traits::difference_type n = 1 );
4

5
templateconstexpr BidirIt prev(
6
  BidirIt it,
7
  typename std::iterator_traits::difference_type n = 1 );
8
prev()的含义：
9
表示迭代器左移n个单位，即迭代器-n。
10
若移动n个单位的步长后，超出迭代器范围[begin,end)，则此行为未定义。

prev()函数返回值：函数的返回值为一个迭代器，也就是传入迭代器左移n个单位后，返回这个移动后的新迭代器，其中n=1，可以省略第二个参数。

3.有关rope的学习

1
#include///头文件
2
using namespace __gnu_cxx;
3
rope  x;
4
int main(){
5
    x.push_back(x); ///在末尾加x
6
    x.insert(pos, x); ///在pos位置加入x
7
    x.erase(pos, x); ///从pos位置删除x个元素
8
    x.copy(pos, len, x); ///从pos开始len个元素用x代替
9
    x.replace(pos, x); ///从pos开始全部换为x
10
    x.substr(pos, x); ///提取pos开始x个元素
11
    x.at(x)/[x]; ///访问第x个元素
12
    return 0;
13
}