前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >C++ STL 详解

C++ STL 详解

作者头像
Fivecc
发布2022-11-21 16:20:30
1.1K0
发布2022-11-21 16:20:30
举报
文章被收录于专栏:前端ACE

以前一直在用C语言,很多数据结构都是自己造的,比如链表、队列等,但是搞竞赛还是C++ 有优势,感觉好多题都是针对C++ 出题的  所以打算学学C++,所以现在先整理一下STL中一些最常用的容器的使用方法和迭代器备用。

容器(Container)

迭代器(Iterator)

1、容器

作为STL的最主要组成部分--容器,分为向量(vector),双端队列(deque),表(list),队列(queue),堆栈(stack),集合(set),多重集合(multiset),映射(map),多重映射(multimap)。

容器

特性

所在头文件

向量vector

可以用常数时间访问和修改任意元素,在序列尾部进行插入和删除时,具有常数时间复杂度,对任意项的插入和删除就有的时间复杂度与到末尾的距离成正比,尤其对向量头的添加和删除的代价是惊人的高的

<vector>

双端队列deque

基本上与向量相同,唯一的不同是,其在序列头部插入和删除操作也具有常量时间复杂度

<deque>

表list

对任意元素的访问与对两端的距离成正比,但对某个位置上插入和删除一个项的花费为常数时间。

<list>

队列queue

插入只可以在尾部进行,删除、检索和修改只允许从头部进行。按照先进先出的原则。

<queue>

堆栈stack

堆栈是项的有限序列,并满足序列中被删除、检索和修改的项只能是最近插入序列的项。即按照后进先出的原则

<stack>

集合set

由节点组成的红黑树,每个节点都包含着一个元素,节点之间以某种作用于元素对的谓词排列,没有两个不同的元素能够拥有相同的次序,具有快速查找的功能。但是它是以牺牲插入删除操作的效率为代价的

<set>

多重集合multiset

和集合基本相同,但可以支持重复元素具有快速查找能力

<set>

映射map

由{键,值}对组成的集合,以某种作用于键对上的谓词排列。具有快速查找能力

<map>

多重集合multimap

比起映射,一个键可以对应多了值。具有快速查找能力

<map>

3、迭代器

它的具体实现在<itertator>中,我们完全可以不管迭代器类是怎么实现的,大多数的时候,把它理解为指针是没有问题的(指针是迭代器的一个特例,它也属于迭代器),但是,决不能完全这么做。

迭代器功能

输入迭代器 Input iterator

、Reads forward

istream

输出迭代器 Output iterator

向前写 Writes forward

ostream,inserter

前向迭代器 Forward iterator

向前读写 Read and Writes forward

双向迭代器 Bidirectional iterator

向前向后读写 Read and Writes forward and backward

list,set,multiset,map,mul timap

随机迭代器 Random access iterator

随机读写 Read and Write with random access

vector,deque,array,string

C++ STL中最基本以及最常用的类或容器无非就是以下几个:

  • string
  • vector
  • set
  • list
  • map

下面就依次介绍它们,并给出一些最常见的最实用的使用方法,做到快速入门。

string

首先看看我们C语言一般怎么使用字符串的

代码语言:javascript
复制
char* s1 = "Hello SYSU!"; //创建指针指向字符串常量,这段字符串我们是不能修改的

//想要创建 可以修改的字符串,我们可以使用数组分配空间
char s2[20] = "Hello SYSU!";
//或者这样
char s3[] = "Hello SYSU!";

//当然我们也可以动态分配内存
char* s4 = (char*)malloc(20);
gets(s4);

C++ 标准库中的string表示可变长的字符串,它在头文件string里面。

代码语言:javascript
复制
#include <string>

用string初始化字符串分两类:用“=”号就是拷贝初始化,否则就是直接初始化。

代码语言:javascript
复制
string s1;//初始化字符串,空字符串
string s2 = s1; //拷贝初始化,深拷贝字符串
string s3 = "I am Yasuo"; //直接初始化,s3存了字符串
string s4(10, 'a'); //s4存的字符串是aaaaaaaaaa
string s5(s4); //拷贝初始化,深拷贝字符串
string s6("I am Ali"); //直接初始化
string s7 = string(6, 'c'); //拷贝初始化,cccccc
代码语言:javascript
复制
#include <iostream>
#include <string>

using namespace std;

int main()
{
    string s1;//初始化字符串,空字符串
    string s2 = s1; //拷贝初始化,深拷贝字符串
    string s3 = "I am Yasuo"; //直接初始化,s3存了字符串
    string s4(10, 'a'); //s4存的字符串是aaaaaaaaaa
    string s5(s4); //拷贝初始化,深拷贝字符串
    string s6("I am Ali"); //直接初始化
    string s7 = string(6, 'c'); //拷贝初始化,cccccc

    //string的各种操作
    string s8 = s3 + s6;//将两个字符串合并成一个
    s3 = s6;//用一个字符串来替代另一个字符串的对用元素

    cin >> s1;

    cout << s1 << endl;
    cout << s2 << endl;
    cout << s3 << endl;
    cout << s4 << endl;
    cout << s5 << endl;
    cout << s6 << endl;
    cout << s7 << endl;
    cout << s8 << endl;
    cout << "s7 size = " << s7.size() << endl; //字符串长度,不包括结束符
    cout << (s2.empty() ? "This string is empty" : "This string is not empty") << endl;;

    system("pause");
    return 0;
}

string的IO操作

使用cin读入字符串时,遇到空白就停止读取。比如程序输入的是

代码语言:javascript
复制
"     Hello   World"

那么我们得到的字符串将是"Hello",前面的空白没了,后面的world也读不出来。

如果我们想把整个hello world读进来怎么办?那就这样做

代码语言:javascript
复制
cin>>s1>>s2;

hello存在s1里,world存在s2里了。

有时我们想把一个句子存下来,又不想像上面那样创建多个string来存储单词,怎么办?

那就是用getline来获取一整行内容。

代码语言:javascript
复制
string str;
getline(cin, str);
cout << str << endl;

当把string对象和字符面值及字符串面值混在一条语句中使用时,必须确保+的两侧的运算对象至少有一个是string

代码语言:javascript
复制
string s1 = s2 + ", "; //正确
string s3 = "s " + ", "; //错误
string s4 = "hello" + ", " + s1; //错误
string s5 = s1 + "hello " + ", "; //改一下顺序,s1放前头,正确了,注意理解=号右边的运算顺序

处理string中的字符

访问字符串的每个字符

代码语言:javascript
复制
for (int i = 0; i < s3.size(); i++)
{
    cout << s3[i] << endl;
    s3[i] = 's';
}

在C语言中我都是用下标或者指针来访问数组元素,而在C++里,有个新奇的东西叫做迭代器iterator,我们可以使用它来访问容器元素。

代码语言:javascript
复制
string str("hi sysu");
for (string::iterator it = str.begin(); it != str.end(); it++)
{
    cout << *it << endl;
}

我们也可以是使用const_iterator使得访问元素时是能读不能写,这跟常量指针意思差不多。

代码语言:javascript
复制
string str2("hi sysu");
for (string::const_iterator it = str2.begin(); it != str2.end(); it++)
{
    cout << *it << endl;
    *it = 'l'; //这是错误的,不能写
}

string还有一些很好用的函数,比如找子串

代码语言:javascript
复制
string sq("heoolo sdaa ss");
cout << s.find("aa", 0) << endl; //返回的是子串位置。第二个参数是查找的起始位置,如果找不到,就返回string::npos
if (s.find("aa1", 0) == string::npos)
{
    cout << "找不到该子串!" << endl;
}

vector

