迭代器
迭代器(iterator)是一种抽象的设计概念,现实程序语言中并没有直接对应于这个概念的实物。在<
迭代器案例
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
//普通指针也是一种迭代器
void f01()
{
int a[5] = { 0,1,2,3,6 }; //第一种遍历方式
int *p = a;
for (int i = 0; i < 5; i++)
{
//cout << a[i] << endl;
cout << *(p++) << endl;
}
}
void f02() //f02和f03是第二种遍历方式
{
vector<int>v;//声明了一个vector容器
//向容器内添加数据
v.push_back(0);
v.push_back(1);
v.push_back(2);
v.push_back(3);
//通过迭代器可以遍历容器
//每个容器都有自己专有的迭代器
vector<int>::iterator ibegin = v.begin(); //begin在第一个元素
vector<int>::iterator iend = v.end(); //end在最后一个元素的后面一位
while (ibegin != iend) //遍历
{
cout << *ibegin << endl;
ibegin++;
}
//缺点:麻烦,简单的见f03()
}
void f03()
{
vector<int>v;//声明了一个vector容器
//向容器内添加数据
v.push_back(0);
v.push_back(1);
v.push_back(2);
v.push_back(3);
for (vector<int>::iterator i = v.begin(); i != v.end(); i++)
{
cout << *i << endl;
}
}
void myPr(int n)
{
cout << n << endl;
}
void f04()//第四种遍历方式,用算法库,需要 #include<algorithm> 和 回调函数void myPr(int n)
{
vector<int>v;//声明了一个vector容器
//向容器内添加数据
v.push_back(0);
v.push_back(1);
v.push_back(2);
v.push_back(3);
for_each(v.begin(), v.end(), myPr);
//实现方法见定义
//for (; _UFirst != _ULast; ++_UFirst)
//{
// _Func(*_UFirst);
//}
}
//自定义数据类型
class pe
{
public:
pe(string na, int age)
{
this->Name = na;
this->Age = age;
}
string Name;
int Age;
};
void f05()
{
vector<pe>v;
pe p1("AAA", 10);
pe p2("BBB", 20);
pe p3("CCC", 30);
pe p4("DDD", 40);
v.push_back(p1);
v.push_back(p2);
v.push_back(p3);
v.push_back(p4);
for (vector<pe>::iterator i = v.begin(); i != v.end(); i++)
{
cout << (*i).Name << " " << (*i).Age << endl;
}
}
void f06()
{
vector<pe*>v;
pe p1("AAA", 10);
pe p2("BBB", 20);
pe p3("CCC", 30);
pe p4("DDD", 40);
v.push_back(&p1);
v.push_back(&p2);
v.push_back(&p3);
v.push_back(&p4);
for (vector<pe*>::iterator i = v.begin(); i != v.end(); i++)
{
cout << (**i).Name << " " << (**i).Age << endl;
}
}
//容器可以嵌套容器
void f07()
{
vector<vector<int>>v;//容器嵌套容器,类似于二维数组
vector<int>v1;
vector<int>v2;
vector<int>v3;
vector<int>v4;
for (int i = 0; i < 10; i += 2)
{
v1.push_back(i + 5);
v2.push_back(i + 15);
v3.push_back(i + 105);
v4.push_back(i + 315);
}
v.push_back(v1);
v.push_back(v2);
v.push_back(v3);
v.push_back(v4);
for (vector<vector<int>>::iterator it = v.begin(); it != v.end(); it++)
{
for (vector<int>::iterator vit = (*it).begin(); vit != (*it).end(); vit++)
{
cout << *vit << " ";
}
cout << endl;
}
}
int main()
{
f07();
return 0;
}
案例中包括:
- 简单的遍历算法
- 容器迭代器举例
- 默认数据类型迭代器
- 自定义数据类型迭代器
- Cpp Algorithm 库遍历算法
- 容器嵌套迭代器的使用
algorithm常用算法
这部分教程里没有,是自己加的。
c++之中的algorithm库包含了所有vector、list、set、map数据结构能想到的一些函数,例如查找,替换,排序,计数等常用的功能的。
max(),min(),abs()
max(x,y)
和min(x,y)
参数必须是两个,如果想比较x,y,z的最大值,可写为max(x,max(y,z))
。
abs(x)
返回x的绝对值。x必须为整数,浮点型的绝对值要用math头文件下的fabs。
swap()
swap(x,y)
交换x,y的数值
reverse()
reverse(it,it2)
可以将数组指针在[it,it2)之间的元素或容器的迭代器在[it,it2)范围内的元素进行反转
#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
int a[10]={10,11,12,13,14,15};
reverse(a,a+4);
for(int i=0;i<6;i++){
printf("%d ",a[i]);
}
return 0;
}
输出:13 12 11 10 14 15
#include<stdio.h>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
string str="abcdefghi";
reverse(str.begin()+2,str.begin()+6);
for(int i=0;i<str.length();i++){
printf("%c",str[i]);
}
return 0;
}
输出:abfedcghi
next_permutation()
next_permutation() 给出一个序列在全排列中的下一个序列。
#include<stdio.h>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
int a[10]={1,2,3};
do{
printf("%d %d %d\n",a[0],a[1],a[2]);
}while(next_permutation(a,a+3)); //循环停止的条件是什么
return 0;
}
输出:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
fill()
fill() 可以把数组或容器中的某一段区间赋为某个相同的值。和memset不同,这里的赋值可以使数组类型对应范围中的任意值。
#include<stdio.h>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
int a[10]={1,2,3,4,5};
fill(a,a+5,233);
for(int i=0;i<5;i++){
printf("%d ",a[i]);
}
return 0;
}
输出:233 233 233 233 233 每一个都是233了
sort()
Sort函数有三个参数:(第三个参数可不写)
(1)第一个是要排序的数组的起始地址。
(2)第二个是结束的地址(最后一位要排序的地址)
(3)第三个参数是排序的方法,可以是从大到小也可是从小到大,还可以不写第三个参数,此时默认的排序方法是从小到大排序。
默认为递增排序,若要递减排序,需要增加比较函数
bool cmp(int a,int b){
return a>b;
}
sort(a,a+n,cmp);
struct node{
int x,y;
}a[10];
bool cmp(node a,node b){
return a.x>b.x;
}
//
bool cmp(int x,int y){
if(a.x!=b.x) return a.x>b.x;
else return a.y<b.y;
}
对于递增和递减,标准库里已经有现成的了,就在functional里,include进来就行了。functional提供了一堆基于模板的比较函数对象。它们是(看名字就知道意思了):equal_to、not_equal_to、greater、greater_equal、less、less_equal。普通的问题,greater和less就足够了,直接拿过来用:
升序:sort(begin,end,less<data-type>());
降序:sort(begin,end,greater<data-type>()).
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
int a[20]={2,4,1,23,5,76,0,43,24,65},i;
for(i=0;i<20;i++)
cout<<a[i]<<" ";
cout<<endl;
sort(a,a+20,greater<int>());
for(i=0;i<20;i++)
cout<<a[i]<<" ";
cout<<endl;
sort(a,a+20,less<int>());
for(i=0;i<20;i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
输出:
2 4 1 23 5 76 0 43 24 65 0 0 0 0 0 0 0 0 0 0
76 65 43 24 23 5 4 2 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 2 4 5 23 24 43 65 76
容器排序,在STL标砖容器中,只有vector/string/deque可以sort
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
bool cmp(int a,int b){
return a>b;
}
int main()
{
vector<int> vi;
vi.push_back(3);
vi.push_back(1);
vi.push_back(2);
sort(vi.begin(),vi.end(),cmp);
for(int i=0;i<3;i++){
printf("%d ",vi[i]);
}
return 0;
}
输出:3 2 1
lower_bound()和upper_bound()
ower_bound 和 upper_bound()需要用在一个有序数组或容器中。
lower_bound(first,last,val) 用来寻找数组或容器的[first,last)范围内第一个值大于等于val元素的位置,如果是数组,返回该位置的指针;如果是容器,返回该位置的迭代器。
upper_bound(first,last,val) 用来寻找在数组或容器的[first,last)范围内第一个值大于val元素的位置,如果是数组,返回该位置的指针;如果是容器,返回该位置的迭代器。
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int a[10]={1,2,2,3,3,3,5,5,5,5};
printf("%d,%d\n",lower_bound(a,a+10,3)-a,upper_bound(a,a+10,3)-a);
return 0;
}
**注意其中的 -a**
输出:3,6
String容器
C风格字符串(以空字符结尾的字符数组)太过复杂难于掌握,不适合大程序的开发,所以C++标准库定义了一种string类,定义在头文件<string>
。
String和c风格字符串对比:
- Char是一个指针,String是一个类
string封装了char,管理这个字符串,是一个char*型的容器。 - String封装了很多实用的成员方法
查找find,拷贝copy,删除delete 替换replace,插入insert - 不用考虑内存释放和越界
string管理char*所分配的内存。每一次string的复制,取值都由string类负责维护,不用担心复制越界和取值越界等。
String常用操作代码接口
string 构造函数
string();//创建一个空的字符串 例如: string str;
string(const string& str);//使用一个string对象初始化另一个string对象
string(const char* s);//使用字符串s初始化
string(int n, char c);//使用n个字符c初始化
string大小函数
size() //返回字符串中有效字符长度
length() //返回字符串中有效字符长度
capacity() //返回空间的总长度,字符长度size超过capacity会自动扩容
empty() //检测字符串是否为空串,是返回true,不是返回false
clear() //清空有效字符串,空间不释放,内容没改变,只是size变为0
reserve(size_t n=0) //为字符串预留空间,就是提前开辟一段你想要大小的空间,如果不用reserve,编译器会自己开辟一段空间。
resize(size_t n,char c)
//将有效字符串个数改成n个,n小于size,缩小size到n。n大于size,增大size到n,多出来的空间用字符c填充,不给c,用'\0'填充
- length和size底层实现是一样的,引入size的原因是为了与其它容器保持一致,一般情况下用size
- clear()函数只是将对象的size置0,不改变底层空间大小
- resize(size_t n,char c),当n小于对象size时,直接改变对象的size到n。当n大于对象size时,直接增大对象size到n,多出来的空间用给的字符c填充,没给字符c默认用\0填充。
string基本赋值操作
string& operator=(const char* s);//char*类型字符串 赋值给当前的字符串
string& operator=(const string &s);//把字符串s赋给当前的字符串
string& operator=(char c);//字符赋值给当前的字符串
string& assign(const char *s);//把字符串s赋给当前的字符串
string& assign(const char *s, int n);//把字符串s的前n个字符赋给当前的字符串
string& assign(const string &s);//把字符串s赋给当前字符串
string& assign(int n, char c);//用n个字符c赋给当前字符串
string& assign(const string &s, int start, int n);//将s从start开始n个字符赋值给字符串
string存取字符操作
char& operator[](int n);//通过[]方式取字符
char& at(int n);//通过at方法获取字符
string拼接操作
string& operator+=(const string& str);//重载+=操作符
string& operator+=(const char* str);//重载+=操作符
string& operator+=(const char c);//重载+=操作符
string& append(const char *s);//把字符串s连接到当前字符串结尾
string& append(const char *s, int n);//把字符串s的前n个字符连接到当前字符串结尾
string& append(const string &s);//同operator+=()
string& append(const string &s, int pos, int n);//把字符串s中从pos开始的n个字符连接到当前字符串结尾
string& append(int n, char c);//在当前字符串结尾添加n个字符c
string查找和替换
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* s, 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
string& replace(int pos, int n, const char* s); //替换从pos开始的n个字符为字符串s
- rfind表示从右开始找;
- 注意函数有两个参数,一个是目标字符,一个是开始查找的位置。
- 需要一个int类型变量去接这个返回值,不然可能会出现乱码。
- 替换中,是替换pos开始的n个字符为字符串str。仔细理解这句话。
string比较操作
compare函数在 >时返回 1,<时返回 -1,==时返回 0。
比较区分大小写,比较时参考字典顺序,排越前面的越小。
大写的A比小写的a小。
int compare(const string &s) const;//与字符串s比较
int compare(const char *s) const;//与字符串s比较
string子串(截取字符串)
这是一个常用的功能
string substr(int pos = 0, int n = npos) const;//返回由pos开始的n个字符组成的字符串
案例:截取网址里的字段
比如:www.abc.a.asdfgghhj.com.cn
string s1 = "www.abc.a.asdfgghhj.com.cn",t;
vector<string>v;
int start = 0;
int pos = 0;
while ((pos = s1.find('.', start))!=-1)
{
v.push_back(s1.substr(start, pos - start));
start=(pos+1);
}
v.push_back(s1.substr(start, pos - start));
for (vector<string>::iterator i = v.begin(); i != v.end(); i++)
{
cout << *i << endl;
}
string插入和删除操作
string& insert(int pos, const char* s); //插入字符串
string& insert(int pos, const string& str); //插入字符串
string& insert(int pos, int n, char c);//在指定位置插入n个字符c
string& erase(int pos, int n = npos);//删除从Pos开始的n个字符
string和c-style字符串转换
//string 转 char*
string str = "itcast";
const char* cstr = str.c_str(); //或者强转
//char* 转 string
char* s = "itcast";
string str(s);
const char*
可以隐式类型转换为string
,反之不可以
String相关注意事项
s.at()
和s[]
的区别
如果[]访问越界,会直接出错
at越界 会抛出一个异常out_of_range
比如
//头:#include<stdexcept>
try
{
s.at(100);
}
catch (out_of_range &e)
{
cout << e.what() << endl;
}
代码中out_of_range
也可以更换为exception
下标运算符返回字符的引用在重新分配内存时的错误
为了修改string字符串的内容,下标操作符[]和at都会返回字符的引用。但当字符串的内存被重新分配之后,可能发生错误.
比如:
string s = "abcdefg";
char& a = s[2];
char& b = s[3];
a = '1';
b = '2';
cout << s << endl;
cout << (int*)s.c_str() << endl;
s = "pppppppppppppppppppppppp";
//a = '1';
//b = '2';
cout << s << endl;
cout << (int*)s.c_str() << endl;
案例:字母大小写转换
验证码不区分大小写时,就是全部转换为大写或者小写,然后验证。
string s1 = "abCDEfg";
for (int i = 0; i < s1.size(); i++)
{
//小写转大写
//s1[i] = toupper(s1[i]);
s1[i] = tolower(s1[i]);//大写转小写
}
cout << s1 << endl;
vector容器
vector基础功能
front()//首元素
back()//末尾元素
v.rend()//首元素的前面一位的指针
v.end()//末尾元素后面一位的指针
v.begin()//首元素的指针
v.rbegin()//末尾元素的指针
insert()//中间插入
push_back()//放入数据
pop_back()//弹出数据
vector数据结构
Vector所采用的数据结构非常简单,线性连续空间,它以两个迭代器_Myfirst和_Mylast分别指向配置得来的连续空间中目前已被使用的范围,并以迭代器_Myend指向整块连续内存空间的尾端。
为了降低空间配置时的速度成本,vector实际配置的大小可能比客户端需求大一些,以备将来可能的扩充,这边是容量的概念。换句话说,一个vector的容量永远大于或等于其大小,一旦容量等于大小,便是满载,下次再有新增元素,整个vector容器就得另觅居所。
注意:
所谓动态增加大小,并不是在原空间之后续接新空间(因为无法保证原空间之后尚有可配置的空间),而是一块更大的内存空间,然后将原数据拷贝新空间,并释放原空间。因此,对vector的任何操作,一旦引起空间的重新配置,指向原vector的所有迭代器就都失效了。这是程序员容易犯的一个错误,务必小心。
测试vector扩展内存
vector<int> v;
for (int i = 0; i < 10; i++) {
v.push_back(i);
cout << v.capacity() << endl; // v.capacity()容器的容量
}
vector常用操作代码接口
vector构造函数
vector<T> v; //采用模板实现类实现,默认构造函数
vector(v.begin(), v.end());//将v[begin(), end())区间中的元素拷贝给本身。
vector(n, elem);//构造函数将n个elem拷贝给本身。
vector(const vector &vec);//拷贝构造函数。
//例子 使用第二个构造函数 我们可以...
int arr[] = {2,3,4,1,9};
vector<int> v1(arr, arr + sizeof(arr) / sizeof(int));
vector常用赋值操作
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
vector& operator=(const vector &vec);//重载等号操作符
swap(vec);// 将vec与本身的元素互换。
vector大小操作
size();//返回容器中元素的个数
empty();//判断容器是否为空
resize(int num);//重新指定容器的长度为num,若容器变长,则以默认值填充新位置。如果容器变短,则末尾超出容器长度的元素被删除。
resize(int num, elem);//重新指定容器的长度为num,若容器变长,则以elem值填充新位置。如果容器变短,则末尾超出容器长>度的元素被删除。
capacity();//容器的容量
reserve(int len);//容器预留len个元素长度,预留位置不初始化,元素不可访问。
vector数据存取操作
at(int idx); //返回索引idx所指的数据,如果idx越界,抛出out_of_range异常。
operator[];//返回索引idx所指的数据,越界时,运行直接报错
front();//返回容器中第一个数据元素
back();//返回容器中最后一个数据元素
vector插入和删除操作
insert(const_iterator pos, int count,ele);//迭代器指向位置pos插入count个元素ele.
push_back(ele); //尾部插入元素ele
pop_back();//删除最后一个元素
erase(const_iterator start, const_iterator end);//删除迭代器从start到end之间的元素
erase(const_iterator pos);//删除迭代器指向的元素
clear();//删除容器中所有元素
案例:巧用swap收缩内存
vector<int> v;
for (int i = 0; i < 100000; i++) {
v.push_back(i);
}
cout << "capacity:" << v.capacity() << endl;
cout << "size:" << v.size() << endl;
//此时 通过resize改变容器大小
v.resize(10);
cout << "capacity:" << v.capacity() << endl;
cout << "size:" << v.size() << endl;
//容量没有改变
vector<int>(v).swap(v);
cout << "capacity:" << v.capacity() << endl;
cout << "size:" << v.size() << endl;
核心代码vector<int>(v).swap(v);
vector<int>(v)
是vector(const vector &vec)
交换的本质是指针的交换。
交换前,匿名对象(假设为x)x被拷贝构造与v相同。然后利用swap函数交换了x和v的指针。
案例:reserve预留空间,查看数据迁移次数
vector<int>v;
int num = 0;
int *p = NULL;
//v.reserve(100000); //预留空间
for (int i = 0; i < 100000; i++)
{
v.push_back(i);
if (p != &v[0])
{
p = &v[0];
num++;
}
}
cout << num << endl;
案例:逆序遍历
需要使用反向迭代器:reverse_iterator
vector<int>v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
for (vector<int>::reverse_iterator i = v.rbegin(); i != v.rend(); i++)
{
cout << *i << endl;
}
案例:如何判断迭代器是否是随机访问迭代器
下面的代码vector<int>::iterator i = v.begin();
可以通过就说明可以随机访问。
vector<int>v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
vector<int>::iterator i = v.begin();
i = i + 1;
deque容器
Vector容器是单向开口的连续内存空间,deque则是一种双向开口的连续线性空间。所谓的双向开口,意思是可以在头尾两端分别做元素的插入和删除操作,当然,vector容器也可以在头尾两端插入元素,但是在其头部操作效率奇差,无法被接受。
Deque容器和vector容器最大的差异,
一在于deque允许使用常数项时间对头端进行元素的插入和删除操作。
二在于deque没有容量的概念,因为它是动态的以分段连续空间组合而成,随时可以增加一段新的空间并链接起来,换句话说,像vector那样,”旧空间不足而重新配置一块更大空间,然后复制元素,再释放旧空间”这样的事情在deque身上是不会发生的。
也因此,deque没有必须要提供所谓的空间保留(reserve)功能.
虽然deque容器也提供了Random Access Iterator,但是它的迭代器并不是普通的指针,其复杂度和vector不是一个量级,这当然影响各个运算的层面。因此,除非有必要,我们应该尽可能的使用vector,而不是deque。对deque进行的排序操作,为了最高效率,可将deque先完整的复制到一个vector中,对vector容器进行排序,再复制回deque.
deque常用操作代码接口
deque构造函数
deque<T> deqT;//默认构造形式
deque(beg, end);//构造函数将[beg, end)区间中的元素拷贝给本身。
deque(n, elem);//构造函数将n个elem拷贝给本身。
deque(const deque &deq);//拷贝构造函数。
deque赋值操作
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
deque& operator=(const deque &deq); //重载等号操作符
swap(deq);// 将deq与本身的元素互换
deque大小操作
deque.size();//返回容器中元素的个数
deque.empty();//判断容器是否为空
deque.resize(num);//重新指定容器的长度为num,若容器变长,则以默认值填充新位置。如果容器变短,则末尾超出容器长度的元素被删除。
deque.resize(num, elem); //重新指定容器的长度为num,若容器变长,则以elem值填充新位置,如果容器变短,则末尾超出容器长度的元素被删除。
deque双端插入和删除操作
push_back(elem);//在容器尾部添加一个数据
push_front(elem);//在容器头部插入一个数据
pop_back();//删除容器最后一个数据
pop_front();//删除容器第一个数据
deque数据存取
at(idx);//返回索引idx所指的数据,如果idx越界,抛出out_of_range。
operator[];//返回索引idx所指的数据,如果idx越界,不抛出异常,直接出错。
front();//返回第一个数据。
back();//返回最后一个数据
deque插入操作
insert(pos,elem);//在pos位置插入一个elem元素的拷贝,返回新数据的位置。
insert(pos,n,elem);//在pos位置插入n个elem数据,无返回值。
insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据,无返回值。
deque删除操作
clear();//移除容器的所有数据
erase(beg,end);//删除[beg,end)区间的数据,返回下一个数据的位置。
erase(pos);//删除pos位置的数据,返回下一个数据的位置。
相关使用技巧
多种类型的迭代器(反转、只读)
反转迭代器前面已经提到
for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
{
//*it = 100; //报错,因为使用了只读迭代器。
cout << *it << endl;
}
stack容器
stack常用操作代码接口
stack构造函数
stack<T> stkT;//stack采用模板类实现, stack对象的默认构造形式:
stack(const stack &stk);//拷贝构造函数
stack赋值操作
stack& operator=(const stack &stk);//重载等号操作符
stack数据存取操作
push(elem);//向栈顶添加元素
pop();//从栈顶移除第一个元素
top();//返回栈顶元素
stack大小操作
empty();//判断堆栈是否为空
size();//返回堆栈的大小
queue容器
queue常用操作代码接口
queue构造函数
queue<T> queT;//queue采用模板类实现,queue对象的默认构造形式:
queue(const queue &que);//拷贝构造函数
queue存取、插入和删除操作
push(elem);//往队尾添加元素
pop();//从队头移除第一个元素
back();//返回最后一个元素
front();//返回第一个元素
queue赋值操作
queue& operator=(const queue &que);//重载等号操作符
queue大小操作
empty();//判断队列是否为空
size();//返回队列的大小
list容器
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。
相较于vector的连续线性空间,list就显得负责许多,它的好处是每次插入或者删除一个元素,就是配置或者释放一个元素的空间。因此,list对于空间的运用有绝对的精准,一点也不浪费。而且,对于任何位置的元素插入或元素的移除,list永远是常数时间。
List和vector是两个最常被使用的容器。
List容器是一个双向链表。
- 采用动态存储分配,不会造成内存浪费和溢出
- 链表执行插入和删除操作十分方便,修改指针即可,不需要移动大量元素
- 链表灵活,但是空间和时间额外耗费较大
List迭代器
List容器不能像vector一样以普通指针作为迭代器,因为其节点不能保证在同一块连续的内存空间上。List迭代器必须有能力指向list的节点,并有能力进行正确的递增、递减、取值、成员存取操作。所谓”list正确的递增,递减、取值、成员取用”是指,递增时指向下一个节点,递减时指向上一个节点,取值时取的是节点的数据值,成员取用时取的是节点的成员。
由于list是一个双向链表,迭代器必须能够具备前移、后移的能力,所以list容器提供的是Bidirectional Iterators.
List有一个重要的性质,插入操作和删除操作都不会造成原有list迭代器的失效。这在vector是不成立的,因为vector的插入操作可能造成记忆体重新配置,导致原有的迭代器全部失效,甚至List元素的删除,也只有被删除的那个元素的迭代器失效,其他迭代器不受任何影响。
list容器的数据结构
ist容器不仅是一个双向链表,而且还是一个循环的双向链表。
List常用功能代码接口
list构造函数
list<T> lstT;//list采用采用模板类实现,对象的默认构造形式:
list(beg,end);//构造函数将[beg, end)区间中的元素拷贝给本身。
list(n,elem);//构造函数将n个elem拷贝给本身。
list(const list &lst);//拷贝构造函数。
list数据元素插入和删除操作
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值匹配的元素。
list大小操作
size();//返回容器中元素的个数
empty();//判断容器是否为空
resize(num);//重新指定容器的长度为num,
若容器变长,则以默认值填充新位置。
如果容器变短,则末尾超出容器长度的元素被删除。
resize(num, elem);//重新指定容器的长度为num,
若容器变长,则以elem值填充新位置。
如果容器变短,则末尾超出容器长度的元素被删除。
list赋值操作
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
list& operator=(const list &lst);//重载等号操作符
swap(lst);//将lst与本身的元素互换。
list数据的存取
front();//返回第一个元素。
back();//返回最后一个元素。
list反转和排序
注意:所有系统提供的标准算法,使用的容器提供的迭代器必须支持随机访问。不支持算计访问的迭代器的容器,内部会对应提供相应的算法的接口。
reverse();//反转链表,比如lst包含1,3,5元素,运行此方法后,lst就包含5,3,1元素。
sort(); //list排序,默认小到大。大到小需要函数做参,如下:
默认小到大。大到小需要函数做参,如下:
bool cmp(int a,int b)
{
return a>b;
}
自定义数据类型排序,必须制定排序类型;如下
class pe
{
public:
pe(string na,int age):Nam(na),Ag(age){}
string Nam;
int Ag;
};
bool cmppe(pe&a, pe&b)
{
return a.Ag < b.Ag;
}
void f02()
{
list<pe>l;
pe p1("AA", 10);
pe p2("BB", 12);
pe p3("CC", 1310);
pe p4("DD", 1);
pe p5("EE", 120);
l.push_back(p1);
l.push_back(p2);
l.push_back(p3);
l.push_back(p4);
l.push_back(p5);
for (list<pe>::iterator it = l.begin(); it != l.end(); it++)
{
cout << (*it).Nam << " " << (*it).Ag << endl;
}
l.sort(cmppe);
for (list<pe>::iterator it = l.begin(); it != l.end(); it++)
{
cout << (*it).Nam << " " << (*it).Ag << endl;
}
}
set和multiset容器
#include <set>
set和multiset头文件一样
关联型容器,插入数据自动排序
Set的特性是。所有元素都会根据元素的键值自动被排序。Set的元素不像map那样可以同时拥有实值和键值,set的元素即是键值又是实值。Set不允许两个元素有相同的键值。
我们可以通过set的迭代器改变set元素的值吗?不行,因为set元素值就是其键值,关系到set元素的排序规则。如果任意改变set元素值,会严重破坏set组织。换句话说,set的iterator是一种const_iterator.
set拥有和list某些相同的性质,当对容器中的元素进行插入操作或者删除操作的时候,操作之前所有的迭代器,在操作完成之后依然有效,被删除的那个元素的迭代器必然是一个例外。
multiset特性及用法和set完全相同,唯一的差别在于它允许键值重复。set和multiset的底层实现是红黑树,红黑树为平衡二叉树的一种。
set容器不可以通过迭代器修改里面的值,因为默认有排序规则
set常用功能代码接口
set构造函数
set<T> st;//set默认构造函数:
mulitset<T> mst; //multiset默认构造函数:
set(const set &st);//拷贝构造函数
set赋值操作
set& operator=(const set &st);//重载等号操作符
swap(st);//交换两个集合容器
set大小操作
size();//返回容器中元素的数目
empty();//判断容器是否为空
set插入和删除操作
insert(elem);//在容器中插入元素。
clear();//清除所有元素
erase(pos);//删除pos迭代器所指的元素,返回下一个元素的迭代器。
erase(beg, end);//删除区间[beg,end)的所有元素 ,返回下一个元素的迭代器。
erase(elem);//删除容器中值为elem的元素。
由于,set不可以插入相同的值。我们可以用下面的代码查看set是否成功插入
set<int>se;
pair<set<int>::iterator,bool> pa=se.insert(10);
cout << pa.second << endl;
pa = se.insert(10);
cout << pa.second << endl;
set查找操作
find(key);//查找键key是否存在,若存在,返回该键的元素的迭代器;若不存在,返回set.end();
count(key);//查找键key的元素个数,对于set来说,结果只有0和1;
lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。返回队组。
关于equal_range
的用法,详见下面的例子:
set<int>se;
se.insert(10);
se.insert(20);
se.insert(50);
se.insert(30);
se.insert(40);
pair<set<int>::iterator,set<int>::iterator> it = se.equal_range(50); //返回对组
if (it.first!=se.end())
{
cout << "找到lower" << *(it.first) << endl;
}
else
{
cout << "没有找到" << endl;
}
if (it.second != se.end())
{
cout << "找到upper" << *(it.second) << endl;
}
else
{
cout << "没有找到" << endl;
利用仿函数,让set从大到小排序
class mycmp
{
public:
bool operator()(int a, int b)
{
return a > b;
}
};
void f05()
{
//利用仿函数,让set从大到小排序
set<int, mycmp>s;
s.insert(10);
s.insert(20);
s.insert(50);
s.insert(30);
s.insert(40);
for (set<int,mycmp>::iterator it = s.begin(); it != s.end(); it++)
{
cout << *it << endl;
}
}
对组(pair)
对组(pair)将一对值组合成一个值,这一对值可以具有不同的数据类型,两个值可以分别用pair的两个公有属性first和second访问。
类模板:template <class T1, class T2> struct pair.
如何创建对组?
//第一种方法创建一个对组
pair<string, int> pair1(string("name"), 20);
cout << pair1.first << endl; //访问pair第一个值
cout << pair1.second << endl;//访问pair第二个值
//第二种
pair<string, int> pair2 = make_pair("name", 30);
cout << pair2.first << endl;
cout << pair2.second << endl;
//pair=赋值
pair<string, int> pair3 = pair2;
cout << pair3.first << endl;
cout << pair3.second << endl;
map容器
Map的特性是,所有元素都会根据元素的键值自动排序。Map所有的元素都是pair,同时拥有实值和键值,pair的第一元素被视为键值,第二元素被视为实值,map不允许两个元素有相同的键值。
我们可以通过map的迭代器改变map的键值吗?答案是不行,因为map的键值关系到map元素的排列规则,任意改变map键值将会严重破坏map组织。如果想要修改元素的实值,那么是可以的。
Map和list拥有相同的某些性质,当对它的容器元素进行新增操作或者删除操作时,操作之前的所有迭代器,在操作完成之后依然有效,当然被删除的那个元素的迭代器必然是个例外。
Multimap和map的操作类似,唯一区别multimap键值可重复。
Map和multimap都是以红黑树为底层实现机制。
map常用功能代码接口
map构造函数
map<T1, T2> mapTT;//map默认构造函数:
map(const map &mp);//拷贝构造函数
map赋值操作
map& operator=(const map &mp);//重载等号操作符
swap(mp);//交换两个集合容器
map大小操作
size();//返回容器中元素的数目
empty();//判断容器是否为空
map插入数据元素操作
map.insert(...); //往容器插入元素,返回pair<iterator,bool>
map<int, string> mapStu;
// 第一种 通过pair的方式插入对象
mapStu.insert(pair<int, string>(3, "小张"));
// 第二种 通过pair的方式插入对象
mapStu.inset(make_pair(-1, "校长"));
// 第三种 通过value_type的方式插入对象
mapStu.insert(map<int, string>::value_type(1, "小李"));
// 第四种 通过数组的方式插入值
mapStu[3] = "小刘";
mapStu[5] = "小王";
不建议使用[]访问,因为如果没有这个键值,就会自动创建
map删除操作
clear();//删除所有元素
erase(pos);//删除pos迭代器所指的元素,返回下一个元素的迭代器。
erase(beg,end);//删除区间[beg,end)的所有元素 ,返回下一个元素的迭代器。
erase(keyElem);//删除容器中key为keyElem的对组。
map查找操作
find(key);//查找键key是否存在,若存在,返回该键的元素的迭代器;/若不存在,返回map.end();
count(keyElem);//返回容器中key为keyElem的对组个数。对map来说,要么是0,要么是1。对multimap来说,值可能大于1。
lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。
容器的使用时机
vector | deque | list | set | multiset | map | multimap | |
---|---|---|---|---|---|---|---|
典型内存结构 | 单端数组 | 双端数组 | 双向链表 | 二叉树 | 二叉树 | 二叉树 | 二叉树 |
可随机存取 | 是 | 是 | 否 | 否 | 否 | 对key而言:不是 | 否 |
元素搜寻速度 | 慢 | 慢 | 非常慢 | 快 | 快 | 对key而言:快 | 对key而言:快 |
元素安插移除 | 尾端 | 头尾两端 | 任何位置 | - | - | - | - |
-
vector的使用场景:比如软件历史操作记录的存储,我们经常要查看历史记录,比如上一次的记录,上上次的记录,但却不会去删除记录,因为记录是事实的描述。
-
deque的使用场景:比如排队购票系统,对排队者的存储可以采用deque,支持头端的快速移除,尾端的快速添加。如果采用vector,则头端移除时,会移动大量的数据,速度慢。
-
vector与deque的比较:
- 一:vector.at()比deque.at()效率高,比如vector.at(0)是固定的,deque的开始位置 却是不固定的。
- 二:如果有大量释放操作的话,vector花的时间更少,这跟二者的内部实现有关。
- 三:deque支持头部的快速插入与快速移除,这是deque的优点。
-
list的使用场景:比如公交车乘客的存储,随时可能有乘客下车,支持频繁的不确实位置元素的移除插入。
-
set的使用场景:比如对手机游戏的个人得分记录的存储,存储要求从高分到低分的顺序排列。
-
map的使用场景:比如按ID号存储十万个用户,想要快速要通过ID查找对应的用户。二叉树的查找效率,这时就体现出来了。如果是vector容器,最坏的情况下可能要遍历完整个容器才能找到该用户。
常用算法
函数对象(仿函数)
重载函数调用操作符的类,其对象常称为函数对象(function object),即它们是行为类似函数的对象,也叫仿函数(functor),其实就是重载“()”操作符,使得类对象可以像函数那样调用。
注意:
1.函数对象(仿函数)是一个类,不是一个函数。
2.函数对象(仿函数)重载了”() ”操作符使得它可以像函数一样调用。
分类:假定某个类有一个重载的operator(),而且重载的operator()要求获取一个参数,我们就将这个类称为“一元仿函数”(unary functor);相反,如果重载的operator()要求获取两个参数,就将这个类称为“二元仿函数”(binary functor)。
函数对象的作用主要是什么?STL提供的算法往往都有两个版本,其中一个版本表现出最常用的某种运算,另一版本则允许用户通过template参数的形式来指定所要采取的策略。
- 函数对象很像函数调用方式,因此也称为 仿函数
class myp
{
public:
void operator()(int num)
{
cout << num << endl;
}
};
void f01()
myp m1;
m1(1212);
}
- 函数对象,超出普通函数的概念,内部可以拥有自己的状态。比如,统计打印次数
class myp2
{
public:
int cot=0;
void operator()(int num)
{
cout << num << endl;
cot++;
}
};
void f02()
{
myp2 m2;
m2(1212);
m2(1213);
m2(1214);
m2(1210);
m2(1233);
cout << m2.cot << endl;
}
- 函数对象可以作为函数的参数传递
void work01(myp mp, int n)
{
mp(n);
}
void f03()
{
work01(myp(), 100);
}
int main()
{
f03();
return 0;
}
总结:
1、函数对象通常不定义构造函数和析构函数,所以在构造和析构时不会发生任何问题,避免了函数调用的运行时问题。
2、函数对象超出普通函数的概念,函数对象可以有自己的状态
3、函数对象可内联编译,性能好。用函数指针几乎不可能
4、模版函数对象使函数对象具有通用性,这也是它的优势之一
谓词
谓词是指普通函数或重载的operator()返回值是bool类型的函数对象(仿函数)。如果operator接受一个参数,那么叫做一元谓词,如果接受两个参数,那么叫做二元谓词,谓词可作为一个判断式。
class GreaterThenFive
{
public:
bool operator()(int num)
{
return num > 5;
}
};
//一元谓词
void test01()
{
vector<int> v;
for (int i = 0; i < 10;i ++)
{
v.push_back(i);
}
vector<int>::iterator it = find_if(v.begin(), v.end(), GreaterThenFive());
if (it == v.end())
{
cout << "没有找到" << endl;
}
else
{
cout << "找到了: " << *it << endl;
}
}
//二元谓词
class MyCompare
{
public:
bool operator()(int num1, int num2)
{
return num1 > num2;
}
};
void test02()
{
vector<int> v;
v.push_back(10);
v.push_back(40);
v.push_back(20);
v.push_back(90);
v.push_back(60);
//默认从小到大
sort(v.begin(), v.end());
for (vector<int>::iterator it = v.begin(); it != v.end();it++)
{
cout << *it << " ";
}
cout << endl;
cout << "----------------------------" << endl;
//使用函数对象改变算法策略,排序从大到小
sort(v.begin(), v.end(),MyCompare());
for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
匿名函数(lambda表达式){}
普通函数与lambda函数对比
匿名函数是许多编程语言都支持的概念,有函数体,没有函数名。
函数对象能维护状态,但语法开销大,而函数指针语法开销小,却没法保存范围内的状态。
仅展示基本使用方法
[]是该表达式的声明
()是函数的参数
{}是函数的实现
内建函数对象
需要引入头文件 #include<functional>
。
STL内建了一些函数对象。分为:
算数类函数对象,关系运算类函数对象,逻辑运算类仿函数。这些仿函数所产生的对象,用法和一般函数完全相同,当然我们还可以产生无名的临时对象来履行函数功能。使用内建函数对象,需要引入头文件 #include
- 6个算数类函数对象,除了negate是一元运算,其他都是二元运算。
template<class T> T plus<T>//加法仿函数
template<class T> T minus<T>//减法仿函数
template<class T> T multiplies<T>//乘法仿函数
template<class T> T divides<T>//除法仿函数
template<class T> T modulus<T>//取模仿函数
template<class T> T negate<T>//取反仿函数
- 6个关系运算类函数对象,每一种都是二元运算。
template<class T> bool equal_to<T>//等于
template<class T> bool not_equal_to<T>//不等于
template<class T> bool greater<T>//大于 //可以用于部分容器排序
template<class T> bool greater_equal<T>//大于等于
template<class T> bool less<T>//小于
template<class T> bool less_equal<T>//小于等于
- 逻辑运算类运算函数,not为一元运算,其余为二元运算。
template<class T> bool logical_and<T>//逻辑与
template<class T> bool logical_or<T>//逻辑或
template<class T> bool logical_not<T>//逻辑非
标签:容器,string,STL,元素,back,笔记,学习,int,vector
From: https://www.cnblogs.com/BryceAi/p/17677933.html