STL学习笔记
目录
一、容器
二、容器方法
*** 1.vector 动态数组 ***
***2.deque 双端队列***
*** 3.list 双向链表 ***
*** 4.set 关联容器,不允许有重复的 ***
*** 5.multiset 可以有重复 ***
*** 6.unordered_set / unordered_multiset ***
*** 7.map 关联容器,“键-值”对 唯一 ***
*** 8.multimap “键-值”对 键可重复 ***
*** 9.unordered_map / unordered_multimap ***
*** 10.stack LIFO “栈” ***
*** 11.queue FIFO "队列" ***
*** 12.priority-queue 优先队列 ***
*** 13.string 字符串 ***
一、容器
在STL中实现的容器有如下:
| Container | Description | Header File | Iterator(迭代器) |
| -------------- | ---------------------------- | ----------- | ---------------- |
| vector | 动态数组 | <vector> | Random Access |
| list | "链表" | <list> | Bidirectional |
| deque | 双端队列 | <deque> | Random Access |
| set | 关联容器,不允许有重复的 | <set> | Bidirectional |
| multiset | 关联容器,允许有重复元素 | <set> | Bidirectional |
| map | 关联容器,“键-值”对 唯一 | <map> | Bidirectional |
| multimap | 关联容器,“键-值”对 键可重复 | <map> | Bidirectional |
| stack | LIFO “栈” | <stack> | No Iterator |
| queue | FIFO "队列" | <queue> | NO Iterator |
| priority-queue | 优先队列 | <queue> | NO Iterator |
容器分类:
- Sequence Container 顺序容器
- vector
- deque
- list
- Associate Container 关联容器
- set
- multiset
- map
- multimap
- Derived Container 派生容器
- stack
- queue
- priority-queue
二、容器方法
*** 1.vector 动态数组 ***
--insert 插入
(1)insert( const_iterator pos, T&& value ); 在指定位置前插入 value
例子:insert(v.begin(),1) 在首位前插入元素1
(2)insert( const_iterator pos, size_type count, const T& value ); 在指定位置前插入 count 个 value
例子:insert(v.begin(),5,,1) 在首位前插入 5 元素 1
(3) insert( const_iterator pos, InputIt first, InputIt last ); 在指定位置前插入 [first,last) 里的元素
注意:若 InputIt 为整数类型,则此重载与重载 (2) 拥有相同效果。
例子 insert(v.begin(),1,,5) 则在首位前插入一个 5
--push_back 在末尾插入元素
例子:push_back(1) 在末尾插入元素 1
--pop_back 删除末尾元素元素
例子: v.pop_back()
--clear 清除容器内全部内容
例子: v.clear()
--emplace 原位构造函数
emplace( const_iterator pos, Args&&... args ); 在 pos 前构造元素
例子:v.(v.begin(),1) 在首位前构造元素 1
--emplace_back
emplace_back( Args&&... args ); 在末尾构造元素
例子:v.emplace_back(1) 在在末尾后构造元素 1
--erase 擦除元素
(1) erase( const_iterator pos ); 移除位于 pos 的元素。
例子:v.erase(v.begin()); 移除位于首位的元素
(2) erase( const_iterator first, const_iterator last ); 移除范围 [first; last) 中的元素。
例子: v.erase(v.begin(),v.end()); 移除范围 [v.begin(),v.end()) 中的元素
注意:end()不能为 pos 值
(3) template< class T, class Alloc, class U >
void erase(std::vector<T,Alloc>& c, const U& value);
从容器中擦除所有比较等于 value 的元素
(4) template< class T, class Alloc, class Pred >
void erase_if(std::vector<T,Alloc>& c, Pred pred);
从容器中擦除所有满足 pred 的元素
--reserve 预留存储空间
void reserve( size_type new_cap );
增加 vector 的容量到大于或等于 new_cap 的值。若 new_cap 大于当前的 capacity() ,则分配新存储,否则该方法不做任何事。
reserve() 不更改 vector 的 size 。
--resize 改变容器中可存储元素的个数
void resize( size_type count );
重设容器大小以容纳 count 个元素。
若当前大小大于 count ,则减小容器为其首 count 个元素。
--swap 交换
void swap( vector& other )
将内容与 other 的交换。不在单个元素上调用任何移动、复制或交换操作。
--empty 检查容器是否为空
bool empty()
--size 返回容纳的元素数
size_type size()
--max_size 返回可容纳的最大元素数
size_type max_size()
--capacity 返回当前存储空间能够容纳的元素数
size_type capacity()
--shrink_to_fit 通过释放未使用的内存减少内存的使用
void shrink_to_fit();
请求移除未使用的容量。
它是减少 capacity() 到 size()非强制性请求。请求是否达成依赖于实现。
***2.deque 双端队列***
和 vector 基本相同
扩展:
--push_front 插入元素到容器起始
--pop_front 移除首元素
--emplace_front 在容器头部就地构造元素
*** 3.list 双向链表 ***
和 deque 基本相同
扩展:
--merge 合并二个已排序列表
void merge( list&& other );
归并二个已排序链表为一个。链表应以升序排序。不复制元素。操作后容器 other 变为空。若 other 与 *this 指代同一对象则函数不做任何事
--splice 从另一个list中移动元素
(1) void splice( const_iterator pos, list&& other );
从 other 转移所有元素到 *this 中。元素被插入到 pos 所指向的元素之前。
操作后容器 other 变为空。若 other 与 *this 指代同一对象则行为未定义。
(2)void splice( const_iterator pos, list&& other, const_iterator it );
从 other 转移 it 所指向的元素到 *this 。元素被插入到 pos 所指向的元素之前。
(3)void splice( const_iterator pos, list&& other,const_iterator first, const_iterator last );
从 other 转移范围 [first, last) 中的元素到 *this 。元素被插入到 pos 所指向的元素之前。
若 pos 是范围 [first,last) 中的迭代器则行为未定义。
--reverse 将该链表的所有元素的顺序反转
--unique 删除连续的重复元素
size_type unique(); 从容器移除所有 相继 的重复元素。只留下相等元素组中的第一个元素。
--sort 对元素进行排序
(1)void sort(); 以升序排序元素
(2)template< class Compare >
void sort( Compare comp );
例子:l.sort(greater<int>()); 升序排列
l.sort(less<int>()); 降序排列
--remove/remove_if 移除所有满足特定标准的元素
(1)size_type remove( const T& value );
例子:l.remove(1) 移除全部 1 元素
(2) template< class UnaryPredicate >
size_type remove_if( UnaryPredicate p );
例子:l.remove_if([](int n){ return n > 10; }) 移除全部大于 10 的元素
*** 4.set 关联容器,不允许有重复的 ***
--insert
(1)std::pair<iterator,bool> insert( value_type&& value ); 插入元素
例子:s.insert(1); 插入元素 1
(2)template< class InputIt >
void insert( InputIt first, InputIt last ); 插入 [first,last) 范围内的元素
例子: int a[]={1,2,3};
s.insert(a,a+3); 插入 [a,a+3) 范围内的元素
--empty
--clear
--size
--max_size
--swap
--erase 移除元素
(1)iterator erase( iterator pos ); 移除位于 pos 位置的元素
(2)iterator erase( const_iterator first, const_iterator last ); 移除范围 [first; last) 中的元素,它必须是 *this 中的合法范围
(3)size_type erase( const key_type& key ); 移除关键等于 key 的元素(若存在一个)
--emplace
template< class... Args >
std::pair<iterator,bool> emplace( Args&&... args );
若容器中无拥有该关键的元素,则插入以给定的 args 原位构造的新元素到容器。
--emplace_hint
template <class... Args>
iterator emplace_hint( const_iterator hint, Args&&... args );
插入新元素到容器中尽可能接近于恰在 hint 前的位置。原位构造元素,即不进行复制或移动操作。
--merge 从另一容器接合结点(C++17)
--count 返回匹配特定键的元素数量 (因为没有重复元素,所以一般为 1 或 0)
--find 寻找带有特定键的元素
--contains 检查容器是否含有带特定关键的元素 (c++20)
--equal_range 返回容器中所有拥有给定关键的元素范围。范围以二个迭代器定义,一个指向首个不小于 key 的元素,
另一个指向首个大于 key 的元素
--lower_bound 返回指向首个不小于给定键的元素的迭代器
--upper_bound 返回指向首个大于给定键的元素的迭代器
*** 5.multiset 可以有重复 ***
和set一样,区别在于可以元素重复
*** 6.unordered_set / unordered_multiset ***
体内实现了哈希表,是无序的,查找时间为常量级(单个)
*** 7.map 关联容器,“键-值”对 唯一 ***
--empty
--size
--max_size
--erase 与set类似 三种方法
--clear 清除容器内全部内容
--merge 从另一容器接合结点(C++17)
--count 返回匹配特定键的元素数量 (因为没有重复元素,所以一般为 1 或 0)
--find 寻找带有特定键的元素
--contains 检查容器是否含有带特定关键的元素 (c++20)
--equal_range 返回容器中所有拥有给定关键的元素范围。范围以二个迭代器定义,一个指向首个不小于 key 的元素,
另一个指向首个大于 key 的元素
--lower_bound 返回指向首个不小于给定键的元素的迭代器
--upper_bound 返回指向首个大于给定键的元素的迭代器--insert 插入元素
(1) std::pair<iterator,bool> insert( value_type&& value ); 插入 value
例子:(6种方法)
map<int,string> m;
m[1] = "hh";
m.insert(map<int,string>::value_type(2,"ss"));
m.insert(pair<int,string>(3,"ee"));
m.insert(make_pair<int,string>(4,"gg"));
m.insert({6,"ww"});
m.insert({{7,"tt"},{8,"oo"}});
(注意:此为列表模式 如:{map<int,string>::value_type(2,"ss"),map<int,string>::value_type(2,"ss")}也可以)
for(auto i = m.begin(); i != m.end(); ++i)
{
cout << "key:" << i->first << " value:" << i->second << endl;
}
(2) iterator insert( const_iterator hint, value_type&& value ); 插入 value 到尽可能接近
例子: m.insert(m.begin(),pair<int,string>(5,"aa"));
*** 8.multimap “键-值”对 键可重复 ***
与map类似
--inseert (5种方法)
multimap<int,string> m;
m.insert(map<int,string>::value_type(2,"ss"));
m.insert(pair<int,string>(3,"ee"));
m.insert(make_pair<int,string>(4,"gg"));
m.insert({6,"ww"});
m.insert({{7,"tt"},{8,"oo"}});
*** 9.unordered_map / unordered_multimap ***
使用方法和map一样
体内实现了哈希表,是无序的,查找时间为常量级(单个)
*** 10.stack LIFO “栈” ***
注意:stack<int> 等价于 stack<int,deque<int>> 即 默认使用 deque
注意:stack是一个适配器
stack的三种写法
satck<int,vector<int>> 、stack<int,list<int>> 、 stack<int,deque<int>>
注意:stack<int> 等价于 stack<int,deque<int>>
--top 访问栈顶元素 返回 stack 中顶元素的引用
--empty
--size
--push 向栈顶插入元素
--pop 删除栈顶元素
--emplace 于顶原位构造元素
--swap
*** 11.queue FIFO "队列" ***
注意queue是一个适配器
注意: queue<int> 等价于 queue<<int,deque<int>> 即 默认使用 deque
queue的写法 queue<int,list<int>> 、 queue<int,deque<int>>
--empty
--size
--push 向队列尾部插入元素
--pop 删除栈顶元素
--emplace 于尾部原位构造元素
--swap
--front 访问第一个元素
--back 访问最后一个元素
*** 12.priority-queue 优先队列 ***
注意queue是一个适配器 分为最大优先值排序、最小优先值排序
注意: priority_queue<int> 等价于 priority_queue<<int,vector<int>> 即 默认使用 vector
queue的写法 priority_queue<int,deque<int>> 、 priority_queue<int,vector<int>>
注意:queue默认由大到小排序 即
priority_queue<int> pq;
pq.push(2);
pq.push(1);
py.push(4);
py.push(3);
其内部排序为 4 3 2 1
想要按由最小优先值排序可加greater 如 priority_queue<int,deque<int>,greater<int>>
--top 访问栈顶元素
--empty
--size
--push 插入元素,并对底层容器排序
--pop 删除栈顶元素
--emplace 原位构造元素并排序底层容器
--swap
*** 13.string 字符串 ***
--size()/length() :返回字符串的长度,实际字符的个数,不包含'\0'
如: s1.size(), s1.length()
--at(): 返回字符串中指定位置的那个字符,如果指定位置超过字符串的长度(越界),就会抛出异常.
如:
char ch = s1.at(5);
--c_str() :将C++中的字符串对象转换成C语言中的字符串(const char*)
如:
const char* p = s1.c_str();
--empty() :判断字符串是否为空,返回值为bool类型
如:
if (s1.empty())
{}
--find() : 查找指定的字符或字符串,返回字符或字符串首次出现的位置(下标)
如:
str.find('a', 2) ;//从下标2的位置开始查找字符 'a'
str.find(str1) ;//查找字符串str1在str中首次出现的位置
--substr(): 裁剪字符串
如:
str.substr(2) ; //从下标2的位置开始裁剪,舍弃前两个字符
str.substr(3,2); //从下标3的位置开始裁剪,裁剪两个字符
--swap(): 交换两个字符串的内容
如:
str.swap(str1)
--clear(): 清除字符串的内容
如 :
str.clear()
--find
--compare 比较二个字符串
--max_size
--begin
--front
--end
--back
--data 返回指向字符串首字符的指针
--reserve 保留存储
--capacity 返回当前对象分配的存储空间能保存的字符数量
--shrink_to_fit 通过释放不使用内存减少内存使用
--starts_with 检查 string 是否始于给定前缀
--ends_with 检查 string 是否终于给定后缀
--copy
size_type copy( CharT* dest,
size_type count,
size_type pos = 0) const;
复制子串 [pos, pos+count) 到 dest 所指向的字符串