cpp-STL

C++ STL总结new

作者：CJL sysu

参考文献：

  1. C++_vector操作(vector容器部分参考了)

  2. B站,黑马程序员C++教学视频

1.vector容器

需要头文件#include<vector>

(1)构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<vector>
#include<iostream>
using namespace std;

//vector构造总结
vector<int>b;
vector<int>a(10); //定义具有10个整型元素的向量（尖括号为元素类型名，它可以是任何合法的数据类型），不具有初值，其值不确定
vector<int>a(10,1);  //定义具有10个整型元素的向量，且给出的每个元素初值为1
vector<int>a(b);   //用向量b给向量a赋值，a的值完全等价于b的值
vector<int>a(b.begin(),b.begin()+3);   //将向量b中从0-2（共三个）的元素赋值给a，a的类型为int型
int c[7]={1,2,3,4,5,6,7};//从数组中获得初值
vector<int> a(c, c + 7);
vector<int>a{ 1,2,3,4,5,6,7 };//初始化
vector<int>a = { 1,2,3,4,5,6,7 };//和上面的等价

(2)基本操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
void test01()//基本操作
{
        vector<int> a, b;
        int i=0;
        //b为向量，将b的0-2个元素赋值给向量a
        a.assign(b.begin(), b.begin() + 3);
        
        //a含有4个值为2的元素
        a.assign(4, 2);
        
        //返回a的最后一个元素
        a.back();
        
        //返回a的第一个元素
        a.front();
        
        //返回a的第i元素,当且仅当a存在
        a[i];
        
        //清空a中的元素
        a.clear();
        
        //判断a是否为空，空则返回true，非空则返回false
        a.empty();
        
        //删除a向量的最后一个元素
        a.pop_back();
        
        //删除a中第一个（从第0个算起）到第二个元素，也就是说删除的元素从a.begin()+1算起（包括它）一直到a.begin()+3（不包括它）结束
        a.erase(a.begin() + 1, a.begin() + 3);
        
        //在a的最后一个向量后插入一个元素，其值为5
        a.push_back(5);
        
        //在a的第一个元素（从第0个算起）位置(前面)插入数值5,
        a.insert(a.begin() + 1, 5);
        
        //在a的第一个元素（从第0个算起）位置（前面）插入3个数，其值都为5
        a.insert(a.begin() + 1, 3, 5);
        
        //d为数组，在a的第一个元素（从第0个元素算起）的位置（前面）插入b的第三个元素到第5个元素（不包括b+6）
        int d[8];
        a.insert(a.begin() + 1, d + 3, d + 6);
        
        //返回a中元素的个数
        a.size();
        
        //返回a在内存中总共可以容纳的元素个数
        a.capacity();
        
        //将a的现有元素个数调整至10个，多则删，少则补，其值随机
        a.resize(10);
        
        //将a的现有元素个数调整至10个，多则删，少则补，其值为2
        a.resize(10, 2);
        
        //将a的容量扩充至100，
        a.reserve(100);
        
        //b为向量，将a中的元素和b中的元素整体交换
        a.swap(b);
        
        //b为向量，向量的比较操作还有 != >= > <= <
        a == b;
}

(3)反向迭代

1
2
3
4
5
6
7
8
9
void test02()
{
        //反向迭代
        vector<int>a = { 1,2,3,4,5,6,7,8,9,10 };
        for (vector<int>::reverse_iterator iter = a.rbegin(); iter != a.rend(); iter++)
        {
                cout << *iter << endl;//10 9 8 7 6 5 4 3 2 1
        }
}

(4)插入
插入位置都在pos迭代器之前一个位置，返回的迭代器指向插入的第一个元素
在迭代器 pos 指定的位置之前插入一个新元素elem，并返回表示新插入元素位置的迭代器。 iterator insert(pos, elem)
在迭代器 pos 指定的位置之前插入 n 个元素 elem，并返回表示第一个新插入元素位置的迭代器。 iterator insert(pos, n, elem)
在迭代器 pos 指定的位置之前，插入其他容器（不仅限于vector)中位于[first, last)区域的所有元素，并返回表示第一个新插入元素位置的迭代器。 iterator insert(pos, first, last)
在迭代器 pos 指定的位置之前，插入初始化列表(用大括号{}括起来的多个元素，中间有逗号隔开)中所有的元素，并返回表示第一个新插入元素位置的迭代器。 iterator insert(pos, initlist) 
1
2
3
4
5
6
7
8
9
10
11
12
void test03()
{
        vector<int>a = { 1,2,3,4,5,6,7,8,9,10 };
        vector<int>::iterator it1 = a.begin() + 4;
        vector<int>::iterator it2 = a.insert(it1, { -1,-2,-3 });
        cout << *it2 << endl;//-1
        for (auto k : a)
        {
                cout << k << " ";//1 2 3 4 -1 -2 -3 5 6 7 8 9 10
        }
        cout << endl;
}

(5)

