首页 > 其他分享 >STL学习笔记

STL学习笔记

时间:2023-09-05 21:22:42浏览次数:45  
标签:容器 string STL 元素 back 笔记 学习 int vector

迭代器

迭代器(iterator)是一种抽象的设计概念,现实程序语言中并没有直接对应于这个概念的实物。在<>一书中提供了23中设计模式的完整描述,其中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

相关文章

  • C++语言学习09
    STL标准模版库STL是StandardTemplateLibrary的缩写,中文名标准模版库,由惠普实验室提供(使用C++模板语言封装的常用的数据结构与算法)STL中有六大组件:算法:以函数模板形式实现的常用算法,例如:swap\max\min\find\sort容器:以类模板的形式实现的常用的数据结构,例如:vector\list\arra......
  • vi/vim笔记
    一些vi配置:#光标所在行显示下划线:setcursorline#对应关闭为setnocursorline#高亮显示光标所在列setcursorcolumn#对应关闭为setnocursorcolumn#tab键字符替换为4个空格setts=4setsw=4setexpandtabsetautoindent#复制粘贴模式setpasteif&diffco......
  • Markdown学习
    Markdown学习标题三级标题四级标题HelloWorld!HelloWorld!HelloWorld!HelloWorld! 引用选择狂神说JAVA,走向人生巅峰 分割线 图片 超链接点击跳转到狂神博客  列表13 ABC 表格名字性别生日张三男1997.1.1......
  • Paddle图神经网络训练-PGLBox代码阅读笔记
    图存储部分paddle/fluid/framework/fleet/heter_psgraph_gpu_wrapper.hGPU图主入口graph_gpu_ps_table.hGPU图的主要存储结构,neighbor采样等都在这里完成gpu_graph_node.h节点,边,邻居等数据结构定义paddle/fluid/distributed/ps/table/common_graph_tabl......
  • 《Java编程思想第四版》学习笔记23
    在Inning中,可以看到无论构建器还是event()方法都指出自己会“掷”出一个违例,但它们实际上没有那样做。这是合法的,因为它允许我们强迫用户捕获可能在覆盖过的event()版本里添加的任何违例。同样的道理也适用于abstract方法,就象在atBat()里展示的那样。“interfaceStorm”非......
  • C++学习笔记
    字符串的比较字符串比较一般不用关系运算符比较,“hello”=="hello"底层是存储地址的比较逻辑运算符&&||!&&短路与运算,如果第一个条件为真就判断下一个条件,为假结果为假;如果第一个为假,就直接返回假,不判断第二个条件||短路或运算:碰到条件为真就停止运算,返回真值!非逻辑运算符:条件......
  • 【C++STL基础入门】队列的基础使用
    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档@TOC前言C++标准模板库(STL)提供了一系列强大的容器和算法,方便我们在编程中处理数据和实现各种功能。其中,queue(队列)是STL中的一个重要容器,用于按照先进先出(FIFO)的顺序处理元素。本文将介绍queue的基础使用方法,帮助读者初......
  • 深度神经网络中基于卷积操作的自适应学习算法研究
    本文提出了一种基于卷积操作的自适应学习算法,用于深度神经网络中。该算法通过引入复杂的数学公式和高阶张量操作,实现了对复杂模式的准确建模和学习。我们通过对网络架构的改进和参数的优化,提高了模型的泛化能力和性能表现。实验结果表明,我们的算法在多个基准数据集上取得了优于现有......
  • MinDoc:针对IT团队的文档、笔记系统
    作为一名IT从业者,无论是在公司团队中,还是在平时自己写一些笔记、博客等文档,我都习惯使用markdown来进行书写。在使用过许多支持markdown语法的系统或软件(如Typora、未知、我来、思源、觅道等)后,我总觉得它们不能满足我的需求。直到我发现了MinDoc这款针对IT团队开发的简单好用的开源......
  • 【学习笔记】笛卡尔树
    概述有若干二元组\((k,w)\),笛卡尔树要求关于\(k\)满足二叉搜索树的性质,关于\(w\)满足堆的性质。构建以要求\(w\)满足小根堆为例,使用单调栈维护当前的右链。现将所有二元组按\(k\)升序排序,每次插入一个元素时不断弹栈找到第一个小于\(w\)的节点,并将当前节点作为其右......