10STL

1. STL初始

STL(标志模板库)存在意义: 为了建立数据结构和算法的一套标志.

1 基本概念:

1. STL从广义的分为: 容器(container),算法(algorithm),迭代器(iteration)
2. 容器与算法直接通过迭代器进行无缝连接
3. STL几乎所有的代码多采用了模板类或者模板函数

STL6大组件

1. 容器: 各种数据结果, 如vector, list, deque, set, map等,用来存放数据

   容器分为序列式容器和关联式容器两种

   序列式容器: 序列式容器每个元素均有固定的位置

   关联式容器: 二叉树结构, 各个元素没有顺序关系

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

   质变算法: 运算过程中会更改区间内元素的内容

   非质变算法: 运算过程中不会更改区间内的元素内容

3. 迭代器: 扮演了容器与算法直接的胶合剂

   算法只能通过迭代器去访问容器

   种类:

   1. 输入迭代器: 对数据的只读访问
   2. 输出迭代器: 对数据的只写访问
   3. 前向迭代器: 读写操作, 并能向前推进迭代器(++,==等)
   4. 双向迭代器: 读写操作, 并能向前和向后操作(-- ++等)
   5. 随机访问迭代器: 读写操作, 可以跳跃式访问任意数据, 功能最强的迭代器(n+,n-)

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

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

6. 空间配置器: 负责空间的配置和管理容器

2 容器 vector 容器, 可以把容器看成一个指针

1. 容器中的.push_back是向后置添加