pop_back() 删除 vector 容器中最后一个元素，该容器的大小（size)会减 1， 但容量(capacity)不会发生改变。
erase(pos) 删除vector容器中pos迭代器指定位置处的元素,并返回指向被删除元素下一个位置元素的迭代器
该容器的大小(size)会减1,但容量(capacity)不会发生改变。
???swap(beg)、 pop_back() 先调用 swap() 函数交换要删除的目标元素和容器最后一个元素的位置，
然后使用 pop_back) 删除该目标元素。
erase(beg,end) 删除vector容器中位于迭代器[beg,end)指定区域内的所有元素,并返回指向被删除区域下一个
位置元素的迭代器。该容器的大小(size)会减小,但容量（capacity）不会发生改变。
remove() 删除容器中所有和指定元素值相等的元素,并返回指向最后一个元素下一个位置的迭代器。
值得一提的是,调用该函数不会改变容器的大小和容量。
clear() 删除 vector 容器中所有的元素,使其变成空的 vector 容器。
该函数会改变 vector 的大小(变为 0) ,但不是改变其容量。		 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void test04()
{
        vector<int>a = { 1,2,3,4,5,6,6,6,6,7,8,9,10 };
        int size = a.size();
        ptrdiff_t cnt = count(a.begin(), a.end(), 6);//ptrdiff==long long
        auto it = remove(a.begin(), a.end(), 6);
        cout << *it << endl;//7
        cout << cnt << endl;//4
        for (auto k : a)
        {
                cout << k << " ";//1 2 3 4 5 7 8 9 10 7 8 9 10
        }
        cout << endl;
        a.resize(size - cnt);
        for (auto k : a)
        {
                cout << k << " ";//1 2 3 4 5 7 8 9 10
        }
}

2.deque 容器

需要头文件#include<deque>

(1)遍历容器

1
2
3
4
5
6
7
8
9
10
void printdeque(const deque<int>& d)
{
        for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
//注意迭代器也要换成带const的
        {
                cout << *it << " ";
                //*it = 100;加const后容器中的数据不可以修改了
        }
        cout << endl;
}

(2)构造容器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void test01()
{
        deque<int>d1;
        for (int i = 0; i < 10; i++)
                d1.push_front(i+1);
        printdeque(d1);
        //区间赋值
        deque<int>d2(d1.begin(), d1.end());
        printdeque(d2);
        deque<int>d3(10, 100);
        printdeque(d3);
        deque<int>d4(d3);
        printdeque(d4);
}

程序输出:

1
2
3
4
10 9 8 7 6 5 4 3 2 1
10 9 8 7 6 5 4 3 2 1
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100

(3)赋值操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void test01()
{
        deque<int>d1;
        for (int i = 0; i < 10; i++)
                d1.push_back(i + 1);
        printdeque(d1);
        //operator= 赋值
        deque<int>d2;
        d2 = d1;
        printdeque(d2);
        //assign赋值
        deque<int>d3;
        d3.assign(d2.begin(), d2.end());
        printdeque(d3);
        deque<int>d4;
        d4.assign(10, 100);
        printdeque(d4);
}

程序输出：

1
2
3
4
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
100 100 100 100 100 100 100 100 100 100

(4) 插入和删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void test01()
{
        deque<int> d1;
        d1.push_back(1);//尾插入1
        d1.pop_back()//尾删
        d1.push_front(1);//头插入1
        d1.pop_front();//头删
        //插入
        printdeque(d1);//1 2 3 4
        d1.insert(d1.begin(), 100);//100 1 2 3 4
        d1.insert(d1.begin() + 1, 2, 1000);//100 1000 1000 1 2 3 4
        printdeque(d1);
        //按照区间进行插入
        deque<int>d2;
        d2.push_back(1);
        d2.push_back(2);
        d2.push_back(3);
        d1.insert(d1.begin(), d2.begin(), d2.end());
        printdeque(d1);//1 2 3
        //删除
        deque<int>::iterator it = d1.begin() + 1;
        d1.erase(it);
        printdeque(d1);// 1 3
        d1.clear();
        printdeque(d1);//空
}

(5)数据存取

1
2
3
4
5
6
deque d1;
d1[2];//d1中第二个元素
d1.at(2);//d1中第二个元素
//访问头尾元素
cout << "第一个元素为" << d.front() << endl;
cout << "最后一个元素为" << d.back() << endl;

3.stack 容器

需要头文件#include<stack>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void test01()
{
        stack<int> s;
        //特点：符合先进后出的数据结构
        s.push(10);
        s.push(20);
        s.push(30);
        s.push(40);
        int m = s.size();
        for (int i = 0; i < m; i++)
        {
                cout << s.top() << " ";//40 30 20 10
                s.pop();
        }
        cout << endl;
}

4.queue容器

需要头文件#include<queue>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Person
{
public:
        Person(string name, int age)
        {
                this->m_name = name;
                this->m_age = age;
        }
        string m_name;
        int m_age;
};
void test01()
{
        queue<Person>q;
        Person p1("唐僧", 30);
        Person p2("孙悟空", 1000);
        Person p3("猪八戒", 900);
        Person p4("沙僧", 800);
        q.push(p1);
        q.push(p2);
        q.push(p3);
        q.push(p4);
        cout << "队伍人数：" << q.size() << endl;
        while (!q.empty())
        {
                //查看队头
                cout << "队头：姓名" << q.front().m_name << " 年龄" << q.front().m_age << endl;
                //查看队尾
                cout << "队尾：姓名" << q.back().m_name << " 年龄" << q.back().m_age << endl;
                q.pop();
        }
}

