1. 容器

1.1 序列式容器

1.1.1 vector

1. 初始化

void test()
{
    // 1. 创建无参对象
    vector<int> vec;

    // 2. 传count个value
    vector<int> vec(10, 2);

    // 3. 迭代器范围 [arr, arr + 10) 前闭后开
    int arr[10] = {2, 4, 6, 8, 0, 1, 3, 5, 7, 9};
    vecotr<int> vec(arr, arr + 10);

    // 4. 拷贝构造函数或移动构造函数
    vector<int> vec(10, 2);
    vector<int> vec2(vec);

    // 5. 大括号形式
    vector<int> vec = {2, 4, 6, 8, 0, 1, 3, 5, 7, 9};
}

2. 遍历

void test()
{
    // 遍历方式1
    for (size_t idx = 0; idx != vec.size(); ++ idx)
    {
        cout << vec[idx] << " ";
    }
    cout << endl;

    // 遍历方式2
    vector<int>::iterator it;
    for (it = vec.begin(); it != vec.end(); ++ it)
    {
        cout << *it << " ";
    }
    cout << endl;

    // 遍历方式3
    for (auto &elem : vec)
    {
        cout << elem << " ";
    }
    cout << endl;
}

3. 插入与删除

void test()
{
    /*********************一、在vector尾部进行插入和删除*********************/
    vector<int> number{1, 3, 7, 9, 5, 8, 2, 6};
    cout << "在vector尾部进行插入和删除..." << endl;

    number.push_back(10); // push_back()两倍扩容
    number.pop_back();

    /*********************二、在vector头部进行插入和删除*********************/
    // vector不支持在头部进行插入和删除
    // 原因：vector是一端开口的，如果在头部插入一个元素，那么会将后面所有的元素都后移一位，然后将最开始的
    // 位置空出来，存新插入的元素。如果在头部进行删除的话，后面的元素都要向前挪动一格，这样时间复杂度就是
    // O(N)，效率比较低

    /*********************三、在vector任意位置进行插入insert()*********************/

    /* vector的insert()扩容原理：
    对于push_back()而言，每次插入元素的个数是一定的，那么每次按照两倍形式进行扩容，容量肯定是够的。但是对于
    insert()而言，每次插入元素的个数是不确定的，所以就没有一个统一的标准进行扩容

    将capacity() = n, size() = m, 插入元素的个数 = t;
    1. t < n - m; 不会发生扩容
    2. n - m < t < m; 按照2 * m进行扩容
    3. t > n - m && m < t < n; 按照t + m进行扩容
    4. t > n - m && t > n; 按照t + m进行扩容 */

    // 1. 在某个位置插入一个元素
    // 由于vector的扩容原理，可能发生vector迭代器失效问题
    // 所以需要在每次插入前，手动将迭代器复位
    it = number.begin();
    it ++;
    it ++;
    number.insert(it, 30);
    cout << "*it = " << *it << endl;
    cout << "number.size() = " << number.size() << endl;
    cout << "number.capacity() = " << number.capacity() << endl;
    cout << endl;

    // 2. 在某个位置插入count个元素
    it = number.begin();
    it ++;
    it ++;
    number.insert(it, 4, 400);

    // 3. 在某个位置插入迭代器范围的元素
    it = number.begin();
    it ++;
    it ++;
    vector<int> vec = {22, 33, 44, 55};
    number.insert(it, vec.begin(), vec.end());

    // 4. 在某个位置插入大括号的元素
    it = number.begin();
    it ++;
    it ++;
    number.insert(it, {100, 200, 300});

    /*********************四、在vector中删除连续重复元素的问题*********************/
    vector<int> number = {1, 3, 4, 5, 5, 5, 6, 7, 8, 5, 5};

    for (vector<int>::iterator it = number.begin(); it != number.end();)
    {
        if (*it == 5)
            number.erase(it); // 删除当前元素会导致后面的元素向前移动
        else // 删除连续重复的元素
            ++ it;
    }

    /*********************五、vector元素的清空*********************/
    // vector会将元素的清楚与空间的回收分开，所以会分别提供clear()和shrink_to_fit()
    number.clear(); // 只是把元素清空，空间没有回收
    number.shrink_to_fit(); // 回收多余空间 capacity() - size()
    cout << "number.size() = " << number.size() << endl; 
    cout << "number.capacity() = " << number.capacity() << endl;

    /*********************六、vector插入自定义类型元素 emplace_back()*********************/
    vector<Point> vec;
    vec.push_back(Point(1, 2));
    vec.emplace_back(3, 4); // 就相当于插入了Point(3, 4)，使用了可变模板参数

    /*********************七、获取vector第一个元素的地址data()*********************/
    int *firstElemAddr = vec.data();
    int *firstElemAddr = &*vec.begin();
}

