C++八股——STL相关

发布时间:2024年01月13日

C++的STL(Standard Template Library,标准模板库)包括以下六大主要组件:

容器(Containers):

vector:动态数组,支持随机访问和高效内存管理。
list:双向链表,支持高效插入和删除操作,但不支持随机访问。
deque:双端队列,两端都可以高效地进行插入和删除元素,同时支持随机访问。
stack:后进先出(LIFO)的数据结构,基于容器实现(如通常基于deque或vector)。
queue:先进先出(FIFO)的数据结构,同样基于容器实现。
priority_queue:优先队列,其中元素总是保持排序状态,最高优先级的元素总是在顶部。
set:有序集合,不允许重复元素,内部自动排序。
map:关联数组或键值对集合,键是唯一的且自动排序。
multiset 和 multimap:允许键重复的集合和映射。
迭代器(Iterators):

提供了一种统一的方式来遍历容器中的元素,它们是通用化的指针,可以用来读取或修改容器中的数据,并在不同容器之间提供一种抽象接口。
算法(Algorithms):

一系列函数模板,用于执行常见的数据处理任务,如排序、搜索、计数、复制、填充等,这些算法可以作用于任何满足迭代器要求的容器上。
仿函数(Functors 或 Function Objects):

类似于函数的对象,重载了 () 操作符,可以在算法中用作谓词或其他可调用实体。C++11及以后版本引入了lambda表达式,进一步增强了这一功能。
适配器(Adapters):

将一个容器转换为具有不同接口或行为的容器,例如 stack、queue 和 priority_queue 可以看作是其他容器的适配器,还有 queue adaptor(堆栈适配队列)、heap adaptor(堆)等。
空间配置器(Allocators):

定义了如何分配和管理容器所需的内存,允许程序员自定义内存管理策略以适应特定的应用需求。
这些组件相互配合,提供了灵活而强大的工具集,使得C++程序能够更高效地设计和实现各种数据结构相关的问题解决方案。

c++容器常见函数

vector:

push_back(element):在容器末尾添加元素。
pop_back():删除容器末尾的元素。
insert(iterator, element):在迭代器指定的位置插入元素。
erase(iterator):删除迭代器所指向的元素。
at(index):通过索引随机访问元素(抛出异常如果索引越界)。
[index]:通过索引随机访问元素(不检查边界)。
resize(size):改变容器大小,可能增加或减少元素个数。
clear():清空容器内的所有元素。

list:

push_back(element):在链表末尾添加元素。
push_front(element):在链表头部添加元素。
pop_back():删除链表末尾的元素。
pop_front():删除链表头部的元素。
insert(iterator, element):在迭代器指定位置插入元素。
erase(iterator):删除迭代器指向的元素。
remove(value):移除所有等于给定值的元素。

deque:

同样具有与vector类似的push_back, pop_back, push_front, pop_front, insert, erase等方法。
front() 和 back():分别返回首尾元素的引用。

stack:

push(element):将元素压入栈顶。
pop():弹出并删除栈顶元素。
top():返回栈顶元素但不删除(需要保证栈非空)。

queue:

push(element):在队列尾部添加元素(后进)。
pop():从队列头部删除元素(先进)。
front():返回队列头部元素但不删除(需要保证队列非空)。
priority_queue:

push(element):添加元素到优先队列中,按优先级排序。
pop():删除并返回优先级最高的元素。
top():返回但不删除优先级最高的元素。

set:

insert(element):插入元素,若已存在则不插入。
erase(element/iterator):删除指定元素或由迭代器指向的元素。
find(key):查找特定键值,返回一个迭代器指向找到的元素或end()表示未找到。
count(key):返回键值出现次数(在set中始终为1或0)。

map:

insert({key, value}):插入键值对。
erase(key/iterator):删除特定键对应的项或由迭代器指向的项。
find(key):查找键值,返回一个迭代器指向找到的键值对或end()表示未找到。
operator:获取或插入键对应的值(如果不存在,则插入新键值对)。
multiset/multimap:

除了允许重复键之外,其接口与set/map基本相同,包括insert, erase, find, count等操作。

C++各个容器通用函数

C++ STL容器虽然各有特点,但它们都支持一些共同的基本操作。以下是一些常见的通用函数:

迭代器访问:

begin():返回指向容器第一个元素的迭代器(如果为空则返回end())。
end():返回一个“超尾”迭代器,它指向容器最后一个元素之后的位置。
cbegin() 和 cend():与begin和end类似,但返回的是常量迭代器。

大小和容量:

size():返回容器中元素的数量。
empty():检查容器是否为空。
capacity():在某些容器(如vector, deque)中,返回当前分配的空间可容纳的最大元素数量。

插入操作:

insert(iterator position, const T& value):在指定迭代器位置插入一个元素。
对于顺序容器,如vector、deque、list等还提供其他形式的插入方法,例如插入范围或单个值到容器任意位置。

删除操作:

erase(iterator position):删除迭代器所指向的元素。
erase(iterator first, iterator last):删除从first到last之间的所有元素。
对于栈和队列,通常通过pop系列函数来删除元素(如std::stack::pop、std::queue::pop等)。

查找操作:

由于不同容器内部组织方式各异,查找功能由具体算法实现,如std::find(container.begin(), container.end(), value)用于线性查找。
集合类容器如set、map等,提供了基于键的高效查找,如std::set::find(key)、std::map<K,V>::find(key)。

修改内容:

在允许修改元素的容器中,可以通过迭代器直接修改元素值。
容器变换:

clear():清空容器内的所有元素。

需要注意的是,并非所有容器都支持上述所有操作,比如stack和queue只支持顶部元素的添加和删除操作,不直接支持随机访问或遍历。而像priority_queue则有自己特定的插入(push)和删除最高优先级元素(pop)的方法。同时,关联容器如set、map、multiset、multimap除了共享一些基本概念外,其接口也根据各自特性有所不同。

文章来源:https://blog.csdn.net/beidideshu/article/details/135570868
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。