H_On个人小站

个人站

这都被你发现了【惊
奖励你一朵小红花~


StandardTemplateLibrary

常用 stl 知识点总结

更新:

  • 2022-01-27 更新 bitset 相关,以前觉得用的不多,现在感觉还挺好用=w=
  • 2022-07-05 更新一些 string 相关操作:切片、反转、分割。

一些扩展:

  • getlinesscanfstringstream,控制小数输出,二元组,高级 for 循环请看:STL 进阶
  • <iomanip>,字符串和数组转换:STL 补充包

目录

简介

STL Standard Template Library - 标准模板库又称 C++ 泛型库,它在 std 命名空间中定义了常用的数据结构和算法,大大增加了我们编写算法的效率,使我们在摸索/学习算法或者解决问题时能够通过各种各样的容器来构造简单便利的数据结构。

vector 向量容器

你可以将 vector 容器理解为一个高级的数组,与数组一样能够通过下标来随机存取,但并不需要提前声明容器容量,也有很多便利的 方法 来对容器内部的元素进行操作。

贴(只在这里解释一遍,方便后续理解):“方法”是面对对象思想中的一个成分,与“函数”类似,也有传入变量,返回变量的定义。但“函数”面对的是整个程序的使用,“方法”针对的是“对象”的操作,“对象”也可以理解为一个“变量”,“对象”可以使用的“专属的函数”就是“方法”
函数与方法的使用有点不一样,这里简单介绍一下
函数:函数名(参数);
方法:对象变量名.方法名(参数);

vector 向量容器的声明

需要头文件 #include <vector>

vector<T> v;                    // T 是容器内元素的变量类型
vector<int> v;                  //声明一个空的 vector 容器 v ,其内部元素的数据类型是 int
vector<double> v(6);            //声明一个储存 double 型数据的 vector 容器,让它具有 6 的初始容量,下标是 0~5 初始值是 0.0
vector<double> v(8, 2.33);      //定义一个 v ,容量是 8 ,每个元素的值是2.33

迭代器

实际上,能够 遍历 一个 容器工具 都可以称作是 迭代器
而 STL 中为我们定义的迭代器也是同样的道理,而且已经足够好用了。
使用方法:容器类型<变量类型>::iterator 迭代器名;

例:vector<int>::iterator p;
p 就是储存 int 类型数据的 vector 容器的迭代器。

迭代器实质上是指针,也就是指向的数据的地址,因此会有【迭代器地址】的概念。
但是这个迭代器是有储存类型的,因此并不与普通的“指针变量”完全通用,只能说“形式上类似”,“实质上相同”。再次强调,使用方法是不完全相同的。

迭代器的遍历通常是这个样子的:
for (p = v.begin(); p != v.end(); p++) cout << *p << ' ';
可以看到迭代器指向的元素是与指针类似,可以使用 “++” 自增运算符。但是注意,迭代器只能使用 p++/p-- 不能使用 ++p/--p ,因为 p++ 实际上是一个特殊的操作,相当于链表中的 p = p->next 在迭代器操作中的简写。而 p 本身也可以用 *p 的形式来表示指向的元素,包括后面的【映射容器】中有两个元素,也可以使用 p->firstp->second 来指向其中的内容,与结构体指针也是有异曲同工之妙,关于多个内容的容器,后续会有具体的例子。

有关迭代器的使用,下文会给出实例,但不会再做详细解释了。

vector 向量容器的常用方法

v.push_back(e);                 //从容器末端追加一个元素,容器末端自动扩张
v.begin();                      //返回向量容器的首地址,也就是第一个元素的迭代器地址
v.end();                        //返回向量容器的尾地址,注意尾地址是最后一个元素的下一个位置的迭代器地址
v.insert(v.begin() + n, e);     //往指定地址的位置插入一个元素,如例:在 n 号元素**前**插入num
v.erase(p0[, p1]);              //删除一个元素,或删除一段元素,p 为迭代器地址
v.size()                        //返回 v 的大小(元素个数)
v.empty()                       //如果容器为空,返回“真”,如果不为空,返回“假”
v.clear()                       //清空容器内容

vector 向量容器的操作和遍历

