C++ STL容器与常用库函数

简介: C++ STL容器与常用库函数

STL容器:

一、#include

英文翻译:vector :向量

vector是变长数组(动态变化),支持随机访问,不支持在任意位置O(1)插入。为了保证效率,元素的增删一般应该在末尾进行。

声明

#include 头文件

vectora; 相当于一个长度动态变化的int数组

vectorb[233]; 相当于第一维长233,第二位长度动态变化的int数组

struct rec{…};

vectorc; 自定义的结构体类型也可以保存在vector中

size/empty

size函数返回vector的实际长度(包含的元素个数),empty函数返回一个bool类型,表明vector是否为空。二者的时间复杂度都是O(1)。

所有的STL容器都支持这两个方法,含义也相同。

clear

clear函数把vector清空。

front/back

front函数返回vector的第一个元素,等价于*a.begin() 和 a[0]。

back函数返回vector的最后一个元素,等价于*==a.end() 和 a[a.size() – 1]。

push_back() 和pop_back()

a.push_back(x) 把元素x插入到vector a的尾部。

b.pop_back()删除vector a的最后一个元素。

 
#include<iostream>
#include<vector>
using namespace std;
 
int main()
{
    
    vector<int> a;        //相当于一个长度动态变化的int数组
    vector<int> b[233];    //相当于第一维长233,第二位长度动态变化的int数组
    a.size();      //函数返回vector的实际长度(包含的元素个数)
    a.empty();     //函数返回一个bool类型,表明vector是否为空。
    a.clear();     //clear函数把vector清空
    struct rec{
        int a;
        double b;
    };
    vector<rec> c;    //自定义的结构体类型也可以保存在vector中
    
    
    vector<int> d({1,2,3});
    cout<<d.front()<<" "<<d[0]<<" "<<endl;
    cout<<d.back()<<" "<<d[d.size()-1]<<" "<<endl;
    
    d.push_back(4);
    for(auto x:d)cout<<x<<" ";//把元素x插入到vector a的尾部。
        cout<<endl;
    d.pop_back();
    for(auto x:d)cout<<x<<" ";//删除vector a的最后一个元素。
        cout<<endl;
    return 0;
}

二、#include

英文翻译:queue :队列

头文件queue主要包括循环队列(先进先出)

queue和优先队列priority_queue两个容器。

声明

queueq;//队列

structrec{…}; queue q; //结构体rec中必须定义小于号

priority_queueq; // 大根堆

priority_queue, greater q; //小根堆

priority_queue>q; //小根堆

循环队列 queue

push从队尾插入

pop从队头弹出

front返回队头元素

back返回队尾元素

优先队列 priority_queue(堆)

**默认为大根堆

push把元素插入堆

pop删除堆顶元素

top 查询堆顶元素(最大值)

 
#include<iostream>
#include<queue>
using namespace std;
 
int main()
{
    queue<int> q;//队列
    queue<double> q1;
    struct rec{
        int a,b;
        bool operator< (const rec& t)const
        {
            return a<t.a;
        }
    }; queue<rec> q2;     //结构体rec中必须定义小于号
 
    priority_queue<int> q3;        // 大根堆
    priority_queue<int, vector<int>, greater<int>>q4;    // 小根堆
    priority_queue<pair<int, int>>q5;
    
    
    queue<int> s;//队列
    s.push(1);  //从队尾插入
    s.pop();    //从队头弹出
    s.front();   //返回队头元素
    s.back();    //返回队尾元素
    
    priority_queue<int> s1;
    s1.push(1); //把元素插入堆
    s1.pop();   //删除堆顶元素
    s1.top();   //查询堆顶元素(最大值)
    s1.push(-x); //按小根堆插入
    return 0;
}

三、#include

英文翻译:stack :堆栈

头文件stack包含栈。声明和前面的容器类似。

push 向栈顶插入

pop 弹出栈顶元素

 
#include<iostream>
#include<stack>
using namespace std;
 
