C++ STL

举报
御麟 发表于 2023/04/26 21:12:24 2023/04/26
【摘要】 ​STL全称是Standard Template Library1996年，惠普公司免费公开了STLC++成为算法竞赛中最受欢迎的语言，得益于STL中有大量的算法数据结构，运行速度不亚于手搓的算法模板STL是算法竞赛的必修课本文总结了一些算法竞赛中常用的STL​编辑长久以来软件界一直希望建立一种可重复利用的东西面向对象和泛型编程，目的就是复用性的提升STL从广义上分为容器，算法和迭代容器和算...

​

STL全称是Standard Template Library

1996年，惠普公司免费公开了STL

C++成为算法竞赛中最受欢迎的语言，得益于STL中有大量的算法数据结构，运行速度不亚于手搓的算法模板

STL是算法竞赛的必修课

本文总结了一些算法竞赛中常用的STL

​编辑

长久以来软件界一直希望建立一种可重复利用的东西

面向对象和泛型编程，目的就是复用性的提升

STL从广义上分为容器，算法和迭代

容器和算法之间通过迭代器进行无缝连接

STL几乎所有的代码都采用了模板类或者模板函数

STL的六大组件

容器，算法，迭代器，仿函数，空间配置器，适配器

1.容器：各种数据结构，如vector，list，deque，set，map等，来存放数据

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

3.迭代器：扮演了容器和算法之间的胶合器

4仿函数：行为类似函数，可作为算法的某种策略

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

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

容器

容器可以分为序列式容器和关联式容器

算法

可以分为质变算法和非质变算法

迭代器

输入迭代器

输出迭代器

前向迭代器

双向迭代器

随机访问迭代器

vector的遍历方法

#include<iostream>
#include<vector>
using namespace std;
​
int main(){
    vector<int> a;
    a.push_back(10);
    a.push_back(20);
    a.push_back(30);
    a.push_back(40);
    vector<int>::iterator abegin=a.begin();
    vector<int>::iterator aend=a.end();
    while(abegin!=aend){
        cout <<*abegin<<endl;
        abegin++; 
    }
    return 0;
}
#include<iostream>
#include<vector>
using namespace std;
​
int main(){
    vector<int> a;
    a.push_back(10);
    a.push_back(20);
    a.push_back(30);
    a.push_back(40);
    vector<int>::iterator abegin=a.begin();
    vector<int>::iterator aend=a.end();
    for(vector<int>::iterator it=a.begin();it!=a.end();it++){
        cout <<*it<<endl;
    }
    return 0;
}
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
​
void myprint(int a){
    cout <<a<<endl;
}
​
int main(){
    vector<int> a;
    a.push_back(10);
    a.push_back(20);
    a.push_back(30);
    a.push_back(40);
    vector<int>::iterator abegin=a.begin();
    vector<int>::iterator aend=a.end();
    for_each(abegin,aend,myprint);
    return 0;
}

Vector容器嵌套容器

vector<vector<int>>v;

#include<iostream>
#include<vector>
using namespace std;
​
vector<vector<int> > v;
vector<int> v1;
vector<int> v2;
vector<int> v3;
vector<int> v4; 
​
int main(){
    for(int i=0;i<4;i++){
        v1.push_back(i+1);
        v2.push_back(i+2);
        v3.push_back(i+3);
        v4.push_back(i+4);
    }
    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;
    }
    return 0;
} 
/*
[Error] '>>' should be '> >' within a nested template argument list
vector<vector<int> >嵌套时候> >中间要加一个空格 
*/

string

字符串string本质是一个类

char *是个指针

string是个类，类的内部封装了char *，管理这个字符串，是个char *的容器

string中有很多成员方法

string()； //创建一个空字符串，例如string str；

string'(const char* s) //使用字符串s初始化

string(const string& str)使用一个string对象初始化另一个string对象

string(int n,char c);使用n个字符初始化

string str4;

str4.assign("hello world");

#include<iostream>
#include<string>
using namespace std;
​
int main(){
    string str;
    str.assign("hello world");
    cout <<str<<endl;
    string str2;
    str2=str;
    cout <<str2<<endl;
    string str3="hello world";
    cout <<str3<<endl;
    return 0;
}

字符串拼接

#include<iostream>
#include<string>
using namespace std;
​
int main(){
    string str;
    str.assign("hello world");
    str+=",hello C++";
    str+='!';
    str.append("\nI love Code!");
    str.append("hackerdsdsg",6);
    str.append("tyut yyds",4,5);
    cout <<str<<endl;
    
    return 0;
}

字符串查找

查找指定字符串是否存在

在指定位置替换字符串

find rfind

str1.find("as",1);

find找的是第一次出现的位置

rfind找的是最后一次位置

replace替换

replace(1,3,"1111");

从一位开始，替换3个字符，换成字符串" 1111"

字符串比较

compare

string存取

str.size();返回长度

str[i]; str.at(i);可以访问每一个元素

字符串的插入和删除

insert(pose,"");

erase(pose,num);

子串获取

substr

vector

单端数组

