c++使用stl刷题

参考黑马教程，C语言中文网，从其他语言（C，Java）快速入门c++刷题（二）

模板（函数模板，类模板）

函数模板：template

​ 自动类型推导，必须推导出一致的数据类型T才可以使用

容器，算法，迭代器，仿函数，适配器，空间配置器

1.客器:各种教据结构，如vector、list、deque、set、map等,用来存放数据。

2.算法:各种常用的算法。如sort、find、copy、for_each等

3.迭代器:扮演了容器与算法之间的胶合剂。

4.仿函数:行为类似函数。可作为算法的某种策略。

5.适配器:一种用来修饰容器或者仿函数或迭代器接口的东西。

6.空间配置器:负责空间的配置与管理。

**序列式容器:**强调值的排序，序列式容器中的每个元素均有固定的位置。

关联式容器:二叉树结构，各元素之间没有严格的物理上的顺序关系

**质变算法：**是指运算过程中会更改区间内的元素的内容。例如拷贝，替换，删除等等
**非质变算法:**是指运算过程中不会更改区间内的元素内容，例如查找、计数、华历、寻找极值等等

迭代器：容器和算法之间的粘合剂（类似指针）

C++ 对模板（Template）支持得很好，STL 就是借助模板把常用的数据结构及其算法都实现了一遍，并且做到了数据结构和算法的分离。例如，vector 的底层为顺序表（数组），list 的底层为双向链表，deque 的底层为循环队列，set 的底层为红黑树，hash_set 的底层为哈希表。

容器中常见的函数成员

序列容器包含一些相同的成员函数，它们的功能也相同

动态数组，向量#include

定义

操作

auto相当于vector::iterator

尾部添加5
v.push_back(5);

插入元素
v.insert(v.begin()+i,value);//在第i+1个元素前面插入value;

删除元素，参数是迭代器
v.erase(v.begin() + 5);//删除第6个元素  

清空向量
v.clear();//clear

获取起始地址或结束地址
v.begin();//起始地址
v.end();//结束地址

反转元素，逆序
reverse(v.begin(),v.end());//反转

使用sort排序，可以自定义排序规则
sort(v.begin(),v.end());

//迭代器遍历
for (auto it = c.begin(); it != c.end(); it++)
    cout << *it << endl;

//下标遍历
for (unsigned i = 0; i < c.size(); i++) {
    cout << c[i]<< endl;
}

算法

需要头文件#include

(1) 使用reverse将元素翻转：

reverse(vec.begin(),vec.end()); 将元素翻转(在vector中，如果一个函数中需要两个迭代器，一般后一个都不包含.)

(2)使用sort排序：

sort(vec.begin(),vec.end());(默认是按升序排列,即从小到大).

可以通过重写排序比较函数按照降序比较，如下：

定义排序比较函数：

bool Comp(const int &a,const int &b)
{
   return a>b;
}

调用时:sort(vec.begin(),vec.end(),Comp)，这样就降序排序。

双端数组

内部：

赋值，操作：同vector

大小: 没有容量限制

push_back(elem);	//在容器尾部加入一个元素
pop_back();		//删除容器中最后一个元素
push_front(elem);	//在容器开头插入一个元素
pop_front();	//从容器开头移除第一个元素
insert(pos,elem);	//在pos位置插elem元素的拷贝，返回新数据的位置。
insert(pos,n,elem);		//在pos位置插入n个elem数据，无返回值。
insert(pos,beg,end);	//在pos位置插入[beg,end)区间的数据，无返回值。
clear();	//移除容器的所有数据
erase(beg,end);		//删除[beg,end)区间的数据，返回下一个数据的位置。
erase(pos);		//删除pos位置的数据，返回下一个数据的位置。

remove(elem);	//删除容器中所有与elem值匹配的元素。

数据存储
front();  //返回第一个数据
back();

L.reverse();
L.sort(成员函数)

有序集合

multiset 可重复

set s;
s.insert(e) ;//向集合添加元素
s.erase(pos);//删pos迭代器所指元素，返回下一个元素的迭代器 
s.erase(beg,end);

s.erase(e);
	set::iterator pos = 	s.find(30);//查找
	if (pos != s.end())
	{cout<<"找到元素: "<<*pos << endl;}

s.count(30);//统计0/1

#include 
#include 
using namespace std;
int main() {
    set s;
    s.insert(2);//向集合添加元素
    s.insert(3);//向集合添加元素
    cout << *(s.begin()) << endl; //输出第一个元素
    for (int i = 0; i < 10; i++) {//插入0 - 9
        s.insert(i);
    }
    for (set::iterator it = s.begin(); it != s.end(); it++) {
        cout << *it << " ";//集合的遍历，it是一个迭代的指针
    }
    cout << endl << (s.find(2) != s.end()) << endl;//查找，元素
    s.erase(3);//删除元素
    cout << (s.find(3) != s.end()) << endl;
    return 0;
}

仿函数自定义排序规则

返回两个数据

pairp(value1, value2);
pairp = make_pair( value1, value2 );

cout< 
map/multimap 
按键从小到大排序
 
multimap和 map 容器唯一的不同在于，multimap 容器中存储元素的键可以重复。
 
map m;
//第—种插入方式
m.insert(pair(1，10));
//第二种插入方式
m.insert(make_pair(2，20));
//第三种插入方式
m.insert(map::value_type(3，30));
//第四种插入方式
m[4] = 40;printMap(m);

erase(key);
find(key);
count(key);
 
#include 
#include 
 
 
3.适配器 
容器适配器
基础容器筛选条件
默认使用的基础容器
stack
基础容器需包含以下成员函数：empty()size()back()push_back()pop_back()满足条件的基础容器有 vector、deque、list。
deque
queue
基础容器需包含以下成员函数：empty()size()front()back()push_back()pop_front()满足条件的基础容器有 deque、list。
deque
priority_queue
基础容器需包含以下成员函数：empty()size()front()push_back()pop_back()满足条件的基础容器有vector、deque。
vector
stack 
stack s;
s.empty()               如果栈为空返回true，否则返回false
s.size()                返回栈中元素的个数
s.pop()                 删除栈顶元素但不返回其值
s.top()                 返回栈顶的元素，但不删除该元素
s.push()                在栈顶压入新元素
 
#include 
#include 
using namespace std ;
int main() {
	stack s; //定义一个空栈s
    for (int i = 0; i < 6; i++) {
		s.push(i); //将元素i压入栈s中
	}
	cout << s.top() << endl; //访问s的栈顶元素
    cout << s.size() << endl; //输出s的元素个数
    s.pop(); //移除栈顶元素
	return 0;
}
 
queue 
q.push(x):将x元素接到队列的末端；
q.pop() 弹出队列的第一个元素，并不会返回元素的值；
q.front()访问队首元
q.back()访问队尾元素
q.size()访问队中的元素个数
 
#include 
#include 
using namespace std ;
int main() {
	queue q; //定义一个空队列q
    for ( int i = 0; i< 6; i++) {
		q.push(i); //将i的值依次压入队列q中
    }
	cout << q.front() << " " << q.back() << endl; //访问队列的队首元素和队尾元素
    cout << q.size() << endl; //输出队列的元素个数
	q.pop(); //移除队列的队首元素
	return 0 ;
}