#include <iostream>
#include <vector>
using namespace std;
int main() {
        //定义一个空的 int 型的向量容器
        vector<int> v;
        //尾部扩充的方式添加三个元素
        v.push_back(12);
        v.push_back(17);
        v.push_back(4);

        //定义一个对应类型的迭代器
        vector<int>::iterator p;

        //遍历输出容器内元素
        cout << "v: ";
        for (p = v.begin(); p != v.end(); p++) cout << *p << ' ';
        cout << endl;

        //查看现在容器内元素个数
        cout << "v.size() = " << v.size() << endl;

        //将容器清空
        v.clear();
        //再次查看容器长度
        cout << "After v.clear(), v.size() = " << v.size() << endl;
        //循环添加元素
        for (int i = 0; i < 6; i++) v.push_back(i);

        //在 3 号元素的前面插入一个数
        v.insert(v.begin() + 3, 233);
        //遍历查看一下容器内容
        cout << "After insert befor serial number 3 a number:" << endl;
        for (p = v.begin(); p != v.end(); p++) cout << *p << ' '; cout << endl;
        cout << "v.size() = " << v.size() << endl;

        //删除 5 号元素
        v.erase(v.begin() + 5);
        //遍历查看一下容器内容
        cout << "After delete number of serial number 5 :" << endl;
        for (p = v.begin(); p != v.end(); p++) cout << *p << ' '; cout << endl;

        //删除 2 号到 5 号之间的元素,注意:这个范围是【左闭右开】的
        v.erase(v.begin() + 2, v.begin() + 5);
        //遍历查看一下容器内容
        cout << "After delete numbers of serial number 2 to 5 :" << endl;
        for (p = v.begin(); p != v.end(); p++) cout << *p << ' ';
        cout << endl;

        //测试一下 empty() 方法的功能
        if (v.empty()) cout << "Is empty" << endl; else cout << "Not empty" << endl;
        v.clear();
        if (v.empty()) cout << "Is empty" << endl; else cout << "Not empty" << endl;
        return 0;
}
v: 12 17 4
v.size() = 3
After v.clear(), v.size() = 0
After insert befor serial number 3 a number:
0 1 2 233 3 4 5
v.size() = 7
After delete number of serial number 5 :
0 1 2 233 3 5
After delete numbers of serial number 2 to 5 :
0 1 5
Not empty
Is empty

string 字符串

string 是 C++ 中直接提供的一种新的【数据类型】。 字符串变量不同于字符数组构成的字符串,string 型的变量不需要提前定义长度,也就是说它的长度是 可变的string 型的变量可以很方便的添加和删除其中的字符和字符串,也可以直接使用下标进行查改。 它在声明的时候计算机会分配一个空间,当你的字符串变的过于长,超过现在已经分配的内存的时候,它会自动开辟一片新的 足够长 的内存,来存放变长的字符串。 这种变量类型在处理字符串上就变得很简便,最重要的是,更好理解了。

string 字符串的声明

string 型变量的使用并不需要特殊的头文件
一部分 string 字符串的操作需要头文件 #include <string>

string s;                       //声明一个空的 string 容器 s ,s 是一个空字符串,字符串长度为 0

string 字符串的常用方法

s.append(str);                  //从字符串末端追加一个字符串,注意只能是字符串不能是字符
s.begin();                      //返回字符串的首地址,也就是第一个字符的迭代器地址
s.end();                        //返回字符串的尾地址,也就是最后一个字符的下一个位置的迭代器地址
s.insert(p, str);               //往指定位置插入一个字符串,p 是整数下标
s.insert(p, c);                 //往指定迭代器位置插入一个字符,p 是迭代器
s.erase(p0[, p1]);              //删除迭代器所指的元素,或删除一个区间的所有元素,左闭右开
s.replace(step, len, str);      //从 step 开始,将写下来的 len 个字符替换成一个字符串 str。step 和 len 都是整数,str 是字符串。
s.compare(str);                 //比较两个字符串大小,两个字符串相等返回 0 ;s < str 返回一个负数;s > str 返回一个正数
s.find(c/str);                  //返回字符串 s 中第一次出现字符 c 或字符串 str 的下标值。如果没有找到返回 -1
s.length();                     //返回字符串的长度
s.empty();                      //判断字符串是否为空
s.clear();                      //清空字符串,但通常直接赋值空字符串来清空字符串即可: s = "";
s.c_str();                      //返回一个与 C 语言中的字符数组同类型的指针,使 string 类型的变量可以实用 C 中的 printf() 函数和 sscanf() 函数

string 字符串的操作及遍历

C++ 为 string 字符串类型的变量提供了很多方便实用的功能

s1 </<=/>/>=/==/!= s2           //两个字符串可以进行逻辑判断
s1 = s2                         //字符串之间可以互相赋值
s1 += s2                        //在 s1 尾部追加字符串(或字符)
s1 = s2 + s3                    //两个字符串可以相加,结果与顺序有关,如例:s2 在前面 s3 在后面

string 字符串也支持直接将字符数组的值赋给 string 类型变量

char s2[2000] = "abcd";
string s1 = s2;

集中测试

