目录
STL介绍
什么是STL
- STL 位于各个 C++ 的头文件中,即它并非以二进制代码的形式提供,而是以源代码的形式提供
- STL是容器、算法和其他组件的集合
泛性编程
- 占位符,使用了泛型的代码称为模板
- C++ 中,用以支持泛型应用的就是标准 模板库 STL,它提供了 C++ 泛型设计常用的类模板和函数模板
STL基本组成
- 容器:用来封装数据结构的模板类
- 算法:包含数据结构算法的模板函数,在 std 命名空间中定义,其中大部 分算法都包含在头文件
<algorithm>
中,少部分位于头文件<numeric>
中 - 迭代器:对容器中数据的读和写,是通过迭代器完成的
- 函数对象:如果一个类将 () 运算符重载为成员函数,这个类就称为函数对象类,这个类的对象就是函数对象(又称仿函数)
- 适配器:可以使一个类的接口(模板的参数)适配成用户指定的形式,从而让原本不能在一起工作的两个类工作在一起
- 内存分配器:为容器类模板提供自定义的内存申请和释放功能
STL序列式容器
什么是STL容器
- 容器是模板类的集合,容器中封装的是组织数据的方法
- STL有三类标准容器:序列容器、排序容器、哈希容器,后两类也被称为关联容器
- 容器种类和功能
什么是迭代器
-
迭代器类型
-
输入迭代器和输出迭代器比较特殊,它们不是把数组或容器当做操作对象,而是把输入流/输出流作为操作对象
-
前向迭代器,支持++p、p++,*p操作
-
双向迭代器,还支持--p、p--
-
随机访问迭代器,还支持p+=i、p-=i、p[i]
-
-
不同容器的迭代器
- array、vector是随机访问迭代器
- list、set、map是双向迭代器
-
迭代器定义方式
什么是序列式容器
- 类型
- array<T, N>:数组容器,用来存储N个T类型的元素,长度固定不变
- vector<T>:向量容器,长度可变,尾部插入元素O(1)
- deque<T>:双端队列容器,头部和尾部插入都是O(1)
- list<T>:链表容器,用双向链表组织元素,插入方便,访问慢(从头开始访问)
- forward_list<T>:正向链表容器,用单向链表组织,比list块、节省内存
- 容器常见的函数成员
- begin(),返回指向容器第一个元素的迭代器
- end(),指向容器最后一个元素后一个位置的迭代器
- rbegin(),返回指向最后一个元素的迭代器
- sort(),序列式容器不会自动进行排序,要手动调用sort
array容器
-
特点:大小固定,无法动态扩展,只允许访问和替换
-
定义方式
std::array<double, 10> values
-
初始化
std::array<double, 10> values {0.5,1.0,1.5,,2.0}
-
访问
1.values[4] = values[3] + 2.O*values[1]; %不安全 2.values.at(i) = i; %安全 3.get<n>(values); %n必须是常量,使用的是get<n>模板函数
-
基于范围的遍历
-
读
for (double x : prices) std::cout << x << std::endl;
-
写
for (double &x : prices) x = x * 0.80;
-
-
表示首元素地址
value.begin() &value[0] value.data()
vector容器
-
特点:array 实现的是静态数组(容量固定的数组),而 vector 实现的是一个动态数组,即可以进行元素的插入和删除
-
设置内存分配
values.reserve(20) #分配至少容纳20个元素的内存
-
初始化
std::vector<double> values(num, value) #num个value值
-
独特之处
- push_back进行初始化
- 当vector容器容量发生变化时,所有元素可能会被复制或移动到新的内存地址,需要重新初始化迭代器
-
访问元素同array
-
容量和大小
- capacity()是指在不分配更多内存的情况下,容器可以保存的最多元素个数
- size()是指容器实际所包含的元素个数
-
emplace_back和push_back区别
push_back() 向容器尾部添加元素时,首先会创建这个元素,然后再将这个元素拷贝或者移动到容器中(如果是拷贝的话,事后会自行销毁先前创建的这个元素); 而emplace_back() 在实现时,则是直接在容器尾部创建这个元素,省去了拷贝或移动元素的过程。 emplace_back执行效率更高
-
指定位置插入元素
- insert() 函数的功能是在 vector 容器的指定位置插入一个或多个元素
-
emplace() 每次只能插入一个元素。在插入元素时,是在容器的指定位置直接构造元素,而不是先单独生成,再将其复制(或移动)到容器中。 因此,在实际使用中,推荐大家优先使用 emplace()。
-
删除
-
vector<bool>
- vector<bool>不是容器,底层是用一个bit位来存储元素
- 避免是用vector<bool>,可以使用deque<bool>替代
deque容器
-
特点:和 vector 不同的是,deque 还擅长在序列头部添加或删除元素,并且更重要的一点是, deque 容器中存储元素并不能保证所有元素都存储到连续的内存空间中。 当需要向序列两端频繁的添加或删除元素时,应首选 deque 容器。
-
因为元素不是存储在连续内存空间中,所以最好不要用指针去访问deque容器
-
访问第一个和最后一个元素
values.front() = 10; %访问首元素 values.back() = 20; %访问最后一个元素
-
成员方法
list容器
-
特点:双向链表,如何需要对序列进行大量添加或删除元素的操作,而直接访问元素的需求却很少,建议使用 list 容器存储序列
-
访问:list 容器不支持随机访问,未提供下标操作符 [] 和 at() 成员函数,也没有提供 data() 成员函数。 通过 front() 和 back() 成员函数,可以分别获得 list 容器中第一个元素和最后一个元素的引用形式
-
添加元素:
- 删除元素
-
splice方法
-
将其它list容器中的元素,添加到当前list容器指定位置处
void splice(iterator position, list &x)
-
-
empty和size都可以判断容器为空,用empty更好
STL关联式容器
- 特点:存储的元素是键值对,并且默认根据键值大小做升序排序,底层用红黑树来存储键值对
pair容器
-
定义和初始化
# 1.构造函数 pair <string, string> pair1("1","2"); # 2.拷贝构造函数 pair <string, string> pair3(pair2); # 3.移动构造函数 pair <string, string> pair4(make_pair("1", "2")); #make_pair返回一个临时pair对象
-
取键:pair1.first,取值:pair1.second
-
swap函数:用来交换两个pair对象的键值对
pair1.swap(pair2);
map容器
-
特点:使用 map 容器存储的各个键值对,键的值既不能重复也不能被修改,该容器存储的都是pair<const K, T>类型
-
定义和初始化
std::map<std::string, int>myMap{ {"C 语言教程",10},{"STL 教程",20} };
-
查找
- find(key) 成员方法,它能帮我们查找指定 key 值的键值对,如果成功找到,则返回一个指向该键值对 的双向迭代器
- lower_bound(key) 返回的是指向第一个键不小于 key 的键值对的迭代器;
- upper_bound(key) 返回的是指向第一个键大于 key 的键值对的迭代器
-
获取键值
-
[]:只有当 map 容器中确实存有包含该指定键的键值对,借助重载的 [ ] 运算符才能成功获取该键对应的值;反之,若当前 map 容 器中没有包含该指定键的键值对,则此时使用 [ ] 运算符将不再是访问容器中的元素,而变成了向该 map 容器中增添一个键值对
string cValue = myMap["C 语言教程"];
-
at:at() 成员方法也需要根据指定的键,才能从容器中找到该键对应的值;不同之处在于,如果在当前容器中查找失败,该方法不会向容器中添加新的键值对,而是直 接抛出 out_of_range 异常
cout << myMap.at("C 语言教程") << endl;
-
find:返回迭代器,当 find() 方法查找失败时,其返回的迭代器指向的是容器中 最后一个键值对之后的位置,即不指向任何有意义的键值对
-
-
插入
-
不指定pos,返回键值对
ret = mymap.insert({ "C 语言教程","http://c.biancheng.net/c/" });
-
指定pos,返回迭代器
std::map<string, string>::iterator it = mymap.begin(); //向 it 位置以普通引用的方式插入 STL auto iter1 = mymap.insert(it, STL);
-
插入其他容器指定区域内的所有键值对
std::map<string, string>::iterator first = ++mymap.begin(); std::map<string, string>::iterator last = mymap.end(); //将<first,last>区域内的键值对插入到 copymap 中 copymap.insert(first, last);
-
插入多个键值对
mymap.insert({ {"STL 教程", "http://c.biancheng.net/stl/"}, { "Java 教程","http://c.biancheng.net/java/" } });
-
insert的增添效率更高,[]的更新效率更高
-
-
emplace
pair<map<string, string>::iterator, bool> ret = mymap.emplace("STL 教程", "http://c.biancheng.net/stl/");
- 当该方法将键值对成功插入到 map 容器中时,其返回的迭代器指向该新插入的键值对,同时 bool 变量的值为 true
- 当插入失败时,则表明 map 容器中存在具有相同键的键值对,此时返回的迭代器指向此具有相同键的键值对,同时 bool 变量的值为 false。
-
emplace_hint
- 该方法不仅要传入创建键值对所需要的数据,还需要传入一个迭代器作为第一个参数,指明要插入的位置(新键值对键会插入到该迭代 器指向的键值对的前面)
- 该方法的返回值是一个迭代器,而不再是 pair 对象。当成功插入新键值对时,返回的迭代器指向新插入的键值对;反之,如果插入失败,则表明 map 容器中存有相同键的键值对,返回的迭代器就指向这个键值对
- 在实现向 map 容器中插入键值对时,应优先考虑使用 emplace() 或者 emplace_hint()
-
按key排序
-
指定升序
std::map<std::string, int, std::less<std::string> >myMap{ {"C 语言教程",10},{"STL 教程",20}};
-
指定降序
std::map<std::string, int, std::greater<std::string> >myMap{ {"C 语言教程",10},{"STL 教程",20}};
-
multimap容器
- 特点:和 map 容器的区别在于,multimap 容器中可以同时存储多(≥2)个键相同的键值对
- 方法:
- insert
- erase
- emplace
- emplace_hint
- count(key)
- find(key)
set容器
-
特点:使用 set 容器存储的各个键值对,要求键 key 和值 value 必须相等
-
定义和初始化
std::set<std::string> myset{"http://c.biancheng.net/java/", "http://c.biancheng.net/stl/","http://c.biancheng.net/python/"};
自定义关联式容器的排序方式
- 使用函数对象类来自定义排序
class cmp {
public:
//重载 () 运算符
bool operator ()(const string &a,const string &b) {
//按照字符串的长度,做升序排序(即存储的字符串从短到长)
return (a.length() < b.length());
}
};
int main() {
//创建 set 容器,并使用自定义的 cmp 排序规则
std::set<string, cmp>myset{"http://c.biancheng.net/stl/", "http://c.biancheng.net/python/","http://c.biancheng.net/java/"};
修改关联式容器中键值对的键
-
map 和 multimap 容器只能采用“先删除,再添加”的方式修改某个键值对的键
-
借助const_cast,可以直接修改set和multiset容器中元素的非键部分
class student { public: student(string name, int id, int age) :name(name), id(id), age(age){ } const int& getid() const { return id; } void setname(const string name){ this->name = name; } } class cmp { public: bool operator ()(const student &stua, const student &stub) { //按照字符串的长度,做升序排序(即存储的字符串从短到长) return stua.getid() < stub.getid(); } }; set<student, cmp> myset{ {"zhangsan",10,20},{"lisi",20,21},{"wangwu",15,19} }; //*iter会调用operator*,其返回的是一个 const T&类型元素,用const_cast去掉常 量限定 set<student>::iterator iter = mymap.begin(); const_cast<student&>(*iter).setname("xiaoming");
无序关联式容器
无序容器(哈希容器)是什么
- 区别
- 关联式容器的底层实现采用的树存储结构,更确切的说是红黑树结构;
- 无序容器的底层实现采用的是哈希表的存储结构。
- 特点
- 无序容器内部存储的键值对是无序的,各键值对的存储位置取决于该键值对中的键
- 和关联式容器相比,无序容器擅长通过指定键查找对应的值(平均时间复杂度为 O(1));但对于使用迭代器遍历容器中存储的元素, 无序容器的执行效率则不如关联式容器。
- 选择
- 实际场景中如果涉及 大量遍历容器的操作,建议首选关联式容器
- 反之,如果更多的操作是通过键获取对应的值,则应首选无序容器
- 类型
- unordered_map、unordered_multimap
- unordered_set、unordered_multiset
C++无序容器自定义哈希函数和排序方式
-
假设我们想创建一个可存储 Person 类对象的 unordered_set 容器,考虑到 Person 为自定义的类型,因此默认的 hash 哈希函数不再适用,这时就需要以函数对象类的方式自定义一个哈希函数
-
使用函数对象类实现自定义哈希函数
class hash_fun { public: int operator()(const Person &A) const { return A.getAge(); } }; std::unordered_set<Person, hash_fun> myset;
容器适配器
什么是容器适配器
- 容器适配器,就是将不适用的序列式容器(包括 vector、deque 和 list)变得适用,即通过封装某个序列式容器,并重新组合该容器中包含的成员函数,使其满足某些特定场景的需要。
stack容器适配器
- 无迭代器,访问元素的唯一方式是遍历容器,通过不断移除访问过的元素,去访问下一个元素
queue容器适配器
- 无迭代器,访问元素的唯一方式是遍历容器,通过不断移除访问过的元素,去访问下一个元素
priority_queue
- 优先级队列,遵循的并不是 “First in,First out”(先入先出)原则,而是“First in,Largest out”原则
- 可以自定义排序方式,在插入或者删除时会自动按照排序方式重新排列
迭代器适配器
- 迭代器适配器,其本质也是一个模板类,该模板类是借助以上 5 种基础迭代器实现的
reverse_iterator反向迭代器
-
特点
- 当反向迭代器执行 ++ 运算时,底层的基础迭代器实则在执行 -- 操作,意味着反向迭代器在反向遍历容器;
- 当反向迭代器执行 -- 运算时,底层的基础迭代器实则在执行 ++ 操作,意味着反向迭代器在正向遍历容器。
-
定义和初始化
std::reverse_iterator<std::vector<int>::iterator> my_reiter(myvector.end())
插入迭代器
-
back和front迭代器的使用:
std::forward_list<int> foo; std::back_insert_iterator< std::vector<int> > back_it(foo); //将 5 插入到 foo 的末尾 back_it = 5;
-
insert迭代器的使用:
std::list<int> foo(2,5); std::list<int>::iterator it = ++foo.begin(); std::insert_iterator<std::list<int>> insert_it (foo,it); //it 是一个基础迭代器,表示新元素的插入位置
流迭代器
-
操作对象不再是某个容器,而是流对象。即通过流迭代器,我们可以读取指定流对象中的数据,也可以将数据写入到流对象中
-
输入流迭代器用于直接从指定的输入流中读取元素
double value1; //创建表示结束的输入流迭代器 istream_iterator<double> eos; //创建一个可逐个读取输入流中数据的迭代器,同时这里会让用户输入数据 istream_iterator<double> iit(cin); //判断输入流中是否有数据 if (iit != eos) { //读取一个元素,并赋值给 value1 value1 = *iit; } //如果输入流中此时没有数据,则用户要输入一个;反之,如果流中有数据,iit 迭代器后移一位,做读取下一个元素做准备 iit++;
-
输出流迭代器用于将数据写到指定的输出流(如 cout)中
//创建一个输出流迭代器 ostream_iterator<string> out_it(cout); //向 cout 输出流写入 string 字符串 *out_it = "http://c.biancheng.net/stl/"; cout << endl; //创建一个输出流迭代器,设置分隔符 , ostream_iterator<int> out_it1(cout, ","); //向 cout 输出流依次写入 1、2、3 *out_it1 = 1; *out_it1 = 2; *out_it1 = 3; /*和copy函数连用*/ //创建一个 vector 容器 vector<int> myvector; //初始化 myvector 容器 for (int i = 1; i < 10; ++i) { myvector.push_back(i); } //创建输出流迭代器 std::ostream_iterator<int> out_it(std::cout, ", "); //将 myvector 容器中存储的元素写入到 cout 输出流中 std::copy(myvector.begin(), myvector.end(), out_it);
流缓冲区迭代器
move_iterator移动迭代器
-
创建
//创建一个 vector 容器 std::vector<std::string> myvec{ "one","two","three" }; //将 vector 容器的随机访问迭代器作为新建移动迭代器底层使用的基础迭代器 typedef std::vector<std::string>::iterator Iter; //创建并初始化移动迭代器 std::move_iterator<Iter>mIter = make_move_iterator(myvec.begin());
-
运用移动迭代器为 othvec 容器初始化
//使用的是移动迭代器,其会将myvec容器中的元素直接移动到 othvec 容器中。 vector<string>othvec(make_move_iterator(myvec.begin()), make_move_iterator(myvec.end())); //创建2个移动迭代器 std::move_iterator<Iter>begin = make_move_iterator(myvec.begin()); std::move_iterator<Iter>end = make_move_iterator(myvec.end()); //通过base方法,获取到当前移动迭代器底层所使用的基础迭代器,以复制的方式初始化 othvec容器 vector <std::string> othvec(begin.base(), end.base());
算法
search函数
- 语法
//查找 [first1, last1) 范围内,和 [first2, last2) 序列满足 pred 规则的第一个子序列
ForwardIterator search (ForwardIterator first1, ForwardIterator last1,
ForwardIterator first2, ForwardIterator last2,
BinaryPredicate pred);
- 实例
//以函数对象的形式定义一个匹配规则
class mycomp2 {
public:
bool operator()(const int& i, const int& j) {
return (i%j == 0);
}
};
int main() {
vector<int> myvector{ 1,2,3,4,8,12,18,1,2,3 };
int myarr2[] = { 2,4,6 };
//调用第二种语法格式
it = search(myvector.begin(), myvector.end(), myarr2, myarr2 + 3, mycomp2());
}
copy函数
std::vector<int> srce {1, 2, 3, 4};
std::deque<int> dest {5, 6, 7, 8};
std::copy(std::begin(srce), std::end(srce), std::back_inserter(dest));
move函数
std::vector<int> srce {1, 2, 3, 4};
std::deque<int> dest {5, 6, 7, 8};
std::move(std::begin(srce), std::end(srce), std::back_inserter(dest));
标签:std,容器,iterator,迭代,STL,元素,笔记,学习,键值
From: https://www.cnblogs.com/z5onk0/p/16755324.html