Menu

PAT知识点整理之STL

2

参考网站：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);
   }
      1. 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= &quot;12345678&quot;
reverse(str.begin()+2, str.begin()+6); 注意左闭右开// -&gt;12543678

  • 全排列———— next_permutation()

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

Related Posts

2 Comments

  1. Martica William Cusick
    July 31, 2020 @ 4:56 pm

    You do have a fabulous blog thanks. Martica William Cusick

    Reply

  2. make money
    August 30, 2020 @ 11:18 pm

    Your mode of explaining all in this post is truly nice, all be able to effortlessly know it, Thanks a lot. Marla Horton Obie

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *