余睿的博客

浮生若梦,别多会少,不如莫遇

0%

STL体系结构

STL六大部件(Components)

  • 容器(Containers)
    • 容器是用来存放数据的地方,如vectorlist
  • 分配器(Allocators)
    • 容器放置数据需要内存空间,分配器用来为容器分配内存空间。
  • 算法(Algorithms)
    • 对容器的数据进行操作,如sortfind
  • 迭代器(Iterators)
    • 迭代器作为容器与算法之间的桥梁,本质为泛化的指针。
  • 适配器(Adapters)
    • 对容器、分配器、迭代器做一些转换。
  • 仿函数(Functors)

stl六大部件关系

从上图可以看出,与OO(面向对象)不同,在面向对象的方法中,我们数据与操作数据的函数封装在一起,从而形成一个对象;但是在STL的设计中,采用GP(generic programming)的方法,打破了这种封装,将数据与操作数据的函数进行了分离。容器和操作其的算法通过迭代器组装起来。

在STL的体系中,容器被用来存储数据,通过分配器为容器分配内存空间,算法通过迭代器作为桥梁对容器数据进行操作。

各部件的使用如下代码所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;

int main() {
int a[6] = { 3,45,167,9,12 };
vector<int, allocator<int>> v( a,a + 6 );
cout << count_if(v.begin(), v.end(),
not1(bind2nd(less<int>(), 40)));
return 0;
}
  • vector为容器(Container)
  • allocator<int>为分配器(allocator)
  • count_if为算法(Algorithm)
  • v.begin()以及v.end()为迭代器(Iterator)
  • not1为仿函数适配器(Function Adapter(negator))
  • bind2nd为仿函数适配器(Function Adapter(binder))
  • less<int>()为函数对象(function object)

需要注意的是,如果不指定vector的第二个参数(指定分配器),那么将使用默认的分配器进行内存分配;除此之外,分配器的模板参数需要和vector指定的参数相同。如上面的例子都为int

容器的结构与分类

前闭后开区间

在STL中,容器使用左闭右开的方法表示,包含最左边,但是不包含最右边一个元素。如下图所示:

容器空间示意图

通过调用Ierator,我们能得到一个泛化的指针,指针指向容器的某个位置,通过解引用能得到对应的数据。例如上面的*(c.begin())我们能得到该容器的第一个元素,需要注意的是,我们不能通过*(c.end())解引用得到最后一个元素,原因在于容器的设计是左闭右开的,最后一个iterator所指向的内容并不是我们容器里的。

迭代器也能像指针一样使用++--运算符来指向上一个或下一个元素。如下代码所示:

1
2
3
4
5
Container<T> c;
···
Container<T>::iterator ite = c.begin();
for(;ite != c.end();++ite)
···

Container表示任意容器,上述代码通过for循环遍历容器。

range-based for stament(since C++11)

自从c++11起,c++提供了range-based for stament 的方式来遍历容器的内容。其基本语法如下:

1
2
3
for( decl : coll ){
statement
}

如下使用范例:

1
2
3
for(int i : {2, 3, 4, 5, 6, 7, 8, 9}){
std::cout<< i <<std::endl;
}

{2, 3, 4, 5, 6, 7, 8, 9}表示一个聚合体,可以是一个数组,其所要表达的是i依次从聚合体中取出一个元素,然后通过std::cout输出。下面来看一个容器的例子:

1
2
3
4
5
6
7
8
std::vector<int> vec;
····
for(auto elem : vec){
std::cout<< elem <<std::endl;
}
for(auto& elem : vec){
elem+=3;
}

在上面的例子中,通过auto来自动推导类型,然后从容器中依次取出元素,交由std::cout输出;在第二个循环中,elem的类型不再是auto,而变为了auto&,我们对容器的内容进行了引用,这样就可以对容器的内容进行更改了。

通过auto确实可以简化代码,但是这种简化却是应该尽量避免的,原因是一旦你这样做了,别人在看该代码的时候可能会对elem的类型产生困惑,不利于阅读。

欢迎关注我的其它发布渠道