**STL(Standard Template Library)**概念
6大组件： 容器，算法，迭代器，仿函数，适配器，空间配置器
STL的优点：1.不需要额外安装其他软件包
2.实现了数据结构和算法的分离
3.程序员可以不用思考STL具体的实现过程，封装易用
4.高可重用性(模板类，模板函数)
5.高性能
6.高移植性
7.跨平台性
容器：
序列式容器：容器的元素的位置是由 进入容器的时机和地点来决定
关联式容器：容器已有规则，通常提供键值key作为索引
vector
动态增长原理
vector：动态数组,可变数组,单口容器
动态增长原理：当插入新元素的时候，如果空间不足，vector会重新申请更大的一块内存空间，将源空间数据拷贝到新空间，释放旧空间数据，再把新元素插入新申请空间.注意：一旦引起空间重新配置，指向原vector的所有迭代器都失效了
3个迭代器属性：start,finish,end_of_storage
finish: 指向数组中最后一个元素的下一个位置
vector常用API
vector构造函数
1
2
3
4
5
6
7
8
9
10
| vector<T> V;
vector(v.begin(), v.end() );
vector(n,elem );
int arr[] ={0,1,2,3,4};
vector<int> vl(arr,arr + sizeof(arr)/sizeof(int) );
|
其他基本操作
属性获取
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public:
iterator begin() { return start; }
iterator end() { return finish; }
reference front() { return *begin(); }
reference back() { return *(end() - 1); }
const_iterator begin() const { return start; }
const_iterator end() const { return finish; }
const_reference front() const { return *begin(); }
const_reference back() const { return *(end() - 1); }
size_type size() const { return size_type(end() - begin()); }
size_type max_size() const { return size_type(-1) / sizeof(T); }
size_type capacity() const { return size_type(end_of_storage - begin()); }
|
元素访问方法
1
2
3
4
5
6
7
8
| vector<typename T> c;
c.at(index);
c[index];
c.front();
c.back();
|
增删改查
1
2
| void push_back(const T& x);
vector<T ,Alloc> ::insert(iterator position, size_type n, const T& x);
|
1
2
3
4
5
6
7
| void pop_back();
iterator erase(iterator first,iterator last);
iterator erase(iterator position);
void clear() { erase(begin(), end()); }
|
容器的调整
1
2
| void reserve(size_type n)
void resize (size_type new_size)
|
vector遍历
1.使用迭代器
1
2
3
4
5
6
7
8
9
10
| template<class T>
void Iter_for(vector<T>& vt){
T temp;
vector<T> :: iterator iter;
for(iter=vt.begin(); iter!=vt.end(); iter++){
temp =*iter;
std::cout<<temp<<std::endl;
}
}
|
2.for_at
1
2
3
4
5
6
7
8
9
10
| template<class T>
void at_for(vector<T>& vt){
T temp;
int i=0;
int m=vt.size();
for(i=0;i<m;i++){
temp=vt.at(i);
std::cout<<temp<<std::endl;
}
}
|
3. STL for_each
for_each原型
1
2
3
4
5
| template < typename InputIterator, typename Function >
Function for_each(InputIterator beg, InputIterator end, Function f) {
while(beg != end)
f(*beg++);
}
|
1
2
3
4
5
6
7
8
9
10
11
| #include<algorithm>
#include<iostream>
#include<vector>
void print(const int& temp){
std::cout<<temp<<endl;
}
void main(){
int nums[4]={1,2,3,4};
vector<int> myvt=std::vector<int>(nums,nums+sizeof(nums)/sizeof(int));
std::for_each(ptr.begin(),ptr.end(),print)
}
|
vector高级编程
元素查找和搜索
使用STL通用算法find()
1
2
3
4
| template<class InputIterator,class T> inline
InputIterator find(InputIterator first,InputIterator last, const T& value);
InputIterator find_if(InputIterator first,InputIterator last,Predicate predicate);
|
元素排序
使用STL通用算法sort()
sort()底层实现是插入排序优化的快排，时间复杂度是 n*log2(n)
1.跟据元素自身定义的大小关系，进行升序排序
1
2
| template <class RandomAccessIterator>
inline void sort(RandomAccessIterator first, RandomAccessIterator);
|
使用方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include<iostream>
#include<vector>
#include<algorithm>
void print(const int& temp){
std::cout<< temp<<" ";
}
int main(){
int nums[] = {34,1,89,0,3,5,11};
std::vector<int> ptr = std::vector<int>(nums,nums+sizeof(nums)/sizeof(int));
std::for_each(ptr.begin(),ptr.end(),print);
std::sort(ptr.begin(),ptr.end());
std::cout<<std::endl;
std::for_each(ptr.begin(),ptr.end(),print);
}
|
2.利用cmp函数定义大小关系，bool cmp{};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include<iostream>
#include<vector>
#include<algorithm>
void print(const int& temp){
std::cout<< temp<<" ";
}
bool cmp(int a,int b){
return (a>b);
}
int main(){
int nums[] = {34,1,89,0,3,5,11};
std::vector<int> ptr = std::vector<int>(nums,nums+sizeof(nums)/sizeof(int));
std::for_each(ptr.begin(),ptr.end(),print);
std::sort(ptr.begin(),ptr.end(),cmp);
std::cout<<std::endl;
std::for_each(ptr.begin(),ptr.end(),print);
}
|