5.string容器

(1)构造

1
2
3
4
5
6
7
8
9
10
11
12
void test01()
{
	string s1;//默认构造,创建一个空的字符串
	cout << "s1=" << s1 << endl;
	const char* str = "hello world!";
	string s2(str);//使用字符串s初始化
	cout << "s2=" << s2 << endl;
	string s3(s2);//使用一个string对象初始化另一个string对象
	cout << "s3=" << s3 << endl;
	string s4(10, 'b');//使用n个字符b初始化
	cout << "s4=" << s4 << endl;
}
1
2
3
4
s1=
s2=hello world!
s3=hello world!
s4=bbbbbbbbbb

(2)赋值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void test01()
{
	string str1;
	str1 = "hello world!";
	cout << "str1 =" << str1 << endl;
	string str2 = str1;
	cout << "str2 =" << str2 << endl;
	//string str3 = 'a';//不知为何不可用
	string str4;
	str4.assign("Hello C艹");
	cout << "str4 =" << str4 << endl;
	string str5;
	str5.assign("hello C艹", 5);//将str4的前五个字符赋给str5
	cout << "str5 =" << str5 << endl;
	string str6;
	str6.assign(str5);
	cout << "str6=" << str6 << endl;
	string str7;
	str7.assign(10, 'w');
	cout << "str7=" << str7 << endl;

}
1
2
3
4
5
6
str1 =hello world!
str2 =hello world!
str4 =Hello C艹
str5 =hello
str6=hello
str7=wwwwwwwwww

(3)拼接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void test01()
{
	string str1 = "我";
	str1 += "爱编程C艹";//拼接字符串
	cout << "str1=" << str1 << endl;
	str1 += "!";//拼接字符
	cout << "str1=" << str1 << endl;
	string str2 = "我也爱C语言";
	str1 += str2;
	cout << "str2=" << str2 << endl;
	string str3 = "I";
	str3.append("love");
	cout << "str3=" << str3 << endl;
	str3.append("gameabcde", 4);
	cout << "str3=" << str3 << endl;
	str3.append(str2);
	cout << "str3=" << str3 << endl;
	str3.append(str2, 4, 7);//从str2的第三个字符开始，截取4个加在末尾，第二个参数为起始字符的位置(位置从0开始计算)，第三个参数为字符的长度
	//中文字符占2个位置，英文字符占1个位置
	cout << "str3=" << str3 << endl;
}
1
2
3
4
5
6
7
str1=我爱编程C艹
str1=我爱编程C艹!
str2=我也爱C语言
str3=Ilove
str3=Ilovegame
str3=Ilovegame我也爱C语言
str3=Ilovegame我也爱C语言爱C语言

(4)查找和替换

1
2
3
4
5
6
7
8
9
10
11
void test01()
{
	string str1 = "abcdefgdefg";
	int pos1 = str1.find("de");
	cout << "pos1=" << pos1 << endl;
	int pos2 = str1.find("df");//找不到则返回-1
	cout << "pos2=" << pos2 << endl;
	//rfind是最后一次出现的位置，find是第一次出现的位置
	int pos3 = str1.rfind("de");
	cout << "pos3=" << pos3 << endl;
}
1
2
3
pos1=3
pos2=-1
pos3=7
1
2
3
4
5
6
void test02()
{
	string str1 = "abcdefg";
	str1.replace(1, 3, "1111");//从1号位置起 3个字符 替换为“1111”
	cout << "str1=" << str1 << endl;
}
1
str1=a1111efg

(5)字符串比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void test01()
{
	string str1 = "hfllo";
	string str2 = "hello";
	if (str1.compare(str2) == 0)
	{
		cout << "str1等于str2" << endl;
	}
	else if (str1.compare(str2) > 0)
	{
		cout << "str1大于str2" << endl;
	}
	else
	{
		cout << "str1小于str2" << endl;
	}
}//通过逐字符比较ASCII值，大于为1，小于为-1，等于为0,以第一个不一样的字符为准
1
str1大于str2

(6)字符存取

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void test01()
{
	string str = "hello";
	for (int i = 0; i < 5; i++)
		cout << str[i] << " ";
	cout << endl;
	for (int i = 0; i < 5; i++)
		cout << str.at(i) << "  ";
	cout << endl;
//改字符
	str[0] = 'x';
	str.at(1) = 'y';
	cout << str << endl;
}
1
2
3
h e l l o
h  e  l  l  o
xyllo

(7)插入和删除

1
2
3
4
5
6
7
8
9
10
void test01()
{
	string str1="abcdefgh";
	str1.insert(2, "xxx");
	cout << str1 << endl;
	str1.erase(2, 3);//删去从2开始的3个字符
	cout << str1 << endl;
	str1.insert(2, 3, 'x');
	cout << str1 << endl;
}
1
2
3
abxxxcdefgh
abcdefgh
abxxxcdefgh

