C++ | STL | 侯捷 | 学习笔记

1 STL概述

STL —— Standard Template Library，标准模板库

C++ Standard LIbrary，C++标准库中包含STL（即STL+一些小东西）

1.1 头文件名称

• C++标准库的 header files 不带 .h，例如：#include<vector>
• 新式 C header files 不带 .h，例如：#include<cstdio>
• 老式 C header files 带 .h 仍然可用，例如：#include<stdio.h>

新式 header 内的组件封装于 namespace std

老式 header 内的组件不封装于 namespace std

1.2 STL基础介绍

STL六大部件：容器(Containers)、分配器(Allocators)、算法(Algorithms)、迭代器(Iterators)、仿函数(Functors)、适配器(Adapters)

• 容器：放数据
• 分配器：是来支持容器将数据放到内存里
• 算法：是一个个函数来处理存放在容器里的数据
• 迭代器：就是来支持算法操作容器的
• 仿函数：作用类似函数，例如相加相减等等
• 适配器：有三种，分别将容器，迭代器，仿函数来进行一个转换

实例：

1. 首先是创建一个 container（vector）
2. allocator 来帮助 container 来分配内存（一般会忽略不写）
3. 用一个 Algorithm 来操作数据（count_if 是数出满足条件的个数）
4. iterator 就是一个泛化的指针，来告诉 Algorithm 要处理哪里的数据
5. 用一个 functor 来判断数据（less 其有两个参数传入，第一个 < 第二个就为真）
6. 先用一个 function adapter（bind2nd）绑定了第二个参数为 40；再用一个 function adapter（not1）来对整个判断结果进行否定

判断条件 predicate 为：not1(bind2nd(less<int>(), 40)) —— 表示 >= 40 数为真

前闭后开：[ )，基本所有容器都有 begin() end()，但 begin 是指向的容器的第一个元素，而 end 是指向的容器最后一个元素的下一个

例子：遍历容器

...
Container<T> c;
Container<T>::iterator i = c.begin();
for (; i != c.end(); ++i)
{
...
}


//但在C++11中可以用新语法简写
...
Container<T> c;
for (auto elem : c)
{
...
}

1.3 typename

在模板参数的关键字使用中与 class 是一样的

在类型前面加上 typename：

template <typename T>
class MyTemplateClass {
public:
    typedef typename T::NestedType NestedType;
};

template <typename T>
void MyTemplateFunction() {
    typename T::SomeType variable;
    // ...
}

在这个例子中，typename 用于告诉编译器 T::NestedType 和 T::SomeType 是类型名称而不是成员变量

typename 是一个用于明确指定符号是一个类型的关键字，以帮助编译器正确解析代码并避免歧义，如果不使用 typename，编译器可能会认为符号是一个值而不是类型，导致编译错误。

2 OOP vs. GP

• OOP —— Object-Oriented programming 面向对象编程

  将数据和操作关联到一起

  例如容器 List，其自带了一个 sort()，因为链表的存储空间不是连续的，Iterator 不能实现加减操作，所以不能使用全局的 ::sort()

• GP —— Generic Programming 泛式编程

  将数据和操作分开

  • 容器和算法的团队就可以各自闭门造车，其间通过 Iterator 联通即可
  • 算法通过 Iterator 确定操作范围，并通过 Iterator 取用容器的元素
  • 所有的算法，其内的最终涉及元素的操作都是比大小

3 容器

3.1 容器结构分类

分类：序列式容器 Sequence Container，关联式容器 Associative Container

• 序列式容器：按照放入的次序进行排列

  • Array 数组，固定大小
  • Vector 向量，会自动扩充大小
  • Deque 双向队列，双向都可以扩充
  • List 链表，双向链表
  • Forward-List 链表，单向链表

• 关联式容器：有 key 和 value，适合快速的查找

  STL中实现使用红黑树（高度平衡二叉树）和哈希表

  • Set，key 就是 value，元素不可重复

  • Map，key 和 value 是分开的，元素不可重复

  • Multi~，元素是可以重复的

  • Unordered~，HashTable Separate Chaining

其中 Array，Forward-List，Unordered~ 都是C++11的

3.2 序列式容器

3.2.1 array

测试

#include <array>
#include <iostream>
#include <ctime> 
#include <cstdlib> //qsort, bsearch, NULL