C++ STL中的verctor好比是C语言中的数组,但是vector又具有数组没有的一些高级功能。与数组相比,vector就是一个可以不用再初始化就必须制定大小的边长数组,当然了,它还有许多高级功能。

要想用vector首先得包含头文件vector。

代码语言:javascript
复制
#include <vector>

怎么初始化?

如果vector的元素类型是int,默认初始化为0;如果vector元素类型为string,则默认初始化为空字符串。

代码语言:javascript
复制
vector<int> v1;
vector<father> v2;
vector<string> v3;
vector<vector<int> >;  //注意空格。这里相当于二维数组int a[n][n];
vector<int> v5 = { 1,2,3,4,5 }; //列表初始化,注意使用的是花括号
vector<string> v6 = { "hi","my","name","is","lee" };
vector<int> v7(5, -1); //初始化为-1,-1,-1,-1,-1。第一个参数是数目,第二个参数是要初始化的值
vector<string> v8(3, "hi");
vector<int> v9(10); //默认初始化为0
vector<int> v10(4); //默认初始化为空字符串

如何向vector添加元素?

请使用push_back加入元素,并且这个元素是被加在数组尾部的。

代码语言:javascript
复制
for (int i = 0; i < 20; i++)
{
    v1.push_back(i);
}

vector其他的操作

访问和操作vector中的每个元素

代码语言:javascript
复制
for (int i = 0; i < v1.size(); i++)
{
    cout << v1[i] << endl;
    v1[i] = 100;
    cout << v1[i] << endl;
}

注意:只能对已存在的元素进行赋值或者修改操作,如果是要加入新元素,务必使用push_back。push_back的作用有两个:告诉编译器为新元素开辟空间、将新元素存入新空间里。

比如下面的代码是错误的,但是编译器不会报错,就像是数组越界。

代码语言:javascript
复制
vector<int> vec;
vec[0] = 1;  //错误!

当然我们也可以选择使用迭代器来访问元素

代码语言:javascript
复制
vector<string> v6 = { "hi","my","name","is","lee" };
for (vector<string>::iterator iter = v6.begin(); iter != v6.end(); iter++)
{
    cout << *iter << endl;
    //下面两种方法都行
    cout << (*iter).empty() << endl;
    cout << iter->empty() << endl; 
}

上面是正向迭代,如果我们想从后往前迭代该如何操作? 使用反向迭代器

代码语言:javascript
复制
for (vector<string>::reverse_iterator iter = v6.rbegin(); iter != v6.rend(); iter++)
{
    cout << *iter << endl;

}

vector最常用的增删操作

代码语言:javascript
复制
#include <iostream>
#include <vector>
#include <string>

using namespace std;

template <typename T>
void showvector(vector<T> v)
{
    for (vector<T>::iterator it = v.begin(); it != v.end(); it++)
    {
        cout << *it;
    }
    cout << endl;
}

int main()
{
    vector<string> v6 = { "hi","my","name","is","lee" };
    v6.resize(3);  //重新调整vector容量大小
    showvector(v6);

    vector<int> v5 = { 1,2,3,4,5 }; //列表初始化,注意使用的是花括号
    cout << v5.front() << endl; //访问第一个元素
    cout << v5.back() << endl; //访问最后一个元素

    showvector(v5);
    v5.pop_back(); //删除最后一个元素
    showvector(v5);
    v5.push_back(6); //加入一个元素并把它放在最后
    showvector(v5);
    v5.insert(v5.begin()+1,9); //在第二个位置插入新元素
    showvector(v5);
    v5.erase(v5.begin() + 3);  //删除第四个元素
    showvector(v5);
    v5.insert(v5.begin() + 1, 7,8); //连续插入7个8
    showvector(v5);
    v5.clear(); //清除所有内容
    showvector(v5);

    system("pause");
    return 0;
} 

注意:虽然vertor对象可以动态增长,但是也或有一点副作用:已知的一个限制就是不能再范围for循环中向vector对象添加元素。另外一个限制就是任何一种可能改变vector对象容量的操作,不如push_back,都会使该迭代器失效。