(8)子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main()
{
	cout << "输入邮箱账号以登录游戏" << endl;
	string email;
	//cin >> email;
	email = "handsome_boy@mail2.sysu.edu.cn";
	int pos = email.find('@');
	if (pos == -1)
	{
		cout << "邮箱账号有误" << endl;
	}
	else
	{
		string name;
		name = email.substr(0, pos);
		cout << "你好，" << name << "，欢迎进入游戏" << endl;
	}
	return 0;
}
1
2
输入邮箱账号以登录游戏
你好，handsome_boy，欢迎进入游戏

(9)string容器其他

  1. string s; // 生成一个空字符串s
  2. string s(str); // 拷贝构造函数生成str的复制品
  3. string s(str, stridx); // 将字符串str内"始于位置stridx"的部分当作字符串的初值
  4. string s(str, stridx, strlen); // 将字符串str内"始于stridx且长度顶多strlen"的部分作为字符串的初值
  5. string s(cstr); // 将C字符串（以NULL结束）作为s的初值
  6. string s(chars, chars_len); // 将C字符串前chars_len个字符作为字符串s的初值。
  7. string s(num, ‘c’); // 生成一个字符串，包含num个c字符
  8. string s(“value”); string s = “value”; // 将s初始化为一个字符串字面值副本
  9. string s(begin, end); // 以区间begin/end(不包含end)内的字符作为字符串s的初值
  10. s.~string(); //销毁所有字符，释放内存

string s;

  1. s.empty(); // s为空串 返回true
  2. s.size(); // 返回s中字符个数 类型应为：string::size_type
  3. s[n]; // 从0开始相当于下标访问
  4. s1+s2; // 把s1和s2连接成新串 返回新串
  5. s1=s2; // 把s1替换为s2的副本
  6. v1==v2; // 比较，相等返回true
  7. !=, <, <=, >, >= 惯有操作 任何一个大写字母都小于任意的小写字母
1
2
3
4
5
6
7
8
9
void test01()
{
	string s("abc");
	cout << s << endl;
	cout << s.size() << endl;
	cout << strlen(s.c_str()) << endl;
	s.~basic_string();
	cout << s << endl;
}
1
2
3
4
abc
3
3

1
2
3
4
5
6
7
8
9
10
11
12
13
void test02()
{
	stringstream sstream;
	string strresult;
	int val = 12345;
	sstream << val;
	sstream >> strresult;
	cout << strresult << endl;
	sstream.clear();
	sstream << "4321";
	sstream >> val;
	cout << val << endl;
}
1
2
12345
4321
1
2
3
4
5
6
7
8
9
10
void test03()
{
	//把string字符串转化为C风格的字符串
	string s = "abcdefg";
	char str[1000];
	strcpy(str, s.c_str());
	str[0] = 'p';
	str[5] = 'u';
	cout << str << endl;
}
1
pbcdeug

6.set容器和multiset容器

需要头文件#include<set>

set不允许容器中有重复的元素

multiset允许容器中有重复的元素

其他操作基本一致

(1)遍历容器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
#include<set>
using namespace std;
void printset(const set<int>&s)
{
        if (s.empty())
        {
                cout << "set数组为空" << endl;
                return;
        }
        for (set<int>::const_iterator it = s.begin(); it != s.end(); it++)
                cout << *it << " ";
        cout << endl;
}

void printmultiset(const multiset<int>& m)
{
        if (m.empty())
        {
                cout << "multiset数组为空" << endl;
                return;
        }
        for (multiset<int>::const_iterator it = m.begin(); it != m.end(); it++)
                cout << *it << " ";
        cout << endl;
}

(2)插入和删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void test01()
{
        set<int>s;
        s.insert(10);
        s.insert(20);
        s.insert(30);
        s.insert(40);
        s.insert(50);
        s.insert(60);
        s.insert(70);
        s.insert(80);
        s.insert(90);
        s.insert(100); 
        s.insert(110);
        s.insert(120);
        printset(s);
        set<int>::iterator it = s.begin();
        set<int>::iterator it2;
        it2 = s.erase(++++it);//删除迭代器所指元素，返回下一个元素的迭代器
        printset(s);
        set<int>::iterator it1 = s.end();
        s.erase(it2, ----it1);//删除区间[it2,----it1)的所有元素，返回下一个元素的迭代器
        printset(s);
        s.erase(110);//删除值为110的元素
        printset(s);
        s.clear();//清空set容器
        printset(s);
}

程序输出：

1
2
3
4
5
10 20 30 40 50 60 70 80 90 100 110 120
10 20 40 50 60 70 80 90 100 110 120
10 20 110 120
10 20 120
set数组为空