int main()
{
    stack<int>stk;
    stk.push(1);//向栈顶插入元素
    stk.pop();  //弹出栈顶元素
    stk.top();  //查询栈顶元素(最大值)
    
    return 0;
}

四、#include

双端队列deque是一个支持在两端高效插入或删除元素的连续线性存储空间。它就像是vector和queue的结合。与vector相比,deque在头部增删元素仅需要O(1)的时间;与queue相比,deque像数组一样支持随机访问。

[] 随机访问

front/back 队头/队尾元素

push_back 从队尾入队

push_front 从队头入队

pop_back 从队尾出队

pop_front 从队头出队

clear 清空队列

 
#include<iostream>
#include<deque>
using namespace std;
 
int main()
{
    deque<int>a;
    a[0]; //随机访问
    a.front();   a.back();//队头/队尾元素
    a.push_back(1);   //从队尾入队
    a.push_front(2);  //从队头入队
    a.pop_back();    //从队尾出队
    a.pop_front();   //从队头出队
    a.clear();       //清空队列
    
    return 0;
}

五、#include

英文翻译: set :集

头文件set主要包括set和multiset两个容器,分别是“有序集合”和“有序多重集合”,即前者的元素不能重复,而后者可以包含若干个相等的元素。set和multiset的内部实现是一棵红黑树,它们支持的函数基本相同。

声明

set s;

struct rec{…}; set s; //结构体rec中必须定义小于号

multiset s;

size/empty/clear

与vector类似

insert

s.insert(x)把一个元素x插入到集合s中,时间复杂度为O(logn)。

在set中,若元素已存在,则不会重复插入该元素,对集合的状态无影响。

find

s.find(x) 在集合s中查找等于x的元素,并返回指向该元素的迭代器。

若不存在,则返回s.end()。时间复杂度为O(logn)。

lower_bound/upper_bound

这两个函数的用法与find类似,但查找的条件略有不同,时间复杂度为 O(logn)。

s.lower_bound(x) 查找大于等于x的元素中最小的一个,并返回指向该元素的迭代器。

s.upper_bound(x) 查找大于x的元素中最小的一个,并返回指向该元素的迭代器。

count

s.count(x)返回集合s中等于x的元素个数,时间复杂度为 O(k +logn),其中k为元素x的个数。

 
#include<iostream>
#include<set>
using namespace std;
 
int main()
{
    set<int>a;//元素不能重复
    multiset<int>b;//元素可以重复
    int x;
    a.insert(x);//把一个元素x插入到集合x中
    if(a.find(x)==a.end())//判断x是否存在于x中
    
    a.lower_bound(x);//查找大于等于x的元素中最小的一个
    a.upper_bound(x);//查找大于x的元素中最小的一个
    
    b.count(x);//返回集合b中等于x的元素个数
    return 0;
}

六、#include

#include

英文翻译: map:地图

map容器是一个键值对key-value的映射,其内部实现是一棵以key为关键码的红黑树。Map的key和value可以是任意类型,其中key必须定义小于号运算符。

声明

map name;

例如:

map vis;

map hash;

map, vector> test;

size/empty/clear/begin/end

均与set类似。

Insert/erase

与set类似,但其参数均是pair。

find

h.find(x)在变量名为h的map中查找key为x的二元组。

[]操作符

h[key]返回key映射的value的引用,时间复杂度为O(logn)。

[]操作符是map最吸引人的地方。我们可以很方便地通过h[key]来得到key对应的value,还可以对h[key]进行赋值操作,改变key对应的value。

 
#include<iostream>
#include<map>
#include<vector>
using namespace std;
 
int main()
{
    //相当于数组
    map<int,int>a;
    a[10000]=8;
    cout<<a[10000]<<endl;
    
    //和数组的区别(可以随便定义数组类型,包括下标)
    map<string,int>b;
    b["zyq"]=9;
    cout<<b["zyq"]<<endl;
    
    map<string,vector<int>>c;
    c["zyq"]=vector<int>({1,2,3,4,5,6});
    cout<<c["zyq"][2]<<endl;
    c.insert({"b",{10}});
    cout<<(c.find("b")==c.end())<<endl;//输出0为存在,输出1为不存在
    return 0;
}

