STL 标准模板库—容器部分【C++】

包含内容：

1. 容器类：vector、list、deque、set、map等
2. 迭代器：“泛型指针”，每个容器都有自己的迭代器，【vector和deque的迭代器是随机迭代器，而list、set、map的迭代器是双向迭代器】。
3. 算法：各种常用的算法，如sort、search、copy、erase等。
4. 仿函数：行为类似函数，可作为算法的某种策略，从实现的角度来看，仿函数是一种重载operator()的类或者模板。
5. 适配器（配接器）:一种用来修饰容器或仿函数或迭代器接口的东西。例如，STL提供的stack，queue，虽然看是容器，其实只能算是一种容器配接器，因为它们的底层完全借助deque，所有操作都是由底层的deque供应的。
6. 配置器：负责空间配置与管理。

1.string容器
文件件的区别：(C++) 、 (C语言）、 (C的字符串函数库）

一些方法：

• capacity()不等同于size()
• 可通过[ ]下标访问，at()函数访问，[区别：[ ]有时不会进行下标越界问题，而函数会有，但这取决于编译器],均以&引用返回。
• max_size() : 一般是2G
• 最好不要频繁的扩充空间，而是预先估计所需大小（reserve(newsize))来设定——效率更高（在vector中优化更明显）

#include
#include
using namespace std;

int main()
{
	//多种初始化方法
	string str1("hello");
	string str2 = " here";
	string str3 = { " my name is" };
	string str4({ " xxx." });
	string str5(4, '=');
	string str6(str1, 0, str1.length() - 3);
	string str7("C-style string", 7);
	cout << str1 << str2 << str3 << str4 < 
 
#include
#include
using namespace std;

int main()
{
	//元素访问
	string s("message"); // 为容量

	s = "abc";
	//at()访问
	s.at(2) = 'x'; // ok
	cout << s << endl;
	cout << "string size = " << s.size() << 'n';
	cout << "string capacity = " << s.capacity() << 'n';
	try {
		// 抛出，即使容量允许访问元素
		s.at(3) = 'x';
	}
	catch (std::out_of_range const& exc) {
		std::cout << exc.what() << 'n';
	}
	cout << "-----------------------------------" << endl;

	string const e("Exemplar");
	for (unsigned i = e.length() - 1; i != 0; i /= 2)
		cout << e[i];
	cout << endl;

	const char* c = &e[0];
	cout << c << endl; // 作为 C 字符串打印

	// 更改 s2 的最后字符为 'y'
	string s2("Exemplar ");
	s2[s2.size() - 1] = 'y';
	cout << s2 << endl;

	return 0;
}
 
 
#include
#include
using namespace std;

int main()
{
	//容量
	string str("hello world");
	//检查字符串是否为空
	if (!str.empty())
	{
		cout << str << endl;
	}
	cout << str.size() << endl;//返回字符数
	cout << str.length() << endl;
	cout << str.max_size() << endl;//返回字符数的最大值
	str.reserve(10);//保留存储
	cout << str << endl;//hello world
	cout << str.capacity() << endl;//15
	str.resize(10);
	cout << str << endl;//hello worl
	cout << str.capacity() << endl;//15

	str.reserve(1000);
	str.shrink_to_fit();//通过释放不使用内存减少内存使用
	cout << str << endl;//hello worl
	cout << str.size() << endl;//10

	return 0;
}
 

 resize(n):重设string大小以含n个字符。若当前大小小于n，则后附额外的字符；若当前大小大于n，则缩减string到为其首n个字符。
 
#include
#include
using namespace std;

int main()
{
	string str("hello world");
	str.push_back('x');
	cout << str << endl;
	str.insert(str.begin(), 'x');
	cout << str << endl;
	str.pop_back();
	cout << str << endl;
	str.erase(str.begin());
	cout << str << endl;
	str.replace(str.begin(), str.begin()+5, 1,'A');
	cout << str << endl;
	cout << str.substr(0, 3);
	cout << str.compare("hello") << endl;
	cout << str.substr(0,5) << endl;

	//访问头和尾
	cout << str.front() << endl;
	cout << str.back() << endl;

	return 0;
}
 
 
2、vector容器 
 
vector与数组不同，vector的大小可以动态变化，容器会自动扩容存储空间（一般是以1.5倍或2倍扩容）。
 
 
在vector中实际上有三个指针：first、last、end，capacity()=end-first，size()=last-first
 
 
vector的[ ]访问和at()函数访问都会进行越界检查
 
 
遍历方式：
 – 下标[ ]访问
 – 迭代器访问（可修改）
 – const_iterator迭代器访问(不可修改)
 
 
迭代器实质：类型* p；//故 const vector<类型>：：iterator it=v.begin();//可以解引用*，改变其值，但是不可++it改变指向
 
 
data()不要轻易使用，一旦被外部拿到地址，可能会有问题
 
 
#include
using namespace std;

//模板函数
template
void show(con c)
{
	typename con::iterator it=c.begin();
	for(it!=c.end();it++)
	{
		cout<<*it<<" ";
	}
	cout<
	vector  v;
	for(int i=0;i<5;i++)
	{
		v.push_back(i);
	}
	show(v);
	v.pop_back();
	show(v);
	return 0;
}
 
reserve()：预留存储空间，若new_cap大于当前的capacity()，则分配鑫存储，否则不做任何事，若new_cap大于capacity()，则所有迭代器和所有元素的引用都被非法化（因为原来的空间被释放了）。
 resize()：重设容器大小，以容纳n个元素。若当前大小小于n，则减小容器为其首n个元素；若当前大小大于n，则后附额外的默认插入的元素。
 
若申请空间很大，实际有效使用元素很少，可以通过一个块内的临时变量复制空间，再去和原变量交换，则可以达到收缩空间的目的。
 插入、删除可能使得迭代器失效，<-----这取决于是否发生了空间的重新分配
 emplace_back()：原位构建，直接将对象构建在此处空间—>效率高
 
3、list容器 
底层是双链表实现，插入和删除的效率都是O(1)
不具有随机访问性，存储密度过低（因为除了数据域，还有指针域）
迭代器是双向迭代器，只能单步移动，不能随机，因此，list没有[ ]下标访问和at()访问
list的迭代器的插入不会影响其他节点，因此，可以对iterator类型的指针来解引用进行值的改写，但是，==删除节点，会导致相邻的对象的迭代器会失效
unique()，唯一性删除： 必须有序才能调用
 
#include
#include
using namespace std;

int main()
{
	list ilist = { 2,4,5,7,9,5,1,0,3 };
	for (auto& x : ilist)
	{
		cout << x << " ";
	}
	cout << endl;
	ilist.sort();
	ilist.unique();//进行唯一性删除
	for (auto& x : ilist)
	{
		cout << x << " ";
	}
	cout << endl;
	return 0;
}
 
 
4、list和vector的区别 
 
5、双端队列deque 
有一块块的固定大小的连续空间构成（块与块之间是不连续的），一旦有必要在deque的前端或尾端增加新的空间，便配置一块固定大小的连续空间，串接在整个deque的头端或尾端。
随即性迭代器，[ ]下标访问、at()访问
 
deque的结构：
 

//迭代器
template
struct _Deque_iterator
{
	typedef _Ty** _Map_pointer;

	_Ty* _M_cur;
	_Ty* _M_first;
	_Ty* _M_last;
	_Map_pointer _M_node;
};

//deque
template
class _Deque_base
{
	typedef _Deque_iterator<_T> iterator;
protected:
	_T** _M_map;
	size_t _M_map_size;
	iterator _M_start;
	iterator _m_finish;
};
 
初始化一个deque对象iqu，他在内存空间的分布应该是这样的：
 
int main()
{
	deque iqu;
	return 0;
}
 
 
当向iqu中添加元素时：
 
	deque iqu;
	for (int i = 1; i <= 5; ++i)
	{
		iqu.push_back(i);
	}
 
缓冲区大小为8：
 
 进行删除：
 
iqu.pop_front();

iqu.pop_front();
 

 再次在尾部插入新元素：
 
for(int i=6li<=15;++i)
{
	iqu.push_back(i);
}
 

 此时，在插入16，iqu.push_back(16); 会引发新的缓冲区配置：
 
 
优先级队列：priority_queue底层必须是vector。 stack和queue的底层实现是deque。
 
6、map容器 
底层实现红黑树（排序二叉树）
遍历方式：
 – operator[ ]：访问或插入指定的元素。【若存在，以引用返回，不存在则进行插入】
 – at()：访问指定的元素，同时进行越界检查
 – 迭代器：双向迭代器
 
template
class map
{
	typedef pair value_type;
};

std::map> smap;//排序规则可更改
 
unordered_map：底层实现哈希表，与map的区别在于不会对map中的关键码进行排序
 
insert（std:;map:: value_type(age,name)）;
 
若关键码会重复，则使用multimap；而map则会将旧值进行覆盖，其返回值是值，insert()却不会覆盖，其返回值是个键值对
 
find()：返回迭代器
count()：只能是0 or 1
 
set容器:可用区检查序列有无重复值：count( )
 
int main()
{
	vector vec = { 1,2,6,7,9,1,4,5,1,6 };
	set a;
	for (auto& x : vec)
	{
		a.insert(x);
	}
	cout << "原size: " << vec.size() << "    现在size: " << a.size() << endl;

	return 0;
}
 

 下一节：迭代器部分...