PAT知识点整理之STL

参考网站：Norway,  芹菜猪肉饺贼棒， Foreordination
参考书籍：《算法笔记》

STL相关

• Vector

  • 概述：变长数组

    • 用法：可以用来以邻接表的方式储存图（需要复习）
    • 例子：

    vector<node> name; //node是结构体的类型
    vector<vector<int> > name; //>>之间加空格

    vector<node> name; //node是结构体的类型
    vector<vector<int> > name; //>>之间加空格

  • 访问：

    1. 下标

       vector<typename>::iterator it;
       //vi[i]和*(vi.begin()+i)是等价的
       for(vector<int>::iterator it = vi.begin(); it != vi.end(); it++){
           printf("%d ", *it);
       }

    3. vi.size()

  • 操作：

    1. push_back(x) 就是在vector后面添加一个元素x， 时间复杂度为O(1)
    2. pop_back() 用以删除vector的尾元素， 时间复杂度为O(1)
    3. size() 获取vector中元素的个数，时间复杂度为O(1) 返回的是unsigned类型
    4. clear() 用来清空vector中的所有元素， 时间复杂度为O(N)， 其中N为vector中元素的个数
    5. insert() insert(it, x)用来向vector的任意迭代器it处插入一个元素x, 时间复杂度O(N)

• Set

  • 概述：自动排序的唯一数组
  • 用途：set重要的作用：自动去重，升序排序。
  • 例子：

    set<typename> name;
    set<int> name;
    // 定义和写法和vector基本一样，同样typename可以是任何基本类型，结构体，STL容器类型。
    //同样，typename是容器的时候，>>后要加空格，避免编译器当成位运算出错。

  • 访问：
    1. set只能通过迭代器iterator访问,因为除了vector和string之外的STL的容器都不支持以下标的方式访问。

       set<int> st;
       for(set<int>::iterator it=st.begin();it!=st.end();it++)
       {
           printf("%d ",*it);
       }

  • 操作：
    1. insert()函数，insert(x)：将x插入set容器中，并且自动递增排序和去重。时间复杂度为O(logN)，N为元素个数
    2. find()函数，find(value)：查找值为value的元素，返回它的迭代器。时间复杂度为O(logN),N为元素个数
    3. erase()函数，erase(x)：删除单个元素，时间复杂度为O(logN)；erase(a,b);删除左闭右开区间内[a,b)的元素，时间复杂度为O(b-a)；
    4. size()函数，size()：用来获得set内元素的个数，时间复杂度为O(1)
    5. clear()函数，clear()：用来清空set所有元素，时间复杂度为O(N)　
    6. earse() : 两个用法 :删除单个元素 erase(it)即删除迭代器为it处的元素 vi.erase(vi.begin() + 3) 删除vi中第4个元素；删除一个区间内的所有元素 erase(first, last) 删除[first, last) 左闭右开

• String

  • 概述：用来代替char[]
  • 用途：当作字符。。。
  • 例子：

    string str;
    string str="abcd";

  • 访问：

    1. 可以如同字符数组一样去访问string

    2. string的迭代器不需要参数，直接定义string::iterator it;

       string str="abcd";
       for(int i=0;i<str.length;i++)
       {
           printf("%c ",str[i]);//a b c d
       }
       
       //通过迭代器访问string内容
       for(string::iterator it=str.begin();it!=str.end();it++)
       {
           pritnf("%c ",*it);
       }

  • 操作：
    1. operator+=这是string的加法， 可以将两个string直接拼接起来
    2. compare operator 两个string类型可以直接使用 == != < <= > >= 比较大小，比较规则是字典序
    3. length()/size() length()返回string的长度
    4. insert(pos, string), 在pos号位置插入字符串string

       string str1 = "abcxyz", str2 = "opq"; str.insert(3, str2);  //abcopqxyz
       str.insert(str1.begin() + 3, str2.begin(), str2.end); //abcopqxyz

    5. erase()

       string str = "abcdefg";
       str.erase(str.begin()+4); // -> abcdfg
       str.erase(str.begin()+2, str.end()-1); // -> abg
       str.erase(3, 2); // -> abcfg

    6. clear() 用以清空string中的数据
    7. substr(pos, len) 返回从pos号位置开始、长度为len的子串
    8. string::npos
    9. find();str1.find(str2)，当str2是str1的子串时，返回其在str中第一次出现的位置；如果不是其子串，那么返回string::npos; str1.find(str2, pos) 从str1的pos号位置开始匹配str2, 返回值同上
    10. replace();
        str.replace(pos, len, str2),把str从pos号位置开始、长度为len的子串替换为str2;
        str.replace(it1, it2, str2),把str的迭代器[it1, it2)范围的子串替换为str2