4. vector源码解读

在vector中，operator[]与at()函数都具有随机访问的功能，但是at()函数有范围检查，所以更加安全一些

1.1.2 deque

1. 初始化
同vector的五种初始化方法

2. 遍历
同vector的三种遍历方法

3. 插入与删除

void test2()
{
    deque<int> number{1, 3, 7, 9, 5, 8, 2, 6};
    display(number);

    cout << "在deque尾部进行插入和删除" << endl;
    number.push_back(10);
    number.pop_back();

    cout << "在deque头部进行插入和删除" << endl;
    number.push_front(100);
    number.pop_front();

    // deque在任意位置进行插入和删除和vector四种方法相同，迭代器不用置位，在任意位置插入迭代器范围的元素时，迭代
    // 器指向可能发生变化

    // deque容器的清空与vector相同

    // deque插入自定义类型元素同vector，多个emplace_front()
}

4. deque源码解读

1.1.3 list

1. 初始化
同vector的五种初始化方法

2. 遍历
由于list不支持随机访问，所以只有两种遍历方法

3. 插入与删除

void test3()
{
    // list在尾部进行插入和删除同deque

    // list在头部进行插入和删除同deque

    // list在任意位置进行插入和删除和vector四种方法相同，迭代器不用置位，任何情况下迭代器指向不会发生变化

    // list删除元素的时候会顺带回收空间，所以不会提供回收空间的函数，只有clear()

    // list插入自定义类型元素同deque

    // list特殊操作：
    list<int> number = {1, 2, 2, 3, 5, 7, 9, 8, 6, 300};
    display(number);


    cout << endl << "测试链表逆置reverse()" << endl;
    number.reverse();
    display(number);

    cout << endl << "测试链表排序sort()" << endl;
    /* number.sort(); */ // 默认从小到大排序
    /* number.sort(std::greater<int>()); */ // 从大到小排序
    number.sort(CompareListLess<int>()); // 自定义比较函数
    display(number);
    cout << endl << "测试去除连续重复元素unique()" << endl;
    number.sort(); // 要去重，最好先排序，让重复的元素连续
    number.unique();
    display(number);

    cout << endl << "测试合并两个有序链表merge()" << endl;
    list<int> number2 = {30, 50, 4, 6, 2};
    number.sort();
    number2.sort(); // 先排序，注意两个链表都只能从小到大进行排序
    number.merge(number2);
    display(number);
    display(number2); // 链表number2被清空

    cout << endl << "测试插入另一个链表splice()" << endl;
    list<int> number3 = {444, 888, 999, 111, 333};
    display(number3);
    auto it = number.begin();
    ++ it;
    ++ it;
    cout << "*it = " << *it << endl;
    number.splice(it, number3);
    display(number);
    display(number3); // 链表number3被清空

    cout << endl << "测试splice()移动一个元素" << endl; 
    list<int> number4 = {1000, 8000, 9000, 6000, 3000};
    display(number4);
    it = number.begin();
    ++ it;
    ++ it;
    cout << "*it = " << *it << endl;
    auto it2 = number4.begin();
    ++ it2;
    ++ it2;
    cout << "*it2 = " << *it2 << endl; 
    // it2指向的元素移动到number的it指向的位置前面
    number.splice(it, number4, it2);
    display(number);
    display(number4); // it2指向的元素没了

    cout << endl << "测试splice()移动两个迭代器所指向的范围元素" << endl; 
    it = number.begin();
    ++ it;
    ++ it;
    it2 = number4.begin();
    auto it3 = number4.end();
    -- it3;
    -- it3;
    cout << "*it = " << *it << endl; 
    cout << "*it2 = " << *it2 << endl; 
    cout << "*it3 = " << *it3 << endl; 
    // it3所指的元素不取，左闭右开区间 [it2, it3)
    number.splice(it, number4, it2, it3); 
    display(number);
    display(number4);

    cout << endl << "测试splice()操作同一个链表" << endl; 
    // 可以但不推荐，有可能发生内存交叉问题，类似的strcpy()、memcpy()
    list<int> numberList = {1, 3, 5, 7, 9, 8, 6, 100, 300, 600};
    auto it4 = numberList.begin();
    ++ it4;
    ++ it4;
    cout << "*it4 = " << *it4 << endl;
    auto it5 = numberList.end();
    -- it5;
    -- it5;
    cout << "*it5 = " << *it5 << endl;
    numberList.splice(it4, number, it5);
    display(numberList);

}