#include <iostream>
#include <string>
using namespace std;
int main() {
        //定义一个字符串变量
        string s;

        //从字符串末端添加一个字符串
        s.append("world");

        //string 型变量可以直接通过输出流输出
        cout << "1 - append: " << s << endl;

        //在指定位置前面插入字符串
        s.insert(0, "Hello");
        cout << "2 - insert string: " << s << endl;

        //在指定迭代器位置前插入一个字符
        s.insert(s.begin() + 5, ' ');
        cout << "3 - insert char: " << s << endl;

        //删除指定迭代器位置的字符
        s.erase(s.begin() + 2);
        cout << "4 - erase char: " << s << endl;

        //删除指定迭代器区间的字符
        s.erase(s.begin() + 2, s.begin() + 6);
        cout << "5 - erase string: " << s << endl;

        //从 1 号元素开始,将连续的 3 个字符替换成一个字符串 " abc "
        s.replace(1, 3, " abc ");
        cout << "6 - replace: " << s << endl;

        //获取字符串长度
        cout << "s.length() = " << s.length() << endl;

        //查找功能测试
        cout << "find 'a' = " << s.find('a') << endl;
        cout << "find \"abc\" = " << s.find("abc") << endl;

        //虽然输出是那个数,是因为二进制第一位是符号位,但输出流显示成无符号的整数了
        cout << "find \"def\" = " << s.find("def") << endl;
        //带符号的话就是 -1 了
        if (s.find("def") == -1) cout << "Not find" << endl;
        else cout << "OK" << endl;

        string s1 = "abc";
        string s2 = "abc";
        string s3 = "def";
        cout << "s1 = " << s1 << " s2 = " << s2 << " s3 = " << s3 << endl;

        //比较两个字符串
        if (s1.compare(s3) == 0) cout << "s1 = s3" << endl;
        else if (s1.compare(s3) > 0) cout << "s1 > s3" << endl;
        else if (s1.compare(s3) < 0) cout << "s1 < s3" << endl;

        //逻辑运算
        if (s1 == s2) cout << "s1 = s2" << endl;
        else cout << "s1 != s2" << endl;
        if (s1 > s3) cout << "s100000000000000 > s3" << endl;
        else cout << "s1 < s3" << endl;

        //简便操作
        s1 += s3; cout << "s1 = " << s1 << endl;
        s1 = s3 + s2; cout << "s1 = " << s1 << endl;

        //迭代器遍历
        cout << "Iterator traversal: ";
        string::iterator p;
        for (p = s.begin(); p != s.end(); p++) cout << *p; cout << endl;

        //下标循环遍历
        cout << "Serial traversal: ";
        for (int i = 0; i < s.length(); i++) cout << s[i]; cout << endl;

        //测试 empty() 方法的功能
        cout << "s.length() = " << s.length() << endl;
        if (s.empty()) cout << "Is empty" << endl; else cout << "Not empty" << endl;
        //s.clear();
        s = "";
        cout << "s.length() = " << s.length() << endl;
        if (s.empty()) cout << "Is empty" << endl; else cout << "Not empty" << endl;
        return 0;
}
1 - append: world
2 - insert string: Helloworld
3 - insert char: Hello world
4 - erase char: Helo world
5 - erase string: Heorld
6 - replace: H abc ld
s.length() = 8
find 'a' = 2
find "abc" = 2
find "def" = 18446744073709551615
Not find
s1 = abc s2 = abc s3 = def
s1 < s3
s1 = s2
s1 < s3
s1 = abcdef
s1 = defabc
Iterator traversal: H abc ld
Serial traversal: H abc ld
s.length() = 8
Not empty
s.length() = 0
Is empty

string 切片

s.substr(start_pos, [cut_len]) 切片操作。

  • 返回一个新的字符串,不修改原数据。
  • cut_len 参数不填就是切到末尾。

示例:

#include <iostream>
using namespace std;
int main() {
    string s = "abcd,efg,hi jk, lmn";
    cout << s.substr(4, 10) << endl;
    cout << s << endl;
    return 0;
}

运行结果:

,efg,hi jk
abcd,efg,hi jk, lmn

string 反转

需要导入 <algorithm> 库。

reverse(s.begin(), s.end()) 反转操作。

  • 传入两个迭代器。

示例:

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
        string s = "abcd,efg,hi jk, lmn";
        reverse(s.begin() + 4, s.end() - 3);
        cout << s << endl;
    return 0;
}

运行结果:

abcd ,kj ih,gfe,lmn

