E

EdwardWong

V1

2022/11/17阅读:17主题:姹紫

STL容器之概述

STL的优势

C++定义数组为例, 可以采用静态数组的方法int a[n], 这种定义数组的方法需要事先确定好数组的长度,即n为变量,这意味着如果在实际应用中无法确定数组长度,则一般会将数组长度设为可能的最大值,这可能会导致存储空间的浪费。

可以采用在堆空间动态申请内存的方法,此时长度可以是变量:

int *p=new int[n]

这种定义方法可根据变量n动态申请内存,不会出现存储空间浪费的问题。 但是上述代码程序在执行的过程中如果出现存储空间不足的情况时,需要动态增加存储空间

  1. 新申请较大的存储空间,执行int* temp=new int[m]

  2. 将原内存空间的数据全部复制到新申请的内存空间中,即执行memecpy(temp,p,sizeof(int)*m)

  3. 将原来的堆空间释放,即执行delete[] p;

vector <int> a; //定义 a 数组,当前数组长度为 0,但和普通数组不同的是,此数组 a 可以根据存储数据的数量自动变长。

//向数组 a 中添加 10 个元素
for (int i = 0; i < 10 ; i++)
a.push_back(i)

//还可以手动调整数组 a 的大小
a.resize(100);

a[90] = 100;
//还可以直接删除数组 a 中所有的元素,此时 a 的长度变为 0

a.clear(); -- > 此时数组的元素个数为0

//重新调整 a 的大小为 20,并存储 20 个 -1 元素。
a.resize(20, -1)

泛型编程

所谓泛型实质上就是不使用具体数据类型(例如int,double,float等),而是使用一种通用的类型来实现程序设计的方法,该方法可以大规模的减少程序代码的编写量,让程序员可以集中精力用于业务逻辑的实现。

T maxt(T x, T y){
return (x>y)? x:y;
}

代码中的T实际是类型占位符,如果将这种类型占位符也叫做数据类型的话,叫做泛型,使用这种类型占位符的编程方式称为泛型编程。

泛型也是一种数据类型,只不过它是一种用来替代所有类型的通用类型。

STL基本组成

通常认为,STL是由容器、算法、迭代器、函数对象、适配器、内存分配器这6部分构成,其中后面4部分是为前2部分服务的,它们各自的含义如表所示:

STL序列式容器

容器的分类

序列式容器的共同特点是不会对存储的元素进行排序,元素排序的顺序取决于存储他们的顺序

容器就是一些模板类的集合,但和普通模板类不同的是,容器中封装的是组织数据方法(也就是数据结构)

STL提供3类标准容器,分别是序列容器排序容器哈希容器,其中后两类容器也称为关联容器

哈希容器与排序容器不同,哈希容器中的元素是未排序的,元素的位置由哈希函数确定

由于哈希容器直到C++11才正式纳入C++标准程序库,而再次之前,民间流传着hash_sethash_multisethash_maphash_multimap版本。 序列容器大致分为以下几类容器:

  • array<T,N> (数组容器) :表示可以存储NT类型的元素,此类容器一旦建立,其长度就是固定不变的,只能修改某个元素的值。

  • vector<T> (向量容器): 用来存放T类型的元素,长度可变的序列容器,插入元素的效率比较差,只有在尾部的时候增加或删除元素的效率最高

  • deque<T> (双向队列容器): 在头部和尾部插入和删除元素的效率较高,但是其他位置处相对较慢。

  • list<T>(双向链表容器),在任何位置插入或者删除元素效率都很高,但是查询相比vector,array要慢。

  • forward_list<T>(正向链表容器): 和list容器比较相似,只不过是单向链表。

容器种常见的函数成员

注意emplace和insert的区别: emplace最大的作用是避免产生不必要的临时变量,因为它可以完成in place的构造,

struct Foo{
Foo(int n, double x);
};

std::vector<Foo> v;
v.emplace(someIterator,42,3.1416); //没有临时变量的产生

v.insert(someIterator,Foo(42,3.1416)); //需要产生一个临时变量

v.insert(someIterator,{42,3.1416}) //需要产生一个临时变量

emplace利用了变参模板完美转发变参模板使得emplace可以接受任意参数,这样可以适用于任意对象的构建,完美转发使得接收下来的参数能够原样的传递给对象的构造函数。

迭代器(iterator)

无论是序列容器还是关联容器,最常做的操作无疑是遍历容器中存储的元素,而实现此操作,多数情况会选用iterator来实现。

