STL---容器、算法、组件化大生产
-
为什么要有STL，自己做算法不好吗？
其实自己做算法挺好的，有时候思路不一样，说不定还更省时间，但是！！你有没有想过，你也总有一天会写出不高效的算法吧，STL都嫌弃的人是不可能用boost了，因为boost里的东西比STL激进多了,c++都学了，何必要阉割STL呢
面向过程--->基于对象--->面向对象--->泛型
- 面向过程：是把程序分成若干个子过程，将事物的方法隐藏于各个函数内--（C语言）。并且只适用于用小型的程序，对于大型程序不易处理变化的需求，所以我们才需要新的抽象。
- 基于对象：与前者相比，可以更好的处理变化，但是各个类之间的关系不容易处理，而且代码的数量比面向过程更大----需要新的抽象。
- 面向对象： 与基于对象相比，有更多的间接性。运用多态，我们可以调用某种方法，而不用指定此方法所属的类型。因而达到更进一步的抽象性。
它为我们带来了------MFC（以C++类的形式封装了Windows API，并且包含一个应用程序框架，以减少应用程序开发人员的工作量。 -
泛型：（Generic）是一种抽象的就如OO是一种抽象一样。
相应语法：Template
它为我们带来了今天的主角：-----STL（简单来说就是 数据结构和算法的模板的集合）
泛型程序设计：（使用模板的程序设计）
- 解释：将一些常用的数据结构（比如：链表、数组、二叉树）和算法（比如 排序，查找）写成模板，以后不论数据结构里放的是什么对象，算法针对什么样的对象，则都无需重新实现数据结构，重新编写算法，而且还能获得非常高的性能（此处有争议哈哈哈哈哈哈哈）
如果说之前我们学了那么多鬼语言，做了那么多的铺垫都仅仅是钻木取火的话，辣么我们现在用STL代表着我们进入工业时代啦！ -
STL的三个关键组件：
- 容器：一个STL容器是一个数据结构，也是类模板，其中包括：vector\deque\list\set\map\stack\queue等。
- 迭代器：可用于一次存取容器中元素，类似于指针。
- 算法：用来操作容器中的元素的函数模板。
这张图片完美的向我们展示了STL该有的责任：
STL
对三大关键组件内容的详细展开:
-
容器：
容器的三大分类
顺序容器、关联容器的存储模型
-
迭代器（iterator）
迭代器的作用：能够让迭代器与算法不干扰的相互发展，最后又能无间隙的粘合起来，重载了*，＋＋，＝＝，！＝，＝运算符。用以操作复杂的数据结构，容器提供迭代器，算法使用迭代器；常见的一些迭代器类型：iterator、const_iterator、reverse_iterator和const_reverse_iterator
例子：
vector <int> ::const_iterator i;
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v;
v.push_back(3); //数组尾部插入3
v.push_back(2);
v.push_back(1);
v.push_back(0);
cout << " 下标 " << v[3] << endl;
cout << " 迭代器 " << endl;
for(vector<int>::iterator i = v.begin();i!= v.end();++i)
{
cout << *i << " ";
}
cout << endl;
//在第一个元素之前插入111 insert begin+n是在第n个元素之前插入
v.insert(v.begin(),111);
//在最后一个元素之后插入222 insert end + n 是在n个元素之后插入
v.insert(v.end(),222);
for(vector<int>::iterator i = v.begin();i!= v.end();++i)
{
cout << *i << " ";
}
cout << endl;
vector<int> arr(10);
for(int i = 0; i < 10; i++)
{
arr[i] = i;
}
for(vector<int>::iterator i = arr.begin();i!= arr.end();++i)
{
cout << *i << " ";
}
cout << endl;
//删除 同insert
arr.erase(arr.begin());
for(vector<int>::iterator i = arr.begin();i!= arr.end();++i)
{
cout << *i << " " ;
}
cout << endl ;
arr.erase(arr.begin(),arr.begin()+5);
for(vector<int>::iterator i = arr.begin();i!= arr.end();++i)
{
cout << *i << " " ;
}
cout << endl ;
return 0 ;
}
- 利用 reverse(v.begin(),v.end())进行数组转置：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
vector<int> v;
for(int i = 0; i < 10; ++i)
{
v.push_back(i);
}
for(vector<int>::iterator it = v.begin(); it != v.end(); ++it)
{
cout << *it << " ";
}
cout << endl;
reverse(v.begin(),v.end());
for(vector<int>::iterator it = v.begin(); it != v.end(); ++it)
{
cout << *it << " ";
}
cout << endl;
return 0;
}
对vector的详细整理：
- vector的初始化：
vector // 创建一个空的vector。
vector c1(c2) // 复制一个vector
vector c(n) // 创建一个vector，含有n个数据，数据均已缺省构造产生
vector c(n, elem) // 创建一个含有n个elem拷贝的vector
vector c(beg,end) // 创建一个含有n个elem拷贝的vector
- 析构函数
c.~vector () // 销毁所有数据，释放内存
- 成员函数
c.assign(beg,end)c.assign(n,elem)
将[beg; end)区间中的数据赋值给c。将n个elem的拷贝赋值给c。
c.at(idx)
传回索引idx所指的数据，如果idx越界，抛出out_of_range。
常用：
c.back() // 传回最后一个数据，不检查这个数据是否存在。
c.begin() // 传回迭代器中的第一个数据地址。
c.capacity() // 返回容器中数据个数。
c.clear() // 移除容器中所有数据。
c.empty() // 判断容器是否为空。
c.end() // 指向迭代器中末端元素的下一个，指向一个不存在元素。
c.erase(pos) // 删除pos位置的数据，传回下一个数据的位置。
c.erase(beg,end) //删除[beg,end)区间的数据，传回下一个数据的位置。
c.front() // 传回第一个数据。
get_allocator // 使用构造函数返回一个拷贝。
c.insert(pos,elem) // 在pos位置插入一个elem拷贝，传回新数据位置。
c.insert(pos,n,elem) // 在pos位置插入n个elem数据。无返回值。
c.insert(pos,beg,end) // 在pos位置插入在[beg,end)区间的数据。无返回值。
c.max_size() // 返回容器中最大数据的数量。
c.pop_back() // 删除最后一个数据。
c.push_back(elem) // 在尾部加入一个数据。
c.rbegin() // 传回一个逆向队列的第一个数据。
c.rend() // 传回一个逆向队列的最后一个数据的下一个位置。
c.resize(num) // 重新指定队列的长度。
c.reserve() // 保留适当的容量。
c.size() // 返回容器中实际数据的个数。
c1.swap(c2)
swap(c1,c2) // 将c1和c2元素互换。同上操作。
operator[] // 返回容器中指定位置的一个引用。
-
用法示例：
- 创建一个vector：
vector容器提供了多种创建方法，下面介绍几种常用的。
创建一个Widget类型的空的vector对象：
vector vWidgets;
创建一个包含500个Widget类型数据的vector：
vector vWidgets(500);
创建一个包含500个Widget类型数据的vector，并且都初始化为0：
vector vWidgets(500, Widget(0));
创建一个Widget的拷贝：
vector vWidgetsFromAnother(vWidgets);
向vector添加一个数据
vector添加数据的缺省方法是push_back()。
push_back()函数表示将数据添加到vector的尾部，并按需要来分配内存。
例如：向vector中添加10个数据，需要如下编写代码：
for(int i= 0;i<10; i++) {
vWidgets.push_back(Widget(i));
}
-
获取vector中指定位置的数据
vector里面的数据是动态分配的，使用push_back()的一系列分配空间常常决定于文件或一些数据源。
如果想知道vector存放了多少数据，可以使用empty()。
获取vector的大小，可以使用size()。
例如，如果想获取一个vector v的大小，但不知道它是否为空，或者已经包含了数据，如果为空想设置为-1，
你可以使用下面的代码实现：
int nSize = v.empty() ? -1 : static_cast(v.size());
- 访问vector中的数据
使用两种方法来访问vector。
1、 vector::at()
2、 vector::operator[]
operator[]主要是为了与C语言进行兼容。它可以像C语言数组一样操作。
但at()是我们的首选，因为at()进行了边界检查，如果访问超过了vector的范围，将抛出一个例外。
由于operator[]容易造成一些错误，所有我们很少用它，下面进行验证一下：
分析下面的代码：
vector v;
v.reserve(10);
for(int i=0; i<7; i++) {
v.push_back(i);
}
try {int iVal1 = v[7];
// not bounds checked - will not throw
int iVal2 = v.at(7);
// bounds checked - will throw if out of range
}
catch(const exception& e) {
cout << e.what();
}
- 删除vector中的数据
vector能够非常容易地添加数据，也能很方便地取出数据，
同样vector提供了erase()，pop_back()，clear()来删除数据，
当删除数据时，应该知道要删除尾部的数据，或者是删除所有数据，还是个别的数据。
Remove_if()有三个参数：
1、 iterator _First：指向第一个数据的迭代指针。
2、 iterator _Last：指向最后一个数据的迭代指针。
3、 predicate _Pred：一个可以对迭代操作的条件函数。
图片.png
- 编程测试顺序容器矢量（vector）的主要功能和使用方法。
解：
#include<algorithm>
#include<vector>
#include<iostream>
#include<functional>
using namespace std;
int main(){
ostream_iterator<int> output(cout," ");
//用输出迭代子output来输出，其中第二参数" "表示用空格分隔各个整数。
int ia[18]={47,29,5,37,13,23,11,61,7,31,41,2,59,19,17,53,43,3};
vector<int> vec(ia,ia+9); //数据填入vector;vector共有7个构造函数,常用3个
//vector(),用以声明空的vector;vector(n),用以声明有n个元素的vector；
//vector(first,last),用以声明一个vector，
//其元素的初值是从区间[first,last)所指定的序列中的元素复制而来的；
vector<int> vec2(18);
if(vec.empty()) cout<<"vector空"<<endl;
else{
cout<<"vector不空，"<<"vector中的元素："<<endl;
unique_copy(vec.begin(),vec.end(),output);
cout<<endl;
}
cout<<"当前分配元素空间数量:"<<vec.capacity()<<endl;
vec.reserve(12);
cout<<"当前为vector保留的最小分配元素空间数量:"<<vec.capacity()<<endl;
vec.erase(vec.begin(),vec.end());
cout<<"当前分配元素空间数量:"<<vec.capacity()<<endl;
vec.resize(10);
cout<<"当前重新分配元素空间数量为10，实际分配元素空间数量:"
<<vec.capacity()<<endl;
vec.assign(ia+10,ia+16);
cout<<"vector存放序列容许最大长度："<<vec.max_size()<<endl;
cout<<"vector中的元素："<<endl;
unique_copy(vec.begin(),vec.end(),output);
cout<<endl;
vec.assign(ia,ia+18);
cout<<"vector中的元素："<<endl;
unique_copy(vec.begin(),vec.end(),output);
cout<<endl;
sort(vec.begin(),vec.end(),greater<int>());//降序排列
cout<<"vector中的元素："<<endl;
unique_copy(vec.begin(),vec.end(),output);
cout<<endl;
cout<<"用反转迭代子输出vector中的元素："<<endl;
unique_copy(vec.rbegin(),vec.rend(),output);
cout<<endl;cout<<"第1个元素："<<vec.front()<<endl;
cout<<"最后1个元素："<<vec.back()<<endl;
cout<<"第8个元素："<<vec[6]<<endl;
cout<<"原vector2中的元素："<<endl;
unique_copy(vec2.begin(),vec2.end(),output);
cout<<endl;
vec2.swap(vec);
cout<<"交换后vector2中的元素："<<endl;
unique_copy(vec2.begin(),vec2.end(),output);
cout<<endl;
return 0;
}
- 编程测试顺序容器列表（list）的主要功能和使用方法。
解：
#include<algorithm>
#include<list>
#include<iostream>
#include<functional>
using namespace std;
int main(){
ostream_iterator<int>output(cout," ");
//用输出迭代子output来输出，其中第二参数" "表示用空格分隔各个整数。
int ia[18]={47,29,5,37,13,23,11,61,7,31,41,2,59,19,17,53,43,3};
list<int> list1(ia,ia+18); //数据填入list1;list共有7个构造函数,常用3个
//list(),用以声明空的list;list(n),用以声明有n个元素的list；
//list(first,last),用以声明一个list，
//其元素的初值是从区间[first,last)所指定的序列中的元素复制而来的；
list<int> list2(18);
if(list1.empty()) cout<<"list1空"<<endl;
else{
cout<<"list1不空，"<<"list1中的元素："<<endl;
unique_copy(list1.begin(),list1.end(),output);
cout<<endl;
}
list1.sort(greater<int>());//降序排列
cout<<"list1中的元素降序排列："<<endl;
unique_copy(list1.begin(),list1.end(),output);
cout<<endl;
cout<<"用反转迭代子输出list1中的元素："<<endl;
unique_copy(list1.rbegin(),list1.rend(),output);
cout<<endl;cout<<"第1个元素："<<list1.front()<<endl;
cout<<"最后1个元素："<<list1.back()<<endl;
cout<<"原list2中的元素："<<endl;
unique_copy(list2.begin(),list2.end(),output);
cout<<endl;
list2.swap(list1);
cout<<"交换后list2中的元素："<<endl;
unique_copy(list2.begin(),list2.end(),output);
cout<<endl;
cout<<"现list1中的元素空了："<<endl;
unique_copy(list1.begin(),list1.end(),output);
cout<<endl;
list1.assign(list2.begin(),list2.end());
cout<<"将list2的元素赋到list1中："<<endl;
unique_copy(list1.begin(),list1.end(),output);
cout<<endl;
list2.resize(10);
cout<<"list2中的元素应剩10个："<<endl;
unique_copy(list2.begin(),list2.end(),output);
cout<<endl;
list1.pop_back();
cout<<"现list1中的元素："<<endl;
unique_copy(list1.begin(),list1.end(),output);
cout<<endl;
list1.pop_front();
cout<<"现list1中的元素："<<endl;
unique_copy(list1.begin(),list1.end(),output);
cout<<endl;
list1.push_back(ia[17]);
cout<<"因原list1中最后的元素与新插入元素相同，未能真正插入："<<endl;
unique_copy(list1.begin(),list1.end(),output);
cout<<endl;
list1.push_front(ia[0]);
cout<<"现list1中的元素："<<endl;
unique_copy(list1.begin(),list1.end(),output);
cout<<endl;
return 0;
}
- 编程测试以双向队列（deque）为基础的容器适配器队列（queue）的主要功能和使用方法。
解：
#include<deque>
#include<queue>
#include<iostream>
using namespace std;
int main(){
int i,j;
double da[10]={3.1,4.2,84.5,18.3,6.8,5.9,8.3,22.8,1.23,4.7};
queue<double> que1;
for(i=0;i<10;i++) que1.push(da[i]);
for(i=0;i<10;i++){
cout<<que1.front()<<'\t';
que1.pop();
}
cout<<endl;
return 0;
}
- 使用映射（map），建立阿拉伯的数字0~9和英文单词Zero到Nine的映射关系，并输入阿拉伯数字（如：1），输出英文数字（如：One）。
解：
#include<iostream.h>
#include<map>
using namespace std;
typedef map<int,char*> ismap;
int main(){
int i=1,j;
char* str[10]={"one","two","three","fore","five","six","sever","eight","nine","ten"};
ismap trans_map1;
ismap::iterator it;
for(i=1;i<=10;i++) trans_map1.insert(ismap::value_type(i,str[i-1]));
for(it=trans_map1.begin();it!=trans_map1.end();it++)
cout<<(*it).first<<'\t'<<(*it).second<<endl;
cout<<trans_map1.size()<<endl;
cout<<"请输入1~10的数字："<<endl;
cin>>j;
it=trans_map1.find(j);
cout<<(*it).first<<'\t'<<(*it).second<<endl;
return 0;
}
这里是一些关于STL的面试题：
https://blog.csdn.net/weiyuefei/article/details/52089146
