施磊c++基础8

STL内容学习简介

C++STL : standard template libaray

vector容器

底层数据结构：动态开辟的数组。每次以空间大的二倍扩容

增加
vec.push_back(20); 末尾添加元素20 — O(1)
vec.insert(it，20);在it迭代器指向的位置插入元素20 — O(n)

删除
vec.pop_back; 末尾删除元素 ---- O(1)
vec.erase(it) ;删除it迭代器指向的位置的元素 — O(n)

查询
operator[ ]使用vec[ i ]访问第i个位置元素 — O(1)
iterator迭代器进行遍历
find，for_each

常用方法
size()
empty()
reserve(20)：给vector预留空间的
resize(20):给容器扩容用的
swap(a,b)：两个容器进行元素交换

deque和list

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

deque < int > deq;

增加：
deq.push_back(20);从末尾添加元素 — O(1)
deq.push_front(20);从首部添加元素 — O(1)
deq.insert(it，20);在it迭代器指向的位置插入元素20 — O(n)

删除：
deq.pop_back();从尾部删除元素 — O(1)
deq.push_front(20);从首部删除元素 — O(1)
deq.erase(it) ;删除it迭代器指向的位置的元素 — O(n)

list：链表容器
底层数据结构：双向的循环链表 — pre,data,next
list< int> mylist;

增加：
mylist.push_back(20);从末尾添加元素 — O(1)
mylist.push_front(20);从首部添加元素 — O(1)
mylist.insert(it，20);在it迭代器指向的位置插入元素20 — O(n)
删除：
mylist.pop_back();从尾部删除元素 — O(1)
mylist.push_front(20);从首部删除元素 — O(1)
mylist.erase(it) ;删除it迭代器指向的位置的元素 — O(1)

对于链表来说，查询的操作比较慢O(n)

vector，deque和list对比

vector特点：动态数组，内存是连续的，2倍方式进行扩容
deque特点：动态开辟的二维数组空间，第二维是固定长度的连续空间。扩容的时候，第一维数据进行二倍扩容
面经问题：deque底层内存是否是连续的？
并不是。第二维度是连续的，但每个第二维之间并不是连续的。

vector和deque之间的区别：
1.底层数据结构
2.前中后插入删除元素的时间复杂度：中间和末尾O(1),在首部插入，deque是O(1)，vector是O(n).
3.对于内存的使用效率来说:vector 需要的内存空间必须是连续的
而deque不需要
4.在中间进行insert()或者erase()的效率:都是O(n)。都要进行元素移动，但是vector是完全连续的，所以比较简单一点，

vector和list之间的区别：
1.底层数据结构：数组 双向循环链表
数组：增加删除O(n)，查询O(n)，随机访问O(1)
链表：增加删除O(1)，查询O(n)，随机访问O(n)

详解容器适配器

1.适配器底层没有自己的数据结构，他是另外一个容器的封装，它的方法，全部由底层依赖的容器进行实现。
2.没有实现自己的迭代器

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;
};

stack：push(),pop(),top(),empty().size()
stack->deque 为什么不依赖vector？

queue:：push(),pop(),front(),back,empty().size()
queue->deque 为什么不依赖vector？

priority_queue：push(),pop(),top(),empty().size()
priority_queue->vector 为什么不依赖deque？

• 上面问题1和问题2：vector 的初始内存使用效率低
  deque一开始就是4096字节的初始化，而vector还要1-2-4-8-16-32 …
  虽然可以用reserve修改，但是涉及到修改源码，不如deque直接方便
• 对于queue来说，需要尾部插入O（1），头部删除vector - O(n)，出队效率低。
• vector需要大片的连续内存，deque只需要分段的内存

那么为什么priority_queue要依赖vector呢？

• priority_queue底层数据结构是大根堆，而大根堆和小根堆都是要在内存连续的数组上构建（父节点和左右孩子节点之间需要坐标来对应）

无序关联容器

无序关联容器 =》 链式哈希表 =》 增删查O(1)

set：集合
unordered_set：单重集合 — 不允许相同元素存在
unordered_multiset：多重集合 — 允许相同元素存在
增加：insert(val)
遍历：iterator自己搜索，调用find方法
删除：erase(key),erase(it)

map：映射表(key,value)
增加：unordered_map<int, string> map1;
map1.insert(make_pair(1000, “张三”));
map1.insert({1010, “李四”});
遍历：可以用[ ]重载访问
但是，[ ]运算符重载有一个问题：

1. 它可以查询
2. 如果key不存在，它会创建一对数据（使用默认值）

int main()
{
	unordered_map<int, string> map1;
	map1.insert(make_pair(1000,"张三"));
	map1[2000] = "李四";
	cout << map1.size() << endl;
	map1[1000] = "王五";
	cout << map1.size() << endl;
}
//2   2

第一个创建2000 - 李四，第二个修改1000 - 张三

unordered_map：单重映射表
unordered_multimap：多重映射表

有序关联容器

有关联容器 =》红黑树 =》增删查O(log2n)
不需要unordered_
set
multiset
map
multimap
插入元素后，会自动排序。
但是既然是这样的话，如果添加了自定义数据类型，就需要重载比较符和输出流。

迭代器iterator

容器的迭代器
vector< int>::iterator it = vec.begin()
可以写成auto it = vec.begin()
编译器会自动识别auto应该变成的类型
并且可以通过迭代器修改容器内元素的值

int main()
{
	vector<int> vec;

	for (int i = 0; i < 20; ++i)
	{
		vec.push_back(rand() % 100);
	}
	auto it1 = vec.begin();
	for (; it1 != vec.end(); ++it1)
	{
		cout << *it1 << " ";
		if (*it1 % 2 == 0)
		{
			*it1 = 0;
		}
	}
	cout << endl;
	for (int v : vec)
	{
		cout << v <<"  ";
	}
	cout << endl;
}

此外还要其他迭代器类型

const_iterator：常量迭代器，只能读，不能写

反向迭代器：
vector< int>::reverse_iterator rit = vec.rbegin();
其中rbegin()返回的是最后一个元素的反向迭代器表示
rend()返回的是首元素前驱位置的迭代器表示

函数对象

通过类创建出来的一个对象，调用起来语法结构像调用函数，我们把这种对象叫做函数对象。它通过重载函数调用操作符（operator()）来实现可调用操作。函数对象可以像普通函数一样被调用，也可以像普通对象一样被拷贝、赋值、作为参数传递给其他函数等。函数对象广泛地应用于STL算法中，例如排序和查找等操作。函数对象可以使程序更加灵活和高效，因为它可以在运行时自定义函数的行为

具体在之后的 lambda表达式部分 会细讲

泛型算法

特点一：泛型算法接受的都是迭代器

当传入的是一元函数时，可以用二元函数＋绑定器实现

#include<iostream>
#include<algorithm>
#include<functional>
#include<vector>
using namespace std;

int main()
{
	int arr[] = { 12,4,15,498,984,94,6,65,56,56,6,5 };
	vector<int> vec(arr, arr + sizeof(arr) / sizeof(arr[0]));
	

	sort(vec.begin(),vec.end());

	for (int i : vec)
	{
		cout << i << " ";
	}

	if (binary_search(vec.begin(), vec.end(), 56))
	{
		cout << "ok" << endl;
	}


	sort(vec.begin(), vec.end(), greater<int>());

	auto it2 = find_if(vec.begin(), vec.end(),
		bind1st(greater<int>(),48)); 

	vec.insert(it2, 48);

	for (int i : vec)
	{
		cout << i << " ";
	}
}