string 分割

  • 方法一:需要导入 <sstream> 库。
    • istringstream iss(s); 将字符串放入输入流,可以使用 getline 循环读取。
    • getline 有两种实现:
      • istream& getline(char* s, streamsize n); 遇到 \n 或数据为空结束读取。
      • istream& getline(char* s, streamsize n, char delim); 遇到 delim 或数据为空结束读取。
  • 方法二:使用字符串的方法实现。
    • s.find() 方法可以查找字符或者字符串。
    • s.substr() 方法可以切片。
    • s.erase() 方法可以删除字符或区间。

示例:

#include <iostream>
#include <vector>
#include <sstream>

using namespace std;

// 使用输入流实现
void split(string &s, const char split_char, vector<string> &res) {
    istringstream iss(s);
    string temp;
    while (getline(iss, temp, split_char)) res.push_back(temp);
}

// 适配不同参数的重写
vector<string> split(string &s, const char split_char) {
    vector<string> res;
    split(s, split_char, res);
    return res;
}

// 使用 find 方法和 substr 方法实现(支持字符串)
void splitByFind(string s, const string &split, vector<string> &res) {
    int pos;
    while(true) {
        pos = s.find(split);
        if (pos == -1) {
            res.push_back(s);
            break;
        }
        res.push_back(s.substr(0, pos));
        s.erase(s.begin(), s.begin() + pos + split.size());
        // 或者
        // s = s.substr(pos + split.size());
    }
}

// 适配不同参数的重写
void splitByFind(string &s, const char split_char, vector<string> &res) {
    string split_string; split_string += split_char;
    splitByFind(s, split_string, res);
}

vector<string> splitByFind(string &s, const char split_char) {
    vector<string> res; splitByFind(s, split_char, res); return res;
}

vector<string> splitByFind(string &s, const string &split_string) {
    vector<string> res; splitByFind(s, split_string, res); return res;
}

int main() {
    string s = "abcd,efg,hi jk, lmn";

    cout << "使用使用输入流实现" << endl;
    vector<string> r; split(s, ',', r); for (string ns : r) cout << ns << endl; cout << "---------------" << endl;
    for (string ns : split(s, ' ')) cout << ns << endl; cout << "---------------" << endl;

    cout << "使用 find 方法和 substr 方法实现(支持字符串)" << endl;
    for (string ns : splitByFind(s, ',')) cout << ns << endl; cout << "---------------" << endl;
    for (string ns : splitByFind(s, ",h")) cout << ns << endl; cout << "---------------" << endl;
    for (string ns : splitByFind(s, "aaa")) cout << ns << endl; cout << "---------------" << endl;

    return 0;
}

运行结果:

使用使用输入流实现
abcd
efg
hi jk
 lmn
---------------
abcd,efg,hi
jk,
lmn
---------------
使用 find 方法和 substr 方法实现(支持字符串)
abcd
efg
hi jk
 lmn
---------------
abcd,efg
i jk, lmn
---------------
abcd,efg,hi jk, lmn
---------------

set 集合容器

顾名思义,集合容器是用来储存一系列相同数据类型元素的容器,但没有一个排序规则计算机无法保存,因此 set 集合容器实现了红黑树(Red-Black Tree)的平衡二叉检索树的数据结构,在插入元素时,set 容器会自动调整二叉树,生成一个左子节点小于根节点小于右子节点的排序树,并且保证左右子树高度相同,以获得最快的检索速度。
平衡二叉检索树的检索效率高于 vectordequelist 等容器。由于 set 容器的构建原理,set 容器并不能修改,因为值如果改变,树的结构就可能需要调整,因此 set 中的内容只能增删查。

简单来说,set 容器可以自动排序插入的元素,可以快速的检索,是一个很适合用于需要对数据进行排列和查找的程序。
set 容器中不能储存重复的元素,如果插入已经存在的元素,将会没有效果;
multiset多重集合容器,与 set 相同可以对元素使用红黑树进行自动排序,可以储存相同的元素,如果需要排序的数据有重复,可以考虑使用 multiset
setmultiset 都定义在头文件 <set>

set 集合容器的声明

需要头文件 #include <set>

set<T> s;                       // T 是容器内元素的变量类型
multiset<T> ms;                 // T 是容器内元素的变量类型

set 集合容器的常用方法

//set 容器的方法
s.insert(e);                    // 将 e 加入集合,自动排序,默认升序,不可重复插入
s.erase(k);                     // 删除键值为 k 的元素,返回删除元素总数(只有 0 或 1 )
s.erase(ptr);                   // 删除迭代器 ptr 指向的元素
s.find(k);                      // 查找键值为 k 的元素的位置,返回迭代器地址,若没找到返回 s.end()
//multiset 容器的方法
ms.insert(e);                   // 将 e 加入集合,自动排序,默认升序,可重复插入
ms.erase(k);                    // 删除所有键值为 k 的元素,返回删除元素总数
s.erase(ptr);                   // 删除迭代器 ptr 指向的元素
ms.find(k);                     // 查找第一个键值为 k 的元素的位置,返回迭代器地址,若没找到返回 ms.end()

