C++的STL容器1

发表于 更新于 分类于 阅读次数： Changyan： 本文字数： 9.8k 阅读时长 ≈ 9 分钟
C++学习笔记

deque容器

deque容器基本概念
双端数组，可以对头端（尾端）进行插入删除操作

deque 与 vector区别
vector对于头部插入删除效率底，数据量越大，效率越低；vector 访问效率高
deque相对而言，对头部插入删除速度会比vector快
vector访问元素时的速度会比deque快，这和两者内部实现有关。

push_front、pop_front 插入和移除头部一个元素
push_back、pop_back 插入和移除尾部一个元素
insert 指定位插入
begin、end 迭代器

deque 内部工作原理
deque内部有个中控器，维护每段缓冲区中的内容，缓冲区中存放真实数据；中控器维护的是每个缓冲区的地址，使得使用deque时像一片连续的内存空间；当数据插满的时候，再找一段内存插入数据进去，再去中控器中记录这个地址
中控器中有很多的节点，指向数据的缓冲器。

deque容器的迭代器支持随机访问

deque构造函数

1
2
3
4
deque<T> qeqT;							//默认构造形式
deque(begin,end);						//构造函数将[begin,end)区间中的元素拷贝给本身
deque(n,elem);							//构造函数将n个elem拷贝给本身
deque(const deque &deq);				//拷贝构造函数
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
#include <iostream>
#include <deque>
#include <string>
using namespace std;

void printDeque(const string str,deque<int> &deq) 
{
	cout << str + ':' << endl;
	for (deque<int>::const_iterator it = deq.begin(); it != deq.end(); it++)
	{
		cout << *it << '\t';
	}
	cout << endl;
}

void test01()
{
	deque<int> deq;
	for (size_t i = 0; i < 10; i++)
	{
		deq.push_back(i);
	}
	printDeque("deq",deq);

	deque<int> d2(deq.begin(),deq.end()-5);
	printDeque("d2",d2);

	deque<int> d3(10, 100);
	printDeque("d3", d3);

	deque<int> d4(d3);
	printDeque("d4", d4);
}

int main()
{
	test01();
	return 0;
}

const_iterator:只读迭代器
iterator:可读可写迭代器
deque容器和vector容器的构造方式几乎一样。

deque 容器赋值操作

1
2
3
deque & operator=(const deque &deq);			//重载等号操作符
assign(beg.end);								//将[begin,end)区间中的数据拷贝给本身
assign(n,elem);									//将n个elem拷贝赋值给本身
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
#include <iostream>
#include <deque>
#include <string>
using namespace std;

void printDeque(const string str, deque<int> &deq)
{
	cout << str + ':' << endl;
	for (deque<int>::const_iterator it = deq.begin(); it != deq.end(); it++)
	{
		cout << *it << '\t';
	}
	cout << endl;
}

int main()
{
	deque<int> d1;
	for (size_t i = 0; i < 10; i++)
	{
		d1.push_back(i);
	}
	printDeque("d1",d1);

	deque<int> d2 = d1;
	printDeque("d2", d2);

	deque<int> d3;
	d3.assign(d2.begin(),d2.end());
	printDeque("d3", d3);

	deque<int> d4;
	d4.assign(10, 100);
	printDeque("d4", d4);
	return 0;
}

deque大小操作

1
2
3
4
deque.empty();				//判断容器是否为空
deque.size();				//返回容器中的元素个数
deque.resize(num);			//重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
deque.resize(num,elem);		//重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
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
#include <iostream>
#include <deque>
#include <string>
using namespace std;

void printDeque(string str, const deque<int> &d)
{
	cout << str + ':' << endl;
	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
	{
		cout << *it << '\t';
	}
	cout << endl;
}

int main()
{
	deque<int> d1;
	for (size_t i = 0; i < 10; i++)
	{
		d1.push_back(i);
	}
	cout << "d1容器是否为空：" << (d1.empty() ? "是" : "否") << endl;
	cout << "d1容器大小：" << d1.size() << endl;

	d1.resize(30);//容器扩大使用默认值填充
	cout << "d1容器大小：" << d1.size() << endl;
	printDeque("28行", d1);

	d1.resize(10);//容器变小
	cout << "d1容器大小：" << d1.size() << endl;
	printDeque("32行", d1);

	d1.resize(20,5);//容器扩大使用指定的值填充
	cout << "d1容器大小：" << d1.size() << endl;
	printDeque("36行", d1);

	return 0;
}

