开发者社区> 邱节> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

【C++】STL梳理

简介: 【C++】STL梳理
+关注继续查看

image.png


0x1 C++ STL0x1 C++ STL

C++ STL(标准模板库)是一套功能强大的 C++ 模板类,提供了通用的模板类和函数,这些模板类和函数可以实现多种流行和常用的算法和数据结构,如向量链表队列

C++ 标准模板库的核心包括以下三个组件:

  • 容器(Containers):用来管理某类对象的集合。每一种容器都有其优点和缺点,所以为了应付程序中的不同需求,STL 准备了七种基本容器类型。
  • 迭代器(Iterators):用来在一个对象集合的元素上进行遍历动作。这个对象集合或许是个容器,或许是容器的一部分。每一种容器都提供了自己的迭代器,而这些迭代器了解该种容器的内部结构。
  • 算法(Algorithms):用来处理对象集合中的元素,比如 Sort,Search,Copy,Erase 那些元素。通过迭代器的协助,我们只需撰写一次算法,就可以将它应用于任意容器之上,这是因为所有容器的迭代器都提供一致的接口。

STL 的基本观念就是将数据和操作分离。数据由容器进行管理,操作则由算法进行,而迭代器在两者之间充当粘合剂,使任何算法都可以和任何容器交互运作。


00x2 C++ STL常用容器x2 C++ STL常用容器

为了应付程序中的不同需求,STL 准备了两类共七种基本容器类型:

  • 序列式容器(Sequence containers):此为可序群集,其中每个元素均有固定位置—取决于插入时机和地点,和元素值无关。如果你以追加方式对一个群集插入六个元素,它们的排列次序将和插入次序一致。STL提供了三个序列式容器:向量(vector)、双端队列(deque)、列表(list),此外你也可以把 string 和 array 当做一种序列式容器。
  • 关联式容器(Associative containers):此为已序群集,元素位置取决于特定的排序准则以及元素值,和插入次序无关。如果你将六个元素置入这样的群集中,它们的位置取决于元素值,和插入次序无关。STL提供了四个关联式容器:集合(set)、多重集合(multiset)、映射(map)和多重映射(multimap)。

对于容器,主要的操作有:容器的建立、插入元素、删除元素、查询、遍历、计算元素个数、检查元素是否为空、输出容器包含的内容。


0x3 vector0x3 vector

一种序列式容器,事实上和数组差不多,但它比数组更优越。一般来说数组不能动态拓展,因此在程序运行的时候不是浪费内存,就是造成越界。而 vector 正好弥补了这个缺陷,当内存空间不够时,需要重新申请一块足够大的内存并进行内存的拷贝。

0x31 特点

  • 拥有一段连续的内存空间,因此它能非常好的支持随机访问,即 [] 操作符和 .at(),随机访问快。(优点)
  • 当向其头部或中间插入或删除元素时,为了保持原本的相对次序,插入或删除点之后的所有元素都必须移动,所以插入或删除的效率比较低。(缺点)
  • 在后面插入删除元素最快,此时一般不需要移动内存。(优点)

总结:相当于可拓展的数组(动态数组),随机访问快,在头部和中间插入或删除效率低,但在尾部插入或删除效率高,适用于对象简单,变化较小,并且频繁随机访问的场景。


0x32 构造函数

  • vector() :无参数 - 构造一个空的vector
  • vector(size_type num) :数量(num) - 构造一个大小为num,值为Type默认值的Vector
  • vector(size_type num, const TYPE &val):数量(num)和值(val) - 构造一个初始放入num个值为val的元素的Vector
  • vector(const vector &from) :vector(from) - 构造一个与vector from 相同的vector
  • vector(input_iterator start, input_iterator end):迭代器(start)和迭代器(end) - 构造一个初始值为[start,end)区间元素的Vector(注:半开区间).
  • vector(initializer_list il, const allocator_type& alloc = allocator_type())C++11新提供的方法,类似如下方式:
    • std::vectora{1, 2, 3, 4, 5}
    • std::vectora = {1, 2, 3, 4, 5}


0x33 常用API

  • Operators : 对vector进行赋值或比较
    • v1 == v2
    • v1 != v2
    • v1 <= v2
    • v1 >= v2
    • v1 < v2
    • v1 > v2
    • v[]
  • assign():对Vector中的元素赋值
  • at() : 返回指定位置的元素
  • back() : 返回最末一个元素
  • begin() : 返回第一个元素的迭代器
  • capacity() : 返回vector所能容纳的元素数量(在不重新分配内存的情况下)
  • clear() : 清空所有元素
  • empty() : 判断Vector是否为空(返回true时为空)
  • end() : 返回最末元素的迭代器(译注:实指向最末元素的下一个位置)
  • erase() : 删除指定元素
  • front() : 返回第一个元素
  • get_allocator() : 返回vector的内存分配器
  • insert() : 插入元素到Vector中
  • max_size() : 返回Vector所能容纳元素的最大数量(上限)
  • pop_back() : 移除最后一个元素
  • push_back() : 在Vector最后添加一个元素
  • rbegin() : 返回Vector尾部的逆迭代器
  • rend() : 返回Vector起始的逆迭代器
  • reserve() : 设置Vector最小的元素容纳数量
  • resize() : 改变Vector元素数量的大小
  • size() : 返回Vector元素数量的大小
  • swap() : 交换两个Vector


0x34 example

#include <iostream>
#include <vector>
using namespace std;
int main() {
    vector<int> vecTemp;
    for (int i = 0; i < 6; i++) {
        vecTemp.push_back(i);
    }
    for (int i = 0; i < vecTemp.size(); i++) {
        cout << vecTemp[i] << " "; // 输出:0 1 2 3 4 5
    }
    
    std::cout << '\n';
    return 0;
}

Output

0 1 2 3 4 5


00x4 dequex4 deque

deque是Double-Ended Queues(双向队列)的缩写,是双向开口的连续内存空间(动态将多个连续空间通过指针数组接合在一起),随时可以增加一段新的空间。deque 的最大任务就是在这些分段的连续空间上,维护其整体连续的假象,并提供随机存取的接口。


0x41 特点

  • 一旦要在 deque 的头部和尾部增加新空间,便配置一段定量连续空间,串在整个 deque 的头部或尾部,因此不论在头部或尾部插入元素都十分迅速。 (优点)
  • 在中间部分安插元素则比较费时,因为必须移动其它元素。(缺点)
  • deque 是 list 和 vector 的折中方案。兼有 list 的优点,也有 vector 随机访问效率高的优点。

总结:支持随机访问,但效率没有 vector 高,在头部和尾部插入或删除效率高,但在中间插入或删除效率低,适用于既要频繁随机访问,又要关心两端数据的插入与删除的场景。


0x42 构造函数

  • deque queT:queue采用模板类实现,queue对象的默认构造形式
  • deque queT(size):构造大小为size的deque,其中值为T类型的默认值
  • deque queT(size, val):构造大小为size的deque,其中值为val
  • deque(const deque &que):拷贝构造函数
  • deque(input_iterator start, input_iterator end):迭代器构造函数


0x43 常用API

  • back():返回最后一个元素
  • front():返回第一个元素
  • insert()
  • pop_back(): 删除尾部的元素
  • pop_front(): 删除头部的元素
  • push_back():在尾部加入一个元素
  • push_front(): 在头部加入一个元素
  • at():访问指定位置元素
  • operator[] (size_type n):重载[]操作符
  • empty():判断队列是否为空
  • size():返回队列的大小


0x44 example

#include <iostream>
#include <deque>
using namespace std;
int main() {
    std::deque<int> first;                   /// 默认构造形式
    std::deque<int> second(5, 200);     /// 构造大小为5的deque,其中值为200
    std::deque<int> third(second.begin(), second.end());    /// 迭代器构造函数
    std::deque<int> fourth(third);           /// 拷贝构造函数
    /// 迭代器构造函数可用于复制数组
    int myInts[] = {19, 20, 21, 22};
    std::deque<int> fifth(myInts, myInts + sizeof(myInts) / sizeof(int));
    std::cout << "The contents of fifth are:";
    for (std::deque<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';
    return 0;
}

Output

The contents of fifth are: 19 20 21 22


0x5 list0x5 list

List 由双向链表(doubly linked list)实现而成,元素存放在堆中,每个元素都是放在一块内存中。没有空间预留习惯,所以每分配一个元素都会从内存中分配,每删除一个元素都会释放它占用的内存。


0x51 特点

  • 内存空间可以是不连续的,通过指针来进行数据的访问,这个特点使得它的随机存取变得非常没有效率,因此它没有提供 [] 操作符的重载。(缺点)
  • 由于链表的特点,在任意位置的插入和删除效率都较高。(优点)
  • 只支持首尾两个元素的直接存取,想获取其他元素(访问时间一样),则需要遍历链表。(缺点)

总结:不支持随机访问,在任意位置的插入和删除效率都较高,适用于经常进行插入和删除操作并且不经常随机访问的场景。


0x52 构造函数

  • list (const allocator_type& alloc = allocator_type())
  • list (size_type n, const value_type& val = value_type(), const allocator_type& alloc = allocator_type())
  • template list (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type())
  • list (const list& x)


0x53 常用API

  • assign() :给list赋值
  • back() :返回最后一个元素
  • begin() :返回指向第一个元素的迭代器
  • clear() :删除所有元素
  • empty() :如果list是空的则返回true
  • end() :返回末尾的迭代器
  • erase() :删除一个元素
  • front() :返回第一个元素
  • get_allocator() :返回list的配置器
  • insert() :插入一个元素到list中
  • max_size() :返回list能容纳的最大元素数量
  • merge() :合并两个list
  • pop_back() :删除最后一个元素
  • pop_front() :删除第一个元素
  • push_back() :在list的末尾添加一个元素
  • push_front() :在list的头部添加一个元素
  • rbegin() :返回指向第一个元素的逆向迭代器
  • remove() :从list删除元素
  • remove_if() :按指定条件删除元素
  • rend() :指向list末尾的逆向迭代器
  • resize() :改变list的大小
  • reverse() :把list的元素倒转
  • size() :返回list中的元素个数
  • sort() :给list排序
  • splice() :合并两个list
  • swap() :交换两个list
  • unique() :删除list中重复的元素


0x54 example

#include <iostream>
#include <list>
using namespace std;
int main() {
    list<char> listTemp;
    for (char c = 'a'; c <= 'z'; ++c)
        listTemp.push_back(c);
    while (!listTemp.empty()) {
        cout << listTemp.front() << " ";
        listTemp.pop_front();
    }
    return 0;
}

Output

a b c d e f g h i j k l m n o p q r s t u v w x y z


0x6 set0x6 set0x6 set

set(集合)顾名思义,就是数学上的集合,集合中以一种特定的顺序保存唯一的元素。


0x61 特点

  • 使用红黑树实现,其内部元素依据其值自动排序,每个元素值只能出现一次,不允许重复。
  • 每次插入值的时候,都需要调整红黑树,效率有一定影响。(缺点)
  • map 和 set 的插入或删除效率比用其他序列容器高,因为对于关联容器来说,不需要做内存拷贝和内存移动。(优点)

总结:由红黑树实现,其内部元素依据其值自动排序,每个元素值只能出现一次,不允许重复,且插入和删除效率比用其他序列容器高,适用于经常查找一个元素是否在某集合中且需要排序的场景。


0x62 构造函数

  • set():无参数 - 构造一个空的set
  • set(InputIterator first, InputIterator last) :迭代器的方式构造set
  • set(const set &from) :copyd的方式构造一个与set from 相同的set
  • set(input_iterator start, input_iterator end) :迭代器(start)和迭代器(end) - 构造一个初始值为[start,end)区间元素的Vector(注:半开区间).
  • set (initializer_list il, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type())C++11新提供的方法,类似如下方式:
    • std::seta{1, 2, 3, 4, 5};


0x63 常用API

  • begin() :返回指向第一个元素的迭代器
  • clear() :清除所有元素
  • count() :返回某个值元素的个数
  • empty() :如果集合为空,返回true
  • end() :返回指向最后一个元素的迭代器
  • equal_range() :返回集合中与给定值相等的上下限的两个迭代器
  • erase() :删除集合中的元素
  • find() :返回一个指向被查找到元素的迭代器
  • get_allocator() :返回集合的分配器
  • insert() :在集合中插入元素
  • lower_bound() :返回指向大于(或等于)某值的第一个元素的迭代器
  • key_comp() :返回一个用于元素间值比较的函数
  • max_size() :返回集合能容纳的元素的最大限值
  • rbegin() :返回指向集合中最后一个元素的反向迭代器
  • rend() :返回指向集合中第一个元素的反向迭代器
  • size() :集合中元素的数目
  • swap() :交换两个集合变量
  • upper_bound() :返回大于某个值元素的迭代器
  • value_comp() :返回一个用于比较元素间的值的函数


0x64 example

#include <iostream>
#include <set>
using namespace std;
int main() {
    set<int> setTemp;
    setTemp.insert(3);
    setTemp.insert(1);
    setTemp.insert(2);
    setTemp.insert(1);
    for (int it : setTemp) {
        cout << it << " ";
    }
    return 0;
}

Output

1 2 3

当 set 集合中的元素为结构体时,该结构体必须实现运算符 < 的重载:

#include <set>
#include <string>
using namespace std;
struct People {
    string name;
    int age;
    bool operator<(const People p) const {
        return age < p.age;
    }
};
int main(int argc, char *argv[]) {
    set<People> setTemp;
    setTemp.insert({"天理", 19});
    setTemp.insert({"天工", 20});
    setTemp.insert({"天大", 21});
    setTemp.insert({"南开", 18});
    set<People>::iterator it;
    for (it = setTemp.begin(); it != setTemp.end(); it++) {
        printf("学校:%s 就读年龄:%d\n", (*it).name.c_str(), (*it).age);
    }
    return 0;
}

Output

学校:南开 就读年龄:18
学校:天理 就读年龄:19
学校:天工 就读年龄:20
学校:天大 就读年龄:21

可以看到结果是按照年龄由小到大的顺序排列。另外 string 要使用c_str()转换一下,否则打印出的是乱码。

Multiset 和 set 相同,只不过它允许重复元素,也就是说 multiset 可包括多个数值相同

的元素。这里不再做过多介绍。


0x7 map0x7 map

map 由红黑树实现,其元素都是 “键值/实值” 所形成的一个对组(key/value pairs),map 内部自建一颗红黑树,这颗树具有对数据自动排序的功能,所以在 map 内部所有的数据都是有序的。


0x71 特点

  • 每个元素都有一个键,且只能出现一次,不允许重复。
  • 根据 key 值快速查找记录,查找的复杂度基本是 O(logN),如果有 1000 个记录,二分查找最多查找 10次(1024)。(优点)
  • 每次插入值的时候,都需要调整红黑树,效率有一定影响。(缺点)
  • 增加和删除节点对迭代器的影响很小,除了那个操作节点,对其他的节点都没有什么影响。(优点)
  • 对于迭代器来说,可以修改实值,而不能修改 key。

总结:元素为键值对,key 和 value 可以是任意你需要的类型,每个元素都有一个键,且只能出现一次,不允许重复,根据 key 快速查找记录,适用于需要存储一个数据字典,并要求方便地根据key找value的场景。


0x72 构造函数

  • map (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type())
  • template map (InputIterator first, InputIterator last,const key_compare& comp = key_compare(),const allocator_type& = allocator_type())
  • map (const map& x)
  • map (const map& x, const allocator_type& alloc)
  • map (map&& x)
  • map (map&& x, const allocator_type& alloc)
  • map (initializer_list il, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type())


0x73 常用API

  • begin() :返回指向map头部的迭代器
  • clear() :删除所有元素
  • count() :返回指定元素出现的次数
  • empty() :如果map为空则返回true
  • end() :返回指向map末尾的迭代器
  • equal_range() :返回特殊条目的迭代器对
  • erase() :删除一个元素
  • find() :查找一个元素
  • get_allocator() :返回map的配置器
  • insert() :插入元素–
  • key_comp() :返回比较元素key的函数
  • lower_bound() :返回键值>=给定元素的第一个位置
  • max_size() :返回可以容纳的最大元素个数
  • rbegin() :返回一个指向map尾部的逆向迭代器
  • rend() :返回一个指向map头部的逆向迭代器
  • size() :返回map中元素的个数
  • swap() :交换两个map
  • upper_bound() :返回键值>给定元素的第一个位置
  • value_comp() :返回比较元素value的函数


0x74 example

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
    map<int, string> mapTemp;
    mapTemp.insert({1, "后端码匠"});
    mapTemp.insert({2, "音视频开发"});
    mapTemp.insert({3, "后端开发"});
    mapTemp.insert({4, "前端开发"});
    mapTemp.insert({4, "客户端开发"});
    map<int, string>::iterator it;
    for (it = mapTemp.begin(); it != mapTemp.end(); it++) {
        printf("编号:%d 岗位:%s\n", (*it).first, (*it).second.c_str());
    }
    return 0;
}

