算法拾遗[4]——STL用法

发表于 | 分类于

主要bb一下优先队列和字符串吧. 哦还有 bitset.

优先队列

  • 定义很容易: priority_queue<int> pq;
  • 内部是一个堆.

基本操作

  • pq.top() 取堆顶元素; (没有 front() 方法!)
  • pq.push(x) 插入;
  • pq.pop() 删除(删除堆顶);
  • pq.empty() 判断是否为空.

自定义优先级

  • 最大堆: priority_queue<int> pq;
  • 最小堆: priority_queue< int, vector<int>, greater<int> > pq;
  • 事实上还有自定义优先级 cmp 的方法(优先级最大的最先出队): 
    1
    2
    3
    4
    5
    6
    7
    8
    struct cmp
    {
        bool operator() (const int a, const int b) const
        { // a优先级较小时返回true.
            return a > b;
        }
    };
    priority_queue<int, vector<int>, cmp> pq; // 此时也是最小堆

例题

  • 百练 4078: http://bailian.openjudge.cn/practice/4078/

字符串

定义更容易: string s;

基本操作

  • s.size() 串长度(下标从0 开始)；
  • s.substr(a, n) 构造子串, a为第一个字符的下标, n为子串字符长度;
  • s'find(it1, it2, x) 在指针 it1 和 it2 中间查找字符 x; (s.find(x) 为整个 s 中查找 x)
  • s.erase(a) 删除元素, a貌似是指针, 可以和 find 合用去除指定字符, 如 s.erase(std::find(s.begin(), s.end(), ' ')); 去掉所有空格;
  • s.empty() 判断是否为空;
  • 支持 push_back 和 pop_back;
  • 支持 +, = 和 == 运算.

遍历操作

  • 可以用 auto it = s.begin(); it != s.end(); it++ 遍历;
  • 但我一般都用 int i = 0; i < s.size(); i++ 遍历.

和数字的转换

字符串转数字

  • stoi, stol, stoll: 字符串转整数;
  • stof, stod, stold: 字符串转浮点数;

数字转字符串

  • to_string 直接转成 std::string.

位向量

定义: bitset<length> b(value);

基本操作

  • 支持位运算 &, ^, <<, >>等;
  • to_string() 转化为字符串;
  • to_ulong(), to_ullong() 转化为无符号整数;
  • flip(i) 第i位取反, 下标从0开始. flip() 全部按位取反.