数组是静态空间，而vector可以动态扩展

并不是在原空间之后连接空间，而是找更大的内存空间，然后将原数据拷贝到新空间

构造

vector的迭代器支持随机访问

vector<int> v3(num,data);

vector<int> v2(v1.begin(),v1.end());

vector<int> v4(v3);

赋值

push_back();

v1=v2;

assign(10,100);

assign(v3.begin(),v3.end());

容量和大小

empty();

capacity(); //容器的容量

size();//返回容器中容量的大小

capacity>=size

resize(int num)重新制定容器长度

resize(int num,elem);容器如果变长，用elem填充新位置

#include<iostream>
#include<vector>
using namespace std;
​
void printVector(vector<int>&v){
    for(vector<int>::iterator it=v.begin();it!=v.end();it++)
        cout <<*it<<' ';
        cout <<endl; 
} 
​
void test01(){
    vector<int>v;
    for(int i=0;i<10;i++)
        v.push_back(i);
    printVector(v);
    if(v.empty()){
        cout <<"v1为空"<<endl;
    }
    else{
        cout <<"v1不为空"<<endl;
        cout <<"v1的容量是"<<v.capacity()<<endl;
        cout <<"v1的大小是" <<v.size()<<endl;
    }
    v.resize(15,100);   //将长度加长为15，默认用0填充新的位置 
    printVector(v);
    v.resize(5);
    printVector(v);    //将长度缩短，超出的会删除掉 
} 
​
int main(){
    test01();
    return 0;
}

插入和删除

#include<iostream>
#include<vector>
using namespace std;
​
int main(){
    vector<int>v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.pop_back();   //将最后一个数据4弹出 
    v.insert(v.begin(),100);    //在迭代器的位置插入一个数据100
    v.insert(v.begin(),3,1000);  //在迭代器的位置插入n个数据
    v.erase(v.begin());  //将迭代器位置的数据删除 
    for(vector<int>::iterator it=v.begin();it!=v.end();it++)
        cout <<*it<<' ';
        cout <<endl;
    return 0;
}

Vector的数据存取

v.size();

用中括号和at访问第i个元素

.front();

返回第一个元素

.back();

返回最后一个元素

容器互换

v1.swap(v2);

用swap收缩内存

v.resize();

vector<int>(v).swap(v);

预留空间

reserve();

不停的加数据，会重新分配内存

可以直接预存空间，避免太多次分配内存

deque

双端数组

构造函数

deque内部有个中控区，维护每段缓冲区的内容，缓冲区中存放真实数据

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

#include<iostream>
#include<deque>
using namespace std;
​
int main(){
    deque<int> u;
    u.push_front(1);
    u.push_front(2);
    u.push_back(3);
    u.push_back(4);
    u.push_front(5);
    for(deque<int>::iterator it=u.begin();it!=u.end();it++)
        cout <<*it<<' ';
        cout <<endl;
        cout <<u.size();
        cout <<endl;
        cout <<u.empty(); 
    cout <<endl;
    for(int i=0;i<u.size();i++)
    cout <<u.at(i);
    cout <<u.back();
    return 0;
}

速度没有vector快

赋值操作

d2=d1;

d3.assign(开始迭代器,终止迭代器);

大小操作

empty();

size();

resize();

插入删除

push_back();

push_front();

pop_front();

pop_back();

insert(pos,elem);

insert(pos,n,elem);

insert(pos,beg,end);

clear();

数据存取

at()或者[];

front();第一个元素;

back();最后一个元素;

排序

#include<iostream>
using namespace std;
#include<deque>
#include<algorithm>
deque<int> u;
int n;
int a;
​
int main(){
    cin >>n;
    while(n--){cin >>a; u.push_back(a);}
    sort(u.begin(),u.end());
    for(deque<int>::iterator it=u.begin();it!=u.end();it++){
        cout <<*it<<' ';
    }
    return 0;
}

stack

stack<int> stk;

push();

pop();

top();

empty();

size();

queue

push();

pop();

front();

back();

empty();

size();

list

由结点组成，数据域和指针域

可以对任意位置进行快速插入和删除

容器遍历速度没有数组快

占用的空间比数组大

STL中的链表是双向循环的链表，next,prev

.front(); .back(); .begin(); pop_back(); .end();

采用动态分配内存

时间和空间额外耗费大

assign(begin,end);

.swap();

大小操作

resize();

empty();

pop_back();

pop_front();

insert();

clear();

erase();

remove();

数据存取

front();

back();

翻转和排序

reserve();

set

关联式容器

set不允许有重复的元素

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

set叫关联式容器

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

set.insert(10);

交换和大小

size();

swap();

插入和删除数据

insert();

clear();

erase();

查找和统计

find();查找数值是否存在，若存在，返回下标

count(); 统计key的个数

Pari

pair<int,int> p(q,a);

pair<int,int> p=make_pair(q,a);

set容器的排序

利用仿函数

map

multimap

map<int,int>

m.insert(pair<int,int>(1,10));

swap();

​

【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
C++ 容器 数据结构
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入