deque是没有容量概念,没有capacity;

deque容器插入和删除

两端插入操作：

1
2
3
4
push_back(elem);					//容器尾部添加一个元素
push_front(elem);					//容器头部添加一个元素
pop_back();							//删除容器最后一个元素
pop_front();						//删除容器第一个元素

指定位置操作：

1
2
3
4
5
6
insert(pos,elem);					//在pos位置插入一个elem元素的拷贝，返回新数据的位置 （pos位置提供一个迭代器位置）
insert(pos,n,elem);					//在pos位置插入n个elem元素，无返回值。
insert(pos,beg,end);				//在pos位置插入[beg,end)区间的数据，无返回值。
clear();							//清空容器的所有数据
erase(beg,end);						//删除[beg，end)区间的数据，返回下一个数据的位置
erase(pos);							//删除pos位置的数据，返回下一个数据的位置
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
#include <iostream>
#include <deque>
#include <string>
using namespace std;

void printDeque(string str, const deque<int> &d)
{
	cout << str + ':' << endl;
	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
	{
		cout << *it << '\t';
	}
	cout << endl;
}

int main()
{
	deque<int> d1;
	d1.push_back(10);
	d1.push_back(20);

	d1.push_front(100);
	d1.push_front(200);
	printDeque("d1", d1);

	d1.pop_back();
	printDeque("d1", d1);
	d1.pop_front();
	printDeque("d1", d1);

	d1.push_back(20);
	d1.push_front(200);

	d1.insert(d1.begin() + 1, 1000);
	printDeque("d1", d1);

	d1.insert(d1.begin() + 1, 2, 10000);
	printDeque("d1", d1);

	deque<int> d2;
	d2.push_back(1);
	d2.push_back(2);
	d2.push_back(3);
	//按照区间插入
	d1.insert(d1.begin(),d2.begin(),d2.end()-1);
	printDeque("d1", d1);

	//删除
	deque<int>::iterator it = d1.begin();
	it++;
	it = d1.erase(it);
	printDeque("d1", d1);

	d1.erase(it, it + 2);
	printDeque("d1", d1);
	
	d1.clear();
	printDeque("d1", d1);
	return 0;
}

总结：
插入和删除提供的位置是迭代器

deque数据存储

1
2
3
4
at(int idx);							//返回索引idx所指的数据
operator [];							//返回索引idx所指的数据
front();								//返回容器中第一个数据元素
back();									//返回容器中最后一个数据元素
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
#include <iostream>
#include <deque>
#include <string>
using namespace std;

int main()
{
	deque<int> d1;

	for (size_t i = 0; i < 10; i++)
	{
		d1.push_back(i);
	}
	for (size_t i = 0; i < 10; i++)
	{
		cout << d1.at(i) << '\t';
	}
	cout << endl;

	d1[3] = 1000;
	for (size_t i = 0; i < 10; i++)
	{
		cout << d1[i] << '\t';
	}
	cout << endl;

	cout << "第一个元素：" << d1.front() << endl;
	cout << "最后一个元素:" << d1.back() << endl;

	return 0;
}

deque排序

利用算法实现deque容器进行排序

1
sort(iterator beg,iterator end);			//对beg和end区间元素进行排序(默认排序规则，从小到大 升序)
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
#include <iostream>
#include <deque>
#include <string>
#include <algorithm>	//标准算法头文件
using namespace std;

void printDeque(const string str, deque<int> &deq)
{
	cout << str + ':' << endl;
	for (deque<int>::const_iterator it = deq.begin(); it != deq.end(); it++)
	{
		cout << *it << '\t';
	}
	cout << endl;
}

int main()
{
	deque<int> d1;
	d1.push_back(10);
	d1.push_back(20);
	d1.push_back(30);
	d1.push_front(100);
	d1.push_front(200);
	d1.push_front(300);
	printDeque("d1",d1);

	sort(d1.begin(), d1.end());
	printDeque("d1", d1);

	return 0;
}