set 集合容器的操作和遍历

set 的操作:

#include <iostream>
#include <set>
using namespace std;
int main() {
        //声明一个 set 集合容器
        set<int> s;

        //插入三个元素
        s.insert(2);
        s.insert(7);
        s.insert(5);
        s.insert(2);//重复插入无效

        //使用迭代器遍历
        set<int>::iterator p;
        for (p = s.begin(); p != s.end(); p++) cout << *p << ' '; cout << endl;

        //删除元素,存在则删除并返回 1 ,不存在返回 0
        cout << s.erase(3) << endl;
        for (p = s.begin(); p != s.end(); p++) cout << *p << ' '; cout << endl;
        cout << s.erase(5) << endl;
        for (p = s.begin(); p != s.end(); p++) cout << *p << ' '; cout << endl;

        s.insert(0);
        //查找元素,找到返回迭代器位置,没找到返回 set 容器尾地址
        if (s.find(2) == s.end()) cout << "Not found 2" << endl;
        else cout << "Found " << *s.find(2) << endl;
        if (s.find(5) == s.end()) cout << "Not found 5" << endl;
        else cout << "Found " << *s.find(5) << endl;
        return 0;
}
2 5 7
0
2 5 7
1
2 7
Found 2
Not found 5

multiset 的操作:

#include <iostream>
#include <set>
using namespace std;
int main() {

        multiset<int> s;
        s.insert(2);
        s.insert(7);
        s.insert(5);
        s.insert(2);//重复插入有效
        multiset<int>::iterator p;
        for (p = s.begin(); p != s.end(); p++) cout << *p << ' '; cout << endl;

        //删除了 两个 2 所以输出 2
        cout << s.erase(2) << endl;
        for (p = s.begin(); p != s.end(); p++) cout << *p << ' '; cout << endl;
        s.insert(0);
        if (s.find(2) == s.end()) cout << "Not found 2" << endl;
        else cout << "Found " << *s.find(2) << endl;
        if (s.find(5) == s.end()) cout << "Not found 5" << endl;
        else cout << "Found " << *s.find(5) << endl;
        return 0;
}
2 2 5 7
2
5 7
Not found 2
Found 5

map 映照容器

映照容器是居于数据对的,可以通过 ,来索引到 的容器,其中的元素是以 键-值对 的形式存储的,是一个比较抽象的数据结构,通过后面的例子可以很容易的理解。

map 映照容器的声明

需要头文件 #include <map>

//因为 map 储存的是 [键-值对] 所以要定义两个数据类型
map<T, T> m;                    // T 是容器内元素的变量类型
multimap<T, T> mm;              // T 是容器内元素的变量类型

map 映照容器的常用方法

//map 容器的方法
m.insert(pair<T, T>(k, v));     //将一个键-值对 k: v 加入集合,自动按键值排序,默认升序,不可重复插入
m.erase(k);                     //删除键值为 k 的元素,返回删除元素总数(只有 0 或 1 )
m.find(k);                      //查找键值为 k 的元素的位置,返回迭代器地址,若没找到返回 m.end()
//multimap 容器的方法
mm.insert(pair<T, T>(k, v));    //将一个键-值对 k: v 加入集合,自动按键值排序,默认升序,可重复插入
mm.erase(k);                    //删除所有键值为 k 的元素,返回删除元素总数
mm.find(k);                     //查找第一个键值为 k 的元素的位置,返回迭代器地址,若没找到返回 mm.end()

map 映照容器的操作和遍历

map 映照容器可以直接通过 键 来访问对应的 值 ,甚至可以直接使用 键 来生成新的 键-值对 。

m[k] = v;                       //可以直接使用这种方式来插入新的键值对,如果此键已经存在则会修改此键对应的值

注意:多重映射容器(multimap)只能使用 insert() 方法来插入元素,不能使用下标添加或访问

map 的操作:

#include <iostream>
#include <map>
using namespace std;
int main() {
        //定义一个 整数-字符串 的映照类型的映照容器
        map<int, string> m;

        //通过 insert() 方法插入 4 个 键-值对
        m.insert(pair<int, string>(42, "H_On"));
        m.insert(pair<int, string>(26, "pyb"));
        m.insert(pair<int, string>(10, "Shell"));
        m.insert(pair<int, string>(42, "H_On"));//重复插入无效

        //使用 键-值 的方式直接添加新元素
        m[12] = "Ice";

        //通过 键做下标 来访问元素值并修改
        m[42] = "hon";

        //使用迭代器遍历,迭代器类型要对应
        map<int, string>::iterator p;
        for (p = m.begin(); p != m.end(); p++) cout << (*p).first << ": " << p->second << endl;

        //删除键值为 42 的元素(键-值对)
        cout << m.erase(42) << endl;
        for (p = m.begin(); p != m.end(); p++) cout << (*p).first << ": " << p->second << endl;

        //通过键值查找元素,找到返回迭代器位置,没找到返回 map 容器尾地址
        if (m.find(16) == m.end()) cout << "Not found 16" << endl;
        else cout << "Found " << (*m.find(16)).second << endl;
        if (m.find(12) == m.end()) cout << "Not found 12" << endl;
        else cout << "Found " << (*m.find(12)).second << endl;

        return 0;
}
10: Shell
12: Ice
26: pyb
42: hon
1
10: Shell
12: Ice
26: pyb
Not found 16
Found Ice

multimap 的操作:

#include <iostream>
#include <map>
using namespace std;
int main() {
        //定义一个 整数-字符串 的映照类型的映照容器
        multimap<int, string> m;

        //插入 5 个 键-值对
        m.insert(pair<int, string>(42, "H_On"));
        m.insert(pair<int, string>(26, "pyb"));
        m.insert(pair<int, string>(10, "Shell"));
        m.insert(pair<int, string>(42, "H_On"));//重复插入有效
        m.insert(pair<int, string>(12, "Ice"));

        //使用迭代器遍历,类型要对应
        multimap<int, string>::iterator p;
        for (p = m.begin(); p != m.end(); p++) cout << (*p).first << ": " << p->second << endl;

        //删除键值为 42 的元素(键-值对)
        cout << m.erase(42) << endl;
        for (p = m.begin(); p != m.end(); p++) cout << (*p).first << ": " << p->second << endl;

        //通过键值查找元素,找到返回迭代器位置,没找到返回 map 容器尾地址
        if (m.find(16) == m.end()) cout << "Not found 16" << endl;
        else cout << "Found " << (*m.find(16)).second << endl;
        if (m.find(12) == m.end()) cout << "Not found 12" << endl;
        else cout << "Found " << (*m.find(12)).second << endl;
        return 0;
}
10: Shell
12: Ice
26: pyb
42: H_On
42: H_On
2
10: Shell
12: Ice
26: pyb
Not found 16
Found Ice

stack 堆栈容器

栈是一个很神奇的概念,但这里并不用想得太麻烦,想像一个羽毛球桶,只有一个开口,只能从瓶口放进羽毛球或者从瓶口把【最上面】的羽毛球拿出来。也就是 stack 堆栈是一个【后进先出(Last In First Out,LIFO)】的数据存储结构。元素只能从栈顶入栈,只能从栈顶出栈,只能读取栈顶元素。

stack 堆栈容器的声明

需要头文件 #include <stack>

stack<T> s;                     // T 是容器内元素的变量类型

stack 堆栈容器的常用方法

s.push(e);                      //从栈顶将元素入栈
s.pop();                        //将栈顶元素出栈
s.top();                        //读取栈顶元素
s.empty();                      //判断队列是否为空

stack 堆栈容器的操作和遍历

#include <iostream>
#include <stack>
using namespace std;
int main() {
        // 定义一个空栈
        stack<int> s;

        // 从栈顶入栈 3 个元素
        s.push(0);
        s.push(1);
        s.push(2);

        // 读取栈顶元素
        cout << s.top() << endl;

        // 将栈顶出栈
        s.pop();
        cout << s.top() << endl;
        return 0;
}
2
1

queue 队列容器

队列是一个【先进先出(First In First Out,FIFO)】的储存结构,元素只能从队尾插入,只能从队首删除。

queue 队列容器的声明

需要头文件 #include <queue>

queue<T> q;                     // T 是容器内元素的变量类型

queue 队列容器的常用方法

q.push(e);                      //后端入队
q.pop();                        //前端出队
q.front();                      //读取队首元素
q.back();                       //读取队尾元素
q.empty();                      //判断队列是否为空

queue 队列容器的操作和遍历

#include <iostream>
#include <queue>
using namespace std;
int main() {
        //声明一个空的队列容器
        queue<int> q;

        //从尾部插入 4 个元素
        q.push(0);
        q.push(1);
        q.push(2);
        q.push(2);

        //读取队首元素
        cout << q.front() << endl;

        //出队一个元素再次查看队首
        q.pop();
        cout << q.front() << endl;
        return 0;
}
0
1