2. 迭代器:v.begin:起始迭代器, 指向容器中第一个元素

   v.end():指向容器中最后一个元素的下一个位置

   便利方式:

   第一种
   vector::iterator itBegin = v.begin();//起始迭代器,指向容器中的第一个元素
   vector::iterator itEed = v.end();//结束迭代器, 指向容器中最后一个元素的下一个位置
   while(1){
   	cout << *itBegin << endl;
   	itgegin++
   }
   
   第二种
   for(vector::iterator it = v.begin(); it != v.end(); it++)
   {
   	cout << *it< 

3 string容器 1 本质:string本质是一个类

string和char*区别:

• char *是一个指针
• string是一个类, 类内部封装了char*, 管理这个字符串, 是一个char*型的容器

2 string构造函数

• string(); //创建一个空的字符串 列如:string str;
• string(const char *s);//使用字符串s初始化
• string(const string & str);使用一个string对象初始化另一个string对象
• string(int n, char ‘c’); 使用n个字符初始化

3 string赋值操作

​ 赋值的函数原型:

• string & operator=(const char* s)

  string s1 ;s1 = “adfadf”; //char*类型字符串赋值给当前的字符串

• string& operator=(const string &s)

  string s1(“afasd”), string s2; s2=s1; //把字符串s1赋值给当前的字符串

• string& operator=(char c);

  s1 = ‘a’;把字符赋值给当前的字符串

• string& assign(const char* s)

• string& assign(const char* s,int n)把字符s的前几个字符赋给当前的字符串

  str(“adfa”,2)//ad

• string& assign(const string &s)

• string& assign(int n, char c) 把n个字符赋值给字符串

4 字符串拼接

string& operator+=(const char* str)

string& operator+=(const char c)

string& operator+=(const string& str)

string& append(const char *s);

string& append(const &string s);

string& append(const char *c,int n);追加*c前n个字符

string& append(const string&s, int pos, int n),从下标为pos开始截取,截取个数为n

5 string查找和替换

功能描述:

• 查找: 查找指定字符串是否存在
• 替换: 在指定的位置替换字符串

函数原型:

查找返回值(下标 || -1)

• int find(const string& str, int pos = 0) const

  查找str在第一个次出现位置, 从pos开始查找

• int find(const char* s, int pos = 0) const

  查找s在第一次出现位置, 从pos开始查找

• int find(const char* s, int pos, int n) const;

  从pos下标位置查找s的前 n个字符第一次出现的位置

• int find(const char c, int pos = 0) const

  查找字符c第一次出现位置

• int rfind(const string& str, int pos = npos) const

  查找str最后一次位置, 从pos开始查找

• int rfind(const char*s, int pos = npos) const

  查找s最后一次位置, 从pos开始查找

• int rfind(const char *c, int pos, int n) const

  从pos查找s的前n个最后最后一次位置

• int rfind(const char c, int pos = 0) const

  查找字符c最后一次出现位置

• string & replace(int pos, int n, const string& str);

  替换从pos开始n个字符为字符串str

从pos位置起, n个字符替换为s

• string& replace(int pos, int n, const char s)*

  替换从pos开始n个字符为字符串str

• string& replace(int pos, int n, const &s)

  替换从pos开始n个字符为字符串str

find和rfind区别: find从左往右找, rfind从右往左找.

6 字符串比较

字符串比较是按照ascll码, =返回0, 大于返回1, 小于返回-1

多个字符串比较, 返回值是第一字符的大小

函数原型

• int compare(const string &s) const
• int compare(char *p)const

单个字符串存取

• char& operator[](int n); //通过[]方式取字符
• char& at(int n);通过at放反获取字符

7 字符串插入和删除

函数原型:

• string& insert(int pos, const char* s);

• string & insert(int pos, const string& str);

• string& insert(int pos, int n, char c);

  在下标为pos前插入n个字符c

• string& erase(int pos, int n = npos);

  删除从Pos开始的n个字符

8 string 子串

函数原型

​ 从字符串中获取想要的子串

• string substr(int pos = 0; int n = npos) const

  返回值有pos开始的n个字符组成的字符串

9 字符串容器易忘点

有参构造

• string s1(3,'c'); cout << s1 << endl//s1 = ccc

  s1等于3个c;

赋值操作

• c2='c':赋值单个字符

• c2.assign("afda", 2); 把字符串传"afda"前2个赋值给c2

• c2.assign(2, 'c'); c2为cc;

字符串添加

• c2.append("dddd",2,3);c2+=dd
• f.find(“随便”,0,0) . 返回值总是0;

字符串查找

• int find(const char* s, int pos, int n) const;

  从post位置查询字符串c前n个字符

字符串替换:

• string c2 = “fasdfa”; c2.replace(1,2,“cccc”),//fccccdfa

字符串比较

• s2.compare(“cc”), //比较第一个字符,大于返回1,等于返回0,小于-1.如果第一个相等, 在依次计较一下个

字符串插入

• s2.insert(0,2,‘n’)//nn
• s2.insert(2"ccc")

4 victor容器(尾部单端数组)

1. 功能:

• vector数据结构和数组非常类似, 也称为单端数组

vector和普通数组区别:

• vector可以动态扩展

动态扩展:

• 并不是在原有空间之后续接新空间, 而是找到更大的内存空间, 将原有数据拷贝到新空间, 并且释放掉原空间
• vector容器迭代器是支持随机访问的迭代器
• end():最后一个元素的下一个下标, rend():第一元素的上一个下标
• begin();第一个元素下标, r_begin()最后一个元素下标

2. 构造->函数原型:

   1. vector v //采用模板实现类实现, 默认构造函数
   2. vector(v.begin(), v.end()) //将 v[begin(), end())区间中元素拷贝给本身
   3. vector(n, elem)//拷贝函数将n个elem拷贝给本身
   4. vector(const vector &vec)//拷贝构造函数

3. vector 赋值操作

   原型:

   • vector& operator=(const vector &vec)//重载等号操作符
   • assign(v.beg(), v.end());//将s1[beg,end)区间中的数据拷贝赋值给本身
   • assign(n, elem)//将n个elem拷贝赋值给本身

4. vector容量和大小

   功能描述:

   • 对vector容器的容量和大小操作

   函数原型:

   • empty: 判断容量是否为空, 如果为空返回值是true,否则为false;
   • capacity/容器的容量
   • size(): //容器中元素的个数
   • resize(int num)/重新定义容器的长度为num, 若容器变长, 则以默认值0填充新位置, 如果容器变短, 则末尾超出容器长度的元素被删除.
   • resize(int num, elem)/重新知道容器的长度为num, 若容器变长, 则以elem值填充新位置. 如果容器变短, 则末尾超出容器长度的元素被删除

5. vector插入和删除, 跟字符串类有稍微区别

函数原型:

• push_back(eles) //尾部插入元素eles

• pop_back()//尾部删除

• insert(const_iterator pos, ele)//从迭代器指向位置pos插入元素ele

• insert(const_iterator pos, int count, ele//从迭代器指向pos, 插入n个ele

• insert(const_iterator pos, const_iterator start,const_iterator end)

  在pos位置插入start到end的元素

• intsert(v.begin()+3)

• erase(const_iterator pos)//删除迭代器指向的元素

• erase(const_iterator start, const_iterator end)//删除迭代器从start到end之间的元素,

• clear() //删除容器中所有的元素

6. vector数据存储

   功能描述:

   • 对vector中的数据的存取操作

   数据原型

   • at(int idx) //返回索引idx所指的数据
   • operator[]//返回索引idx所指的数据
   • front //返回容器中第一个数据元素
   • back //返回容器中最后一个数据元素

7. vector互换容器

   本质是指针指向的内存地址互换

   功能描述:

   • 实现2个容器内元素进行互换

   • 匿名对象执行完后会由空间自动释放

     vectorv;
     for(int i = 0; i < 1000; i++){
     	v.push_back(i);
     }
     v.size(3);
     容量过大,长度过少.造成空间浪费
     vector(v).swap(v) //容量会等于size. 匿名对象v,互换后匿名对象会指向初始化v 容量等于的size的vector
     

   函数原型:

   • swap(vec); //将vec与本身的元素进行符号

   作用: 收缩容器的容量

   如果想限制迭代器会修改容器中的数据可以加const, 迭代器也用const

8. vector预留空间

   功能描述:

   • 减少vector在动态扩展容量时的扩展次数, 尤其在数据量比较大的时候

   v.reserve(100000);
   	int* p = NULL;
   	int num = 0;
   	for (int i = 0; i < 100000; i++) {
   		v.push_back(i);
   		if (p != &v[0]) {
   			p = &v[0];
   			num++;
   		}
   	}
   

   函数原型

   • reserve(int len);//容器预留len个元素长度, 预留位置不初始化, 元素不可访问

5 deque容器 1.基本概率

功能: 双端数组, 可以对头端进行插入和删除操作

deque与vector区别

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

deque内部工作原理:

deque内部有个中控器,中控器有多个节点,每个节点存放的是一个指针, 这个这种指向缓冲区的数据

中控器维护的是每个缓冲区的地址, 使的使用deque时, 像一片连续的内存空间

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hPq9IMXw-1656319123712)(E:yunPanOneDrive桌面typora图片资源捕获.PNG)]

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

