C++标准模板库

cpp 数据结构
C++
发布日期:   2022-02-28
文章字数:   3.5k
阅读时长:   14 分
阅读次数:  

C++ STL库

一、数据结构角度观测C++与C

  1. C++是C的超集，也就是说C++是可以兼容C语言的，C++在C语言的基础上增加了许多的特性和概念。

  2. 头文件引用

    //C语言的方法：带.h的方式进行include
#include<stdio.h>
#include<math.h>
  
//C++的方法，直接引用即可
#include<string>
#include<cstdio>//C++引用C语言标准
#include<cmath>

  3. 输入/输出：C++采用“流”的思路去进行输入输出设计，这样的做法可以大大简化我们的设计，但是这样的做法确是更慢。

    int n; //定义n为整形
//C语言的输入输出（需要指定类型，如下指定为整形）
scanf("%d",&n);
printf("%d",n);
//C++语言的输入输出（不需要指定类型，会根据n进行自主的判定）
cin>>n;
cout<<n;

  4. STL：STL是Standard Template Library的简称，中文名标准模板库，惠普实验室开发的一系列软件的统称。

  5. STL是一些“容器”与“算法”的集合，所谓的这些“容器”无非就是已经实现好了数据结构，能够让程序设计者更为方便的进行调用，“算法”则顾名思义就是已预先实现好了的算法集合。STL的目的是标准化组件，不用重新开发，可以使用现成的组件。STL现在是C++的一部分，因此不用安装额外的库文件。

  6. 在C++标准中，STL被组织为下面的13个头文件：、、、、、、、、、、、和。

二、标准模板库

  1. 容器（Container）：是一种数据结构，list（链表）、vector（向量数组）、stack（栈）、队列（queque），以模板类的方式提供，为了访问容器中的数据，可以使用由容器类输出的迭代器。

  2. 迭代器（Iterator）：是一种特殊的指针，提供了访问容器中的对象的方法，在程序设计中，扮演了容器和算法之间的胶合剂，利用迭代器可以快速而安全的对容器内容进行操作，或是进行算法模板的使用。

  3. 算法（Algorithm）：是一类常用的算法模板，既可以对容器进行操作，同时其开放性也让算法类本身可以针对数组或者是自定义结构体等结构进行直接的操作。

  4. 仿函数（Function object），（又称为函数对象，function object），是一种行为类似函数，重载了()操作符的结构体与类。

  5. 迭代适配器（Iterator Adaptor），一种用来修饰容器或者仿函数的接口，它使得得带适配器使算法能够以逆向模式，安插模式进行工作，甚至还可以与流配合，它对容器起到非常大的辅助作用，同时他还将迭代器进行了更高级别的抽象。

  6. 空间配制器（allocator），是负责空间的配置与管理，重点就是对容器的空间申请和空间释放进行管理，理解为C的malloc和free函数，C++的new和delete关键字。

三、Vector容器

  1. Vector就是一个动态创建空间，且预先加载了常用的数组操作的数组。

  2. 格式为：vectorname;

    #include<vector>

//不带参数的构造函数初始化
vector<int> v1;	//创建一个空的向量v1,size = 0

//带参数的构造函数初始化
vector<double> v2(10);//其已开辟10个元素的空间，double v2[10];
vector<int> v3(10,5); //其已开辟10个元素的空间并全部赋值为5

//通过insert初始化
vector<int> v4(v3.begin(),v3.end());//v4,其内容为向量v3的内容
//insert初始化方式将同类型的迭代器对应的始末区间（左闭右开区间）内的值插入到vector中
vector<int> a(6,6);
vecot<int> b;
//将a[0]~a[2]插入到b中，b.size()由0变为3
b.insert(b.begin(), a.begin(), a.begin() + 3);

//insert也可通过数组地址区间实现插入
int a[6] = {6,6,6,6,6,6};
vector<int> b;
//将a的所有元素插入到b中，同样是左闭右开区间
b.insert(b.begin(), a, a+6);

//insert还可以插入m个值为n的元素
//在b开始位置处插入6个7
b.insert(b.begin(), 6, 7);

//通过同类型的vector初始化
vector<int> v5(v4);//创建一个向量v5，其包含了v4的全部内容

int a[5] = {1,2,3,4,5};
//通过数组a的地址初始化，注意地址是从0到5（左闭右开区间）
vector<int> b(a, a+5);