4. list源码解读

1.2 关联式容器

1.2.1 set/multiset

1. set的基本使用

void test()
{
    // set的特征
    // 1. 元素是唯一的，不能重复
    // 2. 默认情况下，会按照Key值升序排列
    // 3. 底层使用的是红黑树结构

    set<int> number = {1, 3, 5, 7, 9, 3, 5, 10};
/*  set<int, std::greater<int>> number = {1, 3, 5, 7, 9, 3, 5, 10}; // 从大到小初始化  */

    cout << "set的查找操作" << endl;
    size_t cnt1 = number.count(1);
    size_t cnt2 = number.count(8);
    cout << "cnt1 = " << cnt1 << endl;
    cout << "cnt2 = " << cnt2 << endl;

    auto it = number.find(5);
    if (it == number.end())
        cout << "find()没找到" << endl;
    else
        cout << "find()找到 " << *it << endl;

    cout << endl << "set的插入操作" << endl;
    display(number);
    // 1. 插入一个元素
    pair<set<int>::iterator, bool> ret = number.insert(100);
    if (ret.second)
        cout << "插入成功 " << *ret.first << endl;
    else
        cout << "插入失败" << endl;
    display(number);

    // 2. 插入迭代器范围个元素
    vector<int> vec = {1, 3, 5, 2, 4, 6, 200};
    number.insert(vec.begin(), vec.end());
    display(number);

    // 3. 插入大括号个元素
    number.insert({22, 33, 2, 1, 6, 300});
    display(number);

    cout << endl << "set的删除操作" << endl;
    it = number.begin();
    ++ it;
    ++ it;
    /* cout << "*it = " << *it << endl; */
    number.erase(it);
    display(number);

    number.erase(1);
    display(number);

    cout << endl << "set不支持下标访问" << endl;
    /* cout << number[3] << endl; // error */

    cout << endl << "set不支持修改" << endl;
    /* *it = 6; // error */
}

2. set针对于自定义类型的使用
注意要对自定义类型书写比较函数，三种方法