const_itretator.const迭代器.

push_front() : 头部增加, push_back(): 尾部添加

pop_front(): 头部删除, pop.back(): 尾部删除

2 deque构造函数和赋值操作

deque构造类和赋值似于vector;

3 deque大小,插入,删除操作

类似于vector. 但是deque没有capacity容量这个概念

6 stack容器(堆栈容器) 1 基本概念

概念: stack是一种先进后出的数据结果, 它只有一个出口

栈中只有顶端的元素才可以被外界使用, 因此栈不允许有遍历行为

入栈:push. 出栈;pop

栈可以返回元素个数(元素在入栈的时候栈就开始记录个数了)

2 stack常用接口

构造函数:

​ 相比于vector和deque缺少2种(v(n,10)和v(v.begin(),v.end()))

• stack stk; 默认构造
• stack(const stack &stk); 拷贝构造

赋值操作:

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

数据存取:

• push(elem) //向栈顶添加元素
• pop(); //向栈顶删除元素
• top(); //返回栈顶元素

大小操作

• empty(); 判断堆栈是否为空
• size(); 返回栈的大小

7 queue容器 (先进先出) 1 基本概念

概率: queue是一种先进先出的数据结果, 它有两个出口

只能一端进数据, 另一端出数据

队列容器允许从一端新增元素(队尾(最后一个元素)back), 从另一端移除元素(对头(第一个元素)frout)

队列中只有对头和队尾才可以被外界使用, 因此队列不允许遍历行为

队列中进数据称为 —入队(push)

队列中出数据称为 — 出队 (pop)

2 常用接口

构造函数/赋值/大小操作: 类似于stack

数据存储多了:

• back() 返回最后一个元素
• front() 返回第一个元素
• push(elem) 队尾添加一个元素
• pop() 对头删除一个元素

大小操作:

• empty()
• size()

8 list 容器(链表)

STL中的链表是一个双向循环链表

双向: 每个节点的指针域有2个, 一个指向前一个节点, 另一个指向后一个节点

循环: 最后一个节点中的指针域内的其中一个指针指向第一个节点.第一个节点内的指针域中其中一个指针指向最后一个节点

由于链表的存储方式并不是连续的内存空间, 因此链表list中的迭代器只支持前移和后移属于双向迭代器