(3)查找和统计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void test01()
{
        set<int>s;
        s.insert(10);
        s.insert(20);
        s.insert(30);
        s.insert(40);
        s.insert(30);
        s.insert(60);
        s.insert(70);
        s.insert(80);
        s.insert(70);
        s.insert(100);
        s.insert(110);
        s.insert(120);
        printset(s);
        set<int>::iterator it1;
        it1 = s.find(70);//查找70是否存在，若存在，返回该键的元素的迭代器，若不存在，返回set.end()
        if (it1 != s.end())   
                cout << *it1 << endl; 
        else                     
                cout << "未找到元素" << endl;
        int num = s.count(30);
        cout << num << endl;//对于set而言，统计的结果只有0和1
}

程序输出：

1
2
3
10 20 30 40 60 70 80 100 110 120
70
1

(4)set与multiset

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void test01()
{
        multiset<int>s;
        s.insert(10);
        s.insert(20);
        s.insert(30);
        s.insert(40);
        s.insert(30);
        s.insert(60);
        s.insert(70);
        s.insert(80);
        s.insert(70);
        s.insert(100);
        s.insert(110);
        s.insert(120);
        printmultiset(s);
        multiset<int>::iterator it1;
        it1 = s.find(70);
//查找70是否存在，若存在，返回该键的元素的迭代器，若不存在，返回set.end()
        if (it1 != s.end())  
                cout << *(--it1) << endl;  
        else 
                cout << "未找到元素" << endl;
        int num = s.count(30);
        cout << num << endl;//对于multiset而言，统计的结果不只有0和1
}

程序输出：

1
2
3
10 20 30 30 40 60 70 70 80 100 110 120
60
2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void test02()
{
        set<int>s;
        s.insert(20);
        s.insert(20);
        s.insert(30);
        s.insert(40);
        s.insert(30);
        s.insert(60);
        s.insert(70);
        s.insert(80);
        s.insert(70);
        s.insert(100);
        s.insert(110);
        s.insert(120);
        printset(s);
        pair<set<int>::iterator, bool> ret = s.insert(10);
        if (ret.second)
                cout << "第一次插入成功" << endl;
        else 
                cout << "第一次插入失败" << endl; 
        pair<set<int>::iterator, bool> ret1 = s.insert(10);
        if (ret1.second)
                cout << "第二次插入成功" << endl;
        else
                cout << "第二次插入失败" << endl;
}

程序输出：

1
2
3
20 30 40 60 70 80 100 110 120
第一次插入成功
第二次插入失败

7.map和multimap容器

需要头文件#include<map>

map中所有元素都是pair

pair中第一个元素为key(键值)，起到索引作用，第二个元素为value（实值）

所有元素都会根据元素键值自动排序

map/multimap属于关联式容器，底层结构是用二叉树实现

优点：可以根据key值快速找到value值

map和multimap区别:

map不允许容器中有重复key值元素

multimap允许容器中有重复key值元素

