当前位置：首页 > news >正文

c++stl模板总结

news 来源：原创 2025/5/12 2:26:28

stl

总结stl模板
- vector
- deque
- list
- forward_list
- stl集合类
- - set&unorder_set
  - map&unorder_map
- 自适应容器栈和队列
- - stack
  - queue
  - priority_queue

总结stl模板

vector

1.初始化

vector具有多个重载的构造函数，可以在实例化vector时指定他开始时应该包含的元素个数以及元素的初始值，还可以用一个vector初始化另一个vector

vector<int> integers;
vector<int> initVector{1,2,3};//c++11 列表初始化
vector<int> integer=(1,2,3);//初始化10个元素
vector<int> temElments(10);
//用10个元素0初始化vector
vector<int> temElemInit(10, 0);vector<int> copyVector(tenElemInit);
vector<int> partialCopy(a.cbegin(), a.cbegin()+5);

2.常用函数（增删查）

c.insert(it, x) //向任意迭代器it插入一个元素x ，O ( N ) 
c.front()  //返回第一个数据O (1)
c.back() //返回数组中的最后一个数据 O (1) 
c.pop_back()  //删除最后一个数据O (1)
c.push_back(element)   //在尾部加一个数据O (1) 
c.size() //返回实际数据个数（unsigned类型）O (1)
c.resize(n, v)//改变数组大小为n,n个空间数值赋为v，如果没有默认赋值为0c.clear() //清除元素个数O (N)，N为元素个数
c.erase(first, last); //删除[first,last)的所有元素，O ( N )c.begin();
c.end();sort(c.begin(),c.end()); //默认排序
sort(c.begin()+1, end()); //对1，n区间进行从小到大排序

3.遍历

//使用数组访问[]
vector<int> integers{1,2,3};
for(size_t index=0;index<integers.size();index++){cout<<integers[i];//开发时最好使用va.at(intdex),运行阶段检查容器大小，如果索引超出边界，将引发异常
}
//使用指针访问
vecotr<int>::const_iterator elem = integers.cbegin();
while(element!=integers.end()){size_t index = distance(integers.cbegin(), element);cout<<*element<<endl;
}

deque

stl动态数组，与vector类似，但支持在数组开头和末尾插入或删除元素

deque<int> intDeque;

常用函数

dq.push_back()
dq.pop_back();//删除集合最后一个元素
dp.push_front(); 
dp.pop_front();//删除集合第一个元素
dp.size();
dp.clear();
dp.empty();

遍历

for(auto element = intDeque.begin();element!=intDeque.end();++element){
cout<<*element;
}

list

双向链表，插入删除速度快

1.初始化

list<int> listInts;
list<int> list10Int(10);
list<int> list4IntEach1(4,1);
list<int> listCopyAnother(listInts);
list<int> listPartialCopyofAnother(listInts.cbegin(),listInts.cend());

2.常用函数

l.push_back();
l.push_front();
l.insert(interator pos, const T& x);//向指定为位置插入值x
l.insert(interator pos, size_type n, const T& x);l.insert(interator pos, InputIterator f, InputIterator l);
//输入类型InputIterator是一种模板参数类型，可指定任何集合的边界
l.erase(value);
l.erase(l.begin(),l.end());
l.reverse();//对list中的翻转
l.sort();//对元素进行排序
l.sort(SortPredicate_Descending);//指定排序标准bool SortPredicate_Descending(const int& lhs, const int& rhs){return lhs<rhs;
}

forward_list

单向链表

forward_lists<int> flistInt(1,3,4,2,5);
flistInt.remove(2);
flistInt.sort();
fl.push_back();
fl.pop_back();

如果需要频繁插入和删除元素（尤其是在中间），应该使用std::list
要使用list等stl容器存储object时，要实现<和==运算符，以提供排序和删除谓词
无需在两端插入和删除元素时，且不用在中间插入和删除时，请不要使用list，请使用vector
如果不想按照标准进行删除和排序，给sort和remove提供一个谓词函数即可

stl集合类

set&unorder_set

