C++ STL基本概念 学习笔记

组成

1.容器（containers）

2.算法  (algorithms)

3.迭代器 (iterators)

4.仿函数  (functors)

5.配接器 (adapters)

6.空间配置器  (allocators)

1. 容器

序列式容器：元素的可序(ordered), 有序（sorted）

关联式容器：

array: 大小固定的序列容器，保存了一个以严格的线性顺序排列的特定数量的元素。

各种数据结构：vector, list, deque, set, map, 用来存放数据。 从实现来看，是一种calss template

2. 算法

各种常见的算法，sort, search,copy, erase, 从实现来看，是一种function template

3. 迭代器

扮演容器与算法之间的胶合剂，是所谓的泛型指针。从实现的角度看，是一种将operator*,operator->, operator++, operator--等指针相关操作重载的class template. 所有STL容器都带有自己专属的迭代器。

4.仿函数

行为类似函数，可以作为算法的某种策略。

5. 配接器

一种用来修饰容器，仿函数，或者迭代器接口的东西。

例如STL提供的queue和stack，看似容器，实际是一种容器配接器，因为他们的底层完全借助deque，所有底部的操作都由deque提供。

6. 空间配置器

负责空间配置与管理。

-----------------------------------------------------------分割线----------------------------------------------------------------

临时对象的产生与应用：

临时对象是一种无名对象，在型别名称之后直接加括号，并可指定初值。例如shape(3,5),int(8).意义相当于调用相应的构造函数且不指定对象名。STL中常用于仿函数与算法的搭配上：（这一段暂时没理解，后面应该会讲到。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

template<typename T>   // 定义一个模板类 
class print
{
    public:
    void operator()(const T& elem)  // 运算符重载 
    {
        cout << elem << endl;
    }
};    //end

int main(int argc, char *argv[])
{
    int a[6] = {0,1,2,3,4,5};
    vector<int> iv(a, a+6);   // a是第一个元素的地址，a+6超尾, c++STL中的概念
    // print<int>()一个临时对象
    for_each(iv.begin(), iv.end(), print<int>());    
    return 0;
}

STL中的区间表示方法：
任何一个STL算法，都需要获得由一对迭代器(泛型指针)所表示的区间，用以表示操作范围，这一对迭代去所表示的是一个左闭右开的区间[first, last)，这种表示方法，能简化程序的设计。

例如定义一个库函数find()

//例如设计一个find库函数
template<class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value) // InputIterator 
{
    while(first!=last && *first!=value)
    {
        first++
    } 
    return first;    // 如果没找到，first指向的是最后一个元素的后一个位置 
    // c++中超尾的概念 
} 

此外, 上面用到的for_each也应用到了这种区间表示方法：

// 例如对于for_each的设计
template<class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f)  // InputIterator迭代器 
{
    for( ; first!=last; first++)
    {
        f(*first)
    }
    return f;
}

应为上述的两个过程都用到了迭代器的知识，在之前看c++的时候，没有理解迭代器，现在好像理解了它的作用是什么：

回顾一下之前的c++迭代器：

一个迭代器是一个指针，指向对象的一个元素，一个迭代器可以用来访问对象的所有元素，例如用一个指向数组元素的指针可以访问数组的所有元素。迭代器是编写c++通用算法的基础概念，例如STL总的copy函数的实现：

// STL中copy的实现：
template<class iterator>
void copy(iterator begin, iterator end, iterator to)
{
    // begin 迭代器的起始
    // end 迭代器的终止
    // to copy数据的目的地
    while(begin!=end)
    {
        *to = *begin;
        begin++;
        to++;
    } 
} 

为了简化迭代器的开发和基于迭代器的通用算法的分类，c++的STL定义了5中迭代器，输入，输出，前向，双向，随机访问，所有迭代器都具备操作符==，！=， *操作符，部分具有++,--操作符。

例如，定义一个线性表arrayList的迭代器：

// 迭代器的实现
class iterator
{
    protected:
    T* position; 

    public:
    typedef bidirectional_iterator_tag iterator_category;
    typedef T value_type;
    typedef ptrdiff_t difference_type;
    typedef T* pointer;
    typedef T& reference;

    // 构造函数
    iterator(pointer thePosition = 0)
    {
        position = thePosition;
    }

    // 解引用操作符
    T& operator*() const   // 只读函数 
    {
        return *position;
    } 
    T* operator->()        // 只读函数 
    {
        return &(*position);
    }

    // 重载迭代器的++运算符
    // 前缀+
    iterator& operator++()
    {
        position += 1;
        return *this;
    }
    // 后缀+
    iterator operator++(int dummy)  // 伪参数
    {
        iterator old = position;
        position++;
        return old;
    } 

    // 重载--运算符
    // 前缀-
    iterator& operator--()
    {
        position -= 1;
        return *this;
    }
    // 后缀- 
    iterator operator--()
    {
        iterator old = position;
        position++;
        return old;
    }