（1）遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include<map>
using namespace std;
void printmap(const map<int, int>& m)
{
        if (m.empty())
        {
                cout << "map容器为空" << endl;
                return;
        }
        for (map<int, int>::const_iterator it = m.begin(); it != m.end(); it++)
                cout << "学号：" << (*it).first << "    分数：" << it->second << endl;
        cout << endl;
}
void test01()											
{														
	map<int,int>m;										
	m.insert(pair<int, int>(1, 60));					
	m.insert(pair<int, int>(2, 95));					
	m.insert(pair<int, int>(4, 73));					
	m.insert(pair<int, int>(3, 81)）;		   			
	printmap(m);		//会按照key值（学号）自动排序	
														
	map<int, int>m2(m);	//拷贝构造						
	printmap(m2);										
	map<int, int>m3;									
	m3 = m2;											
	printmap(m3);										
}

程序输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
学号：1    分数：60
学号：2    分数：95
学号：3    分数：81
学号：4    分数：73
		
学号：1    分数：60
学号：2    分数：95
学号：3    分数：81
学号：4    分数：73
		
学号：1    分数：60
学号：2    分数：95
学号：3    分数：81
学号：4    分数：73

(2)大小和交换

1
2
3
4
map<int,int> ma;
ma.size();
map<int,int>ma1;
ma.swap(ma1);

(3)插入和删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void test01()
{
        map<int, int>m;
        //1
        m.insert(pair<int, int>(1, 60));
        m.insert(pair<int, int>(3, 95));
        m.insert(pair<int, int>(4, 73));
        m.insert(pair<int, int>(5, 81));
        //2
        m.insert(make_pair(2, 10));
        //3
        m.insert(map<int, int>::value_type(6, 30));
        //4
        m[7] = 40;
//这种插数方法和其他的不同在于可以修改已经插入的key对应的value
        printmap(m);
        //删除
        m.erase(m.begin(), ++++m.begin());
        printmap(m);
        m.erase(4);//按照key删除
        printmap(m);
        m.clear();
        printmap(m);
}

程序输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
学号：1    分数：60
学号：2    分数：10
学号：3    分数：95
学号：4    分数：73
学号：5    分数：81
学号：6    分数：30
学号：7    分数：40

学号：3    分数：95
学号：4    分数：73
学号：5    分数：81
学号：6    分数：30
学号：7    分数：40

学号：3    分数：95
学号：5    分数：81
学号：6    分数：30
学号：7    分数：40

(4)查找与统计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void test01()
{
        map<int, int>m;
        m.insert(pair<int, int>(1, 60));
        m.insert(pair<int, int>(3, 95));
        m.insert(pair<int, int>(4, 73));
        m.insert(pair<int, int>(5, 81));
        m.insert(pair<int, int>(2, 84));
        map<int, int>::iterator it;
        it = m.find(4);
        if (it != m.end())
                cout << it->second << endl;//73
        else
                cout << "编号不存在" << endl;
        cout << m.count(4) << endl;//1
}

8.priority_queue

参考文献

头文件#incldue<queue>

priority_queue是一个元素有序排列的队列。默认队列头部的元素优先级最高。因为它是一个队列，所以只能访问第一个元素，这也意味着优先级最高的元素总是第一个被处理。

它能够实现常数时间的（默认）最大元素查找，对数代价的插入与释出

(1)构造

1
2
priority_queue<int> pq1;
priority_queue<int,vector<int>,greater<int>> pq2;

priority_queue 模板有 3 个参数，其中两个有默认的参数；

第一个参数是存储对象的类型，

第二个参数是存储元素的底层容器，

第三个参数是函数对象，它定义了一个用来决定元素顺序的断言。

(2)元素访问

top()访问栈顶元素

1
2
3
4
5
6
7
8
9
10
11
12
#include<iostream>
#include<queue>
using namespace std;
int main()
{
    priority_queue<int,vector<int>,less<int>> pq1;
    pq1.push(10);
    pq1.push(40);
    pq1.push(20);
    cout<<pq1.top()<<endl;
    return 0;
}

输出

1
40

(2)容量

empty()判断是否为空

size()返回容器大小

(3)修改器

push插入元素并排序

pop删除队首元素并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<queue>
using namespace std;
int main()
{
    priority_queue<int> pq1;
    pq1.push(10);
    pq1.push(40);
    pq1.push(20);
    pq1.push(30);
    cout<<"The elements of the priority queue are : "<<endl;
    while(!pq1.empty())
    {
        cout<<pq1.top()<<" ";
        pq1.pop();
    }
    return 0;
}

输出:

1
2
The elements of the priority queue are : 
40 30 20 10

如果添加greater<int>仿函数,相对小的数优先级更高

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<queue>
using namespace std;
int main()
{
    priority_queue<int,vector<int>,greater<int>> pq1;
    pq1.push(10);
    pq1.push(40);
    pq1.push(20);
    pq1.push(30);
    cout<<"The elements of the priority queue are : "<<endl;
    while(!pq1.empty())
    {
        cout<<pq1.top()<<" ";
        pq1.pop();
    }
    return 0;
}

输出:

1
2
The elements of the priority queue are : 
10 20 30 40

9.STL常用算法

以下除特别说明，都需要#include<algorithm>头文件

（1）for_each和transform

1
2
3
4
5
6
7
8
9
10
11
void test01()
{
        vector<int>v;
        for (int i = 0; i < 10; i++)
                v.push_back(i + 1);
        vector<int>vtarget;
        vtarget.resize(v.size());
        transform(v.begin(), v.end(), vtarget.begin(), Transform());
//101 102 103 104 105 106 107 108 109 110
        for_each(vtarget.begin(), vtarget.end(), myprint());
}
find 查找元素
find_if 按条件查找元素
adjacent_find 查找相邻重复元素
binary_search 二分查找法
count 统计元素个数
count_if 按条件统计元素个数

(2)find

功能描述:.查找指定元素, 找到返回指定元素的选代器, 找不到返回结束选代器end()

函数原型 :

find(iterator beg, iterator end, value);

按值查找元素,找到返回指定位置选代器,找不到返回结束选代器位置

beg 开始迭代器

end结束迭代器

value查找的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void test01()
{
        vector<int>v;
        for (int i = 0; i < 10; i++)
        {
                v.push_back(i + 1);
        }
        vector<int>::iterator it = find(v.begin(), v.end(), 5);
        if (it == v.end())
        {
                cout << "未找到" << endl;
        }
        else
                cout << "找到：" << *it << endl;//找到：5
}

(3)find_if

功能描述:

按条件查找元素

函数原型:.find_if(iterator beg, iterator end, _Pred);

按值查找元素,找到返回指定位置选代器,找不到返回结束选代器位置

beg开始迭代器

end结束迭代器

_Pred函数或者谓词(返回bool类型的仿函数)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class mycompare
{
public:
        bool operator()(int a)
        {
                return a > 5;
        }
};
void test01()
{
        vector<int>v;
        for (int i = 0; i < 10; i++)
                v.push_back(i + 1);
        vector<int>::iterator it = find_if(v.begin(), v.end(), mycompare());
        if (it == v.end())
                cout << "未找到" << endl;
        else
                cout << "找到" << *it << endl;//找到6
}

查找指定的元素，查到返回true，否则返回false

注意：在无序序列中不可用,因为结果会出错

降序也不行，只能用于升序序列

1
2
3
4
5
6
7
8
void test01()
{
	vector<int>v={0,1,2,3,4,5,6,7,8};
	if (binary_search(v.begin(), v.end(), 6))
		cout << "找到了" << endl;
	else
		cout << "未找到" << endl;
}//找到了

(5)adjacent_find

查找相邻重复元素，返回相邻元素的第一个位置的迭代器

少用，但是考试会考

1
2
3
4
5
6
7
8
9
void test01()
{
	vector<int>v={0,2,0,3,1,4,3,3,2};
	vector<int>::iterator pos = adjacent_find(v.begin(), v.end());
	if (pos == v.end())
		cout << "未找到" << endl;
	else
		cout << *pos << endl;
}//输出3

(6)count

统计元素个数

1
2
3
4
5
6
void test01()
{
	vector<int>v={0,1,2,3,5,3,3,6,8};
	int cou = count(v.begin(), v.end(), 3);
	cout << cou << endl;
}//输出3

(7)count_if

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class greaterfive
{
public:
	bool operator()(int a)
	{
		return a > 5;
	}
};
void test01()
{
	vector<int>v={0,1,2,7,5,6,3,6,8};
	int cou = count_if(v.begin(), v.end(), greaterfive());
	cout << cou << endl;
}

程序输出:

1
4

(8)sort排序算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void myprint(int val)
{
	cout << val << " ";
}
void test01()
{
	vector<int>v={10,30,50,20,40,90};
	for_each(v.begin(), v.end(), myprint);
	cout << endl;
	sort(v.begin(), v.end());
	for_each(v.begin(), v.end(), myprint);
	cout << endl;
	sort(v.begin(), v.end(), greater<int>());
	for_each(v.begin(), v.end(), myprint);
	cout << endl;
}

程序输出：

1
2
3
10 30 50 20 40 90
10 20 30 40 50 90
90 50 40 30 20 10

(9)random_shuffle

1
2
3
4
5
6
void test01()
{
	srand((unsigned int)time(NULL));
	vector<int>v={0,1,2,3,4,5,6,7,8,9};
	random_shuffle(v.begin(), v.end());//随机打乱v的排序
}

(10)merge

可以把两个有序序列合在一起，形成一个新的有序序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void myprint(int val)
{
	cout << val << " ";
}
void test01()
{
	vector<int>v1;
	vector<int>v2;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
		v2.push_back(i + 1);
	}
	vector<int>vTarget;//目标容器
	vTarget.resize(v1.size() + v2.size());
	merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
	for_each(vTarget.begin(), vTarget.end(), myprint);
	cout << endl;
}