map和unordered_map的区别

一.头文件不同,分别是:

#include

#include

二.其实现不同

map:其实现是使用了红黑树

unordered_map:其实现使用的是哈希表

三.特点

map:

1.元素有序,并且具有自动排序的功能(因为红黑树具有自动排序的功能)

2.元素按照二叉搜索树存储的,也就是说,其左子树上所有节点的键值都小于根节点的键值,右子树所有节点的键值都大于根节点的键值,使用中序遍历可将键值按照从小到大遍历出来

3.空间占用率高,因为map内部实现了红黑树,虽然提高了运行效率,但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质,使得每一个节点都占用大量的空间

4.适用情况:对顺序有要求的情况下,如排序等

unordered_map:

  1. 元素无序。
  2. 查找速度非常的快。
  3. 哈希表的建立比较耗费时间
  4. 适用情况:对于查找问题
  5. 对于unordered_map或者unordered_set容器,其遍历顺序与创建该容器时输入元素的顺序是不一定一致的,遍历是按照哈希表从前往后依次遍历的

七、#include

1.size/empty/clear/begin/end

string均可以用

2.substr();

返回字符串长度

 
#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
    string a="abnd";
    a+="hdush";//a="abndhdush"
    a+='z';//a="abndhdushz"
    //从第1个(起始点在0)位置开始,输出3个字符
    cout<<a.substr(1,3);//bnd
    cout<<endl;
    //输出从4开始的整个子串
    cout<<a.substr(4);//hdushz
    return 0;
}

八、位运算

& 与

| 或

~ 非

^ 异或

>> 右移

<< 左移

常用操作:

  1. 求x的第k位数字 x >> k & 1
  2. lowbit(x) = x & -x,返回x的最后一位1

九、总结:

 
vector, 变长数组,倍增的思想
    size()  返回元素个数
    empty()  返回是否为空
    clear()  清空
    front()/back()
    push_back()/pop_back()
    begin()/end()
    []
    支持比较运算,按字典序
 
pair<int, int>
    first, 第一个元素
    second, 第二个元素
    支持比较运算,以first为第一关键字,以second为第二关键字(字典序)
 
string,字符串
    size()/length()  返回字符串长度
    empty()
    clear()
    substr(起始下标,(子串长度))  返回子串
    c_str()  返回字符串所在字符数组的起始地址
 
queue, 队列
    size()
    empty()
    push()  向队尾插入一个元素
    front()  返回队头元素
    back()  返回队尾元素
    pop()  弹出队头元素
 
priority_queue, 优先队列,默认是大根堆
    size()
    empty()
    push()  插入一个元素
    top()  返回堆顶元素
    pop()  弹出堆顶元素
    定义成小根堆的方式:priority_queue<int, vector<int>, greater<int>> q;
    也可以使用push(-x)  变成一个小根堆
 
stack, 栈
    size()
    empty()
    push()  向栈顶插入一个元素
    top()  返回栈顶元素
    pop()  弹出栈顶元素
 
deque, 双端队列
    size()
    empty()
    clear()
    front()/back()
    push_back()/pop_back()
    push_front()/pop_front()
    begin()/end()
    []
 
set, map, multiset, multimap, 基于平衡二叉树(红黑树),动态维护有序序列
    size()
    empty()
    clear()
    begin()/end()
    ++, -- 返回前驱和后继,时间复杂度 O(logn)
 
    set/multiset
        insert()  插入一个数
        find()  查找一个数
        count()  返回某一个数的个数
        erase()
            (1) 输入是一个数x,删除所有x   O(k + logn)
            (2) 输入一个迭代器,删除这个迭代器
        lower_bound()/upper_bound()
            lower_bound(x)  返回大于等于x的最小的数的迭代器
            upper_bound(x)  返回大于x的最小的数的迭代器
    map/multimap
        insert()  插入的数是一个pair
        erase()  输入的参数是pair或者迭代器
        find()
        []  注意multimap不支持此操作。 时间复杂度是 O(logn)
        lower_bound()/upper_bound()
unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
    和上面类似,增删改查的时间复杂度是 O(1)
    不支持 lower_bound()/upper_bound(), 迭代器的++,--
bitset, 圧位
    bitset<10000> s;
    ~, &, |, ^
    >>, <<
    ==, !=
    []
 
    count()  返回有多少个1
 
    any()  判断是否至少有一个1
    none()  判断是否全为0
 
    set()  把所有位置成1
    set(k, v)  将第k位变成v
    reset()  把所有位变成0
    flip()  等价于~
    flip(k) 把第k位取反

常用库函数

C++帮我们实现好了很多有用的函数,我们要避免重复造轮子

#include算法库

reverse 翻转(十星重要度)

翻转一个vector:

reverse(a.begin(), a.end());

翻转一个数组,元素存放在下标1~n:

reverse(a + 1, a + 1 + n);

 
 cout<<"*****vector翻转*******"<<endl;
    vector<int> a({1,2,3,4,5});
    reverse(a.begin(),a.end());
    for(int x:a)cout<<x<<" ";
    cout<<endl;
    
 cout<<"*****数组翻转**********"<<endl;
    int b[]={1,2,3,4,5};
    reverse(b,b+5);
    for(int y:b)cout<<y<<" ";
    cout<<endl;

unique 去重

返回去重之后的尾迭代器(或指针),仍然为前闭后开,即这个迭代器是去重之后末尾元素的下一个位置。该函数常用于离散化,利用迭代器(或指针)的减法,可计算出去重后的元素个数。

把一个vector去重:

int m = unique(a.begin(), a.end()) – a.begin();

把一个数组去重,元素存放在下标1~n:

int m = unique(a + 1, a + 1 + n) – (a + 1);

 
    cout<<"*****vector去重**********"<<endl;
    vector<int> a1({1,1,2,2,3,3,4,5,8,8,8,8,8,8});
    int n=unique(a1.begin(),a1.end())-a1.begin();
    cout<<"去掉重复数剩余:"<<n<<endl;
    for(int i=0;i<n;i++)cout<<a1[i]<<" ";
    cout<<endl;
    
    cout<<"*****数组去重**********"<<endl;
    int b1[]={1,1,2,2,3,3,4,5,8,8,8,8,8,8};
    int m=unique(b1,b1+14)-b1;
    cout<<"去掉重复数剩余:"<<m<<endl;
    for(int i=0;i<m;i++)cout<<b1[i]<<" ";
    cout<<endl;

random_shuffle 随机打乱

用法与reverse相同

 
    cout<<"*****生成随机数*********"<<endl;
    vector<int> c({1,1,2,8,5,8});
    srand((time(0)));//需要生成随机数
    random_shuffle(c.begin(),c.end());
    for(int q:c)cout<<q<<" ";
    cout<<endl;

sort(十星重要度)

对两个迭代器(或指针)指定的部分进行快速排序。可以在第三个参数传入定义大小比较的函数,或者重载“小于号”运算符。

把一个int数组(元素存放在下标1~n)从大到小排序,传入比较函数:

int a[MAX_SIZE];
bool cmp(int a, int b) {return a > b; }
sort(a + 1, a + 1 + n, cmp);

把自定义的结构体vector排序,重载“小于号”运算符:

方法一:

struct rec{ int id, x, y; }
vector a;
bool operator <(const rec &a, const rec &b) {
return a.x < b.x ||a.x == b.x && a.y < b.y;
}
sort(a.begin(), a.end());

方法二:(推荐)

struct rep
{
int x,y;
}r[5];
//结构体的比较函数
bool cmp1(rep a,rep b) //自己决定如何排序
{
return a.x
}
 