换句话说,不同容器的内部结构各异,容器的本质是一串能存储多个数据的存储单元,因此诸如数据的排序、查找、求和等需要对数据进行遍历的操作方法应该是类似的。

可以利用泛型技术,将它们设计成适用所有容器的通用算法,从而将容器和算法分离开。

STL标准库为每一种标准容器定义了一种迭代器类型,这意味着不同容器的迭代器不同,功能强弱不同。常见的迭代器按功能强弱可以分为输入迭代器输出迭代器前向迭代器双向迭代器随机访问迭代器五种。

输入迭代器和输出迭代器比较特殊,但他们不是把数组或容器当作操作对象,而是把输入流/输出流作为操作对象

  • 前向迭代器(forward iterator) 假设p是一个前向迭代器,则p支持++p,p++,*p操作,还可以被复制或赋值,可以用==!=运算符进行比较,此外,两个正向迭代器可以互相赋值

  • 双向迭代器(bidirectional iterator) 双向迭代器具有正向迭代器的全部功能,除此之外,假设p是一个双向迭代器,则还可以进行--p或者p--操作(即一次向后移动一个位置)。

  • 随机访问迭代器(random access iterator)

随机访问迭代器具有双向迭代器的全部功能,除此之外,假设p是一个随机访问迭代器,i是一个整型变量或常量,则p还支持以下操作:

  • p+=i: 使得p往后移动i个元素

  • p-=i: 使得p往前移动i个元素

  • p+i:返回p后面第i个元素的迭代器

  • p-i: 返回p前面第i个元素的迭代器

  • p[i]: 返回p后面第i个元素的引用

此外,两个随机访问迭代器p1p2还可以用<,><=>=运算符进行比较。 另外,表达式p2-p1也是有定义的,其返回值表示p2所指向元素和p1所指向元素的序号之差(p2p1之间的元素个数减一)。

容器适配器queuestack没有迭代器, 他们包含一些成员函数,可以用来对元素进行访问

迭代器的定义方式

尽管不同容器对应着不同类别的迭代器,但这些迭代器有着较为统一的定义方式,具体分为4种。

常量迭代器和非常量迭代器的区别在于: 通过非常量迭代器还能修改其指向的元素

反向迭代器和正向迭代器的区别在于:1. 对正向迭代器进行++操作时,迭代器会指向容器中的后一个元素; 2. 对反向迭代器进行++操作时,迭代器会指向容器中的前一个元素

以上4种定义迭代器的方式,并不是每个容器都适用,有一部分容器同时支持以上4种方式,比如array,dequevector;而有些容器只支持其中部分的定义方式,例如forward_list容器只支持定义正向迭代器,不支持定义反向迭代器。

//遍历 vector 容器。
#include <iostream>

//需要引入 vector 头文件
#include <vector>

using namespace std;

int main()
{
vector<int> v{1,2,3,4,5,6,7,8,9,10}; //v被初始化成有10个元素

cout << "第一种遍历方法:" << endl;

//size返回元素个数
for (int i = 0; i < v.size(); ++i)
cout << v[i] <<" "; //像普通数组一样使用vector容器
//创建一个正向迭代器,当然,vector也支持其他 3 种定义迭代器的方式

cout << endl << "第二种遍历方法:" << endl;

vector<int>::iterator i;

//用 != 比较两个迭代器
for (i = v.begin(); i != v.end(); ++i)
cout << *i << " ";

cout << endl << "第三种遍历方法:" << endl;

for (i = v.begin(); i < v.end(); ++i) //用 < 比较两个迭代器
cout << *i << " ";

cout << endl << "第四种遍历方法:" << endl;

i = v.begin();
while (i < v.end()) { //间隔一个输出
cout << *i << " ";
i += 2; // 随机访问迭代器支持 "+= 整数" 的操作
}
}

随机访问迭代器支持+=整数的操作。

listset/multisetmap/multimap都支持双向迭代器

//创建一个v list容器
list<int> v;

//创建一个常量正向迭代器,同样,list也支持其他三种定义迭代器的方式

list<int>::const_iterator i;

//合法的代码

for(i=v.begin();i!=v.end();++i){
cout << *i;
}

// 不合法的代码(因为双向迭代器不支持`<`进行比较)

for(i=v.begin();i<v.end();++i){
cout << *i;
}

// 双向迭代器也不允许用下标随机访问元素
for(int i=0;i<v,size();++i){
cout << v[i];
}

其实关于数组也是容器,其迭代器就是指针,而且是随机访问迭代器

分类:

后端

标签:

C++

作者介绍

E
EdwardWong
V1