程序输出：

1
0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10

(11)reverse

逆序

1
2
3
4
5
6
7
8
9
10
11
12
13
void myprint(int val)
{
	cout << val << " ";
}
void test01()
{
	vector<int>v={10,30,40,50,20};
	for_each(v.begin(), v.end(), myprint);
	cout << endl;
	reverse(v.begin(), v.end());
	for_each(v.begin(), v.end(), myprint);
	cout << endl;
}

程序输出：

1
2
10 30 40 50 20
20 50 40 30 10

(12)copy将容器内指定范围的元素拷贝到另一容器中

注意：新容器需要预留空间

1
2
3
4
5
6
7
8
9
10
11
12
13
void myprint(int val)
{
	cout << val << " ";
}
void test01()
{
	vector<int>v={10,30,40,50,20};
	vector<int>v2;
	v2.resize(v.size());
	copy(v.begin(), v.end(), v2.begin());
	for_each(v2.begin(), v2.end(), myprint);
	cout << endl;
}

程序输出:

1
10 30 40 50 20

13.replace和replace_if

replace将容器内指定范围的旧元素修改为新元素

replace_if将区间内满足条件替换成指定元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void myprint(int val)
{
	cout << val << " ";
}
class compare
{
public:
	bool operator()(int a)
	{
		return a >= 40;
	}
};
void test01()
{
	vector<int>v={10,30,40,30,20,10,30,40,50,20};
	for_each(v.begin(), v.end(), myprint);
	cout << endl;
	replace(v.begin(), v.begin() + 4, 30, 300);
	for_each(v.begin(), v.end(), myprint);
	cout << endl;
	replace_if(v.begin(), v.end(), compare(), 66);
	for_each(v.begin(), v.end(), myprint);
	cout << endl;
}

程序输出：

1
2
3
10 30 40 30 20 10 30 40 50 20
10 300 40 300 20 10 30 40 50 20
10 66 66 66 20 10 30 66 66 20

(14)swap

交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void myprint(int val)
{
	cout << val << " ";
}
//swap交换两个同种类型容器的元素
void test01()
{
	vector<int>v={10,30,40,30,20,10,30,40,50,20};
	vector<int>v1;
	for (int i = 0; i < 10; i++)
		v1.push_back(i + 1);
	for_each(v.begin(), v.end(), myprint);
	cout << endl;
	for_each(v1.begin(), v1.end(), myprint);
	cout << endl;
	swap(v, v1);
	for_each(v.begin(), v.end(), myprint);
	cout << endl;
	for_each(v1.begin(), v1.end(), myprint);
	cout << endl;
}
void test02()//也可以swap两个数
{
	int a = 3, b = 4;
	swap(a, b);
	cout << a << " " << b << endl;//4 3
}