//通过copy函数赋值
vector<int> a(5,1);
int a1[5] = {2,2,2,2,2};
vector<int> b(10);
/*将a中元素全部拷贝到b开始的位置中,注意拷贝的区间为a.begin() ~ a.end()的左闭右开的区间*/
copy(a.begin(), a.end(), b.begin());
//拷贝区间也可以是数组地址构成的区间
copy(a1, a1+5, b.begin() + 5);

  3. 迭代器：一种安全的访问控制器，它本身是一种指针，用于直接的元素访问。其遍历访问的大致思路是，创建容器的迭代器，让迭代器指向第一个元素，逐步向后移动并最终指向最后一个元素结束。

    vector<int> v;       //创建一个向量vs
vector<int>::iterator it;   //C98标准
for(it=v.begin();it!=v.end();it++){
    cout<<*it<<' ';
}
//
 for(int i=0;i<v.size();i++){
        cout<<v[i]<<' ';
}

  4. 常用接口

    vector<int> v;

//在向量的末尾添加一个新元素val，并自动让容器大小增大一个
v.push_back(10);  //插入一个数据10

//移除向量尾的最后一个元素，并且将容器大小减小一个
v.pop_back();

//插入元素到指定位置，通过在元素之前在指定位置插入新元素来扩展向量，从而有效地增加容器大小所插入的元素数量
 v.insert(v.begin(),10);     //在向量最前端插入数据10
 v.insert(v.begin(),5,20);   //在向量最前端插入5个数据20
 vector<int> k(2,50);   //创建一个新的向量k,其拥有2个元素内容均为50
 v.insert(v.begin(),k.begin(),k.end());  //在向量v最前端插入向量K的全部内容

//删除一个元素，或者是一段区间的元素，将会自动缩减空间使用
v.erase(v.begin());     //删除第一个元素
v.erase(v.begin(),v.begin()+4); //删除从第一个开始后4个元素（包括第一个）

//将向量中所有元素清空
v.clear();	//清空向量

//返回向量中的数据元素个数
cout<<v.size()<<endl;   //输出5

//返回向量最大已开辟的空间大小
vector<int> v(3,10);    //创建默认有3个值为10的元素的向量v
v.insert(v.begin(),10,20);   //在向量最前端插入10个值为20的数据
v.erase(v.begin(),v.begin()+4); //删除从第一个开始后4个元素（包括第一个）
cout<<v.capacity()<<endl;   //输出13

//返回计算机支持开辟vector的最大空间值，一般来说和计算机内存和CPU相关，是一个极大的数据，而且不同计算机中可能有不同的值
vector<int> v(5,10);    //创建默认有5个值为10的元素的向量v
cout<<v.max_size()<<endl;   //输出4611686018427387903

四、List容器

  1. 初始化

    #include<list>
list<int> l1;           //创建一个空链表
list<int> l2(10);       //创建一个链表其有10个空元素
list<int> l3(5,20);     //创建一个链表其有5个元素内容为20
list<int> l4(l3.begin(),l3.end());  //创建一个链表其内容为l3的内容
list<int> l5(l4);               //创建一个链表其内容为l4的内容

  2. 迭代器

    list<int> li;
for(list<int>::iterator it=li.begin();it!=li.end();it++)
{
    cout<<*it<<' ';
}

  3. 常用接口

    list<int> li;
//判断是否为空empty()
//返回一个bool类型的值，只存在真和假，当链表为空时为真，不为空时为假
if(li.empty())
{     //当链表为空的时候执行
    cout<<"is empty()"<<endl;
}
else
{
    cout<<"not empty()"<<endl;
}

//获取大小size()，返回链表元素的个数
cout<<li.size()<<endl;

//链表前插入push_front() &&链表前删除 pop_front()
li.push_front(10);
li.pop_front();

//链表后插入push_back() &&链表后删除 pop_back()
li.push_back(10);
li.pop_back();

//插入元素到指定位置，通过在元素之前在指定位置插入新元素来扩展向量
li.insert(li.begin(),10);     //在链表最前端插入数据10
li.insert(li.begin(),5,20);   //在链表最前端插入5个数据内容为20
list<int> k(2,50);   //创建一个新的链表k,其拥有2个元素内容均为50
li.insert(li.begin(),k.begin(),k.end());  //在链表li最前端插入链表上K的全部内容

//删除一个元素，或者是一段区间的元素，将会自动缩减空间使用
li.erase(li.begin());     //删除第一个元素
li.erase(li.begin(),li.begin()+4); //删除前4个元素