对于支持水机访问的迭代器的容器，都可以利用sort算法直接对其进行排序

stack容器

先进后出 push pop

stack常用接口

构造函数：

1
2
stack<T> stk;					//stack采用模板类实现，stack对象的默认构造形式
stack(const stack & stk);		//拷贝构造函数

赋值操作：

1
stack & operator=(const stack &stk);			//重载等号操作符

数据存储

1
2
3
push(elem);					//向栈顶添加元素
pop();						//从栈顶一处第一元素
top();						//返回栈顶元素

大小操作：

1
2
empty();					//判断堆栈是否为空
size();						//返回栈的大小
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
#include <iostream>
#include <stack>
using namespace std;

int main()
{
	stack<int> s;
	s.push(10);
	s.push(20);
	s.push(30);
	s.push(40);

	stack<int> s1(s);

	while (!s.empty())
	{
		cout << "栈顶元素:" << s.top() << endl;
		s.pop();
	}

	cout << "栈大小:" << s.size() << endl;

	s = s1;

	while (!s.empty())
	{
		cout << "s栈顶元素:" << s.top() << endl;
		s.pop();
	}

	while (!s1.empty())
	{
		cout << "s1栈顶元素:" << s1.top() << endl;
		s1.pop();
	}

}

queue容器

是一种先进先出(First In First Out,FIFO)的数据结构，它有两个出口

队尾只能插入数据(push)；队头只能取数据(pop) ;队尾back();队头front();队头队尾看个人指定

队列容器允许从一端新增元素，从另一端移除元素
队列中只有队头和队尾才可以被外界使用，因此队列不允许有遍历行为；

构造函数：

1
2
queue<T> stk;					//queue采用模板类实现，queue对象的默认构造形式
queue(const queue & stk);		//拷贝构造函数

赋值操作：

1
queue & operator=(const queue &stk);			//重载等号操作符

数据存储

1
2
3
4
push(elem);					//向队尾添加元素
pop();						//从队头移除第一元素
front();					//返回第一个元素
back();						//返回最后一个元素

大小操作：

1
2
empty();					//判断队列是否为空
size();						//返回队列的大小
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
66
67
#include <iostream>
#include <queue>
#include <string>
using namespace std;

class Person
{
public:
	Person(string name, int age) :m_name(name), m_age(age)
	{

	}
	~Person();

	string readname(void)
	{
		return this->m_name;
	}

	int readage(void)
	{
		return this->m_age;
	}

private:
	string m_name;
	int m_age;
};


Person::~Person()
{
}

int main()
{
	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().readname() << "    年龄：" << q.front().readage() << endl;

		//查看队尾
		cout << "队尾元素 ----- 姓名" << q.back().readname() << "    年龄：" << q.back().readage() << endl;

		//出队
		q.pop();
	}

	cout << "容量" << q.size() << endl;
}

list容器

STL中的链表是一个双向循环链表
push_front、push_back、pop_front、pop_back、insert、begin、end

list构造函数

1
2
3
4
list<T> lst;						//list采用模板类实现，对象的默认构造形式
list(begin,end);					//构造函数将[begin,end)区间中的元素拷贝给本身
list(n,elem);						//构造函数将n个elem拷贝给本身
list(const list & lst);				//拷贝构造函数
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
#include <iostream>
#include <list>
using namespace std;

void printList(const list<int> &lst)
{
	for (list<int>::const_iterator it = lst.begin(); it != lst.end(); it++)
	{
		cout << *it << '\t';
	}
	cout << endl;
}

int main()
{
	list<int> lst;

	lst.push_back(10);
	lst.push_back(20);
	lst.push_back(30);
	lst.push_back(40);

	printList(lst);

	list<int>::iterator it = lst.begin();
	it++;
	it++;
	list<int> lst2(it, lst.end());	//构造部分区间
	printList(lst2);	//

	list<int> lst3(lst);
	printList(lst3);	//

	list<int> lst4(10,1000);
	printList(lst4);	//

	return 0;
}

list赋值和交换