deque 双端队列容器

顾名思义是一个可以从两端进行出入操作的队列。内部数据存储结构与 vector 相同,也可以用下标进行随机存取。

deque 双端队列容器的声明

需要头文件 #include <deque>

deque<T> d;                     // T 是容器内元素的变量类型
deque<int> d(6);                //声明一个储存 int 型数据的 deque 容器,让它具有 6 的初始容量,下标是 0~5 初始值是 0
vector<double> d(8, 2.33);      //定义一个 d ,容量是 8 ,每个元素的值是2.33

deque 双端队列容器的常用方法

d.push_back(e);                 //后端插入元素,尾部扩充
d.push_front(e);                //前端插入元素,头部扩充
d.pop_back(e);                  //尾部出队
d.pop_front(e);                 //前端出队
d.front();                      //读取队首元素
d.back();                       //读取队尾元素
d.insert(p, e);                 //在迭代器位置之前插入
d.erase(p[, p1]);               //删除迭代器位置或一段区间中的元素

deque 双端队列容器的操作和遍历

#include <iostream>
#include <deque>
using namespace std;
int main() {
        deque<int> d;

        //尾部插入
        d.push_back(0);
        d.push_back(1);
        d.push_back(2);

        //下标方式遍历
        for (int i = 0; i < d.size(); i++) cout << d[i] << ' '; cout << endl;

        //前端插入
        d.push_front(2);
        //中间插入
        d.insert(d.begin() + 2, 2);

        //迭代器遍历
        deque<int>::iterator p;
        for (p = d.begin(); p != d.end(); p++) cout << *p << ' '; cout << endl;

        //删除操作
        d.erase(d.begin() + 2);
        for (p = d.begin(); p != d.end(); p++) cout << *p << ' '; cout << endl;
        d.erase(d.begin() + 1, d.begin() + 3);
        for (p = d.begin(); p != d.end(); p++) cout << *p << ' '; cout << endl;
        return 0;
}
0 1 2
2 0 2 1 2
2 0 1 2
2 2

bitset 位容器

位容器可以方便的把整型直接变成二进制形式,可以按位读写

bitset 位容器的声明

// 需要头文件
#include <bitset>
// N 是位容器的位数,声明时必须确定容器位数
bitset<N> b;
// 例,这样生成一个可以储存八位二进制的位容器
bitset<8> b;
// 也可以用字符串生成,位数不足的前面会自动填充 0
string s = "10010";
bitset<8> b(s);
bitset<8> b(string("1010"));

bitset 位容器的常用方法

// 查
b[p]            // 下标访问返回 0 or 1
b.test(int p)   // 访问 p 下标处的元素的值,0 返回 false;1 返回 true
b.count()       // 返回容器里 1 的个数
b.any()         // 检查容器中是否有 1 ,有返回 true
b.none()        // 检查容器中是否没有 1 ,没有返回 true
b.all()         // 判断容器是否 全为 1 ,全 1 返回 true
// 改
b.set()         // 全设为 1
b.set(p)        // p 位置设为 1
b.set(p, x)     // p 位置设为 x
b.reset()       // 全设为 0
b.reset(p)      // p 位置设为 0
b.flip()        // 全部取反
b.flip(p)       // p 位置取反
// ?
b.to_ulong()    // 返回它转为 unsigned long 的值,超出范围报错
b.to_ullong()   // 转 unsigned long long
b.to_string()   // 转 string 字符串

bitset 位容器的便捷操作

bitset<4> b1 (string("100"));
bitset<4> b2 (string("011"));
b1 ^= b2        // b1 对 b2 按位 异或 后赋值给 b1
b1 &= b2        // 按位 与
b1 |= b2        // 按位 或
b1 <<= 2        // b1 左移 2 位 低位补 0
b1 >>= 1        // b1 右移 1 位 高位补 0
b1 = ~b1        // 按位取反
b1 == b2
b1 != b2

通用方法简介

  1. empty() 方法:
    上面介绍的所有容器都适用,使用方法 容器变量名.empty() 如果容器为空,返回布尔值 booltrue,如果容器不为空返回假 false
  2. size() 方法:
    上面介绍的所有容器都适用,使用方法 容器变量名.size() 可以获取容器内的元素的个数,字符串变量 string 可以获取字符串长度。
  3. clear() 方法:
    上面介绍的所有容器除了 栈和队列 都适用,使用方法 容器变量名.clear() 可以将容器内的内容全部清空。
  4. begin() 方法,end() 方法:
    上面介绍的所有容器除了 栈和队列 都适用,使用方法 容器变量名.begin() 容器变量名.end() 可以获得容器的首地址,尾地址。