1 list基本概念

功能: 将数据进行链式存储(链式是有多个节点构成,),

节点(本身是一个地址): 是由数据域(数据)和指针域(*p指向下一个节点),最后一个节点的指针域指向NULL

链表优点:

• 可以对任意位置进行快速插入或删除元素, 在随意位置插入一个数据后,只需让前一个位置的节点中的指针域指向这个数据的节点. 这个数据的节点内的指针域指向后一个数据的节点

• 删除: 只需让这个元素的上一个节点内的指针域指向这个元素的下一个元素的节点

• 采用动态存储分配, 不会造成内存浪费和溢出

• 链表执行插入和删除操作十分方便, 修改指针即可, 不需要移动大量元素

链表缺点:

• list容器的读取速度没有数组快
• 占用的空间比数组大
• 链表灵活, 但是空间(指针域) 和时间(遍历)额外耗费比较大,访问速度慢

list有一个重要的性质, 插入操作和删除多不会造成原有list迭代器的实效, 这在vector是不成立的

总结: STL中list和vector是两个最常被使用的容器, 各有优缺点

2 list构造函数

函数原型:

• list lst;
• list(beg,end); 构造函数将[beg,end)区间中的元素拷贝到本身
• list(n,elem); 构造函数将n个elem拷贝到本身
• list(const list &lst); 拷贝构造函数

3 list赋值和交换

函数原型:

• assign(beg, end); 将[beg, end)区间中的数据拷贝赋值给本身
• assign(n, elme); 将n个elme赋值给本身
• list & operator=(const list &list); 重载=号操作符
• swap(list); 将list与本身元素互换

4 list大小操作 5 list插入和删除

删除相比vector多了一个接口

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

6 list容器接口

• 尾插 —push_back
• 尾删 —pop_back
• 头插 —push_front
• 头删 —pop_front
• 插入 —insert
• 删除 —erase
• 移除 —remove(elem) 删除容器所有的elem
• 清空 —clear

7 list数据存储

不支持at(index), operator[i].

函数原型:

• front(); 返回第一个元素
• back(); 返回最后一个元素

原因: 不是个连续的空间存储数据,本质是个链表 迭代器不是随机迭代器,是个双向迭代器.支持++和–但是不支持+1,-1.

验证迭代器是否是连续的或者是双向的 只需要看是否支持+1或者-1

8 list反转和排序

函数原型:

• reverse(); 反转链表

• sort();链表排序

  不可以用sort(l.begin(), l.end()). 原因: 所有不支持随机访问迭代器的容器, 不可以用标志算法. 但是内部会提供成员函数的一些算法

  如果是sort降序

  bool so(Person &s1, Person &s2) {
  	return s1.age < s2.age;
  }
  l.sort(so)
  

  如果是一个类, 也需要在sort参数里放函数的回调或者是仿函数(对于自定义数据类型必须要指定规则)

9 set/ multiset 集合容器 1 基本概念

所有元素多会在插入时自动被排序

本质:

• set/mutiset属于关联式容器, 底层结构是二叉树实现.

met和multiset的区别

• set不允许容器中有重复的元素
• multiset允许容器中有重复的元素

2 set构造和赋值

构造数据原型:

• set st //默认构造
• set//拷贝构造

赋值:

• set& operator = (const set &st)

没有push只有insert, 不允许重新指定大小

3 set大小和交换

函数原型:

• size(); 返回容器中元素的数目;
• resize(); 不允许使用; 不允许使用pushback
• empty(); 判断容器是否为空
• swap(st)交换两个集合容器

4 set插入和删除

函数原型:

• insert(elem); 在容器中插入元素,插入同一个值相当于没插入

  原因:返回值是一个对组(pairib), 这个对组

  pairiterator, bool> name

  multiser的返回值是一个迭代器.

  pair::iterator,bool> name = s.insert(elem)

  pair::iterator, bool> name = s.insert(elem);
  if(name.second){
  	cout << "插入成功" < 

• clear(); 清除所有元素

• erase(pos) 删除 pos迭代器所指的元素, 返回下一个元素的迭代器

• erase(beg,end); 删除区间[beg, end)的所有元素, 返回下一个元素的迭代器

多了一个

• erase(elem);; 删除容器中所有值为elem的元素

5 set查找和统计

函数原型

• find(key)查找key是否存在, 返回该键的元素的迭代器, 若不存在, 返回set.end()

  if()
  

• count(key) 统计key的元素个数

总结:

• 查找 —find(key) (返回的是迭代器)
• 统计 —count (对于set, 结果为0或者是1)

6 set和multiset的区别

区别:

• set不可以插入重复数据, 而multiset可以
• set插入数据的同时会返回插入结果, 表示插入是否成功
• multiset不会检测数据, 因此可以插入重复数据

总结:

• 如果不允许插入重复数据可以利用set;
• 如果需要插入重复数据利用multiset

7 pair对组创建

功能描述:

• 成对出现的数据, 利用数组可以返回两个数据

两种创建方式

• pair p(value1, value2)
• pair p = mark-pair(value1, value2)

8 set容器排序

• 利用仿函数更改排序规则

注意点: vc2019 实现仿函数必须在参数列表后面加const. bool operator()(int a, int b)const {}

set存放自定义数据类型:

class pCompare {
public:
	bool operator()(const Person &p1, const Person &p2)const {
		return p1.age > p2.age;
	}
};

10 map/multimap容器 高性能高效率 1 map基本概念

• map所有元素多是pair
• pair中第一个元素为key(键值), 起到索引作用, 第二个元素为value(实质)
• 所有元素多会根据元素的键值自动排序

本质:

• map/multimap属于关联式容器, 底层结构使用二叉树实现.

优点:

• 可以根据key值快速找到value值

map和multimap区别:

• map不允许容器中有重复key值元素
• multimap运行容器中有重复key值元素

2 map构造和赋值

函数原型:

• map mp //默认构造
• map//拷贝构造

赋值:

• map& operator = (const map &mp)//重载等号操作符

3 map大小和交换

函数原型:

• size(): //返回容器中元素的数目
• empty()://判断容器是否为空
• swap(): //交换连个几何容器

4 map插入和删除

函数原型:

• insert(elem) 在容器中插入元素
• clear() 清楚所有元素
• erase(pos) 删除pos迭代器所指的元素, 返回下一个元素的迭代器
• erase(beg, end); 删除区间[beg,end}的所有元素, 返回下一个元素的迭代器
• erase(key); 删除容器中为key的元素

插入:

sets;
不推荐最后两种
//第一种
s.insert(pair(key, value1));
//第二种:
s.insert(make_pair(key, value));
//第三种
s.insert(map::value_type(key, value));
//第四种
s[key] = value//可以利用这种通过下标访问元素

5 map查找和统计

函数原型:

• find(key) 查找key是否存在, 若存在, 返回该键的元素迭代器; 若不存在,返回set.end();
• count(key); 统计key的元素个数, 返回值是整数

总结:

• 查找 — find(返回的迭代器)
• 统计 —count(对于map, 结果是0或者1)

6 map容器排序

• 利用仿函数, 可以改变排序规则

10.10 各个容器的区别:

1. vector:

   它维护一段连续的内存空间，具有固定的起始地址，因而能非常方便地进行随机存取，即 [] 操作符，但因为它的内存区域是连续的，所以在它中间插入或删除某个元素，需要复制并移动现有的元素。此外，当被插入的内存空间不够时，需要重新申请一块足够大的内存并进行内存拷贝。值得注意的是，vector每次扩容为原来的两倍，对小对象来说执行效率高，但如果遇到大对象，执行效率就低了。

2. list:

11 函数对象 1 概念:

• 重载函数调用操作的符, 对象常称为函数对象
• 函数对象使用重载的()时, 行为类似函数调用, 也叫仿函数

本质:

函数对象(仿函数)是一个类, 不是一个函数

2 函数对象使用

特点:

• 函数对象在使用时, 可以像普通函数那样调用, 可以有参数, 可以有返回值

• 函数对象超出普通函数的概念, 函数对象可以有自己的状态

  对象内部有成员属性, 在重载()内部可以操控这个成员属性

• 函数对象可以作为参数传递

3 谓词(pred) : 仿函数的返回参数是一个布尔值

概念:

• 返回bool类型的仿函数称为谓词
• 如果operator()接收一个参数, 那么叫做一元谓词
• 如果operator()接收两个参数, 那么叫做二元谓词

class Person {
public:
	bool operator()(int num) {//一元谓词
		return num > 5;
	}
};

4 内建函数对象 1 概念:

STL内建了一些函数对象

分类:

• 算数仿函数
• 关系仿函数
• 逻辑仿函数

用法:

• 这些仿函数所产生的对象, 用法和一般函数完全相同
• 使用内建函数对象, 需要引入头文件#include

2 算数仿函数

功能描述:

• 实现四则运算
• 其中negate是一元运算, 其他多是二元运算

仿函数原型:

• template T plus //加法仿函数

  plus p; cout<< p(10,20)<< endl

• template T minus//减法仿函数 [ˈmaɪnəs]

• template T multiplies //乘法仿函数[ˈmʌltɪplaɪz]

• template divides 除法仿函数 [dɪˈvaɪdz]

• template modolus取模仿函数

• template T negate 取反仿函数 [nɪˈɡeɪt]

3 关系运算符

仿函数原型:

• template bool equal_to 等于
• template bool not_equal_to 不等于
• template bool greater 大于
• template bool greater_equal 大于等于
• template bool less 小于
• template bool less_equal 小于等于

4 逻辑仿函数

函数原型:

• templatebool logical_and 逻辑与 [ˈlɒdʒɪkl]
• template bool logical_or 逻辑或
• template bool logical_not逻辑非

transform:搬运算法

11 STL-常用算法 1 便利算法

概念:

• 算法主要由头文件 ``组成
• 是所有STL头文件中最大的一个, 范围涉及到比较, 交换, 查找,遍历操作, 复制, 修改等.
• 体积很小, 只包括几个在序列上面进行简单数学运算的模板函数
• 定义了一些模板类, 用以声明函数对象

foreach遍历利用仿函数或者函数

• foreach(begin(), end(), op());// 函数对象要调用仿函数

• foreach(begin(), end(), op);//普通函数直接使用函数名

transform遍历

功能描述:

• 搬运容器到另一个容器中

函数原型:

• transform(iterator beg1, iterator end1, iterator beg2, _func);

注意点: 搬运目标容器前必须要开辟空间

2 查找算法

算法简介:

• find //查找元素
• find_if //按条件查找元素
• adjacent_find //查找相邻重复元素
• binary_search //二分查找法 ,
• count //统计元素个数
• count_if 按条件统计元素个数

2.1 find

功能描述:

• 查找指定元素, 找到返回指定元素的迭代器, 找不到返回结束迭代器end()

函数原型:

find(iterator beg, iterator end, value)

总结: 利用find可以在容器中找指定的元素, 返回值是迭代器

2.2 find_if条件查找

函数原型:

• find_if(iterator beg, iterator end, Pred)

  按值查找元素, 找到返回指定位置迭代器, 找不到返回结束迭代器位置

  Pred 函数或者谓词(返回bool类型的仿函数

2.3 adjacent_find 查找相邻重复元素

函数原型:

• adjacent_find(iterator beg, iterator end);

  查找相邻重复元素, 返回相邻元素的第一个位置的迭代器

2.4 binary_search

函数原型:

• bool binary_serach(it beg, it end, value)

  查找指定的元素, 查到返回true, 否则false

  注意在无序列表中不可用

2.5 count统计元素个数

函数原型

• count(iterator beg, iterator end, value)

  统计元素的个数

2.6 按条件统计元素个数

函数原型:

• count_if(iterator beg, iterator end, _Pred)

  按条件统计元素次数

3 常用的排序算法

算法简介:

• sort 对容器内的元素进行排序
• random_shuffle //洗牌 指定范围的元素随机调整排序 [ˈʃʌfl]
• merge 容器元素合并, 并存储到另一个容器
• reverse 反转指定范围的元素

3.1 sort

原型:

• sort(begin, end, _Pred) 第三个参数可以不填, 默认从下标0开始
• 按值查找元素, 找到返回指定位置迭代器, 找不到放回end()迭代器

3.2 random_shuffle

函数原型:

• 洗牌 指定范围内的元素随机调整位置

函数原型:

• random_shuffle()

  加随机种子, 可以每次加载多能随机

总结: 比较使用, 加随机种子

3.3 merge 合并容器中的元素, 并存储到另一容器中

函数原型:

• merge(beg1, end1, beg2, end2, iterator dest);

  容器元素合并, 并存储到另一个容器中

  注意: 两个容器必须是有序的,而且是一致的顺序(顺序or逆序) 合并后依然是有序的

  dest 目标容器开始迭代器

  合并的容器必须开辟空间

3.4 reverse

函数原型:

• reverse(beg,end)

  反转指定范围的元素

4 常用拷贝和替换算法

算法简介:

• copy 容器内指定范围的元素拷贝到另一个容器中
• replace 将容器内指定范围的旧元素修改为新元素
• replace_if 容器内指定范围满足条件的元素替换为新元素
• swap 互换两个容器的元素

4.1 copy

函数原型

• copy(beg, end, dest)

  按照查找元素, 找到返回指定位置迭代器, 找不到返回end()

  dest: 目标起始迭代器

4.2 replace

函数原型:

• replace(beg, end, oldvalue, newvalue)

  将区间内旧元素替换成新元素

4.3 replace_if

函数原型:

• replace_if(beg, end, _pred, newvalue)

  按条件替换元素, 满足条件的替换成指定元素

  _pred 谓词

  newvalue 替换的新元素

4.4 swap

函数原型:

• swap(container c1, container c2)

  互换两个容器的元素,c1/c2容器

  注意: 交换的容器同一种类型

5 常用算法生成算法

注意:

• 算术生成算法属于小型算法, 使用时包含的头文件为#include [nju(ː)ˈmɛrɪk]

算法简介:

• accumulate 计算区间类 容器元素累计总和
• fill 向容器添加元素

5.1 accumulate 在numeric里面

函数原型:

• accumulate(beg, end, value)

  参数3是个起始值

5.5 fill

函数原型:

• fill(beg, end, value)

  向容器中填充指定的元素

6 常用的集合算法

算法简介:

• set_intersection 求两个容器的交集
• set_union 求连个容器的并集
• set_difference 求两个容器的差集

6.1 set_intersection

函数原型:

原容器必须是一个有序序列

• set_intersection(beg1, end1, beg2, end2, dest)

  求两个结合的交集

  dest 目标容器开始迭代器

  min(v1.size(), v2.size()) 取出两个容器的最小长度

  返回值是一个交集的最后迭代器

注意:

• 两个集合必须是有序序列
• 返回目标的最后一个元素的迭代器地址
• 目标容器开辟空间需要从两个容器中的最小值

6.2 set_union

函数原型:

• set_union(beg1, end1, beg2, end2, dest)

  求两个容器的并集

  两个容器多必须是有序系列

  返回值是并集的最后一个迭代器

6.3 set_difference

函数原型:

• set_difference(beg1,end1,beg2,end2, dest)

  差集: 非交集的部分

注意点:

开辟的空间为max(v1.size(),v2.size);

replace_if

函数原型:

• replace_if(beg, end, _pred, newvalue)

  按条件替换元素, 满足条件的替换成指定元素

  _pred 谓词

  newvalue 替换的新元素

4.4 swap

函数原型:

• swap(container c1, container c2)

  互换两个容器的元素,c1/c2容器

  注意: 交换的容器同一种类型

5 常用算法生成算法

注意:

• 算术生成算法属于小型算法, 使用时包含的头文件为#include [nju(ː)ˈmɛrɪk]

算法简介:

• accumulate 计算区间类 容器元素累计总和
• fill 向容器添加元素

5.1 accumulate 在numeric里面

函数原型:

• accumulate(beg, end, value)

  参数3是个起始值

5.5 fill

函数原型:

• fill(beg, end, value)

  向容器中填充指定的元素

6 常用的集合算法

算法简介:

• set_intersection 求两个容器的交集
• set_union 求连个容器的并集
• set_difference 求两个容器的差集

6.1 set_intersection

函数原型:

原容器必须是一个有序序列

• set_intersection(beg1, end1, beg2, end2, dest)

  求两个结合的交集

  dest 目标容器开始迭代器

  min(v1.size(), v2.size()) 取出两个容器的最小长度

  返回值是一个交集的最后迭代器

注意:

• 两个集合必须是有序序列
• 返回目标的最后一个元素的迭代器地址
• 目标容器开辟空间需要从两个容器中的最小值

6.2 set_union

函数原型:

• set_union(beg1, end1, beg2, end2, dest)

  求两个容器的并集

  两个容器多必须是有序系列

  返回值是并集的最后一个迭代器

6.3 set_difference

函数原型:

• set_difference(beg1,end1,beg2,end2, dest)

  差集: 非交集的部分

注意点:

开辟的空间为max(v1.size(),v2.size);