序列式容器
vector list deque
0. 迭代器
前向迭代器
支持++p,*p等操作
双向迭代器
支持--p等操作哦
随机访问迭代器
p+=i 迭代器往后移动i个元素
p+i 返回迭代器后第i个元素的迭代器
p[i] 返回p后面第i个元素的引用
| 迭代器定义方式 | 具体格式 |
|---|---|
| 正向迭代器 | 容器类名::iterator 迭代器名; |
| 常量正向迭代器 | 容器类名::const_iterator 迭代器名; |
| 反向迭代器 | 容器类名::reverse_iterator 迭代器名; |
| 常量反向迭代器 | 容器类名::const_reverse_iterator 迭代器名; |
通过迭代器遍历
for(i=v.begin();i<v.end();++i){
cout<<*i<<endl;
}
array<T,N>(数组容器)，存储N个T类型的元素，长度初始化后不可变
vector
deque
list
forward_list
array,vector,deque常见函数
1.STL array
声明后长度不可变
array<typename T,size_t N>
array<double,10> arr{};//不指定值，默认为0
array<double, 10> values {0.5,1.0,1.5,,2.0};//剩余元素为0
| 成员函数 | 功能 |
|---|---|
| begin() | 返回指向容器中第一个元素的随机访问迭代器。 |
| end() | 返回指向容器最后一个元素之后一个位置的随机访问迭代器，通常和 begin() 结合使用。 |
| rbegin() | 返回指向最后一个元素的随机访问迭代器。 |
| rend() | 返回指向第一个元素之前一个位置的随机访问迭代器。 |
| cbegin() | 和 begin() 功能相同，只不过在其基础上增加了 const 属性，不能用于修改元素。 |
| cend() | 和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
| crbegin() | 和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
| crend() | 和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
| size() | 返回容器中当前元素的数量，其值始终等于初始化 array 类的第二个模板参数 N。 |
| max_size() | 返回容器可容纳元素的最大数量，其值始终等于初始化 array 类的第二个模板参数 N。 |
| empty() | 判断容器是否为空，和通过 size()==0 的判断条件功能相同，但其效率可能更快。 |
| at(n) | 返回容器中 n 位置处元素的引用，该函数自动检查 n 是否在有效的范围内，如果不是则抛出 out_of_range 异常。 |
| front() | 返回容器中第一个元素的直接引用，该函数不适用于空的 array 容器。 |
| back() | 返回容器中最后一个元素的直接应用，该函数同样不适用于空的 array 容器。 |
| data() | 返回一个指向容器首个元素的指针。利用该指针，可实现复制容器中所有元素等类似功能。 |
| fill(val) | 将 val 这个值赋值给容器中的每个元素。 |
| array1.swap(array2) | 交换 array1 和 array2 容器中的所有元素，但前提是它们具有相同的长度和类型。 |
array通过[]访问元素，为了避免越界，可以使用at()成员函数，越界会抛出out_of_range异常
2.STL vector
vector<double> val;
//扩容，当val.size()>20则不做操作
val.reserve(20)；
std::vector<int> primes {2, 3, 5, 7, 11, 13, 17, 19};
std::vector<double> values(20);//指定元素个数，初始为0
std::vector<double> values(20,1);//指定元素个数，初始为1
| 函数成员 | 函数功能 |
|---|---|
| begin() | 返回指向容器中第一个元素的迭代器。 |
| end() | 返回指向容器最后一个元素所在位置后一个位置的迭代器，通常和 begin() 结合使用。 |
| rbegin() | 返回指向最后一个元素的迭代器。 |
| rend() | 返回指向第一个元素所在位置前一个位置的迭代器。 |
| cbegin() | 和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
| cend() | 和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
| crbegin() | 和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
| crend() | 和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
| size() | 返回实际元素个数。 |
| max_size() | 返回元素个数的最大值。这通常是一个很大的值，一般是 232-1，所以我们很少会用到这个函数。 |
| resize() | 改变实际元素的个数。 |
| capacity() | 返回当前容量。 |
| empty() | 判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。 |
| reserve() | 增加容器的容量。 |
| shrink _to_fit() | 将内存减少到等于当前元素实际所使用的大小。 |
| operator[ ] | 重载了 [ ] 运算符，可以向访问数组中元素那样，通过下标即可访问甚至修改 vector 容器中的元素。 |
| at() | 使用经过边界检查的索引访问元素。 |
| front() | 返回第一个元素的引用。 |
| back() | 返回最后一个元素的引用。 |
| data() | 返回指向容器中第一个元素的指针。 |
| assign() | 用新元素替换原有内容。 |
| push_back() | 在序列的尾部添加一个元素。 |
| pop_back() | 移出序列尾部的元素。 |
| insert() | 在指定的位置插入一个或多个元素。并返回新插入元素所在位置的迭代器 |
| erase() | 移出一个元素或一段元素。，根据索引删除， |
| clear() | 移出所有的元素，容器大小变为 0。 |
| swap() | 交换两个容器的所有元素。 |
| remove() | 根据值删除元素，不会改变容器的大小和容量 |
| emplace() | 在指定的位置直接生成一个元素。 |
| emplace_back() | 在序列尾部生成一个元素。 |
访问元素的方式
vec[n];
vec.at(n);
vec.front();//首元素
vec.back();//尾元素
vec.data();//返回首元素的指针
*(vec.data()+n);
push_back();
emplace_back();
这两个函数都可以在容器末尾添加元素
push_back添加元素时，会生成一个元素，再将元素移动（或拷贝）至容器中，而emplace_back会
直接在容器末尾生成，因此emplace_back更加高效
iterator insert(pos,elem);//在指定位置之前插入一个元素elem
iterator insert(pos,n,elem);//在指定位置之前插入n个元素elem
iterator insert(pos,first,last);//在pos之前，插入其他容器中[first,last)区域内的所有元素，返回第一个新元素的迭代器的位置
iterator insert(pos,initlist);//在pos之前插入初始化列表的所有元素，返回第一个新元素的迭代器的位置
iterator emplace(const_iterator pos,args);
pos:指定插入元素的位置，args：新插入元素的构造函数对应的多个参数
删除元素
erase(n);//删除指定位置的元素
erase(first,last);//删除指定位置[first,last)的元素
remove(pos,n);//从pos开始删除值为n的元素
remove不会改变容器大小和容量
remove() 的实现原理是，在遍历容器中的元素时，一旦遇到目标元素，就做上标记，然后继续遍历，直到找到一个非目标元素，即用此元素将最先做标记的位置覆盖掉，同时将此非目标元素所在的位置也做上标记，等待找到新的非目标元素将其覆盖。因此，1,3,3,4,3,5，remove(3)如果将上面程序中 demo 容器的元素全部输出，得到的结果为 1 4 5 4 3 5。
因此删除指定元素需要和erase搭配
auto it=remove(demo.begin(),demo.end(),3);
demo.erase(it,demo.end());
vector<int> demo{1,2,3};
demo.clear();
//demo.size()=0
//demo.capacity()=6
vector<bool>并不是一个STL容器，也不容纳bool
vector<bool> 打包 bool 以节省空间，每个保存在“vector”中的“bool”占用一个单独的bit，而禁止有指向单个比特的指针。
3.STL deque
deque相比vector，可以高效的在容器底部或尾部插入元素，且容器内的元素不一定会放在一段连续内存里
deque<int> dq;//初始化空队列
deque<int> dq(100);//初始化100个默认值的队列
deque<int> dq(100,1);//初始化100个1的队列
| 函数成员 | 函数功能 |
|---|---|
| begin() | 返回指向容器中第一个元素的迭代器。 |
| end() | 返回指向容器最后一个元素所在位置后一个位置的迭代器，通常和 begin() 结合使用。 |
| rbegin() | 返回指向最后一个元素的迭代器。 |
| rend() | 返回指向第一个元素所在位置前一个位置的迭代器。 |
| cbegin() | 和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
| cend() | 和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
| crbegin() | 和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
| crend() | 和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
| size() | 返回实际元素个数。 |
| max_size() | 返回容器所能容纳元素个数的最大值。这通常是一个很大的值，一般是 232-1，我们很少会用到这个函数。 |
| resize() | 改变实际元素的个数。 |
| empty() | 判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。 |
| shrink _to_fit() | 将内存减少到等于当前元素实际所使用的大小。 |
| at() | 使用经过边界检查的索引访问元素。 |
| front() | 返回第一个元素的引用。 |
| back() | 返回最后一个元素的引用。 |
| assign() | 用新元素替换原有内容。 |
| push_back() | 在序列的尾部添加一个元素。 |
| push_front() | 在序列的头部添加一个元素。 |
| pop_back() | 移除容器尾部的元素。 |
| pop_front() | 移除容器头部的元素。 |
| insert() | 在指定的位置插入一个或多个元素。 |
| erase() | 移除一个元素或一段元素。 |
| clear() | 移出所有的元素，容器大小变为 0。 |
| swap() | 交换两个容器的所有元素。 |
| emplace() | 在指定的位置直接生成一个元素。 |
| emplace_front() | 在容器头部生成一个元素。和 push_front() 的区别是，该函数直接在容器头部构造元素，省去了复制移动元素的过程。 |
| emplace_back() | 在容器尾部生成一个元素。和 push_back() 的区别是，该函数直接在容器尾部构造元素，省去了复制移动元素的过程。 |
注：创建first容器后，容器进行添加操作，会导致first失效
访问deque元素
dq[n];//访问容器的中第n个元素
dq.at(n);//访问容器的中第n个元素,有边界控制
dq.front();//访问dq的首元素
dq.back();//访问dq的尾元素
4.STL list
list双向链表容器，各元素靠指针维持顺序，分别指向前后两个元素，不能通过索引访问元素
list<int> l;
list<int> l(10);
list<int> l(10,5);
| 函数 | 功能 |
|---|---|
| remove(val) | 删除容器中所有等于 val 的元素。 |
| remove_if() | 删除容器中满足条件的元素。 |
| unique() | 删除容器中相邻的重复元素，只保留一个。 |
| merge() | 合并两个事先已排好序的 list 容器，并且合并之后的 list 容器依然是有序的。 |
| sort() | 通过更改容器中元素的位置，将它们进行排序。 |
| reverse() | 反转容器中元素的顺序。 |
访问元素：
l.front();//返回list的第一个元素的引用
l.back();//返回list的最后一个元素的引用
list插入元素：
push_front();
push_back();
emplace_back();
emplace_front();
emplace();//在指定位置生成元素
insert();//在指定位置插入元素
splice();//在指定位置插入其他list容器中的元素
splice 将其他list容器中的元素添加当前list容器中指定位置处。
void splice(iterator pos,list& x);//pos：插入位置，x：另一个list容器
void splice(iterator pos,list& x,iterator i);//将x容器中i指向的元素移动到当前容器中pos指明的位置
void splice(iterator pos,list& x,iterator first,iterator last);//将x容器[first,last)范围内所有元素移动到当前容器pos位置上。
splice方法会将x容器中的相应元素添加到当前容器，该元素会从x中删除
unique()
void unique();
void unique(BinaryPredicate);//传入二元谓词函数
两种方式都可去重，第二种可以自定义去重规则
remove_if();//传入自定义为此函数，删除满足条件的元素
5.STL forward_list
C++11新容器，底层为单链表结构，数据存储是分散随机的。可以在序列任何位置添加和删除元素。
forward_list只提供前向迭代器，无rbegin，rend等函数
相较于list，消耗内存小，空间效率高
forward_list<int> fl;
forward_list<int> fl(10);
forward_list<int> fl(10,5);//初始化10个5
| before_begin() | 返回一个前向迭代器，其指向容器中第一个元素之前的位置。 |
|---|---|
| begin() | 返回一个前向迭代器，其指向容器中第一个元素的位置。 |
| end() | 返回一个前向迭代器，其指向容器中最后一个元素之后的位置。 |
| cbefore_begin() | 和 before_begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
| cbegin() | 和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
| cend() | 和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
| empty() | 判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。 |
| max_size() | 返回容器所能包含元素个数的最大值。这通常是一个很大的值，一般是 232-1，所以我们很少会用到这个函数。 |
| front() | 返回第一个元素的引用。 |
| assign() | 用新元素替换容器中原有内容。 |
| push_front() | 在容器头部插入一个元素。 |
| emplace_front() | 在容器头部生成一个元素。该函数和 push_front() 的功能相同，但效率更高。 |
| pop_front() | 删除容器头部的一个元素。 |
| emplace_after() | 在指定位置之后插入一个新元素，并返回一个指向新元素的迭代器。和 insert_after() 的功能相同，但效率更高。 |
| insert_after() | 在指定位置之后插入一个新元素，并返回一个指向新元素的迭代器。 |
| erase_after() | 删除容器中某个指定位置或区域内的所有元素。 |
| swap() | 交换两个容器中的元素，必须保证这两个容器中存储的元素类型是相同的。 |
| resize() | 调整容器的大小。 |
| clear() | 删除容器存储的所有元素。 |
| splice_after() | 将某个 forward_list 容器中指定位置或区域内的元素插入到另一个容器的指定位置之后。 |
| remove(val) | 删除容器中所有等于 val 的元素。 |
| remove_if() | 删除容器中满足条件的元素。 |
| unique() | 删除容器中相邻的重复元素，只保留一个。 |
| merge() | 合并两个事先已排好序的 forward_list 容器，并且合并之后的 forward_list 容器依然是有序的。 |
| sort() | 通过更改容器中元素的位置，将它们进行排序。 |
| reverse() | 反转容器中元素的顺序。 |
forward_list不提供size函数，如果想获取长度，采用iterator中的distance函数。
int count=distance(begin(fl),end(fl));
int count=distance(fl.begin(),fl.end());
begin()，end()为STL容器方法，可以获取容器第一个，最后一个元素的迭代器
begin(),end(),参数可以是普通数组，可可以是容器，为普通数组将返回第一个、最后一个元素的指针，为容器返回迭代器。
6.vector自定义排序
-
重载运算符
struct Book{ int page; string name; bool operator <(const Book& b) const // 升序排序时必须写的函数 { return page < b.page; } bool operator >(const Book& b) const // 降序排序时必须写的函数 { return page > b.page; } } vector<Book> books; sort(books.begin(), books.end(), less<Book>()); -
全局比较函数
struct Book{ int page; string name; }; bool lessmark(const Book& b1, const Book& b2) { return b1.page < b2.page; } bool greatermark(const Book& b1, const Book& b2) { return b1.page > b2.page; } vector<Book> books; sort(books.begin(), books.end(), lessmark); //升序排序 -
仿生函数(重写（）)
struct Book{ int page; string name; }; class CompLess{ public: bool operator ()(const Book& b1, const Book& b2) { return b1.page < b2.page; } }; class CompGreater{ public: bool operator ()(const Book& b1, const Book& b2) { return b1.page > b2.page; } }; vector<Book> books; sort(books.begin(), books.end(), CompLess()); //升序排序