    // 重载！= ,==
    bool operator!=(const iterator right) const
    {
        return position != right.position;
    }

    bool operator==(const iterator right) const
    {
        return position == right.position;
    } 

}

function call操作符(operator( ) )：

在之前学习函数特性的时候，博客《c++ 函数指针》，c++ primer中介绍了函数指针，如需将函数作为参数传递，可以通过函数指针，但是函数指针有缺点，它无法持有自己的状态，也无法达到组件技术中的可适配性(也就是无法再将某些条件加诸其上而改变其状态，（python装饰器实现的便是这一功能)）。STL算法中所接受的条件( 用以改变状态的条件 )都是以仿函数的形式呈现。所谓仿函数(functor)使用起来和函数一样，如果对某个类进行operator()重载，他就成为一个仿函数。

所以这里可以对前面的for_each的第三个参数进行理解，他接受的实际是一个仿函数，这个仿函数相当于条件，可以改变for_each的状态：

再把代码复制过来，就很容易理解了：print类进行了operator()重载，所以他是一个仿函数

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

template<typename T>   // 定义一个模板类 
class print
{
    public:
    void operator()(const T& elem)  // 运算符重载 
    {
        cout << elem << endl;
    }
};    //end

int main(int argc, char *argv[])
{
    int a[6] = {0,1,2,3,4,5};
    vector<int> iv(a, a+6);   // a是第一个元素的地址，a+6超尾, c++STL中的概念
    // print<int>()一个临时对象
    for_each(iv.begin(), iv.end(), print<int>());    
    return 0;
}

再看两个例子：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

template<typename T> 
class plus   // plus()成为一个仿函数 
{
    T operator()(const T& x, const T& y)   // 重载() 
    {
        return x+y;
    }
};

template<typename T>
class minus   // minus()成为一个仿函数 
{
    T operator()(const T& x, const T& y)
    {
        return x-y;
    }
};


int main(int argc, char *argv[])
{
    // 仿函数对象
    plus<int> plusobj;
    minus<int> minusobj;

    cout << plusobj(12, 5) << endl;   // 临时对象 
    cout << minusobj(12, 5) << endl;

    // 和普通函数的用法一样
    cout << plus<int>()(12, 5) << endl;   // 临时对象 
    cout << minus<int>()(12, 5) << endl;

    return 0;
}

后面会介绍如何实现这种可配接能力

---------------------------------------------------------------------------------------------------------------

后面补充一些侯捷老师课上讲的内容：
对于C++ STL中几个部分的理解：

       容器中放入数据，要占用内存，但是在使用容器的时候，我们只关心如何存取数据，而内存的分配工作，是由配置器(Allocator)在背后帮我们完成的。容器中有了数据后，我们需要对数据进行操作，一些操作需要使用到算法中的操作，例如排序或者搜索。面向对象的方法倡导，将数据和方法封装到一个类中，将容器设计为一个类，但是对容器中数据的操作方法却不是在这个类中，那么如果要使用算法中的方法对容器中的数据进行操作，那么就涉及到如何获取到容器中的数据。所以算法和容器之间的桥梁就是迭代器(Iterator)， 迭代器相当于一种泛化的指针。

     仿函数： 实现对象之间的一些操作：比如定义对象之间的加减操作。（后面应该会详细介绍）

     适配器： 实现转换功能，例如，将容器做一些转换，迭代器做一些转换(后面应该会详细讲)

具体代码：

可以看到，在这个程序中用到了前面介绍的模块。

bind2nd： 表示绑定第二个参数。   less()模板函数

前闭后开区间：

begin() 和end()返回的是泛化指针。

通过迭代器遍历整个容器：

// 以vector为例：
vector<int> c;
vector<int>::iterator iter; 
for (iter=c.begin(); iter != c.end(); iter++)
{
    // do something
}

C++11 推出的range-based for statement:
语法：

for (decl : collector)
{
    // statement;
}

利用这种方法访问容器中的元素：

int main()
{
    int ia[6] = {21, 34, 35, 2, 29, 86};
    for (int i : ia)
    {
        cout << i << endl;
    }
    return 0;
}

对于其他容器中的元素，也可以用同样的方法进行访问：

int main()
{
    vector<int> a;
    for (int i = 0; i < 10; i++)
    {
        a.push_back(i + 1);
    }
    // 输出容器a中的元素
    for (auto elem : a)
    {
        elem *= 3;    // 不会改变容器中的值
        cout << elem << endl;
    }
    return 0;
}

或者：

int main()
{
    vector<int> a;
    for (int i = 0; i < 10; i++)
    {
        a.push_back(i + 1);
    }
    // 输出容器a中的元素
    for (auto& elem : a)
    {
        elem *= 3;    // 改变容器中的值
        cout << elem << endl;
    }
    return 0;
}

适度的使用auto可以简化程序的编写。