stl容器set、multiset、unorder_set和unorder_multiset

容器set和multiset能够在容器中快速查找key，key是存储在一维容器中的值，set和multiset的区别就在于后者可以存储重复的值，而前者只能存储唯一的值。
**优点：**底层采用红黑树，插入时排序，适合频繁find场景
缺点：无法替换修改元素
set适合频繁查找型，插入删除是红黑树复杂度，替换的操作是先删除元素然后再插入元素

1.实例化

set<int> setInts1;
multiset<int> mulsetInts1;set<int> setInts2(setInts1);
multiset<int> multisetInts2(setInts1.cbegin(),setInts1.cend());

2.常用

s.inserst(value);
s.insert(s1.cbegin(),s2.cend());
s.count(value);
s.size();//容器包含多少元素
s.find(value); return iterator; //在使用迭代器之前需要判断是否到达容器末尾
s.erase(key);
s.erase(element);
s.erase(iLowerBound, iUpperBound);

stl映射类
map, multimap, unorder_map,unordered_multimap
map和multimap底层为红黑树，同样不能修改元素
map

初始化

map<int, string> mapIntToStr1;
multimap<int, string> mmapIntStr1;map<int, string> mapIntToStr2(mapIntToStr1);
map<int,string> mapIntToStr3(mapIntToStr1.cbegin(),mapIntToStr1.cend());
map<int, string, ReverseSort<int>> mapIntToString4(mapIntToStr1.cbegin(),mapIntToStr1.cend()); 
map<int, string>mmapIntToStr2(mmapIntToStr1);

常用函数：

mp.find(key) //返回键为key的映射的迭代器 $O(logN) $ 注意：用find函数来定位数据出现位置，它返回一个迭代器。当数据存在时，返回数据所在位置的迭代器，数据不存在时，返回mp.end ( ) 
mp.end()
mp.erase(it) //删除迭代器对应的键和值O ( 1 ) O(1)O(1)mp.erase(key)//根据映射的键删除键和值 O ( l o g N ) O(logN)O(logN)mp.erase(first,last)删除左闭右开区间迭代器对应的键和值O(last-first)mp.size()返回映射的对数$ O(1)$
mp.insert(make_pair(int, string))
mp.insert(pair<int, string>(1,"one"));mp.clear()清空map中的所有元素O ( N ) O(N)O(N)mp.insert()插入元素，插入时要构造键值对mp.empty(); //如果map为空，返回true，否则返回falsemp.begin() //返回指向map第一个元素的迭代器（地址）mp.end(); //返回指向map尾部的迭代器（最后一个元素的下一个地址）mp.rbegin(); //返回指向map最后一个元素的迭代器（地址）mp.rend(); //返回指向map第一个元素前面(上一个）的逆向迭代器（地址）mp.count(key);//查看元素是否存在，因为map中键是唯一的，所以存在返回1，不存在返回0mp.lower_bound();//返回一个迭代器，指向键值>= key的第一个元素mp.upper_bound();//返回一个迭代器，指向键值> key的第一个元素

用于正向遍历map ：

map<int,int> mp;mp[1] = 2;mp[2] = 3;mp[3] = 4;auto it = mp.begin();while(it != mp.end()) {cout << it->first << " " << it->second << "\n";it ++;}

用于逆向遍历map：

map<int,int> mp;mp[1] = 2;mp[2] = 3;mp[3] = 4;auto it = mp.rbegin();while(it != mp.rend()) {cout << it->first << " " << it->second << "\n";it ++;}

其他：

map&unorder_map

map：内部用红黑树实现，具有自动排序（按键从小到大）功能。空间占用较大。

unordered_map：内部用哈希表实现，内部元素无序杂乱。查找速度非常快。

map非常适合存储键值对，在查找方面，map的性能可能要比stl vector要高，但是查找速度会随着元素的增加而降低，map的复杂度为log级别