//定义的结构体
struct rep
{
    int x,y;
}r[5];
//结构体的比较函数
bool cmp1(rep a,rep b) //自己决定如何排序
{
    return a.x<a.y;//这里决定sort排序是升序还是降序
}
 
//数组的比较函数
bool cmp(int a,int b) //自己决定如何排序
{
    return a>b;//这里决定sort排序是升序还是降序
}
 
    cout<<"*****随机数排序*********"<<endl;
    sort(c.begin(),c.end(),cmp);
    for(int q1:c)cout<<q1<<" ";
    cout<<endl;
    
    cout<<"*****结构体排序*********"<<endl;
    
    for(int i=0;i<5;i++)
    {
        r[i].x=-i;
        r[i].y=i;
    }
    cout<<"排序前结构体"<<endl;
    for(int i=0;i<5;i++)printf("(%d,%d) ",r[i].x,r[i].y);
    cout<<endl;
    sort(r,r+5,cmp1);
    cout<<"排序后结构体"<<endl;
    for(int i=0;i<5;i++)printf("(%d,%d) ",r[i].x,r[i].y);

lower_bound/upper_bound 二分

lower_bound 的第三个参数传入一个元素x,在两个迭代器(指针)指定的部分上执行二分查找,返回指向第一个大于等于x的元素的位置的迭代器(指针)。

upper_bound 的用法和lower_bound大致相同,唯一的区别是查找第一个大于x的元素。当然,两个迭代器(指针)指定的部分应该是提前排好序的。

在有序int数组(元素存放在下标1~n)中查找大于等于x的最小整数的下标

int I = lower_bound(a + 1, a + 1 + n,. x) – a;

在有序vector 中查找小于等于x的最大整数(假设一定存在):

int y = *--upper_bound(a.begin(), a.end(), x);

 
    cout<<"********二分查找*********"<<endl;
    cout<<"大于等于x的最小整数:"<<endl;
    int x[]={1,2,3,4,5,6,9,10};
    int* p=lower_bound(x,x+7,6);
    cout<<"查找到的值为:"<<*p<<endl;
    int l=*p=lower_bound(x,x+7,10)-x;
    cout<<"大于等于x的最小整数下标:"<<l<<endl<<endl;
    
    cout<<"小于等于x的最大整数"<<endl;
    int* q=upper_bound(x,x+7,4);
    cout<<"查找到的值为:"<<*q<<endl;
    int t=*p=upper_bound(x,x+7,4)-x;
    cout<<"小于等于x的最大整数下标:"<<t<<endl;

全部代码段

 
#include<iostream>
#include<algorithm>
#include<vector>
#include<ctime>
#include<cstdio>
 
using namespace std;
 
struct rep
{
    int x,y;
}r[5];
//结构体的比较函数
bool cmp1(rep a,rep b) //自己决定如何排序
{
    return a.x<a.y;//这里决定sort排序是升序还是降序
}
 
//数组的比较函数
bool cmp(int a,int b) //自己决定如何排序
{
    return a>b;//这里决定sort排序是升序还是降序
}
 