Output

编号:1 岗位:后端码匠
编号:2 岗位:音视频开发
编号:3 岗位:后端开发
编号:4 岗位:前端开发

multimap 和 map 相同,但允许重复元素,也就是说 multimap 可包含多个键值(key)相同的元素。这里不再做过多介绍。


0x8 容器配接器0x8 容器配接器

除了以上七个基本容器类别,为满足特殊需求,STL还提供了一些特别的(并且预先定义好的)容器配接器,根据基本容器类别实现而成。包括:


0x81 stack

stack(堆栈)实现了一个先进后出(FILO)的数据结构。


0x811 构造函数

  • stack stkT :采用模板类实现,stack对象的默认构造形式
  • stack(const stack &stk) :拷贝构造函数


0x812 常用API

  • size():返回栈中的元素数
  • top():返回栈顶的元素
  • pop():从栈中取出并删除元素
  • push(x):向栈中添加元素x
  • empty():在栈为空时返回true


0x82 queue

queue 容器对元素采取 FIFO(先进先出)的管理策略。也就是说,它是个普通的缓冲区(buffer)。


0x821 构造函数

  • explicit queue (const container_type& ctnr)
  • explicit queue (container_type&& ctnr = container_type())
  • template explicit queue (const Alloc& alloc)
  • template queue (const container_type& ctnr, const Alloc& alloc)
  • template queue (container_type&& ctnr, const Alloc& alloc)
  • template queue (const queue& x, const Alloc& alloc)
  • template queue (queue&& x, const Alloc& alloc)