//让整个链表变成升序状态，或者变成自定义的排序状态
li.sort();//升序
li.sort(cmp);//降序

//相对于自定义的降序方法
li.reverse();

五、stack栈容器

  1. 初始化

    #include<stack>

stack<int> s;//创建一个栈
stack<int> v(s);//创建一个栈为s的全部内容

vector<int> v(3,100);           
stack<int,vector<int> > s(v);  //注意，> >符号之间需要有一个空格隔开

  2. 常用接口

    stack<int> s;
cout<<s.size()<<endl;   //直接返回栈中元素的个数

cout<<s.top()<<endl;     //直接返回输出即可
s.top()+=100;            //也可以直接对栈定元素进行修改操作

s.push(5);	//5入栈
s.pop();

while(!s.empty())//判空
{
    cout<<s.top()<<endl;
    s.pop();
}

六、Queue容器

  1. 初始化

    #include<queue>
queue<int> q;//创建一个空的没有数据的队列q
queue<int> v(q);//创建一个队列v其元素为q的全部内容

vector<int> v(3, 100);
queue<int, vector<int> > s(v);//内容就是vector数组的全部内容

  2. 常用接口

    queue<int> q;
cout << q.size() << endl;
q.push(100);//100入队
q.pop();//出队

//访问对头元素，可以返回其数值，也可以进行相应的操作
q.front() += 500; //对队头元素进行修改
cout << q.front() << endl;//直接输出内容

//访问队尾元素，较为少用
q.back()+=500;     //对队尾元素进行修改
cout<< q.back() <<endl;

while(q.empty())//判空
{
    cout<<q.front()<<endl;
    q.pop();
}

七、优先队列（Priority_queue）

  1. 优先队列的底层是以散列的状态（非线性）表现的，他与标准的队列有如下的区别，标准的队列遵从严格的先进先出，优先队列并不遵从标准的先进先出，而是对每一个数据赋予一个权值，根据当前队列权值的状态进行排序，使得权值最大（或最小）的永远排在队列的最前面。

  2. 初始化

    #include<queue>
priority_queue<T, Container, Compare>
priority_queue<T>//直接输入元素则使用默认容器和比较函数
a) T就是Type为数据类型
b) Container是容器类型，（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector）
c) Compare是比较方法，类似于sort第三个参数那样的比较方式，对于自定义类型，需要我们手动进行比较运算符的重载。与sort直接Bool一个函数来进行比较的简单方法不同，Compare需要使用结构体的运算符重载完成，直接bool cmp(int a,int b){  return a>b; } 这么写是无法通过编译的。
    
struct cmp
{ //这个比较要用结构体表示
    bool operator()(int &a, int &b) const
    {
        return a > b;
    }
};
  
priority_queue<int,vector<int>,cmp> q;    //使用自定义比较方法
priority_queue<int> pq;

八、Set容器

  1. Set（集合）属于关联式容器，依据特定的排序准则，自动为其元素排序。Set集合的底层使用一颗红黑树，其属于一种非线性的数据结构，每一次插入数据都会自动进行排序。

  2. Set的性质有：数据自动进行排序且数据唯一，是一种集合元素，允许进行数学上的集合相关的操作。

  3. 初始化

    #include <set>
template < class T,                        
           class Compare = less<T>,        
           class Alloc = allocator<T>      
           > class set;
//基本上就是三个参数，第一个是值，第二个比较器，用于比较内容，默认为less<Key>即降序，第三个是内存配置器，负责内存的分配和销毁。

set<int> s;       //直接指定值的类型创建，其他为默认方法

for (set<int>::iterator it=s.begin(); it!=s.end(); ++it)
        cout << *it << ' ';	//迭代器
 for (auto it=s.cbegin(); it!=s.cend(); ++it)
        cout << *it << ' ';

cout << s.size() << endl;   //直接返回元素个数
s.insert(i);	//插入一个元素，插入元素的类型必须与创建的容器类型一致

//删除一个元素，或者是一段区间的元素，将会自动缩减空间使用。
s.erase(s.begin());  //使用迭代器的方法删除第一个元素
s.erase(s.begin(),s.end());     //删除一段内容，这里是全部删除	

s.clear();//这里只是清空元素，其所占用的最大内存空间还是不会改变的。

//查找元素find()
cout << *s.find(4) << endl;
s.erase(s.find(4));
文章作者: nusqx
文章链接: https://nusqx.top
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 nusqx !
cpp 数据结构
赏
评论
  目录