栈和队列不能使用有些方法的原因是,它们并不是【可迭代对象】。

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
using namespace std;
int main() {
        //定义
        vector<int> v;
        string str;
        set<int> s;
        multiset<int> ms;
        map<int, int> m;
        multimap<int, int> mm;
        stack<int> sta;
        queue<int> q;
        deque<int> d;

        //赋值
        v.push_back(233);
        str = "";
        s.insert(233);
        m[12] = 41;
        m[51] = 23;
        sta.push(233);
        d.push_back(23);

        cout << "method empty()--------------------------------" << endl;
        //使用empty()方法
        if (v.empty()) cout << "v   is  e"; else cout << "v   not e"; cout << endl;
        if (str.empty()) cout << "str is  e"; else cout << "str not e"; cout << endl;
        if (s.empty()) cout << "s   is  e"; else cout << "s   not e"; cout << endl;
        if (ms.empty()) cout << "ms  is  e"; else cout << "ms  not e"; cout << endl;
        if (m.empty()) cout << "m   is  e"; else cout << "m   not e"; cout << endl;
        if (mm.empty()) cout << "mm  is  e"; else cout << "mm  not e"; cout << endl;
        if (sta.empty()) cout << "sta is  e"; else cout << "sta not e"; cout << endl;
        if (q.empty()) cout << "q   is  e"; else cout << "q   not e"; cout << endl;
        if (d.empty()) cout << "d   is  e"; else cout << "d   not e"; cout << endl;

        cout << "method size()---------------------------------" << endl;
        //使用size()方法
        cout << "  v.size = " << v.size() << endl;
        cout << "str.size = " << str.size() << endl;
        cout << "  s.size = " << s.size() << endl;
        cout << " ms.size = " << ms.size() << endl;
        cout << "  m.size = " << m.size() << endl;
        cout << " mm.size = " << mm.size() << endl;
        cout << "sta.size = " << sta.size() << endl;
        cout << "  q.size = " << q.size() << endl;
        cout << "  d.size = " << d.size() << endl;

        cout << "method clear()--------------------------------" << endl;
        //使用clear()方法
        v.clear();
        str.clear();
        s.clear();
        ms.clear();
        m.clear();
        mm.clear();
        d.clear();

        cout << "method begin()--------------------------------" << endl;
        //使用begin()方法
        v.begin();
        str.begin();
        s.begin();
        ms.begin();
        m.begin();
        mm.begin();
        d.begin();

        cout << "method end()----------------------------------" << endl;
        //使用end()方法
        v.end();
        str.end();
        s.end();
        ms.end();
        m.end();
        mm.end();
        d.end();

        return 0;
}
method empty()--------------------------------
v   not e
str is  e
s   not e
ms  is  e
m   not e
mm  is  e
sta not e
q   is  e
d   not e
method size()---------------------------------
  v.size = 1
str.size = 0
  s.size = 1
 ms.size = 0
  m.size = 2
 mm.size = 0
sta.size = 1
  q.size = 0
  d.size = 1
method clear()--------------------------------
method begin()--------------------------------
method end()----------------------------------

自定义比较函数

从大到小排序

struct hon_comp {
        bool operator() (const T &a, const T &b) {
                return a > b;
        }
};
bool hon_comp(const T &a, const T &b) {
        return a > b;
}

这个排序规则可以用在各种地方,例如用在 set 和 map 的自动排序上,或者是 sort() 函数的排序规则上。

struct hon_comp {
        bool operator() (const T &a, const T &b) {
                return a > b;
        }
};
set<int, hon_comp> s;
struct hon_comp {
        bool operator() (const T &a, const T &b) {
                return a > b;
        }
};
map<int, int, hon_comp> s;
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool hon_comp(const int &a, const int &b) {
        return a > b;
}
int main() {
        //定义
        vector<int> v;

        //插入三个元素
        v.push_back(2);
        v.push_back(5);
        v.push_back(4);

        //遍历
        vector<int>::iterator p;
        for (p = v.begin(); p != v.end(); p++) cout << *p << ' '; cout << endl;

        //直接排序,默认是从小到大
        sort(v.begin(), v.end());
        for (p = v.begin(); p != v.end(); p++) cout << *p << ' '; cout << endl;

        //使用自定义排序,从大到小排序
        sort(v.begin(), v.end(), hon_comp);
        for (p = v.begin(); p != v.end(); p++) cout << *p << ' '; cout << endl;
        return 0;
}
2 5 4
2 4 5
5 4 2

STL进阶一点的介绍已经更新了:StandardTemplateLibrary Plus

推荐容器练习题目

  1. 火车出入站
    B. Collecting Packages