c++04STL部分复习

1、deque list vector概括：

/*
deque :双端队列容器
底层数据结构：动态开辟的二维数组，一维数组从2开始，以2倍的方式进行扩容，每次扩容后，原来的第二维的数组
从新的第一堆数组下表的oldsize/2开始存放，上下都预留空行，方便支持首位元素的添加

deque<int>deq;
deq.push_back(20);
deq.push_front(20) 首尾添加都是O（1）
deq.insert(it,20);添加元素O(n)

删除操作:
deq.pop_back();从末尾删除元素
deq.pop_front();从首部删除元素
deq.erase(it);从it指向的位置删除元素

迭代器：
iterator(连续的insert和erase考虑迭代器失效的问题)

list:链表容器
底层数据结构:双向的循环链表
list<int> mylist;
增加：
push_back O(1)
push_front O（1）
insert(it,20)  it指向的位置添加元素O（1） 先要查询，效率很慢

删除:
pop_back(); O(1)
pop_front();O(1)
erase(it) O(n)

查询搜索:
iterator

Vector：向量容器
底层数据结构:动态开辟的数组，每次以原来空间大小的2倍进行扩容的

vector<int>vec;
增加：push_back O(1) 导致扩容
vec.insert(it,20) 迭代器指向的位置添加一个元素

删除：
vec.pop_back() 删除元素末尾
vec.erase(it);
查询：迭代器
operator[] 下标随机访问 vec[5] O(1)
iterator迭代器进行遍历
find for_each
foreach => 通过迭代器实现的

注意:对容器连续插入或者删除小心迭代器失效
常用方法介绍：
size()
empty()
reserve（20);vector预留的空间的
resize(20);扩容的
swap;交换
*/

#include<vector>
#include<time.h>
#include<iostream>
using namespace std;

int main()
{
	vector<int>vec;
	for (int i = 0; i < 20; i++)
	{
		vec.push_back(rand() % 101);
	}
	int size = vec.size();
	for (int i = 0; i < size; i++)
	{
		cout << vec[i] << " ";
	}
	cout << endl;
	vector<int>::iterator it = vec.begin();
	while (it != vec.end())
	{
		cout << *it << " ";
		it++;
	}
	vector<int>::iterator it1 = vec.begin();
	while (it1 != vec.end())
	{
		if (*it1 % 2 == 0)
		{
			it1 = vec.erase(it1); //不是偶数的时候才要++
			continue;
		}
		it1++;
	}
	cout << endl;
	vector<int>::iterator it2 = vec.begin();
	while (vec.end() != it2)
	{
		cout << *it2 << "　";
		it2++;
	}
	return 0;
}
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

2、vector list deque 对比

#if 0
vector特点：动态数组、内存是连续的，2倍的方式进行扩容
deque：动态开辟的二维数组空间，第二维是固定的长度的数组空间
扩容的时候第一维的数组进行2倍扩容

vector和deque之间的区别：
1、底层数据结构
2、前中后插入删除元素的时间复杂度：中间和末尾O（1） 前deque （1）
3 对于内存使用效率，vector需要的内存空间必须是连续的，deque可以分块进行数据存储
不需要内存空间必须是连续一片
4、再中间进行insert或者erase，vector和deque他们的效率谁能更好一点（vector）？谁能差一点（deque）？O（n)
5、vector和list之间的区别？ 数组：增加删除O（n) 查询O（n) 随机访问O(1) 链表:（考虑搜索的时间）增加删除O（1）
1、底层数据结构 ：数组 双向循环链表
#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3、函数对象

#if 0
/*仿函数的好处*/



#include<iostream>
using namespace std;
#if 0
template<typename T>
inline bool _greater(T a, T b)
{
	return a > b;
}
template<typename T>
inline bool _less(T a, T b)
{
	return a < b;
}
#endif 


//c++函数对象实现
/*
1、通过函数对象调用operator(),可以省略函数的调用开销，比通过
函数指针调用函数（不能够inline内联调用）效率高
2、可以添加想要的属性因为用类生成的
*/
template<typename T>
class _greater
{
public:
	bool operator()(T a, T b)
	{
		return a > b;
	}

private:
	int _count;
};
template<typename T>
class _less
{
public:
	bool operator()(T a, T b)
	{
		return a < b;
	}
};

template<typename T, typename Compare>
bool compare(T a, T b, Compare comp)
{
	return comp(a, b);  //通过函数指针调用函数，是没有办法内敛的，
	//效率很低因为有函数调用开销
	// operator() (a,b)
}

int main()
{
	cout << compare(10, 20, _greater<int>()) << endl;
	cout << compare('b', 'y', _less<char>()) << endl;
	return 0;
}

#endif

#include<iostream>
#include<queue>
#include<set>
#include<vector>
using namespace std;

int main()
{
	set<int, greater<int>>set1;
	for (int i = 0; i < 10; i++)
	{
		set1.insert(rand() % 100);
	}
	for (int v : set1)
	{
		cout << v << " ";
	}
	cout << endl;
	return 0;
}

#if 0
int main()
{

	priority_queue<int>que; //vector
	for (int i = 0; i < 10; i++)
	{
		que.push(rand() % 101);
	}
	while (!que.empty())
	{
		cout << que.top() << " ";
		que.pop();

	}
	cout << endl;
	using MinHeap = priority_queue<int, vector<int>, greater<int>>;
	MinHeap que1; //vector
	for (int i = 0; i < 10; i++)
	{
		que1.push(rand() % 101);
	}
	while (!que1.empty())
	{
		cout << que1.top() << " ";
		que1.pop();

	}

	return 0;
}
#endif
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

4、容器适配器

#include<iostream>
#include<vector>
#include<deque>
#include<list>
#include<stack>
#include<queue>
#include<time.h>
using namespace std;

/*
标准容器 - 容器适配器 -> 设计模式，就叫适配器模式
怎么理解这个适配器?
1、适配器底层没有自己的数据结构，它是另外一个容器的封装，它的方法全部依赖于底层容器的实现
2、没有实现自己的迭代器
*/

#if 0
template<typename T, typename Container = deque<T>>
class Stack
{
public:
	void push(const T& val) { con.push_back(val); }
	void pop() { con.pop_back(); }
	T top() const { return con.back(); }
private:
	Container  con;
};
#endif


int main()
{
	//同理priority_queue<int>que;
	queue<int> que;
	for (int i = 0; i < 20; i++)
	{
		que.push(rand() % 100 + 1);
	}
	cout << que.size() << endl;
	while (!que.empty())
	{
		cout << que.front() << " ";
		que.pop();
	}
	cout << endl;
#if 0
	//push入栈 pop出线 top查看栈顶元素  empty判断栈空  size返回元素个数
	stack<int>s;
	for (int i = 0; i < 20; i++)
	{
		s.push(rand() % 100 + 1);
	}
	cout << s.size() << endl;
	while (!s.empty())
	{
		cout << s.top() << " ";
		s.pop();
	}
#endif
	cout << endl;
	return 0;
}
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