总而言之就是:但凡使用了迭代器的循环体,都不要向迭代器所属的容器添加元素!

C++中push_back和insert两个有什么区别?

顾名思义push_back把元素插入容器末尾,insert把元素插入任何你指定的位置。 不过push_back速度一般比insert快。如果能用push_back尽量先用push_back。

set

set跟vector差不多,它跟vector的唯一区别就是,set里面的元素是有序的且唯一的,只要你往set里添加元素,它就会自动排序,而且,如果你添加的元素set里面本来就存在,那么这次添加操作就不执行。要想用set先加个头文件set。

代码语言:javascript
复制
#include <set>
代码语言:javascript
复制
#include <iostream>
#include <set>
#include <string>

using namespace std;

template <typename T>
void showset(set<T> v)
{
    for (set<T>::iterator it = v.begin(); it != v.end(); it++)
    {
        cout << *it;
    }
    cout << endl;
}

int main()
{
    set<int> s1{9,8,1,2,3,4,5,5,5,6,7,7 }; //自动排序,从小到大,剔除相同项
    showset(s1);
    set<string> s2{ "hello","sysy","school","hello" }; //字典序排序
    showset(s2);
    s1.insert(9); //有这个值了,do nothing
    showset(s1);
    s2.insert("aaa"); //没有这个字符串,添加并且排序
    showset(s2);
    
    system("pause");
    return 0;
} 

list

list就是链表,在C语言中我们想使用链表都是自己去实现的,实现起来倒不难,但是如果有现成的高效的链表可以使用的话,我们就不需要重复造轮子了。STL就提供了list容器给我们。

list是一个双向链表,而单链表对应的容器则是foward_list。

list即双向链表的优点是插入和删除元素都比较快捷,缺点是不能随机访问元素。

初始化方式就大同小异了,跟vector基本一样。要想用list先加个头文件list。

代码语言:javascript
复制
#include <list>
代码语言:javascript
复制
#include <iostream>
#include <list>
#include <string>

using namespace std;

template <typename T>
void showlist(list<T> v)
{
    for (list<T>::iterator it = v.begin(); it != v.end(); it++)
    {
        cout << *it;
    }
    cout << endl;
}

int main()
{
    list<int> l1{ 1,2,3,4,5,5,6,7,7 };
    showlist(l1);
    list<double> l2;
    list<char> l3(10);
    list<int> l4(5, 10); //将元素都初始化为10
    showlist(l4);

    
    system("pause");
    return 0;
} 

值得注意的是,list容器不能调用algorithm下的sort函数进行排序,因为sort函数要求容器必须可以随机存储,而list做不到。所以,list自己做了一个自己用的排序函数,用法如下:

代码语言:javascript
复制
list<int> l1{ 8,5,7,6,1,2,3,4,5,5,6,7,7 };
l1.sort();

map

map运用了哈希表地址映射的思想,也就是key-value的思想,来实现的。

首先给出map最好用也最最常用的用法例子,就是用字符串作为key去查询操作对应的value。

要使用map得先加个头文件map。

代码语言:javascript
复制
#include <map>
代码语言:javascript
复制
#include <iostream>
#include <map>
#include <string>

using namespace std;

void showmap(map<string, int> v)
{
    for (map<string, int>::iterator it = v.begin(); it != v.end(); it++)
    {
        cout << it->first << "  " << it->second << endl;  //注意用法,不是用*it来访问了。first表示的是key,second存的是value
    }
    cout << endl;
}