int main()
{
    
    cout<<"*****vector翻转*******"<<endl;
    vector<int> a({1,2,3,4,5});
    reverse(a.begin(),a.end());
    for(int x:a)cout<<x<<" ";
    cout<<endl;
    
    cout<<"*****数组翻转**********"<<endl;
    int b[]={1,2,3,4,5};
    reverse(b,b+5);
    for(int y:b)cout<<y<<" ";
    cout<<endl;
    
    cout<<"*****vector去重**********"<<endl;
    vector<int> a1({1,1,2,2,3,3,4,5,8,8,8,8,8,8});
    int n=unique(a1.begin(),a1.end())-a1.begin();
    cout<<"去掉重复数剩余:"<<n<<endl;
    for(int i=0;i<n;i++)cout<<a1[i]<<" ";
    cout<<endl;
    
    cout<<"*****数组去重**********"<<endl;
    int b1[]={1,1,2,2,3,3,4,5,8,8,8,8,8,8};
    int m=unique(b1,b1+14)-b1;
    cout<<"去掉重复数剩余:"<<m<<endl;
    for(int i=0;i<m;i++)cout<<b1[i]<<" ";
    cout<<endl;
    
    cout<<"*****生成随机数*********"<<endl;
    vector<int> c({1,1,2,8,5,8});
    srand((time(0)));//需要生成随机数
    random_shuffle(c.begin(),c.end());
    for(int q:c)cout<<q<<" ";
    cout<<endl;
    cout<<"*****随机数排序*********"<<endl;
    sort(c.begin(),c.end(),cmp);
    for(int q1:c)cout<<q1<<" ";
    cout<<endl;
    
    cout<<"*****结构体排序*********"<<endl;
    
    for(int i=0;i<5;i++)
    {
        r[i].x=-i;
        r[i].y=i;
    }
    cout<<"排序前结构体"<<endl;
    for(int i=0;i<5;i++)printf("(%d,%d) ",r[i].x,r[i].y);
    cout<<endl;
    sort(r,r+5,cmp1);
    cout<<"排序后结构体"<<endl;
    for(int i=0;i<5;i++)printf("(%d,%d) ",r[i].x,r[i].y);
    cout<<endl;
    
    cout<<"********二分查找*********"<<endl;
    cout<<"大于等于x的最小整数:"<<endl;
    int x[]={1,2,3,4,5,6,9,10};
    int* p=lower_bound(x,x+7,6);
    cout<<"查找到的值为:"<<*p<<endl;
    int l=*p=lower_bound(x,x+7,10)-x;
    cout<<"大于等于x的最小整数下标:"<<l<<endl<<endl;
    
    cout<<"小于等于x的最大整数"<<endl;
    int* q=upper_bound(x,x+7,4);
    cout<<"查找到的值为:"<<*q<<endl;
    int t=*p=upper_bound(x,x+7,4)-x;
    cout<<"小于等于x的最大整数下标:"<<t<<endl;
    
    return 0;
}


目录
相关文章
|
13天前
|
存储 C++ 容器
C++STL(标准模板库)处理学习应用案例
【4月更文挑战第8天】使用C++ STL,通过`std:vector`存储整数数组 `{5, 3, 1, 4, 2}`,然后利用`std::sort`进行排序,输出排序后序列:`std:vector<int> numbers; numbers = {5, 3, 1, 4, 2}; std:sort(numbers.begin(), numbers.end()); for (int number : numbers) { std::cout << number << " "; }`
17 2
|
9天前
|
编译器 C语言 C++
【C++初阶(九)】C++模版(初阶)----函数模版与类模版
【C++初阶(九)】C++模版(初阶)----函数模版与类模版
18 0
|
9天前
|
存储 算法 C++
【C++初阶】STL详解(九) priority_queue的使用与模拟实现
【C++初阶】STL详解(九) priority_queue的使用与模拟实现
20 0
|
9天前
|
存储 算法 编译器
【C++初阶】STL详解(三)vector的介绍与使用
【C++初阶】STL详解(三)vector的介绍与使用
32 0
|
9天前
|
存储 编译器 C++
【C++初阶】STL详解(四)vector的模拟实现
【C++初阶】STL详解(四)vector的模拟实现
42 1
|
11天前
|
C++
glog --- C++日志库
glog --- C++日志库
|
14天前
|
存储 算法 C语言
【C++初阶】8. STL初阶 + String类
【C++初阶】8. STL初阶 + String类
48 1
|
24天前
|
存储 C++ 容器
C++入门指南:string类文档详细解析(非常经典,建议收藏)
C++入门指南:string类文档详细解析(非常经典,建议收藏)
32 0
|
24天前
|
存储 编译器 C语言
C++入门: 类和对象笔记总结(上)
C++入门: 类和对象笔记总结(上)
31 0
|
2天前
|
存储 安全 C语言
【C++】string类
【C++】string类

热门文章

最新文章