unorder_map<int,string> umap;
umap.insert(make_pair(1000, "Thousand");
umap.find(key);//根据键查找迭代器umap.load_factor(); //查找加载因子
umap.max_load_factor(); //查找最大加载因子
umap.max_bucket_count();//查找桶的最大数量

使用场景
需要存储键值对且键值对可能重复时，（如电话簿）
必须保证插入和查找的时间固定时（通常是元素非常多的时候）

疑问？是map快还是umap快

查找速度：由于unorder_map底层采用hash_table，在不发生冲突的情况下，unorder_map的速度更快，在模拟随机插入10万个<int,int>元素，随机查找一个值时，速度相差 $10^3$ 个量级。

解决冲突：采用链式法解决。每个桶（bucket）维护一个链表（或其他数据结构），用于存储所有哈希到该桶的元素。当发生哈希冲突时，新元素将被插入到对应桶的链表中

扩容：插入元素的个数如果大于阈值（um.size()*um.load_factor()，数组长度*装载因子），自动扩容，一般是bucket_size=8, 之后扩容到64.

自适应容器栈和队列

stack

介绍，允许在顶部插入和删除元素，不允许访问中间的元素。

stack默认底层使用deque（双向动态数组）来存储数据，但是可以使用vector和list来存储数据。

stack<int> numsInStack;
stack<double, vector<int>> doublesStackedVec;
stack<int> numsInStackCopy(numsInStack);

2.常用函数

s.push(); //增加元素 O(1) 
s.pop(); //移除栈顶元素 O(1)
s.empty(); //检测栈内是否为空，空为真 O(1) 
s.size(); //返回栈内元素的个数 O(1)
s.top(); //取得栈顶元素（但不删除）O(1)

3.栈的遍历

stack<int> st;
for (int i = 0; i < 10; ++i) st.push(i);
while (!st.empty()) {int tp = st.top(); // 栈顶元素st.pop(); 
}

queue

只允许在末尾插入元素，以及从开头删除元素，queue，不允许访问中间的元素，可以访问开头（front()）和末尾的元素(back()),
std::queue的定义如下：

template<class elementType,class Container = deque<Type>
>class queue;

其中ElementType是queue对象包含的元素的类型，Container是std::queue用于存储其数据的集合类型，可将该模板参数设置为std::list, vector获deque，默认为deque

1.实例化

queue<int> qi;
queue<double, list<double>> dbQInList
queue<int> copyQ(qi);

2.成员函数

q.push(); //在队尾（即最后一个位置）插入一个元素，numsInQ.push(25);
q.pop(); //将队尾（即最开始位置）的元素删除
q.front();//返回向队首元素的引用
q.back(); //返回指向队尾元素的引用
q.empty(); //检查队列是否为空并返回一个bool值
q.size(); //返回队列中的元素

对于queue没有提供begin(), end()等函数 （所以队列不支持遍历），而大多数STL容器都提供了这些函数，包括queue类在底层的deque，vector，list这是有意为之的，因为只允许对queue
执行符合队列行为特征的操作。

priority_queue

priority_queue和queue的不同之处在于，包含最大值的元素在队首，且只能在队首操作
底层默认采用vector作为内部数据结构容器

template<
class elementType,
class Container = vector<Type>
class Compare=less<typename Container::value_type>
>
class priority_queue

1.初始化

priority_queue<int> numsInPrioQ; //使用默认less提供的比较标准，因此队列将值最大的元素放在队首
priority_queue<int, deque<int>, greater<int>> numsInDescendingQ;
priority_queue<int> copyQ(numsInPrioQ);

2.成员函数

pq.push(); 在优先级中插入一个元素
pq.push(); //删除队首元素，即最大的元素
pq.top(); //返回指向队列的最大元素（即队首元素）的引用
pq.empty(); //检查优先级队列是否为空，并返回一个bool值
pq.size(); //返回优先级队列中的元素个数

由以上函数可知，只能使用top()来访问队列中的成员，返回值最大的元素，值最大的元素是通过默认谓词less确定的。

stl

总结stl模板

vector

deque

list

forward_list

stl集合类

set&unorder_set

map&unorder_map

自适应容器栈和队列

stack

queue

priority_queue

相关文章：