• Map

  • 概述：map 可以将任何基本类型(包括STL容器) 映射到任何基本类型(包括STL容器)

  • 用途：

    1. 建立字符和整数映射的题目
    2. 判断大整数或者其他类型数据是否存在的题目，可以把map当bool数组用
    3. 字符串和字符串的映射可能遇到
       如果一个键需要对应多个值，就只能用multimap
       unordered_map 以散列代替map内部的红黑树实现，处理无排序功能
    4. C++11多了unordered_map，说是速度快很多，有时间关注

  • 例子：

    map<typename1, typename2> mp;

  • 访问：

    1. 通过下标访问 m[‘a’]
    2. 通过迭代器

       
       for(map<char,int>::iterator it=mp.begin();it!=mp.end();it++)
       {
       printf("%c %d\n",it->first,it->second);//it->first:当前映射的键，it->second:当前映射的值
       }

  • 操作：

    1. find()，find(key)：返回键为key的映射，时间复杂度为O(logN)

    2. erase()
       删除单个元素：
       mp.erase(it)：it为需要删除的元素的迭代器。时间复杂度为O(1)
       mp.erase(key):key为删除元素的键，时间复杂度为O(logN)；

       删除区间内的元素，左闭右开[start,end)

    3. size()获得map中映射的对数
    4. clear() 用来清空map中的所有元素

• Queue

  • 概述：实现先进先出的容器
  • 用途：
    1. 实现广度优先搜索时，可以不用自己动手实现一个队列，而是用queue代替
  • 例子：

    queue<typename> name;
    queue<int> q;

  • 访问：
    queue是一种先进先出的限制性数据结构。通过front()访问队首元素，通过back()来访问队尾元素。

    queue<int> q;
    for(int i=1;i<=5;i++)
    {
    q.push(i);//依次将i入队，1,2,3,4,5
    }
    printf("%d %d\n",q.front(),q.back());//输出结果1,5

  • 操作：
    1. front()，back()。获取队首，队尾元素，时间复杂度为O(1)
    2. pop()。队首元素出队，时间复杂度为O(1)
    3. empty()。检测queue是否为空，返回bool类型，true为空。
    4. size()。返回queue内元素个数
       
       
       
  • 其他：此外还有个priority_queue（优先队列，自定义优先级）

• Stack

  • 概述：实现后进先出的容器
  • 用途：
    1. 模拟递归
  • 例子：

    stack<typename> sk;

  • 访问：
    只能通过top()来访问栈顶元素。

    stack<int> sk;
    for(int i=1;i<=5;i++)
    {
    sk.push(i);//push(i)用来把i压入栈，入栈顺序1,2,3,4,5
    }
    printf("%d\n",sk.top()); // -> 5

  • 操作：
    1. push() ：将x入栈，时间复杂度为O(1)
    2. top() ：获取栈顶元素，时间复杂度为O(1)
    3. pop() ：出栈顶元素。
    4. empty() : 判断栈是否为空
    5. size() ：获得栈元素个数
       
       
       

• Pair

  Algorithm相关

• 交换———— swap();

• 反转———— reverse();

  int a[10] = {10, 11, 12, 13, 14, 15};
  reverse(a, a+4); //数组
  string str= "12345678"
  reverse(str.begin()+2, str.begin()+6); 注意左闭右开// ->12543678 

• 全排列———— next_permutation()

  int a[10] = {1, 2, 3};
  do{
  // etc...
  }while(next_permutation(a, a+3));