// 方法1：重载小于号
bool operator<(const Point& lhs, const Point& rhs)
{
    cout << "bool operator<(const Point&, const Point&)" << endl;
    if (lhs.getDistance() < rhs.getDistance())
    {
        return true;
    }
    else if (lhs.getDistance() == rhs.getDistance())
    {
        if (lhs._ix < rhs._ix)
        {
            return true;
        }
        else if (lhs._ix == rhs._ix)
        {
            if (lhs._iy < lhs._iy)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        else
        {
            return false;
        }
    }
    else
    {
        return false;
    }
}

// 方法2：伪函数形式
struct ComparePoint
{
    bool operator()(const Point &lhs, const Point &rhs) const
    {
        cout << "bool operator()(const Point &lhs, const Point &rhs)" << endl;
    }
};

// 方法3：命名空间std的扩展 + 模板的特化
namespace std
{
// 模板的特化
template<>
struct less<Point>
{
    bool operator()(const Point &lhs, const Point &rhs) const
    {
        return lhs < rhs; // 重载小于号后可使用
    }
};
} // end of namespace std;

// 初始化方法
/* set<Point, ComparePoint> number = { */
    set<Point> number = {
        Point(1, 2),
    };

// 从大到小初始化方法
/*  set<Point, ComparePointGreater> number = { */
    set<Point, std::greater<Point>> number = {

    };

3. multiset的基本使用
multiset的用法与set基本相同，只是multiset的key可以重复
multiset的自定义类型与set是完全一样的

iterator = insert(Key) // 插入一个Key，肯定成功，这是与set不同的一个地方
iterator = lower_bound(Key) // 返回第一个大于等于Key的迭代器
iterator = upper_bound(Key) // 返回第一个大于Key的迭代器
pair<iterator, iterator> = equal_range(Key) // 返回两个迭代器，分别是lower_bound()和upper_bound()返回的迭代器

multiset的自定义类型与set是完全一样的

1.2.2 map/multimap

// map的特征：
// 1. 存放的是key-value类型，key值是唯一的，不能重复，value值可以重复也可以不重复
// 2. 默认情况下，按照key值进行升序排列
// 3. 底层使用的是红黑树


// 初始化
map<int, string, std::less<int>> number = {
    std::pair<int, string>(1, "beijing"),
    {3, "hebei"},
    std::make_pair(5, "heilongjiang"),
};

// 查找
size_t = count(Key)
iterator = find(Key) // 查找失败 iterator == end()

// 插入
insert(pair) // 类似于set

// map下标操作，支持查找、插入和修改功能
// 注意下标是Key的类型
number[6] = "chongqing"; 

map的自定义类型按照Key值进行排序，Key是内置类型就不用重载<运算符
3. multimap的基本使用

// 与map不同的地方
// 1. key值是不唯一的，可以重复
// 2. find(key)找到的value按初始化的顺序
// 3. iterator = insert(pair) insert一定会成功，构建pair有三种方式
// 4. 由于在key值相同的情况下，value值是不一样的，会发生二义性，所以不支持下标

1.3 无序关联式容器

1.3.1 unordered_set/unordered_multiset

1. unordered_set的基本使用

// unordered_set的模板形式


// unordered_set的特征
// 1. Key值是唯一的，不能重复（类似于set）
// 2. Key值是没有顺序的
// 3. 底层是哈希


// 1. 初始化
无参、count个value、迭代器范围、拷贝（移动）构造函数

// 2. 查找
// size_t = count(Key)
// find(Key)
// pair<it, it> = equal_range(Key)

// 3. 插入
// insert(Key)

// 4. 删除
// iterator = erase(iteartor pos)

// 5. 不支持下标访问

// 6. 不支持迭代器修改

2. unordered_set针对于自定义类型
要实现两个模板函数，std::hash[HTML_REMOVED]实现方法有两种：模板的特化和函数对象，std::equal_to[HTML_REMOVED]运算符有三种，多了一种运算符重载

// 哈希函数实现
// 方式一：函数对象
struct HashPoint
{
    size_t operator()(const Point &rhs) const
    {
        cout << "size_t operator()(const Point &lhs) const" << endl;
        return (rhs.getX() << 1) ^ (rhs.getY() << 2); 
    }
};
// 方式二：命名空间扩展 + 模板特化
namespace std
{
template<>
struct hash<Point>
{
    size_t operator()(const Point &rhs) const
    {
        cout << "size_t std::hash::operator()(const Point &lhs) const" << endl;
        return (rhs.getX() << 1) ^ (rhs.getY() << 2); 
    }
};
}; // end of namespace std

// 比较函数实现
// 方式一：重载operator==
bool operator==(const Point &lhs, const Point &rhs)
{
    cout << "operaotr==(const Point &, const Point &)" << endl;
    return (lhs.getX() == rhs.getX()) && (lhs.getY() == rhs.getY());
}
// 方式二：函数对象
struct EqualToPoint
{
    bool operator()(const Point &lhs, const Point &rhs) const
    {
        cout << "EqualToPoint::operaotr()(const Point &, const Point &)" << endl;
        return (lhs.getX() == rhs.getX()) && (lhs.getY() == rhs.getY());
    }
};
// 方式三：命名空间std扩展 + 模板特化
namespace std
{
template<>
struct equal_to<Point>
{
    bool operator()(const Point &lhs, const Point &rhs) const
    {
        cout << "std::equal_to::operaotr()(const Point &, const Point &)" << endl;
        return (lhs.getX() == rhs.getX()) && (lhs.getY() == rhs.getY());
    }
};
};
#if 1
void test2()
{
    /* unordered_set<Point, std::hash<Point>> number = { */
    unordered_set<Point, HashPoint, EqualToPoint> number = {
        Point(1, 2),
        Point(1, -2),
        Point(-1, 2),
        Point(1, 2),
        Point(3, 2),
        Point(-5, 2),
        Point(3, 2)
    };
    display(number);

3. unordered_multiset的基本使用

// unordered_multiset的特征
// 1. Key值不是唯一的，可以重复（类似于multiset）
// 2. Key值是没有顺序的
// 3. 底层是哈希

// 基本使用（除了insert()的返回值）和针对于自定义类型的使用和unordered_set是完全一样的

1.3.2 unorderer_map/unordered_multimap

1. unordered_map的基本使用

// 和map一样，只是Key没有顺序，底层使用哈希

// 初始化、遍历、查找、插入、支持下标

// 针对自定义类型，如果Key值是内置类型（如string），就不用实现std::hash<Key>和std::equal_to<Key>

2. unordered_multimap的基本使用

// 和multimap一样，只是Key没有顺序，底层使用哈希

// 初始化、遍历、查找、插入、不支持下标

// 针对自定义类型，如果Key值是内置类型（如string），就不用实现std::hash<Key>和std::equal_to<Key>

1.4 容器的选择

1. 容器中元素是否有顺序（重要）
- 有顺序：首选关联式容器或优先级队列，次选序列式容器，不会选无序关联式容器
- 没有顺序：首选无序关联式容器，次选序列式容器，不会选关联式容器和优先级队列
2. 时间复杂度（重要）
- 时间复杂度O(1)：无序关联式容器（哈希）
- 时间复杂度O(logN)：关联式容器（红黑树）
- 时间复杂度O(N)：序列式容器
3. 容器是否具有下标
- vector、deque、map、unordered_map
4. 迭代器的类型
- 随机访问迭代器：vector、deque
- 双向迭代器：list、关联式容器
- 前向迭代器：无序关联式容器
5. 容器是否具有迭代器
- 除了容器适配器，其他容器都有迭代器

2. 迭代器

作为算法操纵容器内元素的桥梁

2.1 输入迭代器（InputIterator）

2.2 输出迭代器（OutputIterator）

2.3 前向访问迭代器（ForwardIterator）

2.4 双向访问迭代器（BidirectionalIterator）

2.5 随机访问迭代器（RandomAccessIterator）

3. 适配器

3.1 容器适配器

3.1.1 stack

template<
    class T,
    class Container = std::deque<T>
> class stack;
/*
The container must satisfy the requirements of SequenceContainer. Additionally, it must provide the following functions with the usual semantics:
back()
push_back()
pop_back()
The standard containers std::vector, std::deque and std::list satisfy these requirements.
*/

3.1.2 queue

template<
    class T,
    class Container = std::deque<T>
> class queue;
/*
The container must satisfy the requirements of SequenceContainer. Additionally, it must provide the following functions with the usual semantics:
back()
front()
push_back()
pop_front()
The standard containers std::deque and std::list satisfy these requirements.
*/

3.1.3 priority_queue

// 1. 底层使用堆
// 2. 将堆顶与新插入的元素进行比较，满足std::less就换位置

// 模板类型
template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type> // 体现了类型萃取
> class priority_queue;
/*
The container must satisfy the requirements of SequenceContainer, and its iterators must satisfy the requirements of RandomAccessIterator. Additionally, it must provide the following functions with the usual semantics:
front()
push_back()
pop_back()
The standard containers std::vector and std::deque satisfy these requirements.
*/

// 初始化、插入、遍历
void test()
{
    vector<int> vec = {1, 3, 8, 9, 5, 3, 6, 7};
    /* priority_queue<int> pque(vec.begin(), vec.end()); // 1. 迭代器范围 */
    priority_queue<int> pque;// 2. 创建空对象

    for (size_t idx = 0; idx != vec.size(); ++ idx)
    {
        pque.push(vec[idx]);
        cout << "优先级最高的元素：" << pque.top() << endl;
    }

    while (!pque.empty())
    {
        cout << pque.top() << "  ";
        pque.pop();
    }
    cout << endl;
}

// 保存自定义类型的话，需要实现比较函数，和set的三种实现方式相同

3.2 迭代器适配器

3.2.1 插入迭代器

3.2.1.1 back_insert_iterator

在赋值运算符函数opeartor=()里调用容器的push_back()

3.2.1.2 front_insert_iterator

在赋值运算符函数opeartor=()里调用容器的push_front()

3.2.1.3 insert_iterator

在赋值运算符函数opeartor=()里调用容器的insert()

void test()
{
    vector<int> vecNumber = {1, 3, 5, 6, 8};
    list<int> listNumber = {11, 22, 77, 44, 99};

    /* copy(listNumber.begin(), listNumber.end(), back_inserter(vecNumber)); */
    copy(listNumber.begin(), listNumber.end(), back_insert_iterator<vector<int>>(vecNumber));
    copy(vecNumber.begin(), vecNumber.end(), ostream_iterator<int>(cout, "  "));
    cout << endl;

    /* copy(vecNumber.begin(), vecNumber.end(), front_inserter(listNumber)); */
    copy(vecNumber.begin(), vecNumber.end(), front_insert_iterator<list<int>>(listNumber));
    copy(listNumber.begin(), listNumber.end(), ostream_iterator<int>(cout, "  "));
    cout << endl;

    set<int> setNumber = {1, 2, 7, 4, 50};
    auto sit = setNumber.begin();
    /* copy(vecNumber.begin(), vecNumber.end(), inserter(setNumber, sit)); */
    copy(vecNumber.begin(), vecNumber.end(), insert_iterator<set<int>>(setNumber, sit)); // 注意多一个迭代器参数
    copy(setNumber.begin(), setNumber.end(), ostream_iterator<int>(cout, "  "));
    cout << endl;
}

3.2.2 流迭代器

写到缓冲区里

3.2.2.1 istreambuf_iterator

void test()
{
    istream_iterator<int> isi(cin);
    vector<int> vec;
    copy(isi, istream_iterator<int>(), std::back_inserter(vec));
    ostream_iterator<int> osi(cout, "\n");
    copy(vec.begin(), vec.end(), osi);
}

3.2.2.2 ostreambuf_iterator

void test()
{
    ostream_iterator<int> osi(cout, "\n"); // 参数：输出流对象、结束标识符（会打出来）
    vector<int> vec = {1, 3, 5, 8, 7};
    copy(vec.begin(), vec.end(), osi);
}

3.2.3 反向迭代器

3.2.3.1 reverse_iterator

void test()
{
    vector<int> vec = {1, 3, 5, 8, 6};
    auto rit = vec.rbegin();
    while (rit != vec.rend())
    {
        cout << *rit << "  ";
        ++ rit;
    }
    cout << endl;
}

3.3 函数适配器

3.3.1 绑定器

3.3.1.1 bind1st

// 第三种形式：bind1st和std::less<>结合，用x绑定函数的第一个参数
    auto it = remove_if(vec.begin(), vec.end(), bind1st(std::less<int>(), 9));

3.3.1.2 bind2nd

// 第四种形式：bind2nd和std::greater结合，用x绑定函数的第二个参数
    auto it = remove_if(vec.begin(), vec.end(), bind2nd(std::greater<int>(), 9));

3.3.1.3 bind

1. bind与function的基本使用

#include <iostream>                                                                                                                                        
#include <functional>

using namespace std;

int add(int x, int y)
{
    return x + y;
}

int func(int x, int y, int z)
{
    return x + y + z;
}

class Example
{
public:
    int add(int x, int y)
    {
        cout << "Example::add(int, int)" << endl;
        return x + y;
    }
};

// 1. bind的基本使用
void test()
{
    /* auto f1 = bind(&add, 3, 4); */
    auto f1 = bind(add, 3, 4);
    cout << "f1() = " << f1() << endl;

    /* auto f2 = bind(&func, 10, 20, 30); */
    auto f2 = bind(func, 10, 20, 30);
    cout << "f2() = " << f2() << endl;

    Example e1;
    // bind需要的是函数的入口地址，直接使用
    // 类名::函数名的形式加取地址
    auto f3 = bind(&Example::add, &e1, 5, 6);
    cout << "f3() = " << f3() << endl;
}

int func2()
{
    return 8;
}

int func3()
{
    return 10;
}

// 2. 函数指针
void test2()
{
    typedef int(*pFunc)();

    // 把func2分成了注册和执行，就延迟了func2的执行
    pFunc f = func2; // 注册回调函数
    cout << "f() = " << f() << endl; // 执行回调函数

    f = func3;
    cout << "f() = " << f() << endl; //
}

void func4(int x1, int x2, int x3, const int &x4, int x5)
{
    cout << "x1 = " << x1 << endl
         << "x2 = " << x2 << endl
         << "x3 = " << x3 << endl
         << "x4 = " << x4 << endl
         << "x5 = " << x5 << endl;
}

// std::placeholders的使用
void test3()
{
    using namespace std::placeholders;

    int number = 50;
    // _n代表第几个实参代替本形参位置
    // std::cref() = (const) reference, (const)引用的包装器
    // std::ref = reference, 引用的包装器
    auto f = bind(func4, std::placeholders::_3, 10, _1, std::cref(number), number);
    number = 100;
    f(11, 22, 33, 44, 55, 66, 77); // 多余的参数就丢弃
}

// function<>的使用
void test4()
{
    // 函数的类型，也叫函数的标签：函数返回类型和函数参数列表

    // f1的类型：int()
    /* auto f1 = bind(add, 3, 4); */
    function<int()> f1 = bind(add, 3, 4);
    cout << "f1() = " << f1() << endl;

    // f2的类型：int()
    function<int()>f2 = bind(func, 10, 20, 30);
    cout << "f2() = " << f2() << endl;

    // f3的类型：int()
    Example e1;
    function<int()>f3 = bind(&Example::add, &e1, 5, 6);
    cout << "f3() = " << f3() << endl;

    // f4的类型: int(int)
    function<int(int)> f4 = bind(add, std::placeholders::_1, 10);
    cout << "f4() = " << f4(9) << endl; 
}

2. bind与function的结合使用

3.3.2 否定器

3.3.2.1 not1

3.3.2.2 not2

3.3.3 成员函数适配器

3.3.3.1 mem_fun（弃）

3.3.3.2 mem_fun_ref（弃）

3.3.3.3 mem_fn

void test()
{
    // 基本使用：传给mem_fn()一个成员函数地址，
    // 返回一个函数对象f
    // 需要传给f一个该成员函数所在类的对象才能执行这个成员函数
    auto f = mem_fn(&Number::print);    
    f(Number(10));
    cout << endl;

    // 与其他算法结合使用
    vector<Number> vec;
    for (int idx = 0; idx != 30; ++ idx)
    {
        vec.push_back(Number(idx));
    }

    /* for_each(vec.begin(), vec.end(), [](Number &rhs) { */
    /*             rhs.print(); */
    /*          }); */
    for_each(vec.begin(), vec.end(), std::bind(&Number::print, std::placeholders::_1));
    cout << endl;

    // 删除所有的偶数
    auto it = remove_if(vec.begin(), vec.end(), std::bind(&Number::isEven, std::placeholders::_1));
    vec.erase(it, vec.end());
    for_each(vec.begin(), vec.end(), std::bind(&Number::print, std::placeholders::_1));
    cout << endl;

    // 删除所有质数
    it = remove_if(vec.begin(), vec.end(), std::bind(&Number::isPrime, std::placeholders::_1));
    vec.erase(it, vec.end());
    for_each(vec.begin(), vec.end(), std::bind(&Number::print, std::placeholders::_1));
    cout << endl;
}

4. 函数对象

函数对象（仿函数）：所有可以与小括号进行结合，并体现函数的形式（将函数对象的概念进行扩充）
1. 重载了函数调用运算符类创建的对象
2. 普通函数或成员函数
3. 函数指针

5. 算法

5.1 非修改式操作

// for_each()的使用

// func必须是一元函数
void func(int &val)
{
    ++ val;
    cout << val << "  "; // 遍历
}

void test()
{
    int a = 100;
    vector<int> vec = {1, 3, 5, 7, 9};
    /* for_each(vec.begin(), vec.end(), func); */

    // 匿名函数，lambda表达式
    // [] 捕获列表
    // () 函数的参数列表
    // ->返回类型
    // {  } 函数体
    for_each(vec.begin(), vec.end(), [&a](int &val)->void { // 匿名函数
                cout << "a = " << a << endl;
                ++ val;
                cout << val << "  ";
             });
    cout << endl;
}

5.2 修改式操作

// remove_if()的使用

// 一元断言函数
bool func(int &value)
{
    return value > 9;
}

void test()
{
    vector<int> vec = {1, 9, 8, 22, 50, 124, 8, 3, 2};
    for_each(vec.begin(), vec.end(), [](int &value){
                cout << value << "  ";
             });
    cout << endl;

    // remove_if将满足函数的Key用后面不满足的Key覆盖
    // 返回指向多余Key的迭代器
    // 可以配合erase()将多余Key删除
    // 为什么要这样呢？因为要满足泛型编程思想，对于vector可能出bug

    // remove_if的第一种形式：传递一元断言
    auto it = remove_if(vec.begin(), vec.end(), func);

    // 第二种形式：传递lambda表达式
    /* auto it = remove_if(vec.begin(), vec.end(), [](int &value)->bool{ */
    /*                         return value > 9; */
    /*                     }); */

    // 第三种形式：bind1st和std::less<>结合
    /* auto it = remove_if(vec.begin(), vec.end(), bind1st(std::less<int>(), 9)); */

    // 第四种形式：bind2nd和std::greater结合
    /* auto it = remove_if(vec.begin(), vec.end(), bind2nd(std::greater<int>(), 9)); */

    vec.erase(it, vec.end());
    for_each(vec.begin(), vec.end(), [](int &value){
                cout << value << "  ";
             });
    cout << endl;

5.3 排序式操作

5.4 集合操作

6. 空间配置器

6.1 实现自定义Vector类

template<typename T>
class Vector
{
    typedef T * iterator;
public:
    Vector()
    : _start(nullptr)
    , _finish(nullptr)
    , _end_of_storage(nullptr)
    {

    }

    ~Vector();
    void push_back(const T &); 
    void pop_back();    
    int size() const;
    int capacity() const;

    iterator begin()
    {
        return _start;
    }

    iterator end()
    {
        return _finish;
    }

private:
    void reallocate();//重新分配内存,动态扩容要用的
private:    
    static std::allocator<T> _alloc;

    T *_start;                 //指向数组中的第一个元素
    T *_finish;                //指向最后一个实际元素之后的那个元素
    T *_end_of_storage;        //指向数组本身之后的位置
};
template <typename T>
std::allocator<T> Vector<T>::_alloc;

template <typename T>
Vector<T>::~Vector()
{
    while (_finish != _start)
    {
        _alloc.destroy(--_finish);
    }
    _alloc.deallocate(_start, capacity());
}

template <typename T>
void Vector<T>::push_back(const T & val)
{
    // 扩容
    if (size() == capacity())
    {
        // 1. 申请两倍新空间
        int oldSize = capacity();
        int newSize = oldSize > 0 ? 2 * oldSize : 1;
        T *tmp = _alloc.allocate(newSize);
        // 2. 拷贝老空间对象到新空间
        uninitialized_copy(_start, _finish, tmp);
        // 3. 销毁老空间位置的对象
        while (_finish != _start)
        {
            _alloc.destroy(--_finish);
        }
        // 4. 回收老空间
        _alloc.deallocate(_start, capacity());

        // 5. 指针指向新空间
        _start = tmp;
        _finish = _start + oldSize;
        _end_of_storage = _start + newSize;
    }

    if (size() < capacity())
    {
        _alloc.construct(_finish ++, val);
    }
}

template <typename T>
void Vector<T>::pop_back()
{
    if (size() > 0) 
    {
        _alloc.destroy(--_finish);
    }
}

template <typename T>
int Vector<T>::size() const
{
    return _finish - _start;
}

template <typename T>
int Vector<T>::capacity() const
{
    return _end_of_storage - _start;
}

template <typename Container>
void display(const Container &con)
{
    cout << "size() = " << con.size() << endl
         << "capacity() = " << con.capacity() << endl;
}

void test()
{
    Vector<int> vec;

    vec.push_back(1);
    display(vec);
    vec.push_back(2);
    display(vec);
    vec.push_back(3);
    display(vec);

    for (auto &elem : vec)
    {
        cout << elem << "  ";
    }
    cout << endl;

    vec.pop_back();
    display(vec);
}

6.2 原理

6.2.1 大于128字节，使用malloc/free

6.2.2 小于等于128字节，使用线程池+16个自由链表

6.3 源码剖析

6.4 总结

Q1：STL中，所有容器申请的空间在内存的那个位置？
A1：都在堆上
Q2：空间配置器中，代码流程是怎样的
A2：第一分支：一级空间配置器，底层调用的是malloc申请空间
第二分支：二级空间配置器，当申请的长度大于128字节的时候，底层走的还是malloc申请堆空间；当申请的长度小于128字节的时候，会使用自由链表（数组长度为16，S_free_list）+内存池（使用_S_start_free与_S_end_free指向内存池的首尾）的思想
Q3：函数调用过程是怎样的？
A3：allocate：进行申请空间，该函数会调用_S_refill
_S_refill：会将申请的空间进行切割，分成多个等分，然后进行挂接，该函数会调用_S_chunk_alloc
_S_chunk_alloc：是真正的申请空间的函数，该函数底层调用的是malloc，申请大片空间。该函数还有可能会进行递归调用。
_S_round_up：向上取整，得到8的整数倍
_S_freelist_index：获取自由链表的下标