void test_array() {
    cout << "\n test_array().......... \n";

    // 创建一个包含long型元素的array容器，ASIZE为数组的大小
    array<long, ASIZE> c;

    // 记录开始时间
    clock_t timeStart = clock();

    // 填充数组 c 中的元素，使用 rand() 生成随机数
    for (long i = 0; i < ASIZE; ++i) {
        c[i] = rand();
    }
    // 输出填充数组所花费的毫秒数
    cout << "milli-seconds : " << (clock() - timeStart) << endl;

    // 输出数组的大小、第一个元素、最后一个元素、起始地址
    cout << "array.size()= " << c.size() << endl;
    cout << "array.front()= " << c.front() << endl;
    cout << "array.back()= " << c.back() << endl;
    cout << "array.data()= " << c.data() << endl;

    // 获取目标值
    long target = get_a_target_long();

    // 记录开始时间
    timeStart = clock();
    // 使用标准库的 qsort 函数（快排）对数组 c 进行排序
    ::qsort(c.data(), ASIZE, sizeof(long), compareLongs);

    // 使用标准库的 bsearch 函数（二分查找）在排序后的数组中搜索目标值
    long* pItem = (long*)::bsearch(&target, c.data(), ASIZE, sizeof(long), compareLongs);
    // 输出排序和搜索所花费的毫秒数
    cout << "qsort()+bsearch(), milli-seconds : " << (clock() - timeStart) << endl;

    // 如果找到目标值，输出该值；否则输出未找到消息
    if (pItem != NULL)
        cout << "found, " << *pItem << endl;
    else
        cout << "not found! " << endl;
}

运行结果：

随机数据填充容器：47ms；排序和搜索：187ms

---

深度探索

C++TR1下（比较简单）：

template <typename _Tp, std::size_t _Nm>
struct array
{
	typedef _Tp value_type;
	typedef _Tp* pointer;
	typedef value_type* iterator; // 迭代器为_Tp*


	value_type _M_instance[_Nm ? _Nm : 1]; // 如果_Nm为0，就分配一个空间

	iterator begin() { return iterator(&_M_instance[0]); }
	iterator end() { return iterator(&_M_instance[_Nm]); }
	...
};

GCC4.9下（复杂且无益处）：

// GCC4.9通过多个typedef以下面的逻辑创建的array里的data
typedef int T[100]; // T即类型int[100] 
T c; // 与int c[100]一样

3.2.2 vector

测试

#include <vector>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio>  //snprintf()
#include <iostream>
#include <ctime> 
#include <algorithm> 	//sort()

// 测试函数，接受一个引用类型的长整型参数
void test_vector(long& value)
{
    cout << "\ntest_vector().......... \n";
     
    vector<string> c;  	// 创建一个字符串类型的向量
    char buf[10];
    
    clock_t timeStart = clock();	// 记录开始时间							
    for(long i=0; i< value; ++i)	// 循环插入随机生成的字符串
    {
        try {
            snprintf(buf, 10, "%d", rand());	// 将随机整数转换为字符串
            c.push_back(string(buf));     	// 将字符串添加到向量中
        } // 这里是处理异常，如内存不够
        catch(exception& p) {
            cout << "i=" << i << " " << p.what() << endl;	
            // 输出出现异常的信息以及对应的索引值
            // 曾經最高 i=58389486 then std::bad_alloc
            abort();	// 异常处理后中止程序
        }
    }
    cout << "milli-seconds : " << (clock()-timeStart) << endl;	// 输出填充向量花费时间
    cout << "vector.max_size()= " << c.max_size() << endl;	// 输出向量的最大容量
    cout << "vector.size()= " << c.size() << endl;	// 输出向量的实际大小
    cout << "vector.front()= " << c.front() << endl;	// 输出向量的首元素
    cout << "vector.back()= " << c.back() << endl;	// 输出向量的末尾元素
    cout << "vector.data()= " << c.data() << endl;	// 输出向量地址
    cout << "vector.capacity()= " << c.capacity() << endl << endl;	// 输出向量的容量

    // 直接find来查找————次序查找
    string target = get_a_target_string();	// 获取一个目标字符串
    {
        timeStart = clock();	// 记录开始时间
        auto pItem = find(c.begin(), c.end(), target);	// 在向量中查找目标字符串
        cout << "std::find(), milli-seconds : " << (clock()-timeStart) << endl;  
        
        if (pItem != c.end())
            cout << "found, " << *pItem << endl << endl;	// 输出找到的目标字符串
        else
            cout << "not found! " << endl << endl;	// 输出未找到目标字符串
    }

    // 先排序再二分法查找
    {
        timeStart = clock();	// 记录开始时间
        sort(c.begin(), c.end());	// 对向量中的字符串进行排序
        cout << "sort(), milli-seconds : " << (clock()-timeStart) << endl; 
        
        timeStart = clock();	    
        string* pItem = (string*)::bsearch(&target, (c.data()), 
                                           c.size(), sizeof(string), compareStrings); 
        cout << "bsearch(), milli-seconds : " << (clock()-timeStart) << endl; 
       
        if (pItem != NULL)
            cout << "found, " << *pItem << endl << endl;	// 输出在排序后向量中找到的目标字符串
        else
            cout << "not found! " << endl << endl;	// 输出在排序后向量中未找到目标字符串
    }
    
    c.clear();	// 清空向量中的数据
    test_moveable(vector<MyString>(),vector<MyStrNoMove>(), value);	// 调用另一个函数进行测试
}