0x822 常用API

  • back() :返回最后一个元素
  • empty() :如果队列空则返回真
  • front():返回第一个元素
  • pop():删除第一个元素
  • push():在末尾加入一个元素
  • size():返回队列中元素的个数


0x83 priority_queue

优先队列类似队列, 但是在这个数据结构中的元素按照一定的规则排列有序。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高优先级先出 (first in, largest out)的行为特征。首先要包含头文件#include, 他和queue不同的就在于我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队。优先队列具有队列的所有特性,包括队列的基本操作,只是在这基础上添加了内部的一个排序,它本质是一个堆实现的


0x831 构造函数

priority_queue

  • Type 就是数据类型,
  • Container 就是容器类型(Container必须是具备随机存取能力的容器,支持如下方法:empty(), size(), front(), push_back(),pop_back()。比如vector,deque等等,但不能用list。STL里面默认用的是vector)。可选
  • Functional 就是比较的方式。可选


0x832 常用API

  • top() :访问队头元素
  • empty() :队列是否为空
  • size() :返回队列内元素个数
  • push() :插入元素到队尾 (并排序)
  • emplace() :原地构造一个元素并插入队列
  • pop() :弹出队头元素
  • swap() :交换内容

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
算法基础STL
C++ 对模板(Template)支持得很好,STL 就是借助模板把常用的数据结构及其算法都实现了一遍,并且做到了数据结构和算法的分离。
0 0
基于STL泛化编程的演讲比赛 小案例 c++
基于STL泛化编程的演讲比赛 小案例 c++
0 0
C++ STL开发温习与总结(三): 3.C++函数技术
C++ STL开发温习与总结(三): 3.C++函数技术
0 0
C++ STL开发温习与总结(一): 1.C++编程技术
C++ STL开发温习与总结(一): 1.C++编程技术
0 0
C++ STL开发温习与总结(四): 4.C++面向对象机制的实现
C++ STL开发温习与总结(四): 4.C++面向对象机制的实现
0 0
使用 STL 的好处
使用 STL 的好处
0 0
C++ STL编程轻松入门基础
C++ STL编程轻松入门基础 1 初识STL:解答一些疑问 1.1 一个最关心的问题:什么是STL 1.2 追根溯源:STL的历史 1.3 千丝万缕的联系 1.4 STL的不同实现版本 2 牛刀小试:且看一个简单例程 2.1 引子 2.2 例程实作 2.3 历史的评价 2.4 如何运行     作为C++标准不可缺少的一部分,STL应该是渗透在C++程序的角角落落里的。
1018 0
C++ STL知识点小结
1.capacity(容量)与size(长度)的区别。 size(长度)指容器当前拥有的元素个数。 capacity(容量)指容器在必须分配新存储空间之前可以存储的元素总数。 微信公众号: 猿人谷 如果您认为阅读这篇博客让您有些收获,不妨点击一下右下角的【推荐】 如果您希望与我交流互动,欢迎关注微信公众号 本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接。
756 0
+关注
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载