int main()
{
    map<string, int> m1; //<>里的第一个参数表示key的类型,第二个参数表示value的类型
    m1["Kobe"] = 100;
    m1["James"] = 99;
    m1["Curry"] = 98;

    string s("Jordan");
    m1[s] = 90;

    cout << m1["Kobe"] << endl;
    cout << m1["Jordan"] << endl;
    cout << m1["Durant"] << endl; //不存在这个key,就显示0

    m1.erase("Curry");//通过关键字来删除
    showmap(m1);
    m1.insert(pair<string, int>("Harris", 89)); //也可以通过insert函数来实现增加元素
    showmap(m1);
    m1.clear(); //清空全部


    system("pause");
    return 0;
}

如果想看看某个存不存在某个key,可以用count来判断

代码语言:javascript
复制
if (m1.count("Lee"))
{
    cout << "Lee is in m1!" << endl;
}
else
{
    cout << "Lee do not exist!" << endl;
}

用迭代器来访问元素

代码语言:javascript
复制
for (map<string, int>::iterator it = m1.begin(); it != m1.end(); it++)
{
    cout << it->first<<"  "<<it->second << endl;  //注意用法,不是用*it来访问了。first表示的是key,second存的是value
}

常用算法:

accumulate() 元素累加

adjacent_difference() 相邻元素的差额

adjacent_find() 搜寻相邻的重复元素

binary_search() 二元搜寻

copy() 复制

copy_backward() 逆向复制

count() 计数

count_if() 在特定条件下计数

equal() 判断相等与否

equal_range() 判断相等与否(传回一个上下限区间范围)

fill() 改填元素值

fill_n() 改填元素值,n 次

find() 搜寻

find_if() 在特定条件下搜寻

find_end() 搜寻某个子序列的最后一次出现地点

find_first_of() 搜寻某些元素的首次出现地点

for_each() 对范围内的每一个元素施行某动作

generate() 以指定动作的运算结果充填特定范围内的元素

generate_n() 以指定动作的运算结果充填 n 个元素内容

includes() 涵盖於

inner_product() 内积

inplace_merge() 合并并取代(覆写)

iter_swap() 元素互换

lexicographical_compare() 以字典排列方式做比较

lower_bound() 下限

max() 最大值

max_element() 最大值所在位置

min() 最小值

min_element() 最小值所在位置

merge() 合并两个序列

mismatch() 找出不吻合点

next_permutation() 获得下一个排列组合

泛型演算法(Generic Algorithms)与 Function Obje4 cts

nth_element() 重新安排序列中第n个元素的左右两端

partial_sort() 局部排序

partial_sort_copy() 局部排序并复制到它处

partial_sum() 局部总和

partition() 切割

prev_permutation() 获得前一个排列组合

random_shuffle() 随机重排

remove() 移除某种元素(但不删除)

remove_copy() 移除某种元素并将结果复制到另一个 container

remove_if() 有条件地移除某种元素

remove_copy_if() 有条件地移除某种元素并将结果复制到另一个 container

replace() 取代某种元素

replace_copy() 取代某种元素,并将结果复制到另一个 container

replace_if() 有条件地取代

replace_copy_if() 有条件地取代,并将结果复制到另一个 container

reverse() 颠倒元素次序

reverse_copy() 颠倒元素次序并将结果复制到另一个 container

rotate() 旋转

rotate_copy() 旋转,并将结果复制到另一个 container

search() 搜寻某个子序列

search_n() 搜寻「连续发生 n 次」的子序列

set_difference() 差集

set_intersection() 交集

set_symmetric_difference() 对称差集

set_union() 联集

sort() 排序

stable_partition() 切割并保持元素相对次序

stable_sort() 排序并保持等值元素的相对次序

swap() 置换(对调)

swap_range() 置换(指定范围)

transform() 以两个序列为基础,交互作用产生第三个序列

unique() 将重复的元素摺叠缩编,使成唯一

unique_copy() 将重复的元素摺叠缩编,使成唯一,并复制到他处

upper_bound() 上限

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019-03-13,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • string
    • string的IO操作
      • 处理string中的字符
      • vector
      • set
      • list
      • map
      相关产品与服务
      容器服务
      腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档