这是 array 在后面插入元素，其中若空间 capacity 不够，其会进行两倍扩充——即空间不够时会将原来的空间 *2

c.push_back(string(buf));

运行结果：

随机数据填充容器：3063ms；直接搜索：0ms（运气很好）；排序后二分查找：2765ms

---

深度探索

GCC2.9下：

一共3个指针：start，finish，end_of_storage

所以 sizeof(vector<int>) 是12

template <class T, class Alloc = alloc>
class vector
{
public:
	typedef T value_type;
	typedef value_type* iterator; // 迭代器就是T*
	typedef value_type& reference;
	typedef size_t size_type;
protected:
	iterator start;
	iterator finish;
	iterator end_of_storage;
public:
	iterator begin() { return start; }
	iterator end() { return finish; }
	size_type size() const { return size_type(end() - begin()); }
	size_type capacity() const { return size_type(end_of_storage - begin()); }
	bool empty() const { return begin() == end(); }
	reference operator[](size_type n) { return *(begin() + n); }
    // 所有连续储存的容器都有[]的重载
	reference front() { return *begin(); }
	reference back() { return *(end() - 1); }
}

vector 每次成长会大量调用元素的拷贝构造函数和析构函数，是一个大成本

void push_back(const T& x)
{
    if (finish != end_of_storage) // 还有备用空间
    {
        construct(finish, x); // 全局函数
        ++finish;
    }
    else // 无备用空间
        insert_aux(end(), x);
}

template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x){
if (finish != end_of_storage){ // insert_aux还会被其他函数调用所以还有检查
    // 在‘备用空间起始处’构建一个元素以vector最后一个元素为初值
    // insert_aux也可能被insert调用，元素插入位置不定
    construct(finish, *(finish - 1));
    ++finish;
    T x_copy = x;
    copy_backward(position, finish - 2, finish - 1);
    *position = x_copy;
}
else{
    const size_type old_size = size();
    const size_type len = old_size != 0 ? 2 * old_size : 1;
    // 原大小为0，则分配1；否则，分配原大小的2倍
    
    iterator new_start = data_allocator::allocate(len);
    iterator new_finish = new_start;
    try{
        // 拷贝安插点前的原内容
        new_finish = uninitialized_copy(start, position, new_start);
        construct(new_finish, x);
        ++new_finish;
        // 拷贝安插点后的原内容
        new_finish = uninitialized_copy(position, finish, new_finish);
    }
    catch (...){
        destroy(new_start, new_finish);
        data_allocator::deallocate(new_start, len);
        throw;
    }
    // 解构并释放原vector
    destroy(begin(), end());
    deallocate();
    // 调整迭代器，指向新vector
    start = new_start;
    finish = new_finish;
    end_of_storage = new_start + len;
}

GCC4.9下变得复杂：

且迭代器也变得乱七八糟，舍近求远，何必如此！！

3.2.3 list

测试

// 同理
void test_list(long& value)
{ 
    ...
        
    list<string> c;  // 创建一个字符串列表  	
    char buf[10];  // 字符串缓冲区
	
    ...
		
    string target = get_a_target_string();  // 获取目标字符串		
    timeStart = clock();		
    auto pItem = find(c.begin(), c.end(), target);  // 在列表中查找目标字符串						
    cout << "std::find()，milli-seconds : " << (clock()-timeStart) << endl;  // 输出查找时间		
	
    ...
    	
    timeStart = clock();		
    c.sort();  // 对列表进行排序						
    cout << "c.sort(), milli-seconds