STL 学习笔记

发表于 | 分类于 | | + s

STL

STL的容器都为左闭右开区间$[begin(), end())$

vector

  • size()：查询$vector$中元素的个数。
  • [index]：直接访问$vector$数组第$index$个元素。
  • push_back(x)：把$x$放在$vector$的表尾。
  • reverse(begin(), end())：把$begin()$到$end()$之间的元素翻转
  • reserve()：手动调整$capacity$
  • rbegin(), rend()：反向迭代器, rbegin()是最后一个元素，rend()是第一个元素

set

  • count()：查询$set$中元素的个数。
  • insert(x)：把$x$插入$set$.
  • lower_bound(x)：找到第一个大于等于$x$的元素(找不到返回$end()$)。
  • erase(x)：删除$x$迭代器所指向元素(不能删去$begin()$)。
  • set<type>::iterator：声明一个迭代器，访问元素使用data->x来访问，类似指针
  • rbegin(), rend()：反向迭代器, rbegin()是最后一个元素，rend()是第一个元素

map

  • rbegin(), rend()：反向迭代器, rbegin()是最后一个元素，rend()是第一个元素

string

  • substr(int a, int len)：把$[a,a+len]$提取出来返回值为$string$
  • length()：得出字符串长度
  • assign()：给string赋值，具体看使用
  • rbegin(), rend()：反向迭代器, rbegin()是最后一个元素，rend()是第一个元素

注意所有end()调用即会出错。

pbds

rope

P3835 【模板】可持久化平衡树
模板：可持久化平衡树

主要用lower_bound和insert(pos, x)
注意复制方法new rope<int >(*seq[v]);

// luogu-judger-enable-o2
#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/rope>
using namespace __gnu_cxx;

namespace flyinthesky {

    const int MAXN = 500000 + 5;

    rope<int > *seq[MAXN]; // 指针方便复制
    int Q;
    inline int rd() {
        register int data = 0, w = 1;
        register char ch = 0;
        while (ch != '-' && (ch > '9' || ch < '0')) ch = getchar();
        if (ch == '-') w = -1 , ch = getchar();
        while (ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
        return w * data;
    } 

    void clean() {
    }
    int solve() {

        clean();
        cin >> Q;
        seq[0] = new rope<int >;
        for (int i = 1; i <= Q; ++i) {
            int v, op, x; v = rd(), op = rd(), x = rd();
            seq[i] = new rope<int >(*seq[v]);
            if (op == 1) {
                seq[i]->insert(lower_bound(seq[i]->begin(), seq[i]->end(), x) - seq[i]->begin(), x);
            }
            if (op == 2) {
                auto it = lower_bound(seq[i]->begin(), seq[i]->end(), x);
                if (it != seq[i]->end() && *it == x) seq[i]->erase(it - seq[i]->begin(), 1);
            }
            if (op == 3) {
                printf("%d\n", lower_bound(seq[i]->begin(), seq[i]->end(), x) - seq[i]->begin() + 1);
            }
            if (op == 4) {
                printf("%d\n", *(seq[i]->begin() + x - 1));
            }
            if (op == 5) {
                auto it = upper_bound(seq[i]->begin(), seq[i]->end(), x);
                --it;
                printf("%d\n", (int)*it);
            }
            if (op == 6) {
                auto it = upper_bound(seq[i]->begin(), seq[i]->end(), x);
                printf("%d\n", (int)*it);
            }
        }

        return 0;
    }
}
int main() { 
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------