程序输出：

1
2
3
4
5
10 30 40 30 20 10 30 40 50 20
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
10 30 40 30 20 10 30 40 50 20
4 3

(15)accumulate和fill

需要头文件#include<numeric>

accumulate计算容器元素累计总和

fill向容器中添加元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void myprint(int val)
{
	cout << val << " ";
}
void test01()
{
	vector<int>v{10,30,40,30,20,10,30,40,50,20};
	for_each(v.begin(), v.end(), myprint);
	cout << endl;
	int total=accumulate(v.begin(), v.end(), 0);
//第三个参数表示起始累加值，0表示最后结果加0
	cout << total << endl;
}
void test02()
{
	vector<int>v;
	v.resize(10);
	for_each(v.begin(), v.end(), myprint);
	cout << endl;
	fill(v.begin(), v.end() - 2, 6);
	for_each(v.begin(), v.end(), myprint);
	cout << endl;
}

程序输出：

1
2
3
4
10 30 40 30 20 10 30 40 50 20
2800
0 0 0 0 0 0 0 0 0
6 6 6 6 6 6 6 6 0 0

(16)交集,并集,差集

set_intersection求两个容器的交集

set_union并集

set_difference差集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void myprint(int val)
{
	cout << val << " ";
}
void test01()
{
	vector<int>v={1,2,3,4,5,6,7,8,9,10};
	for_each(v.begin(), v.end(), myprint);
	cout << endl;
	vector<int>v1={5,6,7,8,9,10,11,12,13,14,15};
	for_each(v1.begin(), v1.end(), myprint);
	cout << endl;
	vector<int>vTarget;
	vTarget.resize(min(v.size(), v1.size()));//min是algorithm的算法
	cout << "intersection:" << endl;
	vector<int>::iterator itEnd=set_intersection(v.begin(), v.end(), v1.begin(), v1.end(),vTarget.begin());
	for_each(vTarget.begin(), itEnd , myprint);//itEnd为数据结束的位置，可避免输出大量0
	cout << endl;
	//
	vTarget.resize(v.size() + v1.size());
	cout << "union:" << endl;//注意：使用set_union必须保证两个集合都是有序序列
	itEnd=set_union(v.begin(), v.end(), v1.begin(), v1.end(), vTarget.begin());
	for_each(vTarget.begin(), itEnd, myprint);
	cout << endl;
	//
	vTarget.resize(max(v.size(), v1.size()));//max是algorithm的算法
	cout << "difference between v & v1:" << endl;
	itEnd=set_difference(v.begin(), v.end(), v1.begin(), v1.end(), vTarget.begin());
	//v和v1的差集表示在v中不在v1中的部分
	for_each(vTarget.begin(), itEnd, myprint);
	cout << endl;
}

程序输出：

1
2
3
4
5
6
7
8
1 2 3 4 5 6 7 8 9 10
5 6 7 8 9 10 11 12 13 14 15
intersection:
5 6 7 8 9 10
union:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
difference between v & v1:
1 2 3 4

(17)next_permutation

全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void test01()
{
	vector<int>vec;
	for (int i = 0; i < 3; i++)
	{
		vec.emplace_back(i + 1);
	}
	for (auto k : vec)
		cout << k << " ";
	cout << endl;
	while (next_permutation(vec.begin(), vec.end()))
	{
		for (auto k : vec)
			cout << k << " ";
		cout << endl;
	}
}

程序输出：

1
2
3
4
5
6
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

(18)lower_bound和upper_bound

lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。

在从小到大的排序数组中，lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

也可以用于vector容器，返回值是迭代器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int maxn = 100000 + 10;
const int INF = 2 * int(1e9) + 10;
#define LL long long
int cmd(int a, int b) {
	return a > b;
}
int main() {
	int num[6] = { 1,2,4,7,15,34 };
	sort(num, num + 6);                           //按从小到大排序 
	int pos1 = lower_bound(num, num + 6, 7) - num;    //返回数组中第一个大于或等于被查数的值 
	int pos2 = upper_bound(num, num + 6, 7) - num;    //返回数组中第一个大于被查数的值
	cout << pos1 << " " << num[pos1] << endl;//3 7
	cout << pos2 << " " << num[pos2] << endl;//4 15
	sort(num, num + 6, cmd);                      //按从大到小排序
	int pos3 = lower_bound(num, num + 6, 7, greater<int>()) - num;  //返回数组中第一个小于或等于被查数的值 
	int pos4 = upper_bound(num, num + 6, 7, greater<int>()) - num;  //返回数组中第一个小于被查数的值 
	cout << pos3 << " " << num[pos3] << endl;//2 7
	cout << pos4 << " " << num[pos4] << endl;//3 4
	return 0;
}
programming language
cpp-STL
https://blog.algorithmpark.xyz/2023/06/08/language/cpp-STL/
作者
CJL
发布于
2023年6月8日
更新于
2024年2月8日
许可协议