C++STL标准库——体系结构与内核分析

本文根据源代码分析 C++ STL 之体系结构，而STL正是泛型编程（GP）最成功的作品，所以事实上就是以 STL 为标的深层次地探讨泛型编程
所谓 Generic Programming（GP，泛型编程），就是使用 template（模板）为主要工具来编写程序

视频学习：侯捷老师《C++标准库——体系结构与内核分析》

C++ Standard Library vs. Standard Template Library

C++ Standard Library C++ 标准库

Standard Template Library STL, 标准模板库

标准库以 header files 形式呈现
C++ 标准库的 header files 不带副档名（.h），例如 #include <vector>
新式 C header files 不带副档名 .h，例如 #include <cstdio>
旧式 C header filles （带有副档名.h）仍然可用，例如 #include <stdio.h>
新式 headers 内的组件封装于 namespace “std”

using namespace std;	// 打开 std 中所有组件，后续所有组件使用不需要加 std::
using std::cout;	    // 仅打开cout，后续使用cout不需要加 std:: ，其他组件仍然需要加 

旧式 headers 内的组件不封装于 namespace “std”

资源网站

CPlusPlus.com

CppReference.com

GCC, the GNU Compiler Collection - GNU Project

Bibliography（书目志）

《 THE C++ STANDARD LIBRARY》（SECOND EDITION）
《 STL源码剖析》（侯捷著）

STL体系结构基础介绍

STL六大部件（Components）：

容器（Containers）
分配器（Allocators）：容器的背后需要 allocator（分配器）来支撑它对内存的使用，容器有一个默认的分配器
算法（Algorithms）
迭代器（Iterators）
适配器（Adapters）
仿函数（Functors）

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

using namespace std;

int main()
{
    int ia[ 6 ] = { 27, 210, 12, 47, 109, 83 };
    vector<int,allocator<int>> vi(ia,ia+6);	// vector为container，allocator<int>为allocator
    
    cout << count_if(vi.begin(), vi.end(), 	// count_if为algorithm，vi.begin()和vi.end()为iterator
                     not1(bind2nd(less<int>(), 40)));	// not1为function adapter(negator)
    // bind2nd为function adapter(binder)，less<int>()为function object
    // not1(bind2nd(less<int>(), 40))为predicate
    return 0;
}

复杂度，Complexity，Big-oh

目前常见的 Big-oh 有下列几种情形：
1.O(1)或O(c)：称为常数时间（constant time）
2.O(n)：称为线性时间（linear time）
3.O(log₂n)：称为次线性时间（sub-linear time）
4.O(n²)：称为平方时间（quadratic time）
5.O(n³)：称为立方时间（cubic time）
6.O(2ⁿ)：称为指数时间（exponential time）
7.O(nlog₂n)：介于线性及二次方成长的中间之行为模式

“前闭后开”区间 [ )

c.begin()指向容器第一个元素，c.end()指向容器最后一个元素的下一个位置，*(c.begin())得到第一个元素，*(c.end())报错

// 遍历容器
Container<T> c;
...
Container<T>::iterator ite = c.begin();
for (; ite != c.end(); ++ite)
    ...

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

for ( decl : coll ) {	// 将coll中每个元素分别赋值给decl
    statement
}

for ( int i : { 2, 3, 5, 7, 9, 13, 17, 19 } ) {
    std::cout << i << std::endl;
}

auto keyword (since C++11)

std::vector<double> vec;
...
for ( auto elem : vec ) {	// auto为自动类型推导
    std::cout << elem << std::endl;
}

for ( auto& elem : vec ) {
    elem *= 3;
}

list<string> c;
...
list<string>::iterator ite;
ite = ::find(c.begin(), c.end(), target);	// 函数名字前面加::表示为全局函数，如果没有写，编译器在当前作用域没有找到该函数，也会到全局去找，加::更明白些

// 上面等价于
list<string> c;
...
auto ite = ::find(c.begin(), c.end(), target);

容器之分类与各种测试

容器——结构与分类

Sequence Containers（序列式容器）
Associative Containers（关联式容器）：标准未规定关联式容器底层实现采用红黑树，但是因为红黑树性能好，底层实现采用了红黑树

Unordered Containers（无序容器）属于 Associative Containers

Array、Forward-List、Unordered Containers 为 C++11 新增

以下测试程序之辅助函数

using std::cin;
using std::cout;
using std::string;

long get_a_target_long()
{
	long target=0;
    cout << "target" (0~" << RAND_MAX << "): ";
    cin >> target;
    return target;
}

string get_a_target_string()
{
    long target=0;
    char buf[10];
    
    cout << "target (0~" << RAND_MAX << "): ";
    cin >> target;
    snprintf(buf, 10, "%d", target);
    return string(buf);
}

int compareLongs(const void* a, const void* b)
{
    return ( *(long*)a - *(long*)b );
}

int compareStrings(const void* a, const void* b)
{
    if ( *(string*)a > *(stirng*)b )
        return 1;
    else if ( *(stirng*)a < *(string*)b )
        return -1;
    else
        return 0;
}

Sequence Containers（序列式容器）

使用容器 array（C++11 新增）

空间固定

#include <array>
#include <iostream>
#include <ctime>
#include <cstdlib>	// qsort, bsearch, NULL
namespace star01
{
    void test_array()
    {
        cout << "\ntest_array().......... \n";
        
    array<long,ASIZE> c;
        
    clock_t timeStart = clock();
        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;	//data()函数返回array首地址
        
    long target = get_a_target_long();
        
        timeStart = clock();
        qsort(c.data(), ASIZE, sizeof(long), compareLongs);
    long* pItem = (long*)bsearch(&target, (c.data()), ASIZE, sizeof(long), compareLongs);	//bsearch不是C++标准库里面提供的，是C语言本身之前提供的函数
        cout << "qsort()+bsearch(), milli-seconds : " << (clock()-timeStart) << endl;
        if(pItem != NULL)
            cout << "found, " << *pItem << endl;
        else
            cout << "not found! " << endl;
    }
}

// print:
// select: 1
// 
// test_array()..........
// milli-seconds : 47
// array.size()= 500000
// array.front()= 3557
// array.back()= 23084
// array.data()= 0x47a20
// target (0~32767): 20000
// qsort()+bsearch(), milli-seconds : 187
// found, 20000

使用容器 vector

每次存满后扩充当前空间倍数（2倍或者其他）
每次扩充两倍或者其他倍数

#include <vector>
#include <stdexcept>
#include <string>
#include <cstdlib>	// abort()
#include <cstdio>	// snprintf()
#include <iostream>
#include <ctime>
#include <algorithm>	// sort(), find()
namespace star02
{
    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 << "mulli-seconds : " << (clock()-timeStart) << endl;
        cout << "vector.size()= " << c.size() << endl;	// vector中实际元素个数
        cout << "vecotr.front()= " << c.front() << endl;
        cout << "vector.back()= " << c.back() << endl;
        cout << "vector.data()= " << c.data() << endl;	// vector空间的首地址
        cout << "vector.capacity()= " << c.capacity() << endl;	// vector申请的空间数量，只能往后扩大，且成倍扩大，当空间满时，申请一个当前空间两倍（可能其他倍数）的空间，将原来的数据一个个复制到新空间，然后删除原空间
        
        
    string target = get_a_target_string();
        {
            timeStart = clock();
        auto pItem = ::find(c.begin(), c.end(), target);	// 函数名字前面加::表示为全局函数，如果没有写，编译器在当前作用域没有找到该函数，也会到全局去找，加::更明白些
            cout << "::find(), milli-seconds : " << (clock()-timeStart) << endl;
            
            if (pItem != c.end())
                cout << "found, " << *pItem << endl;
            else
                cout << "not found! " << endl;
        }
        
        {
         	timeStart = clock();
            sort(c.begin(), c.end());
        string* pItem = (string*)bsearch(&target, (c.data()), c.size(), sizeof(string), compareStrings); //bsearch不是C++标准库里面提供的，是C语言本身之前提供的函数
            cout << "sort()+bsearch(), milli-seconds : " << (clock()-timeStart) << endl;
            
            if (pItem != NULL)
                cout << "found, " << *pItem << endl;
            else
                cout << "not found! " << endl;
        }
    }
}
// print:
// select: 2
// how many elements: 1000000
//
// test_vector().......... 
// milli-seconds : 3063
// vector.size()= 1000000
// vector.front()= 4047
// vector.back()= 2877
// vector.data()= 0x2880020
// vactor.capacity()= 1048576
// target (0~32767): 23456
// ::find(), milli-seconds : 0
// found, 23456
// sort()+bsearch(), milli-seconds : 2765
// found, 23456

使用容器 list

每次扩充一个节点

#include <list>
#include <stdexcept>
#include <string>
#include <cstdlib>	// abort()
#include <cstdio>	// snprintf()
#include <iostream>
#include <ctime>
#include <algorithm>	// find()
namespace star03
{
    void test_list(long& value)
    {
        cout << "\ntest_list().......... \n";
        
    list<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;
                abort();
            }
        }
        cout << "milli-seconds : " << (clock()-timeStart) << endl;
        cout << "list.size()= " << c.size() << endl;
        cout << "list.max_size()= " << c.max_size() << endl;	// max_size()返回容器由于系统或库实现限制而能够容纳的最大元素数量
        cout << "list.front()= " << c.front() << endl;
        cout << "list.back()= " << c.back() << endl;
        
    string target = get_a_target_string();
        timeStart = clock();
    auto pItem = ::find(c.begin(), c.end(), target);	// 函数名字前面加::表示为全局函数，如果没有写，编译器在当前作用域没有找到该函数，也会到全局去找，加::更明白些
        cout << "::find(), milli-seconds : " << (clock()-timeStart) << endl;
        
        if (pItem != c.end())
            cout << "found, " << *pItem << endl;
        else
            cout << "not found! " << endl;
        
        timeStart = clock();
        c.sort();	// 当容器自身也实现了sort排序函数时，其耗时（时间复杂度）一定低于STL中全局函数sort，一定使用自己的sort
        cout << "c.sort(), milli-seconds : " << (clock()-timeStart) << endl;
        
    }	// 又一阵子才离开函数；它在destroy...
}
// print:
// select: 3
// how many elements: 1000000

// test_list().......... 
// milli-seconds : 3265
// list.size()= 1000000
// list.max_size()= 357913941
// list.front()= 4710
// list.back()= 16410
// target (0~32767): 23456
// ::find(), milli-seconds : 16
// found, 23456
// c.sort(), milli-seconds : 2312

使用容器 forward_list（C++11 新增）

每次扩充一个节点

#include <forward_list>
#include <stdexcept>
#include <string>
#include <cstdlib>	// abort()
#include <cstdio>	// snprintf()
#include <iostream>
#include <ctime>
#include <algorithm>	// find()
namespace star04
{
    void test_forward_list(long& value)
    {
        cout << "\ntest_forward_list().......... \n";
    forward_list<string> c;
    char buf[10];
        
    clock_t timeStart = clock();
        for(long i=0; i< value; ++i)
        {
            try {
                snprintf(buf, 10, "%d", rand());
                c.push_front(string(buf));
            }
            catch(exception& p) {	// 防止空间申请失败
                cout << "i=" << i << " " << p.what() << endl;
                abort();
            }
        }
        cout << "milli-seconds : " << (clock()-timeStart) << endl;
        cout << "forward_list.max_size()= " << c.max_size() << endl;	// max_size()返回容器由于系统或库实现限制而能够容纳的最大元素数量
        cout << "forward_list.front()= " << c.front() << endl;
        //! cout << "forward_list.back()= " << c.back() << endl;	// no such member function
        //! cout << "forward_list.size()= " << c.size() << endl;	// no such member function
        
    string target = get_a_target_string();
        timeStart = clock();
    auto pItem = ::find(c.begin(), c.end(), target);	// 函数名字前面加::表示为全局函数，如果没有写，编译器在当前作用域没有找到该函数，也会到全局去找，加::更明白些
        cout << "::find(), milli-seconds : " << (clock()-timeStart) << endl;
        
        if(pItem != c.end())
            cout << "found, " << *pItem << endl;
        else
            cout << "not found! " << endl;
        
        timeStart = clock();
        c.sort();	// 当容器自身也实现了sort排序函数时，其耗时（时间复杂度）一定低于STL中全局函数sort，一定使用自己的sort
        cout << "c.sort(), milli-seconds : " << (clock()-timeStart) << endl;
    }
}
// print:
// select: 4
// how many elements: 1000000

// test_forward_list().......... 
// milli-seconds : 3204
// forward_list.max_size()= 536870911
// forward_list.front()= 8180
// target (0~32767): 23456
// ::find(), milli-seconds : 15
// found, 23456
// c.sort(), milli-seconds : 2656

使用容器 slist

GNU_C 很早之前就有的，非标准，类似于 forward_list

#include <ext\slist>	// extention，扩充的头文件
#include <stdexcept>
#include <string>
#include <cstdlib>	// abort()
#include <cstdio>	// snprintf()
#include <iostream>	
#include <ctime>
namespace star10
{
    void test_slist(long& value)
    {
        cout << "\ntest_slist().......... \n";
        
    __gnu_cxx::slist<string> c;
    char buf[10];
        
    clock_t timeStart = clock();
        for(long i=0; i< value; ++i)
        {
            try {
                snprintf(buf, 10, "%d", rand());
                c.push_front(string(buf));
            }
            catch(exception& p) {	// 防止空间申请失败
                cout << "i=" << i << " " << p.what() << endl;
                abort();
            }
        }
        cout << "milli-seconds : " << (clock()-timeStart) << endl;
        
    }
}
// print:
// select: 10
// how many elements: 1000000
//
// test_slist()...........
// milli-seconds : 3046

使用容器 deque

deque 表面上连续，实际上分段连续，每一个 buffer 上面连续
到达一个 buffer 末尾后，转向下一个 buffer 头，这一行为由 ++ 实现（操作符重载）
当一个 buffer 存满后，会再申请下一个或前一个 buffer
每次扩充一个 buffer

#include <deque>
#include <stdexcept>
#include <string>
#include <cstdlib>	// abort()
#include <cstdio>	// snprintf()
#include <iostream>
#include <ctime>
#include <algorithm>	// sort(), find()
namespace star05
{
    void test_deque(long& value)
    {
        cout << "\ntest_deque().......... \n";
    deque<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;
                abort();
            }
        }
        cout << "milli-seconds : " << (clock()-timeStart) << endl;
        cout << "deque.size()= " << c.size() << endl;
        cout << "deque.front()= " << c.front() << endl;
        cout << "deque.back()= " << c.back() << endl;
        cout << "deque.max_size()= " << c.max_size() << endl;	// max_size()返回容器由于系统或库实现限制而能够容纳的最大元素数量
        
    string target = get_a_target_string();
        timeStart = clock();
    auto pItem = ::find(c.begin(), c.end(), target);	// 函数名字前面加::表示为全局函数，如果没有写，编译器在当前作用域没有找到该函数，也会到全局去找，加::更明白些
        cout << "::find(), milli-seconds : " << (clock()-timeStart) << endl;
        
        if (pItem != c.end())
            cout << "found, " << *pItem << endl;
        else
            cout << "not found! " << endl;
        
        timeStart = clock();
        ::sort(c.begin(), c.end());	// 函数名字前面加::表示为全局函数，如果没有写，编译器在当前作用域没有找到该函数，也会到全局去找，加::更明白些
        cout << "::sort(), milli-seconds : " << (clock()-timeStart) << endl;
    }
}
// print:
// select: 5
// how many elements: 1000000
// 
// test_deque().......... 
// milli-seconds : 2704
// deque.size()= 1000000
// deque.front()= 5249
// deque.back()= 1098
// deque.max_szie()= 1073741823
// target (0~32767): 23456
// ::find(), milli-seconds : 15
// found, 23456
// ::sort(), milli-seconds : 3110

使用容器 stack

deque 涵盖了 stack 功能，stack 源代码内部拥有一个 deque，从技术上属于 Container Adapter（容器适配器）

#include <stack>
#include <stdexcept>
#include <string>
#include <cstdlib>	// abort()
#include <cstdio>	// snprintf()
#include <iostream>
#include <ctime>
namespace star17
{
    void test_stack(long& value)
    {
        cout << "\ntest_stack().......... \n";
    
    stack<string> c;
    char buf[10];
        
    clock_t timeStart = clock();
        for(long i=0; i< value; ++i)
        {
            try {
                snprintf(buf, 10, "%d", rand());
                c.push(string(buf));
            }
            catch(exception& p) {	// 防止空间申请失败
                cout << "i=" << i << " " << p.what() << endl;
                abort();
            }
        }
        cout << "milli-seconds : " << (clock()-timeStart) << endl;
        cout << "stack.size()= " << c.size() << endl;
        cout << "stack.top()= " << c.top() << endl;
        c.pop();
        cout << "stack.size()= " << c.size() << endl;
        cout << "stack.top()= " << c.top() << endl;
    }
}
// print:
// select: 17
// how many elements: 300000
//
// test_stack().......... 
// milli-seconds : 812
// stack.size()= 300000
// stack.top()= 23929
// stack.size()= 299999
// stack.top()= 12911

使用容器 queue

deque 涵盖了 queue 功能，queue 源代码内部拥有一个 deque，从技术上属于 Container Adapter（容器适配器）

#include <queue>
#include <stdexcept>
#include <string>
#include <cstdlib>	// abort()
#include <cstdio>	// snprintf()
#include <iostream>
#include <ctime>
namespace star18
{
    void test_queue(long& value)
    {
        cout << "\ntest_queue().......... \n";
        
    queue<string> c;
    char buf[10];
        
    clock_t timeStart = clock();
        for(long i=0; i< value; ++i)
        {
            try {
                snprintf(buf, 10, "%d", rand());
                c.push(string(buf));
            }
            catch(exception& p) {	// 防止空间申请失败
                cout << "i=" << i << " " << p.what() << endl;
                abort();
            }
        }
        cout << "milli-seconds : " << (clock()-timeStart) << endl;
        cout << "queue.size()= " << c.size() << endl;
        cout << "queue.front()= " << c.front() << endl;
        cout << "queue.back()= " << c.back() << endl;
        c.pop();
        cout << "queue.size()= " << c.size() << endl;
        cout << "queue.front()= " << c.front() << endl;
        cout << "queue.back()= " << c.back() << endl;
    }
}
// print:
// select: 18
// how many elements: 300000
//
// test_queue().......... 
// milli-seconds : 890
// queue.size()= 300000
// queue.front()= 12074
// queue.back()= 14585
// queue.size()= 299999
// queue.front()= 6888
// queue.back()= 14585

使用容器 priority_queue heap

使用少，本身借用其他容器作为底部支撑

Associative Containers（关联式容器）

使用容器 multiset

相比于 set ，可以放重复的元素
标准未规定关联式容器底层实现采用红黑树，但是因为红黑树性能好，底层实现采用了红黑树

#include <set>
#include <stdexcept>
#include <string>
#include <cstdlib>	// abort()
#include <cstdio>	// snprintf()
#include <iostream>
#include <ctime>
#include <algorithm>	// find()
namespace star06
{
    void test_multiset(long& value)
    {
        cout << "\ntest_multiset().......... \n";
        
    multiset<string> c;
    char buf[10];
    clock_t timeStart = clock();
        for(long i=0; i< value; ++i)
        {
            try {
                snprintf(buf, 10, "%d", rand());
                c.insert(string(buf));
            }
            catch(exception& p) {	// 防止空间申请失败
                cout << "i=" << i << " " << p.what() << endl;
                abort();
            }
        }
        cout << "milli-seconds : " << (clock()-timeStart) << endl;
        cout << "multiset.size()= " << c.size() << endl;
        cout << "multiset.max_size()= " << c.max_size() << endl;	// max_size()返回容器由于系统或库实现限制而能够容纳的最大元素数量
        
    string target = get_a_target_string();
        {
            timeStart = clock();
        auto pItem = ::find(c.begin(), c.end(), target);	// 标准库全局函数::find（泛用型），比 c.find(...) 慢很多
            // 函数名字前面加::表示为全局函数，如果没有写，编译器在当前作用域没有找到该函数，也会到全局去找，加::更明白些
            cout << "::find(), milli-seconds : " << (clock()-timeStart) << endl;
            if (pItem != c.end())
                cout << "found, " << *pItem << endl;
            else
                cout << "not found! " << endl;
        }
        {
            timeStart = clock();
        auto pItem = c.find(target);	// 容器自带的find函数，比 ::find(...) 快很多
            cout << "c.find(), milli-seconds : " << (clock()-timeStart) << endl;
            if (pItem != c.end())
                cout << "found, " << *pItem << endl;
            else
                cout << "not found! " << endl;
        }
    }
}
// print:
// select: 6
// how many elements: 1000000
// 
// test_multiset().......... 
// milli-seconds : 6609
// multiset.size()= 1000000
// multiset.max_size()= 214748364
// target (0~32767): 23456
// ::find(), milli-seconds : 203
// found, 23456
// c.find(), milli-seconds : 0
// found, 23456

使用容器 multimap

相比于 map ，可以放重复的元素，一个 key 可以对应多个 value
标准未规定关联式容器底层实现采用红黑树，但是因为红黑树性能好，底层实现采用了红黑树

#include <map>
#include <stdexcept>
#include <string>
#include <cstdlib>	// abort()
#include <cstdio>	// snprintf()
#include <iostream>
#include <ctime>
namespace star07
{
    void test_multimap(long& value)
    {
        cout << "\ntest_multimap().......... \n";
      
    multimap<long, string> c;
    char buf[10];
        
    clock_t timeStart = clock();
        for(long i=0; i< value; ++i)
        {
            try {
                snprintf(buf, 10, "%d", rand());
                // multimap 不可使用 [] 做 insertion
                c.insert(pair<long,string>(i,buf));	// i 是 key , buf 是 value
            }
            catch(exception& p) {	// 防止空间申请失败
                cout << "i=" << i << " " << p.what() << endl;
                abort();
            }
        }
        cout << "milli-seconds : " << (clock()-timeStart) << endl;
        cout << "multimap.size()= " << c.size() << endl;
        cout << "multimap.max_size()= " << c.max_size() << endl;	// max_size()返回容器由于系统或库实现限制而能够容纳的最大元素数量
        
    long target = get_a_target_long();
        timeStart = clock();
    auto pItem = c.find(target);	// 容器自带的find函数，速度比STL中全局函数find快很多，map 不适用 ::find()
        cout << "c.find(), milli-seconds : " << (clock()-timeStart) << endl;
        if (pItem != c.end())
            cout << "found, value=" << (*pItem).second << endl;
        else
            cout << "not found! " << endl;
    }
}
// print:
// select: 7
// how many elements: 1000000
// 
// test_multimap().......... 
// milli-seconds : 4812
// multimap.size()= 1000000
// multimap.max_size()= 178956970
// target (0~32767): 23456
// c.find(), milli-seconds : 0
// found, value=29247

使用容器 unordered_multiset（C++11新增）

相比于 unordered_set ，可以放重复的元素
底层由 hashtable（哈希表）实现

#include <unordered_set>
#include <stdexcept>
#include <string>
#include <cstdlib>	// abort()
#include <cstdio>	// snprintf()
#include <iostream>
#include <ctime>
#include <algorithm>	// find()
namespace star08
{
    void test_unordered_multiset(long& value)
    {
        cout << "\ntest_unordered_multiset().......... \n";
        
    unordered_multiset<string> c;
    char buf[10];
        
    clock_t timeStart = clock();
        for(long i=0; i< value; ++i)
        {
            try {
                snprintf(buf, 10, "%d", rand());
                c.insert(string(buf));
            }
            catch(exception& p) {	// 防止空间申请失败
                cout << "i=" << i << " " << p.what() << endl;
                abort();
            }
        }
        cout << "milli-seconds : " << (clock()-timeStart) << endl;
        cout << "unordered_multiset.size()= " << c.size() << endl;
        cout << "unordered_multiset.max_size()= " << c.max_size() << endl;	// max_size()返回容器由于系统或库实现限制而能够容纳的最大元素数量
        cout << "unordered_multiset.bucket_count()= " << c.bucket_count() << endl;	// 篮子的个数（散列地址个数），即图中灰色黑框数量，篮子的个数一定比存储元素的个数多，当元素的个数比篮子的个数多时，篮子的个数会进行扩展（可能2倍），元素的存储地址会重新计算，存到各个篮子
        cout << "unordered_multiset.load_factor()= " << c.load_factor() << endl;	// 当前负载系数，负载系数是容器中的元素数量(其大小)与篮子数量(bucket_count)之比
        cout << "unordered_multiset.max_load_factor()= " << c.max_load_factor() << endl;	// 最大的负载系数
        cout << "unordered_multiset.max_bucket_count()= " << c.max_bucket_count() << endl;	// 最大的篮子的个数
        for (unsigned i=0; i< 20; ++i) {
            cout << "bucket #" << i << " has " << c.bucket_size(i) << " elements.\n";
        }
        string target = get_a_target_string();
        {
            timeStart = clock();
        auto pItem = ::find(c.begin(), c.end(), target);	// 标准库全局函数::find（泛用型），比 c.find(...) 慢很多
            // 函数名字前面加::表示为全局函数，如果没有写，编译器在当前作用域没有找到该函数，也会到全局去找，加::更明白些
            cout << "::find(), milli-seconds : " << (clock()-timeStart) << endl;
            if (pItem != c.end())
                cout << "found, " << *pItem << endl;
            else
                cout << "not found! " << endl;
        }
        {
        	timeStart = clock();
        auto pItem = c.find(target);	// 容器自带的find函数，比 ::find(...) 快很多
        	cout << "c.find(), milli-seconds : " << (clock()-timeStart) << endl;
            if (pItem != c.end())
                cout << "found, " << *pItem << endl;
            else
                cout << "not found! " <<endl;
        }
    }
}

// print:
// select: 8
// how many elements: 1000000
//
// test_unordered_multiset().......... 
// milli-seconds : 4406
// unordered_multiset.size()= 1000000
// unordered_multiset.max_size()= 357913941
// unordered_multiset.bucket_count()= 1056323
// unordered_multiset.load_factor()= 0.94668
// unordered_multiset.max_load_factor()= 1
// unordered_multiset.max_bucket_count()= 357913941
// bucket #0 has 0 elements.
// bucket #1 has 0 elements.
// bucket #2 has 0 elements.
// bucket #3 has 0 elements.
// bucket #4 has 0 elements.
// bucket #5 has 0 elements.
// bucket #6 has 0 elements.
// bucket #7 has 0 elements.
// bucket #8 has 0 elements.
// bucket #9 has 0 elements.
// bucket #10 has 0 elements.
// bucket #11 has 0 elements.
// bucket #12 has 24 elements.
// bucket #13 has 0 elements.
// bucket #14 has 0 elements.
// bucket #15 has 0 elements.
// bucket #16 has 0 elements.
// bucket #17 has 0 elements.
// bucket #18 has 0 elements.
// bucket #19 has 0 elements.
// target (0~32767): 23456
// ::find(), milli-seconds : 109
// found, 23456
// c.find(), milli-seconds : 0
// found, 23456

使用容器 unordered_multimap（C++11新增）

相比于 unordered_map ，可以放重复的元素，一个 key 可以对应多个 value
底层由 hashtable（哈希表）实现

#include <unordered_map>
#include <stdexcept>
#include <string>
#include <cstdlib>	// abort()
#include <cstdio>	// snprintf()
#include <iostream>
#include <ctime>
namespace star09
{
    void test_unordered_multimap(long& value)
    {
        cout << "\ntest_unordered_multimap().......... \n";
        
    unordered_multimap<long, string> c;
    char buf[10];
        
    clock_t timeStart = clock();
        for(long i=0; i< vlaue; ++i)
        {
            try {
                snprintf(buf, 10, "%d", rand());
                // multimap 不可使用 [] 进行 insertion
                c.insert(pair<long,string>(i,buf));	// i 是 key , buf 是 value
            }
            catch(exception& p) {	// 防止空间申请失败
                cout << "i=" << i << " " << p.what() << endl;
                abort();
            }
        }
        cout << "milli-seconds : " << (clock()-timeStart) << endl;
        cout << "unordered_multimap.size()= " << c.size() << endl;
        cout << "unordered_multimap.max_size()= " << c.max_size() << endl;	// max_size()返回容器由于系统或库实现限制而能够容纳的最大元素数量
        
        
    long target = get_a_target_long();
        timeStart = clock();
    auto pItem = c.find(target);	// 容器自带的find函数，速度比STL中全局函数find快很多，map 不适用 ::find()
        cout << "c.find(), milli-seconds : " (clock()-timeStart) << endl;
        if (pItem != c.end())
            cout << "found, value=" << (*pItem).second << endl;
        else
            cout << "not found! " << endl;
    }
}
// print:
// select: 9
// how many elements: 1000000
// 
// test_unordered_multimap().......... 
// milli-seconds : 4313
// unordered_multimap.size()= 1000000
// unordered_multimap.max_size()= 357913941
// target (0~32767): 23456
// c.find(), milli-seconds : 0
// found, value=15962

使用容器 set

相比于 multiset ，不可以放重复的元素
标准未规定关联式容器底层实现采用红黑树，但是因为红黑树性能好，底层实现采用了红黑树

#include <set>
#include <stdexcept>
#include <string>
#include <cstdlib>	// abort()
#include <cstdio>	// snprintf()
#include <iostream>
#include <ctime>
#include <algorithm>	// find()
namespace star13
{
    void test_set(long& value)
    {
        cout << "\ntest_set().......... \n";
        
    set<string> c;
    char buf[10];
    
    clock_t timeStart = clock();
        for(long i=0; i< value; ++i)
        {
            try {
                snprintf(buf, 10, "%d", rand());
                c.insert(string(buf));
            }
            catch(exception& p) {	// 防止空间申请失败
                cout << "i=" << i << " " << p.what() << endl;
                abort();
            }
        }
        cout << "milli-seconds : " << (clock()-timeStart) << endl;
        cout << "set.size()= " << c.size() << endl;
        cout << "set.max_size()= " << c.max_size() << endl;	// max_size()返回容器由于系统或库实现限制而能够容纳的最大元素数量
        
    string target = get_a_target_string();
        {
        	timeStart = clock();
        auto pItem = ::find(c.begin(), c.end(), target);	// 标准库全局函数::find（泛用型），比 c.find(...) 慢很多
            // 函数名字前面加::表示为全局函数，如果没有写，编译器在当前作用域没有找到该函数，也会到全局去找，加::更明白些
            cout << "::find(), milli-seconds : " << (clock()-timeStart) << endl;
            if (pItem != c.end())
                cout << "found, " << *pItem << endl;
            else
                cout << "not found! " << endl;
        }
        {
            timeStart = clock();
        auto pItem = c.find(target);	// 容器自带的find函数，比 ::find(...) 快很多
            cout << "c.find(), milli-seconds : " << (clock()-timeStart) << endl;
            if (pItem != c.end())
                cout << "found, " << *pItem << endl;
            else
                cout MM "not found! " << endl;
        }
    }
}
// print:
// select: 13
// how many elements: 1000000
// 
// test_set().......... 
// milli-seconds : 3922
// set.size()= 32762
// set.max_size()= 234748364
// target (0~32767): 23456
// ::find(), milli-seconds : 0
// found, 23456
// c.find(), milli-seconds : 0
// found, 23456

使用容器 map

相比于 multimap ，不可以放重复的元素，一个 key 只可以对应一个 value
标准未规定关联式容器底层实现采用红黑树，但是因为红黑树性能好，底层实现采用了红黑树

#include <map>
#include <stdexcept>
#include <string>
#include <cstdlib>	// abort()
#include <cstdio>	// snprintf()
#include <iostream>
#include <ctime>
namespace star14
{
   	void test_map(long& value)
    {
        cout << "\ntest_map().......... \n";
      
    map<long, string> c;
    char buf[10];
        
    clock_t timeStart = clock();
        for(long i=0; i< value; ++i)
        {
            try {
                snprintf(buf, 10, "%d", rand());
                c[i] = string(buf);	// i 是 key , buf 是 value
            }
            catch(exception& p) {	// 防止空间申请失败
                cout << "i=" << i << " " << p.what() << endl;
                abort();
            }
        }
        cout << "milli-seconds : " << (clock()-timeStart) << endl;
        cout << "map.size()= " << c.size() << endl;
        cout << "map.max_size()= " << c.max_size() << endl;	// max_size()返回容器由于系统或库实现限制而能够容纳的最大元素数量
        
    long target = get_a_target_long();
        timeStart = clock();
    auto pItem = c.find(target);	// 容器自带的find函数，速度比STL中全局函数find快很多，map 不适用 ::find()
        cout << "c.find(), milli-seconds : " << (clock()-timeStart) << endl;
        if (pItem != c.end())
            cout << "found, value=" << (*pItem).second << endl;
        else
            cout << "not found! " << endl;
    }
}
// print:
// select: 14
// how many elements: 1000000
// 
// test_map().......... 
// milli-seconds : 4890
// map.size()= 1000000
// map.max_size()= 178956970
// target (0~32767): 23456
// c.find(), milli-seconds : 0
// found, value=19128

使用容器 unordered_set（C++11新增）

相比于 unordered_multiset ，不可以放重复的元素
底层由 hashtable（哈希表）实现

#include <unordered_set>
#include <stdexcept>
#include <string>
#include <cstdlib>	// abort()
#include <cstdio>	// snprintf()
#include <iostream>
#include <ctime>
#include <algorithm>	// find()
namespace star15
{
    void test_unordered_set(long& value)
    {
        cout << "\ntest_unordered_set().......... \n";
        
    unordered_set<string> c;
    char buf[10];
        
    clock_t timeStart = clock();
        for(long i=0; i< value; ++i)
        {
            try {
                snprintf(buf, 10, "%d", rand());
                c.insert(string(buf));
            }
            catch(exception& p) {	// 防止空间申请失败
                cout << "i=" << i << " " << p.what() << endl;
                abort();
            }
        }
        cout << "milli-seconds : " << (clock()-timeStart) << endl;
        cout << "unordered_set.size()= " << c.size() << endl;
        cout << "unordered_set.max_size()= " << c.max_size() << endl;	// max_size()返回容器由于系统或库实现限制而能够容纳的最大元素数量
        cout << "unordered_set.bucket_count()= " << c.bucket_count() << endl;	// 篮子的个数（散列地址个数），即图中灰色黑框数量，篮子的个数一定比存储元素的个数多，当元素的个数比篮子的个数多时，篮子的个数会进行扩展（可能2倍），元素的存储地址会重新计算，存到各个篮子
        cout << "unordered_set.load_factor()= " << c.load_factor() << endl;	// 当前负载系数，负载系数是容器中的元素数量(其大小)与篮子数量(bucket_count)之比
        cout << "unordered_set.max_load_factor()= " << c.max_load_factor() << endl;	// 最大的负载系数
        cout << "unordered_set.max_bucket_count()= " << c.max_bucket_count() << endl;	// 最大的篮子的个数
        for (unsigned i=0; i< 20; ++i) {
            cout << "bucket #" << i << " has " << c.bucket_size(i) << " elements.\n";
        }
        string target = get_a_target_string();
        {
            timeStart = clock();
        auto pItem = ::find(c.begin(), c.end(), target);	// 标准库全局函数::find（泛用型），比 c.find(...) 慢很多
            // 函数名字前面加::表示为全局函数，如果没有写，编译器在当前作用域没有找到该函数，也会到全局去找，加::更明白些
            cout << "::find(), milli-seconds : " << (clock()-timeStart) << endl;
            if (pItem != c.end())
                cout << "found, " << *pItem << endl;
            else
                cout << "not found! " << endl;
        }
        {
        	timeStart = clock();
        auto pItem = c.find(target);	// 容器自带的find函数，比 ::find(...) 快很多
        	cout << "c.find(), milli-seconds : " << (clock()-timeStart) << endl;
            if (pItem != c.end())
                cout << "found, " << *pItem << endl;
            else
                cout << "not found! " <<endl;
        }
    }
}

// print:
// select: 15
// how many elements: 1000000
//
// test_unordered_set().......... 
// milli-seconds : 2891
// unordered_set.size()= 32768
// unordered_set.max_size()= 357913941
// unordered_set.bucket_count()= 62233
// unordered_set.load_factor()= 0.526537
// unordered_set.max_load_factor()= 1
// unordered_set.max_bucket_count()= 357913941
// bucket #0 has 1 elements.
// bucket #1 has 1 elements.
// bucket #2 has 1 elements.
// bucket #3 has 0 elements.
// bucket #4 has 3 elements.
// bucket #5 has 0 elements.
// bucket #6 has 0 elements.
// bucket #7 has 1 elements.
// bucket #8 has 0 elements.
// bucket #9 has 0 elements.
// bucket #10 has 0 elements.
// bucket #11 has 1 elements.
// bucket #12 has 0 elements.
// bucket #13 has 2 elements.
// bucket #14 has 1 elements.
// bucket #15 has 1 elements.
// bucket #16 has 1 elements.
// bucket #17 has 1 elements.
// bucket #18 has 0 elements.
// bucket #19 has 0 elements.
// target (0~32767): 23456
// ::find(), milli-seconds : 109
// found, 23456
// c.find(), milli-seconds : 0
// found, 23456

使用容器 unordered_map（C++11新增）

相比于 unordered_multimap ，不可以放重复的元素，一个 key 只可以对应一个 value
底层由 hashtable（哈希表）实现

#include <unordered_map>
#include <stdexcept>
#include <string>
#include <cstdlib>	// abort()
#include <cstdio>	// snprintf()
#include <iostream>
#include <ctime>
namespace star16
{
    void test_unordered_map(long& value)
    {
        cout << "\ntest_unordered_map().......... \n";
        
    unordered_map<long, string> c;
    char buf[10];
        
    clock_t timeStart = clock();
        for(long i=0; i< value; ++i)
        {
            try {
                snprintf(buf, 10, "%d", rand());
                c[i] = string(buf);	// i 是 key , buf 是 value
            }
            catch(exception& p) {	// 防止空间申请失败
                cout << "i=" << i << " " << p.what() << endl;
                abort();
            }
        }
        cout << "milli-seconds : " << (clock()-timeStart) << endl;
        cout << "unordered_map.size()= " << c.size() << endl;
        cout << "unordered_map.max_size()= " << c.max_size() << endl;	// max_size()返回容器由于系统或库实现限制而能够容纳的最大元素数量
        
        
    long target = get_a_target_long();
        timeStart = clock();
    //! auto pItem = find(c.begin(), c.end(), target);	// map 不适用 ::find()
    auto pItem = c.find(target);
        
        cout << "c.find(), milli-seconds : " << (clock()-timeStart) << endl;
        if (pItem != c.end())
            cout << "found, value=" << (*pItem).second << endl;
        else
            cout << "not found! " << endl;
    }
}
// print:
// select: 16
// how many elements: 1000000
// 
// test_unordered_map().......... 
// milli-seconds : 3797
// unordered_map.size()= 1000000
// unordered_map.max_size()= 357913941
// target (0~32767): 23456
// c.find(), milli-seconds : 0
// found, value=12218

使用容器 hash_set hash_map hash_multiset hash_multimap

以前 GNU_C 编译器所带的库，现在将名字中 hash 改为 unordered，现在属于非标准，仍然可以使用，不过要注意位于哪个资料夹

分配器之测试

容器的背后需要 allocator（分配器）来支撑它对内存的使用，容器有一个默认的分配器

使用 allocator

默认分配器

template<typename _Tp,typename _Alloc=std::allocator<_Tp>>
	class vector:protected _Vector_base<_Tp,_Alloc>
      
template<typename _Tp,typename _Alloc=std::allocator<_Tp>>
	class list:protected _List_base<_Tp,_Alloc>

template<typename _Tp,typename _Alloc=std::allocator<_Tp>>
	class deque:protected _Deque_base<_Tp,_Alloc>

template<typename _Key,typename _Compare=std::less<_Key>,typename _Alloc=std::allocator<_Key>>
	class set
        
template<typename _Key,typename _Tp,typename _Compare=std::less<_Key>,
		typename _Alloc=std::allocator<std::pair<const _Key,_Tp>>>
	class map
        
template<class _Value,
		class _Hash=hash<_Value>,
		class _Pred=std::equal_to<_Value>,
		class _Alloc=std::allocator<_Value>>
	class unordered_set
        
template<class _Key,class _Tp,
		class _Hash=hash<_Key>,
		class _Pred=std::equal_to<_Key>,
		class _Alloc=std::allocator<std::pair<const _Key,_Tp>>>
	class unordered_map

std::allocator 以外的 allocator

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

#include <cstddef>
#include <memory>	// 内含 std::allocator
	// 欲使用 std::allocator 以外的 allocator, 得自行 #include <ext\...>，GNU_C 编译器所带的库，非标准实现
#include <ext\array_allocator.h>
#include <ext\mt_allocator.h>
#include <ext\debug_allocator.h>
#include <ext\pool_allocator.h>
#include <ext\bitmap_allocator.h>
#include <ext\malloc_allocator.h>
#include <ext\new_allocator.h>
namespace star20
{
    void test_list_with_special_allocator()
    {
        cout << "\ntest_list_with_special_allocator().......... \n";
        
        list<string, allocator<string>> c1;
        list<string, __gnu_cxx::malloc_allocator<string>> c2;	// 使用 std::allocator 以外的 allocator需要加__gnu_cxx::
        list<string, __gnu_cxx::new_allocator<string>> c3;
        list<string, __gnu_cxx::__pool_alloc<string>> c4;
        list<string, __gnu_cxx::__mt_alloc<string>> c5;
        list<string, __gnu_cxx::bitmap_allocator<string>> c6;
        
    int choice;
    long value;
        
        cout << "select: ";
        cin >> choice;
        if ( choice != 0) {
            cout << "how many elements: ";
            cin >> value;
        }
        
    char buf[10];
    clock_t timeStart = clock();
        for(long i=0; i< value; ++i)
        {
            try {
                snprintf(buf, 10, "%d", i);
                switch (choice)
                {
                    case 1 :	c1.push_back(string(buf));
                        		break;
                    case 2 :	c2.push_back(string(buf));
                        		break;
                    case 3 :	c3.push_back(string(buf));
                        		break;
                    case 4 :	c4.push_back(string(buf));
                        		break;
                    case 5 :	c5.push_back(string(buf));
                        		break;
                    case 6 :	c6.push_back(string(buf));
                        		break;
                    default:
                        break;
                }
            }
            catch(exception& p) {
                cout << "i=" << i << " " << p.what() << endl;
                abort();
            }
        }
        cout << "a lot of push_back(), milli-seconds : " << (clock()-timeStart) << endl;
        
        // test all allocator's allocate() & deallocate();
        // allocator（分配器）建议与容器搭配使用，不建议单独使用，单独申请空间用 malloc/free 和 new/delete
        int* p;
        allocator<int> alloc1;
        p = alloc1.allocate(1);
        alloc1.deallocate(p,1);
        
        __gnu_cxx::malloc_allocator<int> alloc2;
        p = alloc2.allocate(1);
        alloc2.deallocate(p,1);
        
        __gnu_cxx::new_allocator<int> alloc3;
        p = alloc3.allocate(1);
        alloc3.deallocate(p,1);
        
        __gnu_cxx::__pool_alloc<int> alloc4;
        p = alloc4.allocate(2);
        alloc4.deallocate(p,2);
        
        __gnu_cxx::__mt_alloc<int> alloc5;
        p = alloc5.allocate(1);
        alloc5.deallocate(p,1);
        
        __gnu_cxx::bitmap_allocator<int> alloc6;
        p = alloc6.allocate(3);
        alloc6.deallocate(p,3);
    }
}

源代码之分布（VC，GCC）

C++ STL标准只规定了统一的接口，未明确指出实现，但是编译器厂商因为性能优势大部分实现相同，如 set 底层采用红黑树实现

标准库版本，Visual C++

files layout
…\include STL标准库文件
…\include\cliext 编译器扩展文件
eg: D:\VSworkplace\VS\VC\Tools\MSVC\14.35.32215\include

标准库版本，GNU C++

files layout
…\4.9.2\include
…\include\c++
…\include\c++\bits STL标准库文件
…\include\c++\ext 编译器扩展文件
eg: S:\Dev-Cpp\Dev-Cpp\Dev-Cpp\MinGW64\lib\gcc\x86_64-w64-mingw32\8.1.0\include\c++

OOP（面向对象编程） vs. GP（泛型编程）

OOP (Object-Oriented programming) vs. GP (Generic Programming)

OOP企图将 datas 和 methods 关联在一起

template <class T, class Alloc=alloc>
class list {
	...
	void sort();
};

为什么 list 不能使用 ::sort() 排序
list 的 Iterator 不是 RandomAccessIterator（随机访问迭代器），是 BidirectionalIterator（双向迭代器）
容器自身带 sort 函数时，一定用自身带的，没有才使用 STL 全局函数 sort

// sort 部分源代码
template <class RandomAccessIterator>
inline void sort(RandomAccessIterator first, RandomAccessIterator last) {
    if(first != last) {
        __introsort_loop(first, last, value_type(first),__lg(last - first) * 2);
        __final_insertion_sort(first, last);
    }
}

template <class RandomAccessIterator, class T, class Size>
void __introsort_loop(RandomAccessIterator first, RandomAccessIterator last, T*, Size depth_limit) {
    ...
	RandomAccessIterator cut = __unguarded_partition
        (first, last, T(__median(*first, *(first + (last - first)/2), *(last - 1))));
		// 只有 RanadomAccessIterator 才能如此操作（first + (last - first)/2）
		// BidirectionalIterator 只能自增和自减
    ...
}

GP却是将 datas 和 methods 分开来

Data Structures (Containers)

//	这两个容器都提供 RandomAccessIterator
template <class T, class Alloc=alloc>
class vector{
    ...
};

template <class T, class Alloc=alloc, size_t BufSiz=0>
class deque{
    ...
};

Algorithms

template<typename _RandomAccessIterator>
inline void sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
    ...
}

template<typename _RandomAccessIterator, typename _Compare>
inline void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
    ...
}

采用 GP：

Containers 和 Algorithm 团队可各自闭门造车，其间以 Iterator 沟通即可
Algorithm 通过 Iterators 确定操作范围，并通过 Iterators 取用 Container 元素

template <class T>
inline const T& min(const T& a, const T& b) {
    return b < a ? b : a;
}

template <class T>
inline const T& max(const T& a, const T& b) {
	return a < b ? b : a;    
}

template <class T, class Compare>
inline const T& min(const T& a,const T& b, Compare comp) {
    return comp(b, a) ? b : a;
}

template <class T, class Conpare>
inline const T& max(const T& a,const T& b, Compare comp) {
    return comp(a, b) ? b : a;
}

所有 algorithms，其内最终涉及元素本身的操作，无非就是比大小

bool strLonger(const string& s1, const string& s2)
{
    return s1.size() < s2.size();
}

cout << "max of zoo and hello : " << max(string("zoo"), string("hello")) << endl;	// print: zoo

cout << "longest of zoo and hello : " << max(string("zoo"), string("hello"), strLonger) << endl;	// print: hello

// 第一个 max 调用
template <class T>
inline const T& max(const T& a, const T& b) {
    return a < b ? b : a;
}

// 第二个 max 调用
template <class T, class Compare>
inline const T& max(const T& a, const T& b, Compare comp) {
    return comp(a, b) ? b : a;
}

技术基础：操作符重载 and 模板（泛化，全特化，偏特化）

Operator Overloading，操作符重载

资料网站：operator overloading - cppreference.com

template<class T, class Ref. class Ptr>
struct __list_iteraotr {
    typedef __list_iterator<T, Ref, Ptr> self;
    typedef bidirectional_iterator_tag iterator_category;
    typedef T	value_type;
    typedef Ptr pointer;
    typedef Ref reference;
    typedef __list_node<T>* link_type;
    typedef ptrdiff_t difference_type;
    
    link_type node;
    
    // Operator Overloading
    reference operator*() const { return (*node).data; }
    pointer operator->() const 	{ return &(operator*()); }
    self& operator++()			{ node = (link_type)((*node).next); return * this; }
    self operator++(int)		{ self tmp = *this; ++*this; return tmp; }
    ...
} 

Class Templates，类模板

template <typename T>
class complex
{
    public:
		complex (T r = 0, T i = 0) : re (r), im (i)
        {	}
    	complex& operator += (const complex&);
    	T real () const { return re; }
    	T imag () const { return im; }
    private:
    	T re, im;
    
    friend complex& __dopal (complex*, const complex&);
};

{
    // 用 <> 指出参数类型
    complex<double> c1(2.5, 1.5);
    complex<int> c2(2, 6);
    ...
}

Function Templates，函数模板

class stone
{
    public:
    	stone(int w, int h, int we) : _w(w), _h(h), _weight(we)
        {	}
    	bool operator<(const stone& rhs) const
        { return _weight < rhs._weight; }
    private:
    	int _w, _h, _weight;
};

template <class T>
inline const T& min(const T& a, const T& b)
{
    return b < a ? b : a;
}

{
    // 编译器对 function template 进行实参推导（argument deduction）
    // 实参推导的结果，T为 stone，于是调用 stone::operator<()
    stone r1(2, 3), r2(3, 3), r3;
    r3 = min(r1, r2);
}

Member Templates，成员模板

Specialization，特化

// ref. G2.91 <type_traits.h>
// 泛化
template <class type>
struct __type_traits {
    typedef __true_type		this_dummy_member_must_be_first;
    typedef __false_type	has_trivial_default_constructor;
    typedef __false_type	has_trivial_copy_constructor;
    typedef __false_type	has_trivial_assignment_operator;
    typedef __false_type	has_trivial_destructor;
    typedef __false_type	is_POD_type;	// Plain Old Data
};

// 特化
template<> struct __type_traits<int> {
    typedef __true_type		has_trivial_default_constructor;
    typedef __true_type		has_trivial_copy_constructor;
    typedef __true_type		has_trivial_assignment_operator;
    typedef __true_type		has_trivial_destructor;
    typedef __true_type		is_POD_type;	// Plain Old Data
};

// 特化
template<> struct __type_traits<double> {
    typedef __true_type		has_trivial_default_constructor;
    typedef __true_type		has_trivial_copy_constructor;
    typedef __true_type		has_trivial_assignment_operator;
    typedef __true_type		has_trivial_destructor;
    typedef __true_type		is_POD_type;	// Plain Old Data
};

{
    // 调用泛化版本
    __type_traits<Foo>::has_trivial_destructor
    // 调用特化版本1
	__type_traits<int>::has_trivial_destructor
	// 调用特化版本2
	__type_traits<double>::has_trivial_destructor
}

// 泛化
template <class Key> struct hash { };

// 特化	__STL_TEMPLATE_NULL 等价于 template<>
__STL_TEMPLATE_NULL struct hash<char> {
    size_t operator()(char x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<short> {
    size_t operator()(short x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned short> {
    size_t operator()(unsigned short x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<int> {
    size_t operator()(int x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned int> {
    size_t operator()(unsigned int x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<long> {
    size_t operator()(long x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned long> {
    size_t operator()(unsigned long x) const { return x; }
};

{
    // 调用泛化版本
    hash<Foo>();
    // 调用特化版本4
    int i=hash<int>()(32);
}

// 泛化
template<typename _Tp>	class allocator;

// 特化
// allocator<void> specialization
template<> class allocator<void>
{
    public:
    	typedef size_t		size_type;
    	typedef ptrdiff_t	difference_type;
    	typedef void*		pointer;
    	typedef const void*	const_pointer;
    	typedef void		value_type;
    
    	template<typename _Tp1>	struct rebind
        { typedef allocator<_Tp1> other; };
};

Partial Specialization，偏特化

// 泛化
template <class T, class Alloc = alloc>
class vector
{
    ...
};

// 偏特化，个数的偏特化
template<class Alloc>
class vector<bool, Alloc>	// 两个模板参数绑定其中一个
{
    ...
};

// ref. G2.9 <stl_iterator.h>
// 泛化
template <class Iterator>
struct iterator_traits {
    typedef typename Iterator::iterator_category	iterator_category;
    typedef typename Iterator::value_type			value_type;
    typedef typename Iterator::difference_type		difference_type;
    typedef typename Iterator::pointer				pointer;
    typedef typename Iterator::reference			reference;
};

// 偏特化，范围的偏特化
// partial specialization for regular pointers
template <class T>
struct iterator_traits<T*> {
    typedef random_access_iterator_tag	iterator_category;
    typedef T							value_type;
    typedef ptrdiff_t					difference_type;
    typedef T*							pointer;
    typedef T&							reference;
};
// partial specialization for regular const pointers
template <class T>
struct iterator_traits<const T*> {
    typedef random_access_iterator_tag	iterator_category;
    typedef T							value_type;
    typedef ptrdiff_t					difference_type;
    typedef const T*					pointer;
    typedef const T&					reference;
};

分配器 allocators

operator new() 和 malloc()

所有分配动作最终都会跑到 operator new，operator new 又会调用 malloc

分配的内存如上图，所申请的空间大小为 size（浅蓝色部分）, malloc 会搭配放更多的东西（称为Overhead），详情见内存管理
申请的空间越小，Overhead所占的比例就越高

// ...\vc98\crt\src\newop2.cpp
void *operator new(size_t size, const std::nothrow _t&) _THROW0()
{
    // try to allocate size bytes
    void *p;
    while ((p = malloc(size)) == 0)
    {
        // buy more memory or return null pointer
        _TRY_BEGIN
        if(_callnewh(size)==0) break;
        _CATCH(std::bad_alloc) return (0);
        _CATCH_END
    }
    return (p);
}

// <new.h> of CB5
// inline versions of the nothrow_t versions of new & delete operators
inline void* _RTLENTRY operator new (size_t size, const std::nothrow_t &)
{
    size = size ? size : 1;
    return malloc(size);
}

VC6

VC6⁺ 的 allocator 只是以 ::operator new 和 ::operator delete 完成 allocate() 和 deallocate()，没有任何特殊设计

// VC6 STL 对 allocator 的使用
template<class _Ty, class _A = allocator<_Ty> >
class vector
{
    ...
};
template<class _Ty, class _A = allocator<_Ty> >
class list
{
    ...
};
template<class _Ty, class _A = allocator<_Ty> >
class deque
{
    ...
};
template<class _K, class _Pr = less<_K>, class _A = allocator<_K> >
class set {
    ...
};

// VC6所附的标准库，其 allocator 实现如下（<xmemory>）
#ifndef _FARQ
#define _FARQ
#define _PDFT		ptrdiff_t
#define _SIZT		size_t
#endif
#define _POINTER_X(T,A)		T_FARQ *
#define _REFERENCE_X(T,A)	T_FARQ &

template<class _Ty>
class allocator {
    public:
    typedef _SIZT size_type;
    typedef _PDFT difference_type;
    typedef _Ty _FARQ *pointer;
    typedef _Ty value_type;
    pointer allocate(size_type _N, const void *)	// 第二个参数想知道 _N 个参数的类型
    { return (_Allocate((difference_type)_N, (pointer)0)); }
    void deallocate(void _FARQ *_P, size_type)
    { operator delete(_P); }
};

// 其中用到的 _Allocate() 定义如下：
template<class _Ty> inline _Ty _FARQ *_Allocate(_PDFT _N, _Ty _FARQ *)
{
    if (_N < 0) _N = 0;
    return ((_Ty _FARQ *)operator new((_SIZT)_N * sizeof (_Ty)));
}

// 分配512 ints
int* p = allocator<int>().allocate(512, (int*)0);
allocator<int>().deallocate(p, 512);	// 第二个参数为申请的空间大小，使得我们无法很好的使用，因为没人会记得申请空间大小

BC5

BC++ 的 allocator 只是以 ::operator new 和 ::operator delete 完成 allocate() 和 deallocate()，没有任何特殊设计

// BC5 STL 对 allocator 的使用
template <class T, class Allocator _RWSTD_COMPLEX_DEFAULT(allocator<T>) >
class vector ...
    
template <class T, class Allocator _RWSTD_COMPLEX_DEFAULT(allocator<T>) >
class list ...

template <class T, class Allocator _RWSTD_COMPLEX_DEFAULT(allocator<T>) >
class deque ...

// 在 <stdcomp.h> 中
#define _RWSTD_COMPLEX_DEFAULT(a) = a

// 则上面等价于
template <class T, class Allocator = allocator<T> >
class vector ...
    
template <class T, class Allocator = allocator<T> >
class list ...

template <class T, class Allocator = allocator<T> >
class deque ...

// BC5 所附的标准库，其 allocator 实现如下 （<memory.stl>）
template <class T>
class allocator
{
    public:
    	typedef size_t		size_type;
    	typedef ptrdiff_t	difference_type;
    	typedef T*			pointer;
    	typedef T			value_type;
    
    pointer allocate(size_type n, allocator<void>::const_pointer = 0) {
        pointer tmp = _RWSTD_STATIC_CAST(pointer, (::operator new
                                                   (_RWSTD_STATIC_CAST(size_t, (n * sizeof(value_type))))));
        _RWSTD_THROW_NO_MSG(tmp == 0, bad_alloc);
        return tmp;
    }
    void deallocate(pointer p, size_type) {
        ::operator delete(p);
    }
    ...
};

// 分配512 ints
int* p = allocator<int>().allocate(512);
allocator<int>().deallocate(p,512);

G2.9

GCC 2.9 的 allocator 只是以 ::operator new 和 ::operator delete 完成 allocate() 和 deallocate()，没有任何特殊设计

// G2.9 所附的标准库，其 allocator 实现如下（<defalloc.h>）
// G++ <defalloc.h> 中有这样的注释：
// DO NOT USE THIS TILE unless you have an old container implementation that requires an allocator with the HP-style interface
// SGI STL uses a different allocator interface
// SGI-style allocators are not parametrized with respect to the object tyoe; they traffic in void* pointers
// This file is not included by any other SGI STL header
template <class T>
class allocator {
    public:
    	typedef T		value_type;
    	typedef T*		pointer;
    	typedef size_t	size_type;
    	typedef ptrdiff_t	difference_type;
    	pointer allocate(size_type n) {
            return ::allocate((difference_type)n, (pointer)0);
        }
    	void deallocate(pointer p) { ::deallocate(p); }
};

template <class T>
inline T* allocate(ptrdiff_t size, T*) {
    set_new_handler(0);
    T* tmp =(T*)(::operator new((size_t)(size*sizeof(T))));
    if (tmp == 0) {
        cerr << "out of memory" << endl;
        exit(1);
    }
    return tmp;
}
template <class T>
inline void deallocate(T* buffer) {
    ::operator delete(buffer);
}

// G2.9 STL 对 allocator 的使用
template <class T, class Alloc = alloc>	// 使用了另外一个分配器 alloc
class vector {
    ...
};

template <class T, class Alloc = alloc>
class list {
    ...
};

template <class T, class Alloc = alloc, size_t BufSiz = 0>
class deque {
    ...
};

template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
    ...
};

template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set {
    ...
};

// 分配512 bytes
void* p=alloc::allocate(512);	// 也可 alloc().allocate(512)
alloc::deallocate(p,512);

G2.9 所附的标准库，其 alloc 实现如下（<stl_alloc.h>），源代码及详细介绍见内存管理
设计十六条链表，每一条链表负责某一种特定大小的区块，用链表串起来
第0号链表负责8个字节大小的区块，第7号链表负责8*8=64个字节大小的区块，即第几个*8个字节
函数申请内存，会先去相应大小的链表寻找空闲区块，如果没有，则链表申请很大一块内存，然后做切割，分给申请的函数，这样每个切割的内存都不带 Overhead，减少 Overhead 所占比例

G4.9

// G4.9 STL 对 allocator 的使用
template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
class vector : protected _Vector_base<_Tp, _Alloc>
{
    ...
};

// G4.9 所附的标准库，其 allocator 实现如下
// <bits/allocator.h>
template<typename _Tp>
class allocator: public __allocator_base<_Tp>
{
    ...
};

// <bits/c++allocator.h>
#define __allocator_base __gnu_cxx::new_allocator

// <bits/new_allocator.h>
template<typename _Tp>
class new_allocator
{
    ...
	pointer allocate(size_type __n, const void* = 0) {
        if (__n > this->max_size())
            std::__throw_bad_alloc();
        return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
    }
    
    void deallocate(pointer __p, size_type)
    { ::operator delete(__p); }
    ...
};

// G4.9 所附的标准库，有许多 extention allocators, 其中 __pool_alloc 就是 G2.9 的 alloc
class __pool_alloc_base
{
    protected:
    	enum { _S_align = 8 };
    	enum { _S_max_bytes = 128 };
    	enum { _S_free_list_size = (size_t)_S_max_bytes / (size_t)_S_align };
    	
    	union _Obj
        {
            union _Obj* _M_free_list_link;
            char		_M_client_data[1];	// The client sees this
        };
    
    	static _Obj* volatile	_S_free_list[_S_free_list_size];
    	...
}

template<typename _Tp>
class __pool_alloc : private __pool_alloc_base
{
    ...
};

// 用例：
vector<string, __gnu_cxx::__pool_alloc<string>> vec;

容器之间的实现关系与分类

容器——结构与分类

Sequence Containers（序列式容器）
Associative Containers（关联式容器）：标准未规定关联式容器底层实现采用红黑树，但是因为红黑树性能好，底层实现采用了红黑树

Unordered Containers（无序容器）属于 Associative Containers

Array、Forward-List、Unordered Containers 为 C++11 新增

容器，结果与分类

本图以缩排形式表达“基层与衍生层”的关系
这里所谓衍生，并非继承（inheritance）而是复合（composition）
蓝色框内是容器本身大小，即容器内控制整个数据结构的所需数据大小，与容器内存储的元素大小和个数无关

在 C++11 中，slist 名为 forward_list，hash_set，hash_map 名为 unordered_set，unordered_map
hash_multiset，hash_multimap 名为 unordered_multiset，unordered_multimap；且新添 array

深度探索 list

容器 list

G2.9

​
​

template <class T>
struct __list_node {	// list 跟 它分配器要内存的时候，要的是一个数据加两个指针
    typedef void* void_pointer;
    void_pointer prev;
    void_pointer next;
    T data;
};

template<class T, class Ref, class Ptr>
struct __list_iterator {
    typedef T	value_type;
    typedef Ptr	pointer;
    typedef Ref	reference;
    ...
};

template <class T, class Alloc = alloc>
class list {
    protected:
    	typedef __list_node<T>	list_node;
    public:
    	typedef list_node*	link_type;
    	typedef __list_iterator<T,T&,T*> iterator;
    protected:
    	link_type node;
    ...
};

// G2.9 sizeof(list<T>) = 4
// 对一个容器进行 sizeof，得到的是容器本身大小，即容器内控制整个数据结构的所需数据大小，与容器内存储的元素大小和个数无关，list 有一个 node，是一个指针(4个字节)

list’s iterator

template <class T>
struct __list_node {
    typedef void* void_pointer;
    void_pointer prev;
    void_pointer next;
    T data;
};

template<class T, class Ref, class Ptr>
struct __list_iterator {
    typedef __list_iterator<T, Ref, Ptr> self;
    typedef bidirectional_iterator_tag iterator_category;	// (1)
    typedef T	value_type;								// (2)
    typedef Ptr pointer;								// (3)
    typedef Ref reference;								// (4)
    typedef __list_node<T>* link_type;
    typedef ptrdiff_t difference_type;					// (5)
    
    link_type node;
    
    // 操作符重载
    reference operator*() const { return (*node).data; }	// reference 为 T&
    pointer operator->() const { return &(operator*()); }	// pointer 为 T*
    self& operator++() {	// prefix form 前加加
        node = (link_type)((*node).next);
        return *this;	// return by reference 并不会唤起什么
    }	
    self operator++(int) { 	// postfix form 后加加
        self tmp = *this;	// 记录原值，以为会唤起 operator*，其实是唤起 copy ctor 用以创建 tmp 并以 *this 为初值，不会唤起 operator*，因为 *this 已被解释为 ctor 的参数，编译器先遇到赋值符号=
        ++*this;	// 进行操作，不会唤起 operator*，因为 *this 已被解释为 operator++ 的参数
        return tmp; 	// 返回原值，最后，return by value 唤起 copy ctor
    }
    ...
};

list<int> c;
...
auto ite = c.begin();
++++ite;
// 等价于
++(++ite);
// error
//! ite++++;
// 等价于
//! (ite++)++;

int i(6);
++++i;
// 等价于
++(++i);
// error
//! i++++;
// 等价于
//! (i++)++;	[Error] Ivalue required as increment operand

// 所以 operator++() 返回 reference，模拟 ++++i
// operator++(int) 返回 value，模拟 i++++

reference operator*() const { return (*node).data; }	// reference 为 T&
pointer operator->() const { return &(operator*()); }	// pointer 为 T*

// 当你对某个 type 实施 operator->，而该 type 并非 built-in ptr 时，编译器会做一件很有趣的事：在找出 user-defined operator-> 并将它施行于该 type 后，编译器会对执行结果再次施行 operator->。编译器不断执行这动作直至触及 a pointer to a built-in type，然后才进行成员存取

// 实例
list<Foo>::iterator ite;
...
*ite;	// 获得 a Foo object
ite->method();
// 唤起 Foo::method()
// 相当于 (*ite).method();
// 相当于 (&(*ite))->method();
ite->field = 7;
// 赋值 Foo object's field
// only if field is public
// 相当于 (*ite).field = 7;
// 相当于 (&(*ite))->field=7;

// G4.9 相较于 G2.9
// 模板参数只有一个（易理解）
// node 结构有其 parent
// node 的成员的 type 较精准

// G2.9
template <class T, class Alloc = alloc>
class list {
    public:
    	typedef __list_iterator<T,T&,T*> iterator;
    ...
};
template <class T, class Ref, class Ptr>
struct __list_iterator
{
    typedef Ptr pointer;	// (3)
    typedef Ref reference;	// (4)
    ...
};
template <class T>
struct __list_node {
    typedef void* void_pointer;
    void_pointer prev;
    void_pointer next;
    T data;
};

// G4.9
template <typename _Tp, typename _Alloc = std::allocator<_Tp>>
class list : protected _List_base<_Tp,_Alloc>
{
    public:
    	typedef _List_iterator<_Tp> iterator;
    ...
};
template <typename _Tp>
struct _List_iterator
{
    typedef _Tp* pointer;	// (3)
    typedef _Tp& reference;	// (4)
    ...
};
struct _List_node_base
{
    _List_node_base* _M_next;
    _List_node_base* _M_prev;
};
template <typename _Tp>
struct _List_node : public _List_node_base
{
    _Tp _M_data;
};

// G4.9 sizeof(list<int>) = 8
// 对一个容器进行 sizeof，得到的是容器本身大小，即容器内控制整个数据结构的所需数据大小，与容器内存储的元素大小和个数无关，list 有一个 _M_next 和一个 _M_prev，是两个指针(8个字节) 

迭代器的设计原则和 Iterator Traits 的作用与设计

Iterator 需要遵循的原则

iterators 必须有能力回答 algorithms 的提问
这样的提问在 C++ 标准库开发过程中设计出5种，本例出现3种。另两种从未在 C++ 标准库中被使用过：reference 和 pointer

template <typename _ForwardIterator>
inline void rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last) // rotate() 需要知道 iterators 的三个 associated types
{
    ...
    std::__rotate(__first, __middle, __last, std::iterator_category(__first));
}

/**
 * This function is not a part of the C++ standard but is syntactic sugar for internal library use only
*/
template <typename _Iter> 
inline typename iterator_traits<_Iter>::iterator_category __iterator_category(const _Iter&)
{
    return typename iterator_traits<_Iter>::iterator_category();
}

/// This is a helper function for the rotate algorithm
template <typename _RandonAccessIterator>
void __rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle,
              _RandomAccessIterator __last, random_access_iterator_tag)
{
    ...
    typedef typename iterator_traits<_RandomAccessIterator>::difference_type _Distance; // 两个 iterator 距离表现类型
    typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;	// iterator 所指元素本身类型
    _Distance __n = __last - __first;
    _Distance __k = __middle - __firstl
    ...
    for(;;) {
        if(__k < __n - __k) {
            if(__is_pod(_ValueType) && __k == 1) {
                _ValueType __t = _GLIBCXX_MOVE(*__p)
                ...
            }
        }
    }
}

Iterator 必须提供的5种 associated types

// 算法提问
template <typename I>
inline void algorithm(I first, I last)
{
    ...
    I::iterator_category
    I::pointer
    I::reference
    I::value_type
    I::difference_type
    ...
};

// 迭代器回答
// G2.9
template <class T, class Ref, class Ptr>
struct __list_iterator
{
	typedef bidirectional_iterator_tag iterator_category;	// (1)
	typedef T			value_type;			// (2)
	typedef Ptr			pointer;			// (3)
	typedef Ref			reference;			// (4)
	typedef ptrdiff_t	difference_type;	//(5)
	...
};

// G4.9
template <typename _Tp>
struct _List_iterator
{
	typedef std::bidirectional_iterator_tag iterator_category;	// (1)
	typedef _Tp			value_type;			// (2)
	typedef _Tp*		pointer;			// (3)
	typedef _Tp&		reference;			// (4)
	typedef ptrdiff_t	difference_type;	//(5)
	...
};

Traits 特性，特徵，特质

解决计算机问题的尚方宝剑：加一个中介层
Iterator Traits 用以分离 class iterators 和 non-class iterators
这个 traits 机器必须有能力分辨它所获得的 iterator 是 (1) class iterator T 或是 (2) native pointer（它被视为一种退化的 iterator） to T
利用 partial specialization 可达到目标
Non class (template) iterators 亦即 native pointer，无法定义 associated types. 但它的 associated types 其实很直观
class (template) iterators 都有能力定义自己的 associated types

// 于是当需要知道 I 的 value type 时便可这么写
template <typename I,...>
void algorithm(...) {
    typename iterator_traits<I>::value_type v1;
}

// 如果 I 是 class iterator 进入这里
template <class I>
struct iterator_traits {	// traits 是特性之意
    typedef typename I::value_type value_type;
};

// 两个 partial specialization
// 如果 I 是 pointer to T 进入这里
template <class T>
struct iterator_traits<T*> {
    typedef T value_type;
};

// 如果 I 是 pointer to const T 进入这里
template <class T>
struct iterator_traits<const T*> {
    typedef T value_type;	// 注意是 T 而不是 const T
    // vlaue_type 的主要目的是用来声明变量，而声明一个无法被赋值的变量没什么用，所以 iterator（即便是 constant iterator）的 value type 不应加上 cosnt。iterator 若是 cosnt int*，其 value_type 应该是 int 而非 const int
}；

完整的 iterator_traits

// ref. G2.9 <stl_iterator.h>
template <class I>
struct iterator_traits {
    typedef typename I::iterator_category	iterator_category;
    typedef typename I::value_type			value_type;
    typedef typename I::difference_type		difference_type;
    typedef typename I::pointer				pointer;
    typedef typename I::reference			reference;
};

// partial specialization for regular pointers
template <class T>
struct iterator_traits<T*> {
    typedef random_access_iterator_tag iterator_category;
    typedef T			value_type;
    typedef ptrdiff_t	difference_type;
    typedef T*			pointer;
    typedef T&			reference;
};
// partial specialization for regular const pointers
template <class T>
struct iterator_traits<const T*> {
    typedef random_access_iterator_tag iterator_category;
    typedef T				value_type;
    typedef ptrdiff_t		difference_type;
    typedef const T*		pointer;
    typedef const T&		reference;
};

各式各样的 Traits

• type traits <…/C++/type_traits>
• iterator traits <…/C++/bits/stl_iterator.h>
• char traits <…/C++/bits/char_traits.h>
• allocator traits <…/C++/bits/alloc_traits.h>
• pointer traits <…/C++/bits/ptr_traits.h>
• array traits <…/C++/array>

vector 深度探索

容器 vector

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;		// sizeof(vector<T>)=12
    	iterator finish;
    	iterator end_if_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); }
};

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() 除了被 push_back 调用之外还会被其他函数调用，所以检查
        // 在备用空间起始处建构一个元素，并以 vector 最后一个元素值为其初值
        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（个元素大小）
        // 如果原大小不为0，则分配原大小的两倍
        // 前半段用来放置原数据，后半段准备用来放置新数据
        
        iterator new_start = data_allocator::allocate(len);
        iterator new_finish = new_start;
        try {
            // 将原 vector 的内容拷贝到新 vector
            new_finish = uninitialized_copy(start, position, new_start);
            construct(new_finish, x);	// 为新元素设初值 x
            ++new_finish;	// 调整水位
            // 拷贝安插点后的原内容（因它也可能被 insert(p,x) 呼叫）
            new_finish = uninitialized_copy(position, finish, new_finish);
        }
        catch(...) {
            // "commit or rollback" semantics
            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;
    }
}

vector’s iterator

// G2.9
template <class T, class Alloc = alloc>
class vector {
    public:
    	typedef T value_type;
    	typedef value_type* iterator;	// T*
    ...
};

{
    vector<int> vec;
    ...
    vector<int>::iterator ite = vec.begin();
    iterator_traits<ite>::iterator_category;	// (1) 调用 iterator_traits<T*>
    iterator_traits<ite>::difference_type;		// (2)	
    iterator_traits<ite>::value_type;			// (3)
}

追踪 vector::iterator，发现它就是 _Tp* 外覆一个 iterator adapter，使能支持 5 associated types

// G4.9
template <typename _Tp, typename _Alloc = std::allocator<_Tp>>
class vector : protected _Vector_base<_Tp, _Alloc>
{
    ...
    typedef _Vector_base<_Tp,_Alloc> _Base;
    typedef typename _Base::pointer	pointer;
    typedef __gnu_cxx::__normal_iterator<pointer,vector> iterator;
    ...
};

using std::iterator_traits;
using std::iterator;
template <typename _Iterator, typename _Container>
class __normal_iterator
{
    protected:
    	_Iterator _M_current;
    	typedef iterator_traits<_Iterator> __traits_type;
    public:
    	typedef _Iterator iterator_type;
    	typedef typename __traits_type::iterator_category	iterator_category;
    	typedef typename __traits_type::value_type			value_type;
    	typedef typename __traits_type::difference_type		difference_type;
    	typedef typename __traits_type::reference			reference;
    	typedef typename __traits_type::pointer				pointer;
    
    	_GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT : _M_current(_Iterator()) { }
    ...
}

template <typename _Tp, typename _Alloc>
struct _Vector_base
{
    typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template rebind<_Tp>::other _Tp_alloc_type;
    typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer pointer;
    ...
}

template <typename _Tp>
class allocator : public __glibcxx_base_allocator<_Tp>
{
    public:
    	typedef size_t		size_type;
    	typedef ptrdiff_t	difference_type;
    	typedef _Tp*		pointer;
    	typedef const _Tp*	const_pointer;
    	typedef _Tp&		reference;
    	typedef const _Tp&	const_reference;
    	typedef _Tp			value_type;
    ...
        // Inherit everything else
};

// G4.9
template <typename _Tp, typename _Alloc = std::allocator<_Tp>>
class vector : protected _Vector_base<_Tp, _Alloc>
{
    ...
    typedef _Vector_base<_Tp, _Alloc> _Base;
    typedef typename _Base::pointer		pointer;
    typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;
    ...
}

{
    vector<int> vec;
	...
	vector<int>::iterator ite = vec.begin();
	iterator_traits<ite>::iterator_category;	// (1) 调用 vector<T>::iterator
	iterator_traits<ite>::difference_type		// (2)
	iterator_traits<ite>::value_type			// (3)
}

array、forward_list 深度探索

容器 array

// TR1
template <typename _Tp, std::size_t _Nm>
struct array
{
    typedef _Tp			value_type;
    typedef _Tp*		pointer;
    typedef value_type*	iterator;	// 其 iterator 是 native pointer，G2.9 vector 也是如此
    
    // Support for zero-sized arrays mandatory
    value_type _M_instance[_Nm ? _Nm : 1];
    
    iterator begin() { return iterator(&_M_instance[0]); }
    
    iterator end() { return iterator(&_M_instance[_Nm]); }
    ...
    // 没有 ctor，没有 dtor
}

{
    array<int, 10> myArray;
    auto ite = myArray.begin();
    // array<int, 10>::iterator ite = ...
    ite += 3;
    cout << *ite;
}

{
    int a[100];			// OK
    int[100] b;			// fail
    typedef int T[100];
    T c;				// OK
}

// G4.9
template <typename _Tp, std::size_t _Nm>
struct __array_traits
{
    typedef _Tp _Type[_Nm];
    
    static constexpr _Tp& _S_ref(const _Type& __t, std::size_t __n) noexcept { return const_cast<Tp&>(__t[__n]); }
};

template <typename _Tp, std::size_t _Nm>
struct array
{
    typedef _Tp			value_type;
    typedef value_type*	pointer;
    typedef value_type&	reference;
    typedef value_type* iterator;
    typedef std::size_t	size_type;
    
    // Support for zero-sized arrays mandatory
    typedef _GLIBCXX_STD_C::__array_traits<_Tp, _Nm> _AT_Type;
    typename _AT_Type::_Type _M_elems;
    
    // No explicit construct/copy/destroy for aggregate type
    iterator begin() noexcept { return iterator(data()); }
    iterator end() noexcept { return iterator(data() + _Nm); }
    constexpr size_type size() const noexcept { return _Nm; }
    reference operator[](size_type __n) noexcept {
        return _AT_Type::_S_ref(_M_elems, __n);		// 没有边检
    }
    reference at(size_type __n) {
        if(__n >= _Nm) std::__throw_out_of_range_fmt(...);	// 有边检
        return _AT_Type::_S_ref(_M_elems, __n);
    }
    pointer data() noexcept { return std::__addressof(_AT_Type::_S_ref(_M_elems, 0)); }
    ...
};

容器 forward_list

deque、queue 和 stack 深度探索

容器 deque

template <class T, class Alloc=alloc, size_t BufSiz=0> // BufSiz 所谓 buffer size 是指每个 buffer 容纳的元素个数
class deque {
    public:
    	typedef T value_type;
    	typedef __deque_iterator<T,T&,T*,BufSiz> iterator;
    protected:
    	typedef pointer* map_pointer;	// T**
    protected:
    	iterator start;			// sizeof(vector<T>) = 40
    	iterator finish;		// sizeof(iterator) = 16
    	map_pointer map;
    	size_type map_size;
    public:
    	iterator begin() { return start; }
    	iterator end() { return finish; }
    	size_type size() const { return finish - start; }
    ...
};

// 如果 n 不为 0，返回 n，表示 buffer size 由使用者自定
// 如果 n 为 0，表示 buffer size 使用预设值，那么
//	如果 sz（sizeof(value_type)）小于512，返回 512/sz
//	如果 sz 不小于512，返回1
inline size_t __deque_buf_size(size_t n, size_t sz)
{
    return n != 0 ? n : (sz < 512 ? size_t(512 / sz) : size_t(1));
}

deque’iterator

template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {
    typedef random_access_iterator_tag iterator_category;	// (1)
    typedef T value_type;								// (2)
    typedef Ptr pointer;								// (3)
    typedef Ref reference;								// (4)
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;					// (5)
    typedef T** map_pointer;
    typedef __deque_iterator self;
    
    T* cur;
    T* first;
    T* last;
    map_pointer node;
    ...
};

deque<T>::insert()

// 在 position 处安插一个元素，其值为 x
iterator insert(iterator position, const value_type& x) {
    if (postion.cur == start.cur) {	// 如果安插点是 deque 最前端
        push_front(x);				// 交给 push_front() 做
        return start;
    }
    else if (position.cur == finish.cur) {	// 如果安插点是 deque 最尾端
        push_back(x);						// 交给 push_back() 做
        iterator tmp = finish;
        --tmp;
        return tmp;
    }
    else {
        return insert_aux(position, x);
    }
}

template <class T, class Alloc, size_t BufSize>
typename deque<T, Alloc, BufSize>::iterator
deque<T, Alloc, BufSize>::insert_aux(iterator pos, const value_type& x) {
    difference_type index = pos - start;	// 安插点之前的元素个数
    value_type x_copy = x;
    if (index < size() / 2) {			// 如果安插点之前的元素个数较少
        push_front(front());			// 在最前端加入与第一元素同值的元素
        ...
        copy(front2, pos1, front1);		// 元素搬移
    }
    else {						// 安插点之后的元素个数较少
        push_back(back());		// 在尾端加入与最末元素同值的元素
        ...
        copy_backward(pos, back2, back1);	// 元素搬移
    }
    *pos = x_copy;	// 在安插点上设定新值
    return pos;
}

deque 如何模拟连续空间

全都是 deque iterators 的功劳

reference operator[](size_type n)
{
    return start[difference_type(n)];
}

reference front()
{
    return *start;
}

reference back()
{
    iterator tmp = finish;
    --tmp;
    return *tmp;
}

size_type size() const
{
    return finish - start;
}

bool empty() const
{
    return finish == start;
}

reference operator*() const
{
    return *cur;
}

pointer operator->() const
{
    return &(operator*());
}

// 两根 iterators 之间的距离相当于
// (1) 两根 iterators 间的 buffers 的总长度 +
// (2) itr 至其 buffer 末尾的长度 +
// (3) x 至其 buffer 起头的长度
difference_type operator-(const self& x) const
{
    return difference_type(buffer_size()) * (node - x.node - 1) + (cur - first) + (x.last - x.cur);
    // node - x.node - 1 首尾 buffers 之间的 buffers 数量
    // cur - first 末尾(当前) buffer 的元素量
    // x.last - x.cur 起始 buffer 的元素量
}

void set_node(map_pointer new_node) {
    node = new_node;
    first = *new_node;
    last = first + difference_type(buffer_size());
}

self& operator++() {
    ++cur;					// 切换至下一元素
    if (cur == last) {			// 如果抵达缓冲区尾端
        set_node(node + 1);		// 就跳至下一节点（缓冲区）
        cur = first;			// 的起点
    }
    return *this;
}

self operator++(int) {
    self tmp = *this;
    ++*this;
    return tmp;
}

self& operator--() {
    if (cur == first) {			// 如果目前在缓冲区起头
        set_node(node - 1);		// 就跳至前一节点（缓冲区）
        cur = last;				// 的最末端
    }
    --cur;						// 往前移一元素（此即最末元素）
    return *this;
}

self operator--(int) {
    self tmp = *this;
    --*this;
    return tmp;
}

self& operator+=(difference_type n) {
    difference_type offset = n + (cur - first);
    if (offset >= 0 && offset < difference_type(buffer_size()))
        // 目标位置在同一缓冲区内
        cur += n;
    else {
        // 目标位置不在同一缓冲区内
        difference_type node_offset = offset > 0 ? offset / difference_type(buffer_size())
            									: -difference_type((-offset - 1) / buffer_size()) - 1;
        // 切换至正确的缓冲区
        set_node(node + node_offset);
        // 切换至正确的元素
        cur = first + (offset - node_offset * difference_type(buffer_size()));
    }
    return *this;
}

self operator+(difference_type n) const {
    self tmp = *this;
    return tmp += n;
}

self& operator-=(difference_type n) { 
    return *this += -n;
}

self operator-(difference_type n) const {
	self tmp = *this;
    return tmp -= n;
}

reference operator[](difference_type n) const {
    return *(*this + n);
}

deque

控制中心 map 使用 vector 存储，当空间不足时，进行扩充，原来的值复制到新空间的中段，这样才能向左和向右扩充缓冲区

template <typename _Tp, typename _Alloc>
class _Deque_base
{
    protected:
    	struct _Deque_impl : public _Tp_alloc_type {
            _Tp** _M_map;
            size_t _M_map_size;
            iterator _M_start;
            iterator _M_finish;
            ...
        };
    ...
};

// 如果 node 是个 int，则 buffer 内含的 node 数量是 512/sizeof(int) = 128
// 如果 node 是个 double，则 buffer 内含的 node 数量是 512/sizeof(double) = 64
// 如果 node 是个 class/struct/array，而其大小 >= 512，则 buffer 内含的 node 数量是 1
#define _GLIBCXX_DEQUE_BUF_SIZE 512

inline size_t __deque_buf_size(size_t __size)
{
    return (__size < _GLIBCXX_DEQUE_BUF_SIZE ? size_t(_GLIBCXX_DEQUE_BUF_SIZE / __size) : size_t(1));
}

template<typename _Tp, typename _Alloc = std::allocator<_Tp>>
class deque : protected _Deque_base<_Tp, _Alloc>	// G2.91 允许指派 buffer size，G4.53 没了
{
    ...
    static size_t _S_buffer_size()
    {
        return __deque_buf_size(sizeof(_Tp));
    }
};

容器 queue

queue 内含一个 deque，封住一部分功能
在技术上，queue 当作一个 container adapter

template <class T, class Sequence=deque<T>>
class queue {
    ...
    public:
    	typedef typename Sequence::value_type value_type;
    	typedef typename Sequence::size_type size_type;
    	typedef typename Sequence::reference reference;
    	typedef typename Sequence::const_reference const_reference;
    protected:
    	Sequence c;	// 底层容器
    public:
    	bool empty() const { return c.empty(); }
    	size_type size() const { return c.size(); }
    	reference front() { return c.front(); }
    	const_reference front() const { return c.front(); }
    	reference back() { return c.back(); }
    	const_reference back() const { return c.back(); }
    	void push(const value_type& x) { c.push_back(x); }
    	void pop() { c.pop_front(); }
};

容器 stack

stack 内含一个 deque，封住一部分功能
在技术上，stack 当作一个 container adapter

template <class T, class Sequence=deque<T>>
class stack {
    ...
    public:
    	typedef typename Sequence::value_type value_type;
    	typedef typename Sequence::size_type size_type;
    	typedef typename Sequence::reference reference;
    	typedef typename Sequence::const_reference const_reference;
    protected:
    	Sequence c; // 底层容器
    public:
    	bool empty() const { return c.empty(); }
    	size_type size() const { return c.size(); }
    	reference top() { return c.back(); }
    	const_reference top() const { return c.back(); }
    	void push(const value_type& x) { c.push_back(x); }
    	void pop() { c.pop_back(); }
};

queue 和 stack，关于其 iterator 和底层结构

只要底部数据结构能够提供 queue 和 stack 转调用所需要的函数，这个容器就能作为底部支撑

stack 或 queue 都不允许遍历，也不提供 iterator

stack<string>::iterator ite;		// [Error] 'iterator' is not a member of 'std::stack<std::basic_string<char>>'
queue<string>::iterator ite;		// [Error] 'iterator' is not a member of 'std::queue<std::basic_string<char>>'

stack 和 queue 都可选择 list 或 deque 做为底层结构

默认的作为底部支撑（deque）比较快

{
    stack<string, list<string>> c;
    for(long i=0; i< 10; ++i) {
        snprintf(buf, 10, "%d", rand());
        c.push(string(buf));
    }
    cout << "stack.size()= " << c.size() << endl;
    cout << "stack.top()= " << c.top() << endl;
    c.pop();
    cout << "stack.size()= " << c.size() << endl;
    cout << "stack.top()= " << c.top() << endl;
}

{
    queue<string, list<string>> c;
    for(long i=0; i< 10; ++i) {
        snprintf(buf, 10, "%d", rand());
        c.push(string(buf));
    }
    cout << "queue.size()= " << c.size() << endl;
    cout << "queue.front()= " << c.front() << endl;
    cout << "queue.back()= " << c.back() << endl;
    c.pop();
    cout << "queue.size()= " << c.size() << endl;
    cout << "queue.front()= " << c.front() << endl;
    cout << "queue.back()= " << c.back() << endl;
}

stack 可选择 vector 做为底层结构

{
    stack<string, vector<string>> c;
    for(long i=0; i< 10; ++i) {
        snprintf(buf, 10, "%d", rand());
        c.push(string(buf));
    }
    cout << "stack.size()= " << c.size() << endl;
    cout << "stack.top()= " << c.top() << endl;
    c.pop();
    cout << "stack.size()= " << c.size() << endl;
    cout << "stack.top()= " << c.top() << endl;
}

queue 不可选择 vector 做为底层结构

{
    queue<string, vector<string>> c;	// 使用模板时，编译器不会预先做全面性的检测，而是用多少检查多少
    for(long i=0; i< 10; ++i) {
        snprintf(buf, 10, "%d", rand());
        c.push(string(buf));
    }
    cout << "queue.size()= " << c.size() << endl;
    cout << "queue.front()= " << c.front() << endl;
    cout << "queue.back()= " << c.back() << endl;
    // c.pop();		// [Error] 'class std::vector<std::basic_string<char> >' has no member named 'pop_front'
    cout << "queue.size()= " << c.size() << endl;
    cout << "queue.front()= " << c.front() << endl;
    cout << "queue.back()= " << c.back() << endl;
}

stack 和 queue 都不可选择 set 或 map 做为底层结构

{
    stack<string, set<string>> c;			// 编译器无异议
    for(long i=0; i< 10; ++i) {
        snprintf(buf, 10, "%d", rand());
        // c.push(string(buf));		// [Error] 'class std::set<std::basic_string<char> >' has no member named 'push_back'
    }
    cout << "stack.size()= " << c.size() << endl;
    // cout << "stack.top()= " << c.top() << endl;		 // [Error] 'class std::set<std::basic_string<char> >' has no member named 'back'
    // c.pop();		// [Error] 'class std::set<std::basic_string<char> >' has no member named 'pop_back'
    cout << "stack.size()= " << c.size() << endl;
    // cout << "stack.top()= " << c.top() << endl;		// [Error] 'class std::set<std::basic_string<char> >' has no member named 'back'
}

{
    stack<string, map<string>> c;			// [Error] template argument...
    queue<string, map<string>> c;			// [Error] template argument...
}

RB-tree 深度探索

容器 rb_tree

Red-Black tree（红黑树）是平衡二元搜寻树（balanced binary search tree）中常被使用的一种
平衡二元搜寻树的特徵：排列规则有利 search 和 insert，并保持适度平衡——无任何节点过深

rb_tree 提供 “遍历” 操作及 iterators
按正常规则（++ite）遍历，便能获得排序状态（sorted）（中序遍历红黑树）

我们不应使用 rb_tree 的 iterators 改变元素值（因为元素有其严谨排列规则）
编程层面（programming level）并未阻绝此事。如此设计是正确的，因为 rb_tree 即将为 set 和 map 服务（做为其底部支持），而 map 允许元素的 data 被改变，只有元素的 key 才是不可被改变的

rb_tree 提供两种 insertion 操作：insert_unique() 和 insert_equal()
前者表示节点的 key 一定在整个 tree 中独一无二，否则安插失败（无作用，不会报错）；后者表示节点的 key 可重复

元素本身是可以放两个东西的，一个是 key，一个是 data，，合起来叫 value

template <class Arg, class Result>
struct unary_function {
    typedef Arg argument_type;
    typedef Result result_type;
};

template <class T>	// 仿函数
struct identity : public unary_function<T, T> {
    const T& operator()(const T& x) const { return x; }
};

template <class Arg1, class Arg2, class Result>
struct binary_function {
    typedef Arg1 first_argument_type;
    typedef Arg2 second_argument_type;
    typedef Result result_type;
};

template <class T>
struct less : public binary_function<T, T, bool> {
    bool operator()(const T& x, const T& y) const {
        return x < y;
    }
};

// C++标准库 G2.9
template <class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
class rb_tree {
    protected:
    	typedef __rb_tree_node<Value> rb_tree_node;
    	...
    public:
    	typedef rb_tree_node* link_type;
    	...
    protected:
    	// RB-tree 只以三笔资料表现它自己
    	size_type node_count;		// rb_tree 的大小（节点数量）
    	link_type header;
    	Compare key_compare;		// key 的大小比较准则：应会是个 function object，仿函数大小是0字节，编译器对于大小是0的 class 创造出来的对象是1字节
    	...
        // 大小：9-> 12（边界对齐，以4的倍数分配内存）
};

// App.
rb_tree<int, int, identity<int>, less<int>, alloc> myTree;

容器 rb_tree，用例

// G2.9
// 测试 rb_tree
rb_tree<int, int, identity<int>, less<int>> itree;
cout << itree.empty() << endl;	// print: 1
cout << itree.empty() << endl;	// print: 0

itree.insert_unique(3);
itree.insert_unique(8);
itree.insert_unique(5);
itree.insert_unique(9);
itree.insert_unique(13);
itree.insert_unique(5);		// no effect, since using insert_unique()，不会报错也不会抛出异常
cout << itree.empty() << endl;	// print: 0
cout << itree.size() << endl;	// print: 5，第二个5没放进去
cout << itree.count(5) << endl;	// print: 1

itree.insert_equal(5);
itree.insert_equal(5);
cout << itree.size() << endl;	// print: 7, since using insert_equal()
cout << itree.count(5) << endl;	// print: 3

// G4.9
// 测试 rb_tree
_Rb_tree<int, int, _Identity<int>, less<int>> itree;
cout << itree.empty() << endl;	// print: 1
cout << itree.size() << endl;	// print: 0

itree._M_insert_unique(3);
itree._M_insert_unique(8);
itree._M_insert_unique(5);
itree._M_insert_unique(9);
itree._M_insert_unique(13);
itree._M_insert_unique(5);	// no effect, since using _M_insert_unique()，不会报错也不会抛出异常
cout << itree.empty() << endl;	// print: 0
cout << itree.size() << endl;	// print: 5，第二个5没放进去
cout << itree.count(5) << endl;	// print: 1

itree._M_insert_equal(5);
itree._M_insert_equal(5);
cout << itree.size() << endl;		// print: 7, since using _M_insert_equal()
cout << itree.count(5) << endl; 	// print: 3

// print:
// test_Rb_tree().......... 
// 1
// 0
// 0
// 5
// 1
// 7
// 3

G4.9 Header and body 实现手法，header—— _Rb_tree 包含一个指针或者一个单一的东西来表现它的实现手法 impl，本身无太多设计，真正实作的设计位于 body，body——_Rb_tree_impl
color 是 Enumeration（枚举类型），4个字节
_M_color(_Rb_tree_color 4字节)+_M_parent(_Base_ptr 4字节)+_M_right(_Base_ptr 4字节)+_M_left(_Base_ptr 4字节)+_M_value_field(_Val 4字节)+_M_node_count(size_type 4字节)=24字节

set、multiset 深度探索

容器 set, multiset

set/multiset 以 rb_tree 为底层结构，因此有元素自动排序特性
排序的依据是 key，而 set/multiset 元素的 value 和 key 合一：value 就是 key

set/multiset 提供 “遍历” 操作及 iterators
按正常规则（++ite）遍历，便能获得排序状态（sorted）

我们无法使用 set/multiset 的 iterators 改变元素值（因为 key 有其严谨排列规则）
set/multiset 的 iterator 是其底部的 RB tree 的 const-iterator，就是为了禁止 user 对元素赋值

set 元素的 key 必须独一无二，因此其 insert() 用的是 rb_tree 的 insert_unique()
multiset 元素的 key 可以重复，因此其 insert() 用的是 rb_tree 的 insert_equal()

容器 set

set 的所有操作，都转呼叫底层 t（rb_tree）的操作
从这层意义看，set 未尝不是个 container adapter

template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set {
    public:
    	// typedefs:
    	typedef Key key_type;
    	typedef Key value_type;
    	typedef Compare key_compare;
    	typedef Compare value_compare;
    private:
    	typedef rb_tree<key_type, value_type, identity<value_type>, key_compare, Alloc> rep_type;
    	rep_type t;
    public:
    	typedef typename rep_type::const_iterator iterator;	// const_iterator，这种迭代器不允许修改内容
    ...
};

{
    set<int> iset;
}

{
    set<int, less<int>, alloc> iset;
}

{
    template<int, int, identity<int>, less<int>, alloc> class rb_tree;
}

容器 set, in VC6

VC6 不提供 identity()

// VC6
template <class _K, class _Pr = less<_K>, class _A = allocator<_K> >
class set {
    public:
    	typedef set<_K, _Pr, _A> _Myt;
    	typedef _K value_type;
    	struct _Kfn : public unary_function<value_type, _K> {	// 这相当于 G2.9 的 identity() 或 G4.9 的 _Identity()
            const _K& operator()(const value_type& _X) const {
                return (_X);
            }
        } ;
    	typedef _Pr value_compare;
    	typedef _K key_type;
    	typedef _Pr key_compare;
    	typedef _A allocator_type;
    	typedef _Tree<_K, value_type, _Kfn, _Pr, _A> _Imp;
    ...
    protected:
    	_Imp _Tr;
};

使用容器 multiset

跳转到使用容器 multiset

map、multimap 深度探索

容器 map, multimap

map/multimap 以 rb_tree 为底层结构，因此有元素自动排序特性
排序的依据是 key

map/multimap 提供 “遍历” 操作及 iterators
按正常规则（++ite）遍历，便能获得排序状态（sorted）

我们无法使用 map/multimap 的 iterators 改变元素的 key（因为 key 有其严谨排列规则），但可以用它来改变元素的 data
因此 map/multimap 内部自动将 user 指定的 key type 设为 const，如此便能禁止 user 对元素的 key 赋值

map 元素的 key 必须独一无二，因此其 insert() 用的是 rb_tree 的 insert_unique()
multimap 元素的 key 可以重复，因此其 insert() 用的是 rb_tree 的 insert_equal()

容器 map

template <class Key, class T, class Compare = less<Key>, class Alloc=alloc>
class map {
	public:
    	typedef Key key_type;
    	typedef T data_type;
    	typedef T mapped_type;
    	typedef pair<const Key, T> value_type;	// Key 设为 const，禁止 user 对元素的 Key 赋值
    	typedef Compare key_compare;
    private:
    	typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type;
    	rep_type t;
    public:
    	typedef typename rep_type::iterator iterator;
    ...
};

{
    map<int, stirng> imap;
}

{
    map<int, string, less<int>, alloc> imap;
}

{
    template<int, pair<const int, string>, select1st<pair<const int, string>>, less<int>, alloc> class rb_tree;
}

容器 map, in VC6

VC6 不提供 select1st()

// G2.9
template <class Arg, class Result>
struct unary_function {
    typedef Arg argument_type;
    typedef Result result_type;
};

template <class Pair>
struct select1st : public unary_function<Pair, typename Pair::first_type> {	// 仿函数
    const typename Pair::first_type& operator()(const Pair& x) const {
        return x.first;
    }
};

// VC6
template <class _K, class _Ty, class _Pr = less<_K>, class _A = allocator<_Ty> >
class map {
    public:
    	typedef map<_K, _Ty, _Pr, _A> _Myt;
    	typedef pair<const _K, _Ty> value_type;
    	struct _Kfn : public unary_function<value_type, _K> {	// 这相当 G2.9 的 select1st() 或 G4.9 的 _Select1st()
            const _K& operator()(const value_type& _X) const {
                return (_X.first);
            }
        };
    ...
    
    typedef _Tree<_K, value_type, _Kfn, _Pr, _A> _Imp;
    ...
    protected:
    	_Imp _Tr;
};

容器 map，独特的 operator[]

// G4.9
// [23.3.1.2] element access
	/**
	 * @brief Subscript ( @c [] ) access to %map data
	 * @param __k The key for which data should be retrieved
	 * @return A reference to the data of the (key,data) %pair
	 *
	 * Allows for easy lookup with the subscript( @c [] )
	 * operator. Returns data associated with the key specified in
	 * subscript. If the key does not exist, a pair with that key
	 * is created using default values, which is then returned
	 *
	 * Lookup requires logarithmic time
	 */
mapped_type& operator[](const key_type& __k)
{
    // concept requirements
    __glibcxx_function_requires(_DefaultConstructibleConcept);
    
    iterator __i = lower_bound(__k);	// lower_bound 是二分搜寻（binary search）的一种版本，试图在 sorted [first,last) 中寻找元素 value。若 [first,last) 拥有与 value 相等的元素(s)，便返回一个 iterator 指向其中第一个元素。如果没有这样的元素存在，便返回假设该元素存在时应该出现的位置。也就是说它会返回 iterator 指向第一个不小于 value 的元素。如果 value 大于 [first,last) 内的任何元素，将返回 last。换句话说 lower_bound 返回的是不破坏排序得以安插 value 的第一个适当位置
    // __i->first is greater than or equivalent to __k
    if(__i == end() || key_comp()(__k, (*__i).first))
#if __cplusplus >= 201103L
        __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct,
                                          		std::tuple<const key_type>, std::tuple<>());
#else
    	__i = insert(__i, value_type(__k, mapped_type()));
#endif
    	return (*__i).second;
}

使用容器 map

跳转到使用容器 map

容器 multimap

使用容器 multimap

跳转到使用容器 multimap

hashtable 深度探索

容器 hashtable

我们可以使用 hashtable iterators 改变元素的 data，但不能改变元素的 key（因为 hashtable 根据 key 实现严谨的元素排列）
Separate Chaining 链表法/分离链接法 rehashing 再散列/按照散列函数把元素重新打散 GNU_C是单向链表 VC是双向链表
散列函数一般采用除留取余法
buckets（篮子）大小刻意为质数，扩充时会选择原来倍数附近的质数

// GNU_C实现
static const unsigned long __stl_prime_list[__stl_num_primes] = {
    53,		97,			193,	389,	769,
    1543,	3079,		6151,	12289,	24593,
    49157,	98317,		196613,	393241,	786433,
    1572869,	3145739,	6291469,	12582917,	25165843,
    50331653,	100663319,	201326611,		402653189,
    805306457,	1610612741,	3221225473ul,	429496729lul
};

template <class Value>
struct __hashtable_node {
    __hashtable_node* next;
    Value val;
};
// sizeof(__hashtable_node) = 8

template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
struct __hashtable_iterator {
...
    node* cur;
    hashtable* ht;	// cur进入链表末尾（NULL），有能力回到控制中心（散列表）来
};

// C++ 标准库	HashFcn 为计算每个元素编号的函数，将对象折射为元素编号
// ExtractKey 为萃取出 key，现在散列表可能放着一包东西，比如 pair，这个函数说明怎么从一包东西取出 key
// EqualKey 函数说明什么叫 key 相等
template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc = alloc>
class hashtable {
    public:
    	typedef HashFcn		hasher;
    	typedef EqualKey	key_equal;
    	typedef size_t		size_type;
    private:
    	hasher		hash;
    	key_equal	equals;
    	ExtractKey	get_key;
    
    	typedef __hashtable_node<Value> node;
    
    	vector<node*, Alloc> buckets;
    	size_type num_elements;
    public:
    	size_type bucket_count() const { return buckets.size(); }
    ...
};
// sizeof(hashtable<>) = 19 -> 20
// hash，equals，get_key 为仿函数，理论上大小是0，实际上大小是1
// buckets 是一个 vector，本身有三根指针，大小是12
// num_elements 大小是4
// 因为对齐关系，大小从19调整为20

// App.
{
    hashtable<const char*, const char*, hash<const char*>, identity<const char*>, eqstr, alloc>
        ht(50, hash<const char*>(), eqstr());
    
    ht.insert_unique("kiwi");
    ht.insert_unique("plum");
    ht.insert_unique("apple");
}

// 比较两个 c-string 是否相等，有 strcmp() 可用，但它返回 -1,0,1，不是返回 bool，所以必须加一层外套
struct eqstr {	// 比指针指向内容是否相等，而不是比指针是否相等
    bool operator()(const char* s1, const char* s1) const {
        return strcmp(s1, s2) == 0;
    }
};

hash-function, hash-code

hash function 的目的，就是希望根据元素值算出一个 hash code（一个可进行 modulus 运算的值），使得元素经 hash code 映射之后能够够杂够乱够随机地置于 hashtable 内。愈是杂乱，愈不容易发生碰撞
如果 hash-function 中放的不是已经写好了，就要以下面这种形式为空的 hash 写一个特化版本，具体内容需要自己设计，但是数据都是由基本类型构成的，可以把数据中的各种基础类型的 hash 结合起来使用

// 泛化
template <class Key> struct hash { };

// 特化	__STL_TEMPLATE_NULL 为 template<>
__STL_TEMPLATE_NULL struct hash<char> {
    size_t operator()(char x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<short> {
    size_t operator()(short x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned short> {
    size_t operator()(unsigned short x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<int> {
    size_t operator()(int x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned int> {
    size_t operator()(unsigned int x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<long> {
    size_t operator()(long x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned long> {
    size_t operator()(unsigned long x) const { return x; }
};

{
    hash<Foo>();
    
    int i = hash<int>()(32);
}

注意，标准库没有提供现成的 hash<std::string>

inline size_t __stl_hash_string(const char* s)
{
    unsigned long h = 0;
    for ( ; *s; ++s)	// 本例若 s 指向 "abc"，计算得 h 为 5 * (5 * 'a' + 'b') + 'c'
        h = 5*h + *s;
    
    return size_t(h);
}
__STL_TEMPLATE_NULL struct hash<char*>
{
    size_t operator()(const char* s) const {
        return __stl_hash_string(s);
    }
};
__STL_TEMPLATE_NULL struct hash<const char*>
{
    size_t operator()(const char* s) const {
        return __stl_hash_string(s);
    }
};

// App.
{
    hashtable<const char*, const char*, hash<const char*>, identity<const char*>, eqstr, alloc>
        ht(50, hash<const char*>(), eqstr());
    
    ht.insert_unique("kiwi");
    ht.insert_unique("plum");
    ht.insert_unique("apple");
}
// hash code of "kiwi" = 5*(5*(5*'k'+'i')+'w)+'i=5*(5*(5*107+105)+119)+105=16700%53=5
// hash code of "plum" = 5*(5*(5*'p'+'l')+'u')+'m'=5*(5*(5*112+108)+117)+109=17394%53=10
// hash code of "apple" = 5*(5*(5*(5*'a'+'p')+'p')+'l')+'e'=5*(5*(5*(5*97+112)+112)+108)+101=78066%53=50

modulus 运算

// hashtable 内的部分函数
iterator find(const key_type& key) {
    size_type n = bkt_num_key(key);
    ...
}

iterator count(const key_type& key) const {
    const size_type n = bkt_num_key(key);
    ...
}

template <class V, class K, class HF, class ExK, class EqK, class A>
__hashtable_iterator<V, K, HF, ExK, EqK, A>& __hashtable_iterator<V, K, HF, ExK, EqK, A>::operator++()
{
	...
    size_type bucket = ht->bkt_num(old->val);
    ...
}

size_type bkt_num(const value_type& obj) const {
    return bkt_num_key(get_key(obj));
}

size_type bkt_num(const value_type& obj, size_t n) const {
    return bkt_num_key(get_key(obj), n);
}

size_type bkt_num_key(const key_type& key) const {
    return bkt_num_key(key, buckets.size());
}

size_type bkt_num_key(const key_type& key, size_t n) const {	// 上面函数最终都会跑到这个函数
    return hash(key) % n;	// 这个 hash 不是前面出现的 struct hash（template<> struct hash<char*> { ... };）
    // 而是 class hashtable 中的 hasher hash（template <...> class hashtable { private: hasher hash; ... };）
}

hashtable 用例

// G2.9
template<> struct hash<string>
{
    size_t operator()(string s) const {
        return __stl_hash_string(s.c_str());
    }
};

{
    hashtable<string, string, hash<string>, identity<string>, equal_to<string>, alloc>
		sht(50, hash<string>(), equal_to<string>());

    cout<< sht.size() << endl;	// print: 0
    cout<< sht.bucket_count() << endl;	// print: 53
    
    // my goal!
    hashtable< pair<const string, int>, 
    				string, 
    				hash<string>, 
    				select1st< pair<const string, int> >, 
    				equal_to<string>, 
    				alloc
				>
		siht(100, hash<string>(), equal_to<string>());
    
    cout<< siht.size() << endl;	// print: 0
    cout<< siht.bucket_count() << endl;	// print: 193
    
    siht.insert_unique( make_pair(string("jjhou"),95) );
    siht.insert_unique( make_pair(string("sabrina"),90) );
    siht.insert_unique( make_pair(string("mjchen"),85) );
    cout<< siht.size() << enddl;		// print: 3
    cout<< siht.bucket_count() << endl;	// print: 193
    cout << siht.find(string("sabrina"))->second << endl;	// print: 90
    cout << siht.find(string("jjhou"))->second << endl;		// print: 95
    cout << siht.find(string("mjchen"))->second << endl;	// print: 85
}

// G4.9
// ...\4.9.2\include\c++\bits\basic_string.h
/// std::hash specialization for string
template<> struct hash<string> : public __hash_base<size_t, string>
{
    size_t operator()(const string& __s) const noexcept {
        return std::_Hash_impl::hash(__s.data(),__s.length());
    }
};

template<> struct __is_fast_hash<hash<string>> : std::false_type {
    
};


{
    _Hashtable< string, string, hash<string>, _Identity<string>, equal_to<string>, alloc>
    sht(50, hash<string>(), equal_to<string>());

    cout<< sht.size() << endl;			// print: 0
    cout<< sht.bucket_count() << endl;	// print: 53

	// my goal!
	_Hashtable< pair<const string, int>, 
    				string, 
    				hash<string>, 
    				select1st< pair<const string, int> >, 
    				equal_to<string>, 
    				alloc
				>
		siht(100, hash<string>(), equal_to<string>());	// [Error] wrong number of template arguments (6, should be 10)
    cout<< siht.size() << endl;				// print: 0
    cout<< siht.bucket_count() << endl;		// print: 193
    
    siht.insert_unique( make_pair(string("jjhou"),95) );
    siht.insert_unique( make_pair(string("sabrina"),90) );
    siht.insert_unique( make_pair(string("mjchen"),85) );
    cout<< siht.size() << enddl;		// print: 3
    cout<< siht.bucket_count() << endl;	// print: 193
    cout << siht.find(string("sabrina"))->second << endl;	// print: 90
    cout << siht.find(string("jjhou"))->second << endl;		// print: 95
    cout << siht.find(string("mjchen"))->second << endl;	// print: 85
}

hash_set、hash_multiset，hash_map、hash_multimap 概念

unordered 容器概念

unordered 容器

容器 unordered_set, unordered_multiset 容器 unordered_map, unordered_multimap

// G4.9
template <typename T, 
		typename Hash = hash<T>,
		typename EqPred = equal_to<T>,
		typename Allocator = allocator<T> >
class unordered_set;

template <typename T,
		typename Hash = hash<T>,
		typename EqPred = equal_to<T>,
		typename Allocator = allocator<T> >
class unordered_multiset;

template <typename Key, typename T,
		typename Hash = hash<T>,
		typename EqPred = equal_to<T>,
		typename Allocator = allocator<pair<const Key, T> > >
class unordered_map;

template <typename Key, typename T,
		typename Hash = hash<T>,
		typename EqPred = equal_to<T>,
		typename Allocator = allocator<pair<const Key, T> > >
class unordered_multimap;

使用容器 unordered_set

跳转到使用容器 unordered_set

算法的形式

C++标准库的算法

从语言层面讲

• 容器 Container 是个 class template
• 算法 Algorithm 是个 function template
• 迭代器 Iterator 是个 class template
• 仿函数 Functor 是个 class template
• 适配器 Adapter 是个 class template
• 分配器 Allocator 是个 class template

Algorithms 看不见 Containers，对其一无所知；所以，它所需要的一切信息都必须从 Iterators 取得，而 Iterators（由 Containers 供应）必须能够回答 Algorithm 的所有提问，才能搭配该 Algorithm 的所有操作
如果 Algorithms 发出问题，Iterators无法回答，那么编译到那一行，编译就会失败报错

// 标准库中的算法都是下面两种形式
template<typename Iterator>
Algorithm(Iterator itr1, Iterator itr2)
{
    ...
}

template<typename Iterator, typename Cmp>
Algorithm(Iterator itr1, Iterator itr2, Cmp comp)	// comp 为一个准则，比如怎么比较大小，大和小怎么定义，是一个仿函数
{
    ...
}

迭代器的分类（category）

各种容器的 iterators 的 iterator_category

// 五种 iterator category
struct input_iterator_tag {};	// 输入迭代器
struct output_iterator_tag {};	// 输出迭代器
struct forward_iterator_tag : public input_iterator_tag {};	// 单向迭代器，Forward-List 
struct bidirectional_iterator_tag : public forward_iterator_tag {};	// 双向迭代器，List Set/Multiset Map/Multimap
struct random_access_iterator_tag : public bidirectional_iterator_tag {};	// 随机访问迭代器，Array Vector Deque 
// Unordered Set/Multiset   Unordered Map/Multimap 看 hashtable 链表是单向还是双向才能判断是单向还是双向迭代器

void _display_category(random_access_iterator_tag)
{
    cout << "random_access_iterator" << endl;
}
void _display_category(bidirectional_iterator_tag)
{
    cout << "bidirectional_iterator" << endl;
}
void _display_category(forward_iterator_tag)
{
    cout << "forward_iterator" << endl;
}
void _display_category(output_iterator_tag)
{
    cout << "output_iterator" << endl;
}
void _display_category(input_iterator_tag)
{
    cout << "input_iterator" << endl;
}

template <typename I>
void display_category(I itr)
{
    typename iterator_traits<I>::iterator_category cagy;
    _display_category(cagy);	// 迭代器分类采用对象表示，编译器会自然而然找到该调用上面哪个函数，如果用整数表示则不行
}

{
    cout << "\ntest_iterator_category().......... \n"
        
    display_category(array<int,10>::iterator());
    display_category(vector<int>::iterator());
    display_category(list<int>::iterator());
    display_category(forward_list<int>::iterator());
    display_category(deque<int>::iterator());
    
    display_category(set<int>::iterator());
    display_category(map<int,int>::iterator());
    display_category(multiset<int>::iterator());
    display_category(multimap<int,int>::iterator());
    display_category(unordered_set<int>::iterator());
    display_category(unordered_map<int,int>::iterator());
    display_category(unordered_multiset<int>::iterator());
    display_category(unordered_multimap<int,int>::iterator());
    
    display_category(istream_iterator<int>());	// 从技术上，这两个迭代器是Adapter
    display_category(ostream_iterator<int>(cout,""));
}
// print:
// test_iterator_category().......... 
// random_access_iterator
// random_access_iterator
// bidirectional_iterator
// forward_iterator
// random_access_iterator
// bidirectional_iterator
// bidirectional_iterator
// bidirectional_iterator
// bidirectional_iterator
// forward_iterator
// forward_iterator
// forward_iterator
// forward_iterator
// input_iterator
// output_iterator

各种容器的 iterators 的 iterator_category 的 typeid

#include <typeinfo>	// typeid

void _display_category(random_access_iterator_tag)
{
    cout << "random_access_iterator" << endl;
}
void _display_category(bidirectional_iterator_tag)
{
    cout << "bidirectional_iterator" << endl;
}
void _display_category(forward_iterator_tag)
{
    cout << "forward_iterator" << endl;
}
void _display_category(output_iterator_tag)
{
    cout << "output_iterator" << endl;
}
void _display_category(input_iterator_tag)
{
    cout << "input_iterator" << endl;
}

template <typename I>
void display_category(I itr)
{
    typename iterator_traits<I>::iterator_category cagy;
    _display_category(cagy);
    
    cout << "typeid(itr).name()= " << typeid(itr).name() << endl << endl; // 输出C++编译器本身对于传进来这个类型的命名
    // The output depends on library implementation
    // The particular representation pointed by the returned valueis implementation-defined
    // and may or may not be different for differenct types
}

{
    cout << "\ntest_iterator_category_typeid().......... \n"
        
    display_category(array<int,10>::iterator());
    display_category(vector<int>::iterator());
    display_category(list<int>::iterator());
    display_category(forward_list<int>::iterator());
    display_category(deque<int>::iterator());
    
    display_category(set<int>::iterator());
    display_category(map<int,int>::iterator());
    display_category(multiset<int>::iterator());
    display_category(multimap<int,int>::iterator());
    display_category(unordered_set<int>::iterator());
    display_category(unordered_map<int,int>::iterator());
    display_category(unordered_multiset<int>::iterator());
    display_category(unordered_multimap<int,int>::iterator());
    
    display_category(istream_iterator<int>());
    display_category(ostream_iterator<int>(cout,""));
}
// print:	// 编译器会对命名的类型前面多加一些字符数字，后面也会多加一些字符数字，前后添加的由编译器实现定义的
// test_iterator_category_typeid().......... 
// random_access_iterator
// typeid(itr).name()= Pi
// 
// random_access_iterator
// typeid(itr).name()= N9__gnu_cxx17__normal_iteratorIPiSt6verctorIiSaliEEEE
//
// bidirectional_iterator
// typeid(itr).name()= St14_List_iteratorIiE
// 
// forward_iterator
// typeid(itr).name()= St18_Fwd_list_iteratorIiE
// 
// random_access_iterator
// typeid(itr).name()= St15_Deque_iteratorIiRiPiE
// 
// bidirectional_iterator
// typeid(itr).name()= St23_Rb_tree_const_iteratorIiE
// 
// bidirectional_iterator
// typeid(itr).name()= St17_Rb_tree_iteratorISt4pairIKiiEE
// 
// bidirectional_iterator
// typeid(itr).name()= St23_Rb_tree_const_iteratorIiE
// 
// bidirectional_iterator
// typeid(itr).name()= St17_Rb_tree_iteratorISt4pairIKiiEE
// 
// forward_iterator
// typeid(itr).name()= NSt8__detail14_Node_iteratorIiLb1ELb0EEE

// forward_iterator
// typeid(itr).name()= NSt8__detail14_Node_iteratorISt4pairIKiiELb0ELb0EEE
// 
// forward_iterator
// typeid(itr).name()= NSt8__detail14_Node_iteratorIiLb1ELboEEE
//
// forward_iterator
// typeid(itr).name()= NSt8__detail14_Node_iteratorISt4pairIKiiELboELboEEE
// 
// input_iterator
// typeid(itr).name()= St16istream_iteratorIicSt11char_traitsIcEiE
//
// output_iterator
// typeid(itr).name()= St16ostream_iteratorIicSt11char_traitsIcEE

istream_iterator 的 iterator_category

{
    display_category(istream_iterator<int>());
    display_category(ostream_iterator<int>(cout,""));
}

// 标准库/规格书有记载，不同的标准库的版本的做法可以不同，但是不能影响接口
// G2.9
template <class T, class Distance = ptrdiff_t>
class istream_iterator {
    public:
    	typedef input_iterator_tag iterator_category;	// 定义自己的分类是 input_iterator_tag
    ...
};

// G3.3
template <class _Tp, class _CharT = char, class _Traits = char_traits<_CharT>, class _Dist = ptrdiff_t>
class istream_iterator {
    public:
    	typedef input_iterator_tag iterator_category;
    ...
};

// G4.9
template <typename _Tp, typename _CharT = char, typename _Traits = char_traits<_CharT>, typename _Dist = ptrdiff_t>
class istream_iterator : public iterator<input_iterator_tag, _Tp, _Dist, const _Tp*, const _Tp&>
{
    ...
};

template <typename _Category, 
		typename _Tp, 
		typename _Distance = ptrdiff_t, 
		typename _Pointer = _Tp*, 
		typename _Reference = _Tp&>
struct iterator
{
    typedef _Category iterator_category;
    typedef _Tp value_type;
    typedef _Distance difference_type;
    typedef _Pointer pointer;
    typedef _Reference reference;
};

ostream_iterator 的 iterator_category

{
    display_category(istream_iterator<int>());
    display_category(ostream_iterator<int>(cout,""));
}

// 标准库/规格书有记载，不同的标准库的版本的做法可以不同，但是不能影响接口
// G2.9
template <class T>
class ostream_iterator {
    public:
    	typedef output_iterator_tag iterator_category;	// 定义自己的分类是 output_iterator_tag
    ...
};

// G3.3
template <class _Tp, class _CharT = char, class _Traits = char_traits<_CharT> >
class ostream_iterator {
    public:
    	typedef output_iterator_tag iterator_category;
    ...
};

// G4.9
template <typename _Tp, typename _CharT = char, typename _Traits = char_traits<_CharT> >
class ostream_iterator : public iterator<output_iterator_tag, void, void, void, void>
{
    ...
};

template <typename _Category, 
		typename _Tp, 
		typename _Distance = ptrdiff_t, 
		typename _Pointer = _Tp*, 
		typename _Reference = _Tp&>
struct iterator
{
    typedef _Category iterator_category;
    typedef _Tp value_type;
    typedef _Distance difference_type;
    typedef _Pointer pointer;
    typedef _Reference reference;
};

迭代器分类（category）对算法的影响

iterator_category 对算法的影响

// 由于继承关系，没有专属设计的版本，会调用继承的版本，如 forward_iterator_tag 和 bidirectional_iterator_tag 会调用此版本
template <class InputIterator>
inline iterator_traits<InputIterator>::difference_type 
    __distance(InputIterator first, InputIterator last, input_iterator_tag) {	
    iterator_traits<InputIterator>::difference_type n = 0;
    while(first != last) {
        ++first;
        ++n;
    }
    return n;
}

template <class RandomAccessIterator>
inline iterator_traits<RandomAccessIterator>::difference_type
    __distance(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag) {
    return last - first;
}

template <class InputIterator>
inline iterator_traits<InputIterator>::difference_type
    distance(InputIterator first, InputIterator last) {	// 两个指针的距离，主函数根据迭代器的分类调用次函数
    typedef typename iterator_traits<InputIterator>::iterator_category category;
    return __distance(first, last, category());	// category() temp. obj
}

template <class InputIterator, class Distance>
inline void __advance(InputIterator& i, Distance n, input_iterator_tag) {
    while(n--) ++i;
}

template <class BidirectionalIterator, class Distance>
inline void __advance(BidirectionalIterator& i, Distance n, bidirectional_iterator_tag) {
    if(n>=0)
        while(n--) ++i;
    else
        while(n++) --i;
}

template <class RandomAccessIterator, class Distance>
inline void __advance(RandomAccessIterator& i, Distance n, random_access_iterator_tag) {
    i += n;
}

template <class InputIterator, class Distance>
inline void advance(InputIterator& i, Distance n) {	// 指针前进 n 步
    __advance(i, n, iterator_category(i));
}

template <class Iterator>
inline typename iterator_traits<Iterator>::iterator_category iterator_category(const Iterator&) {
    typedef typename iterator_traits<Iterator>::iterator_category category;
    return category();	// 此函数协助取出 iterator 的 category 并以此创建一个 temp. object
}

iterator_category 和 tyoe traits 对算法的影响

has trivial op=() 不重要的拷贝赋值/系统自带的/浅拷贝 has non-trivial op=() 重要的拷贝赋值/深拷贝
Type Traits 问拷贝复制重不重要，Type Traits 不属于 STL 一部分，但是属于标准库一部分

	<style>.qjoiikyokhqn{zoom:67%;}</style>{% asset_img qjoiikyokhqn image-20250928235508712.png '"""image-20250928235508712"' %}

template <class InputIterator, class OutputIterator>
inline OutputIterator __unique_copy(InputIterator first, 
                                    InputIterator last, 
                                    OutputIterator result, 
                                    output_iterator_tag) {	// 只复制独一无二的元素
    // output iterator 有其特别局限，所以处理前先探求其 value type
    return __unique_copy(first, last, result, value_type(first));
}

template <class Itr>
inline typename iterator_traits<Itr>::value_type* value_type(const Itr&) {
    return static_cast<typename iterator_traits<Itr>::value_type*>(0);
}

template <class InputIterator, class OutputIterator, class T>
OutputIterator __unique_copy(InputIterator first, InputIterator last, OutputIterator result, T*) {
    T value = *first;
    *result = value;
    while (++first != last)
        if (value != *first) {
            value = *first;
            *++result = value;
        }
    return ++result;
}
// 由于 output iterator（例 ostream_iterator）是 write-only
// 无法像 forward iterator 那般可以 read，所以不能有类似（下面）*result!=*first 的动作，因此需设计出（上面）专属版本
template <class InputIterator, class ForwardIterator>
ForwardIterator __unique_copy(InputIterator first, 
                              InputIterator last, 
                              ForwardIterator result, 
                              forward_iterator_tag) {
    *result = *first;				// 登录第一元素
    while (++first != last)			// 遍历整个区间
        if (*result != *first) {	// *result 是 read-op
            *++result = *first;
        }
    return ++result;
}

算法源码中对 iterator_category 的 “暗示”

template <class InputIterator>	// 没有语法实现强制接受什么迭代器，只能通过把模板参数命名为相应迭代器名称来进行暗示
inline iterator_traits<InputIterator>::difference_type distance(InputIterator first, InputIterator last) {
    ...
}

template <class ForwardIterator>
inline void rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last) {
    ...
}

template <class RandomAccessIterator>
inline void sort(RandomAccessIterator first, RandomAccessIterator last) {
    ...
}

template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value) {
    ...
}

template <class BidirectionalIterator, class OutputIterator>
OutputIterator reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result) {
    ...
}

算法源代码剖析（11个例子）

先前示例中出现的算法

{
    // 这是 C 函数
    qsort(c.data(), ASIZE, sizeof(long), compareLongs);
    
    long* pItem = (long*)bsearch(&target, (c.data()), ASIZE, sizeof(long), compareLongs);
}
{
    // 这是 C++ 标准库提供的 algorithms，以函数的形式呈现
    cout << count_if(vi.begin(), vi.end(), not1(bind2nd(less<int>(),40)));
    
    auto ite = find(c.begin(), c.end(), target);
    
    sort(c.begin(), c.end());
}

// C++标准库的算法必须符合这个格式
template<typename Iterator>
std::Algorithm(Iterator itr1, Iterator itr2, ...)
{
    ...
}

算法 accumulate

template <class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init)
{
    for ( ; first != last; ++first)
        // 将元素累加至初值 init 身上
        init = init + *first;
    return init;
}

template <class InputIterator, class T, class BinaryOperation>
T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binary_op)
{
    for ( ; first != last; ++first)
        // 将元素累计算至初值 init 身上
        init = binary_op(init, *first);
    return init;
}

#include <iostream>		// std::cout
#include <functional>	// std::minus
#include <numeric>		// std::accumulate
namespace star34
{
    int myfunc(int x, int y) {
        return x+2*y; 
    }
    
    struct myclass {
        int operator()(int x, int y) {
            return x+3*y;
        }
    }myobj;
    
    void test_accumulate()
    {
        int init = 100;
        int nums[] = {10, 20, 30};
        
        cout << "using default accumulate: ";
        cout << accumulate(nums, nums+3, init);		// print: 160
        cout << '\n';
        
        cout << "using functional's minus: ";
        cout << accumulate(nums, nums+3, init, minus<int>());	// print: 40
        cout << '\n';
        
        cout << "using custom function: ";
        cout << accumulate(nums, nums+3, init, myfunc);		// print: 220
        cout << '\n';
        
        cout << "using custom object: ";
        cout << accumulate(nums, nums+3, init, myobj);	// print: 280
        cout << '\n';
    }
}

算法 for_each

template <class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f)	// 在一个区间[first, last)内执行 Function
{
    for ( ; first != last; ++first)
        f(*first);
    return f;
}

// range-based for statement（since C++11）
for( decl : coll) {
    statement
}
for( int i : {2, 3, 5, 7, 9, 13, 17, 19} ) {
    cout << i << endl;
}

#include <iostream>		// std::cout
#include <algorithm>	// std::for_each
#include <vector>		// std::vector
namespace star35
{
    void myfunc(int i) {
        cout << ' ' << i;
    }
    
    struct myclass {
        void operator()(int i) {
            cout << ' ' << i;
        }
    }myobj;
    
    void test_for_each()
    {
        vector<int> myvec;
        myvec.push_back(10);
        myvec.push_back(20);
        myvec.push_back(30);
        
        for_each(myvec.begin(), myvec.end(), myfunc);
        cout << endl;	// output: 10 20 30
        
        for_each(myvec.begin(), myvec.end(), myobj);
        cout << endl;	// output: 10 20 30
        
        // since C++11, range-based for- statement
        for (auto& elem : myvec)
            elem += 5;
        
        for (auto elem : myvec)
            cout << ' ' << elem;	// output: 15 25 35
    }
}

算法 replace, replace_if, replace_copy

template <class ForwardIterator, class T>
void replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value) {
    // 范围内所有等同于 old_value 者都以 new_value 取代
    for ( ; first != last; ++first)
        if (*first == old_value)
            *first = new_value;
}

template <class ForwardIterator, class Predicate, class T>
void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value) {
    // 范围内所有满足 pred() 为 true 之元素都以 new_value 取代，参数暗示Predicate 判断式返回真或假
    for ( ; first != last; ++first)
        if (pred(*first))
            *first = new_value;
}

template <class InputIterator, class OutputIterator, class T>
OutputIterator replace_copy(InputIterator first, 
                            InputIterator last, 
                            OutputIterator result, 
                            const T& old_value, 
                            const T& new_value) {
    // 范围内所有等同于 old_value 者都以 new_value 放至新区间，不符合者原值放入新区间
    for ( ; first != last; ++first, ++result)
        *result = *first==old_value ? new_value : *first;
    return result;
}

算法 count, count_if

容器不带成员函数 count()：array, vector, list, forward_list, deque
容器带有成员函数 count()：set/multiset, map/multimap, unordered_set/unordered_multiset, unordered_map/unordered_multimap
容器有自己函数版本时，一定调用自己的，速度更快

template <class InputIterator, class T>
typename iterator_traits<InputIterator>::difference_type
    count(InputIterator first, InputIterator last, const T& value) {
    // 以下定义一个初值为0的计数器 n
    typename iterator_traits<InputIterator>::difference_type n = 0;
    for ( ; first != last; ++first)		// 遍历（循序搜寻）
        if (*first==value)				// 如果元素值和 value 相等
            ++n;						// 计数器累加1
    return n;
}

template <class InputIterator, class Predicate>
typename iterator_traits<InputIterator>::difference_type
    count_if(InputIterator first, InputIterator last, Predicate pred) {
    // 以下定义一个初值为0的计数器 n
    typename iterator_traits<InputIterator>::difference_type n = 0;
    for ( ; first != last; ++first)		// 遍历（循序搜寻）
        if(pred(*first))				// 如果元素带入 pred 的结果为 true
            ++n;						// 计数器累加1
    return n;
}

算法 find, find_if

容器不带成员函数 find()：array, vector, list, forward_list, deque
容器带有成员函数 find()：set/multiset, map/multimap, unordered_set/unordered_multiset, unordered_map/unordered_multimap
容器有自己函数版本时，一定调用自己的，速度更快

template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value)
{
    while(first != last && *first != value)		// 循序式搜寻/查找
        ++first;	
    return first;
}

template <class InputIterator, class Predicate>
InputIterator find_if(InputIterator first, InputIterator last, Predicate pred)	// 参数暗示Predicate 判断式返回真或假
{
    while(first != last && !pred(*first))		// 循序式搜寻/查找
        ++first;	
    return first;
}

算法 sort

容器不带成员函数 sort()：array, vector, deque
set/multiset, map/multimap, unordered_set/unordered_multiset, unordered_map/unordered_multimap 遍历自然形成 sorted 状态
容器带有成员函数 sort()：list, forward_list sort函数要求容器迭代器是随机访问迭代器
容器有自己函数版本时，一定调用自己的，速度更快

bool myfunc(int i,int j) {
    return (i<j); 
}

struct myclass {
    bool operator()(int i,int j) {
        return (i<j);
    }
}myobj;

bool test_sort()
{
    int myints[] = {32, 71, 12, 45, 26, 80, 53, 33};
    vector<int> myvec(myints, myints+8);	// myvec内容：32 71 12 45 26 80 53 33
    
    // using default comparison (operator <):
    sort(myvec.begin(), myvec.begin()+4);	// myvec内容：(12 32 45 71)26 80 53 33
    
    // using function as comp
    sort(myvec.begin()+4, myvec.end(), myfunc);		// myvec内容：12 32 45 71(26 33 53 80)
    
    // using object as comp
    sort(myvec.begin(), myvec.end(), myobj);	// myvec内容：(12 26 32 33 45 53 71 80)
    
    // print out content:
    cout << "myvec contains:";
    for (auto elem : myvec)		// C++11 range-based for statement
        cout << ' ' << elem;	// output: 12 26 32 33 45 53 71 80
    
    // using reverse iterators and default comparison (operator <):
    sort(myvec.rbegin(), myvec.rend());
    
    // print out content:
    cout << "myvec contains:";
    for (auto elem : myvec)		// C++11 range-based for statement
        cout << ' ' << elem;	// output: 80 71 53 45 33 32 26 12
}

关于 reverse iterator, rbegin(), rend()

// reverse_iterator() 是个 iterator adapter
reverse_iterator rbegin() {
    return reverse_iterator(end());
}

reverse_iterator rend() {
    return reverse_iterator(begin());
}

算法 binary_search

Test if value exists in sorted sequence binary_search函数使用前一定要排序

template <class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& val)
{
    first = std::lower_bound(first, last, val);
    return (first!=last && !(val < *first));	// 获得的 iterator 所指的位置既非 end，目标值 val 亦不小于首元素（sorted range 之首元素值最小）
}
// 优化：先判断 !(val < *first) 然后才调用 lower_bound() 将获得较佳效率。因为进入 lower_bound() 后乃由中间元素开始比较，虽说二分搜寻也快，毕竟都不必要了


// Returns an iterator pointing to the first element in the range [first,last) which does not compare less than val
// The elements are compared using operator< for the first version, and comp for the second
// The elements in the range shall already be sorted according to this same criterion(operator< or comp), or at least partitioned with respect to val
template <class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& val)
{
    ForwardIterator it;
    iterator_traits<ForwardIterator>::difference_type count, step;
    count = distance(first, last);
    while(count>0)	// 二分查找
    {
        it = first;
        step = count/2;
        advance(it,step);
        if(*it<val) {	// or: if(comp(*it, val)), for version(2)
            first = ++ it;
            count -= step+1;
        }
        else count=step;
    }
    return first;
}

仿函数和函数对象

仿函数 functors

template <typename Iterator, typename Cmp>	// Cmp 就是仿函数
Algorithm(Iterator itr1, Iterator itr2, Cmp comp)
{
    ...
}

// 算术类（Arithmetic）
template <class T>
struct pluc : public binary_function<T, T, T> {		// : public binary_function<T, T, T> 是融入 STL的条件
    T operator()(const T& x, const T& y) const {
        return x + y;
    }
};

template <class T>
struct minus : public binary_function<T, T, T> {	// : public binary_function<T, T, T> 是融入 STL的条件
    T operator()(const T& x, const T& y) const {
        return x - y;
    }
};
...

// 逻辑运算类（Logical）
template <class T>
struct logical_and : public binary_function<T, T, bool> {	// : public binary_function<T, T, bool> 是融入 STL的条件
    bool operator()(const T& x, const T& y) const {
        return x && y;
    }
};
...

// 相对关系类（Relational）
template <class T>
struct equal_to : public binary_function<T, T, bool> {		// : public binary_function<T, T, bool> 是融入 STL的条件
    bool operator()(const T& x, const T& y) const {
        return x == y;
    }
};

template <class T>
struct less : public binary_function<T, T, bool> {		// : public binary_function<T, T, bool> 是融入 STL的条件
    bool operator()(const T& x, const T& y) const {
        return x < y;
    }
};
...

template <class T1, class T2>
struct pair {
    typedef T1 first_type;
    typedef T2 second_type;
    
    T1 first;
    T2 second;
    pair() : first(T1()), second(T2()) {}
    pair(const T1& a, const T2& b) : first(a), second(b) {}
};

// GNU C++独有，非标准
// G2.9	
template <class T>
struct identity : public unary_function<T, T> {
    const T& operator()(const T& x) const {
        return x;
    }
};

template <class Pair>
struct select1st : public unary_function<Pair, typename Pair::first_type> {
    const typename Pair::first_type& operator()(const Pair& x) const {
        return x.first;
    }
};

template <class Pair>
struct select2nd : public unary_function<Pair, typename Pair::second_type> {
    const typename Pair::second_type& operator()(const Pair& x) const {
        return x.second;
    }
};

// G4.9
template <class T>
struct _Identity;

template <class Pair>
struct _Select1st;

template <class Pair>
struct _Select2nd;

// 没有融入 STL
struct myclass {
    bool  operator()(int i, int j) { return ( i<j ); }
}myobj;

bool myfunc(int i, int j) { return ( i<j ); }

// 融入 STL
// 相对关系类（Relational）
template <class T>
struct greater : public binary_function<T, T, bool> {		// : public binary_function<T, T, bool> 是融入 STL的条件
    bool operator()(const T& x, const T& y) const {
        return x > y;
    }
};

template <class T>
struct less : public binary_function<T, T, bool> {		// : public binary_function<T, T, bool> 是融入 STL的条件
    bool operator()(const T& x, const T& y) const {
        return x < y;
    }
};
...

// using default comparison (operator <):
sort(myvec.begin(), myvec.end());
    
// using function as comp
sort(myvec.begin(), myvec.end(), myfunc);
    
// using object as comp
sort(myvec.begin(), myvec.end(), myobj);

// using explicitly default comparison (operator <):
sort(myvec.begin(), myvec.end(), less<int>());	// less<int>() 函数对象

// using another comparision criteria (operator >):
sort(myvec.begin(), myvec.end(), greater<int>());	// greater<int>() 函数对象

仿函数 functors 的可适配（adaptable）条件

// 单独 sizeof 理论值为0，实际值为1，但是作为父类被继承，大小一定是0
template <class Arg, class Result>
struct unary_function {
    typedef Arg argument_type;
    typedef Result result_type;
};

template <class Arg1, class Arg2, class Result>
struct binary_function {
    typedef Arg1 first_argument_type;
    typedef Arg2 second_argument_type;
    typedef Result result_type;
};

// STL 规定每个 Adaptable Function 都应挑选适当者继承之，因为 Function Adapter 将会提问红色问题，例如：
template <class T>
struct less : public binary_function<T, T, bool> {
    bool operator()(const T& x, const T& y) const {
        return x < y;
    }
};
// 于是 less<int> 便有了三个 typedef，分别是：
typedef int first_argument_type;
typedef int second_argument_type;
typedef bool result_type;

存在多种 Adapter

adapter改造某个东西，A把B改造之后，A就代表了B，A就被使用，不会再用到B，而A做的主要事情是交给B做，A内含B而不是继承

容器适配器

容器适配器：stack

template <class T, class Sequence=deque<T>>
class stack {
    ...
    public:
    	typedef typename Sequence::value_type value_type;
    	typedef typename Sequence::size_type size_type;
    	typedef typename Sequence::reference reference;
    	typedef typename Sequence::const_reference const_reference;
    protected:
    	Sequence c; // 底层容器
    public:
    	bool empty() const { return c.empty(); }
    	size_type size() const { return c.size(); }
    	reference top() { return c.back(); }
    	const_reference top() const { return c.back(); }
    	void push(const value_type& x) { c.push_back(x); }
    	void pop() { c.pop_back(); }
};

容器适配器：queue

template <class T, class Sequence=deque<T>>
class queue {
    ...
    public:
    	typedef typename Sequence::value_type value_type;
    	typedef typename Sequence::size_type size_type;
    	typedef typename Sequence::reference reference;
    	typedef typename Sequence::const_reference const_reference;
    protected:
    	Sequence c;	// 底层容器
    public:
    	bool empty() const { return c.empty(); }
    	size_type size() const { return c.size(); }
    	reference front() { return c.front(); }
    	const_reference front() const { return c.front(); }
    	reference back() { return c.back(); }
    	const_reference back() const { return c.back(); }
    	void push(const value_type& x) { c.push_back(x); }
    	void pop() { c.pop_front(); }
};

函数适配器

函数适配器：binder2nd

// 辅助函数，让 user 得以方便使用 binder2nd<Op>
// 编译器会自带推导 Op 的 type
template <class Operation, class T>
inline binder2nd<Operation> bind2nd(const Operation& op, const T& x) {
    // typename 帮助编译器通过代码，编译器编译到这里还不知道 Operation，Operation 要到传参数进来进行实参推导才知道，正常编译到这里会失败
    typedef typename Operation::second_argument_type arg2_type;	// 问 Operation 第二实参是什么类型
    return binder2nd<Operation>(op, arg2_type(x));	// 看 x 是不是这个类型或者能不能转换为这个类型
}

// 类模板没有类型自动推导，靠函数模板推导后传给类模板
// 以下将某个 Adaptable Binary function 转换为 Unary Function
template <class Operation>	// 如果还要再被 adapter 的话也要回答参数和返回类型，所以要继承 unary_function()
class binder2nd : public unary_function<typename Operation::first_argument_type, typename Operation::result_type> {
    protected:
    	Operation op;	// 内部成员，分别用以记录算式和第二实参
    	typename Operation::second_argument_type value;
    public:
    	// constructor，将算式和第二实参记录下来
    	binder2nd(const Operation& x, const typename Operation::second_argument_type& y) : op(x), value(y) {}
    	typename Operation::result_type operator()(const typename Operation::first_argument_type& x) const {
            return op(x, value);	// 实际呼叫算式并取 value 为第二实参
        }
};

template <class InputIterator, class Predicate>
typename iterator_traits<InputIterator>::difference_type 
    count_if(InputIterator first, InputIterator last, Predicate pred) {
    // 以下定义一个初值为0的计数器
    typename iterator_traits<InputIterator>::difference_type n = 0;
    for ( ; first != last; ++first)	// 遍历
        if(pred(*first))	// 如果元素带入 pred 的结果为 true
            ++n;			// 计数器累加1
    return n;
}

函数适配器：not1

// 辅助函数，使 user 得以方便使用 unary_negate<Pred>
template <class Predicate>
inline unary_negate<Predicate> not1(const Predicate& pred) {
    return unary_negate<Predicate>(pred);
}

// 以下某个 Adaptable Predicate 的逻辑负值（logical negation）
template <class Predicate>
class unary_negate : public unary_function<typename Predicate::argument_type, bool> {
    protected:
    	Predicate pred;	// 内部成员
    public:
    	// constructor
    	explicit unary_negate(const Predicate& x) : pred(x) {}
    	bool operator()(const typename Predicate::argument_type& x) const {
            return !pred(x);	// 将 pred 的运算结果 “取否” (negate)
        }
};

template <class InputIterator, class Predicate>
typename iterator_traits<InputIterator>::difference_type 
    count_if(InputIterator first, InputIterator last, Predicate pred) {
    // 以下定义一个初值为0的计数器
    typename iterator_traits<InputIterator>::difference_type n = 0;
    for ( ; first != last; ++first)	// 遍历
        if(pred(*first))	// 如果元素带入 pred 的结果为 true
            ++n;			// 计数器累加1
    return n;
}

新型适配器，bind Since C++11

// ...\include\c++\backward\backward_warning.h
/*
	A list of valid replacements is as follows:
	
	Use:										Instead of:
	<sstream>, basic_stringbuf						<strstream>, strstreambuf
	<sstream>, basic_istringstream					<strstream>, istrstream
	<sstream>, basic_ostringstream					<strstream>, ostrstream
	<sstream>, basic_stringstream					<strstream>, strstream
	<unordered_set>, unordered_set					<ext/hash_set>, hash_set
	<unordered_set>, unordered_multiset				<ext/hash_set>, hash_multiset
	<unordered_map>, unordered_map					<ext/hash_map>, hash_map
	<unordered_map>, unordered_multimap				<ext/hash_map>, hash_multimap
	<functional>, bind								<functional>, binder1st
	<functional>, bind								<functional>, binder2nd
	<functional>, bind								<functional>, bind1st
	<functional>, bind								<functional>, bind2nd
	<memory>, unique_ptr							<memory>, auto_ptr
*/

std::bind 可以绑定：

1. functions
2. function objects
3. member functions，_1 必须是某个 object 地址 _1 是一个占位符号，代表符号
4. data members，_1 必须是某个 object 地址

返回一个 function object ret
调用 ret 相当于调用上述 1, 2, 3，或相当于取出 4

// http://www.cplusplus.com/reference/functional/bind/?kw=bind	案例
#include <functional>	// std::bind

// a function: (also works with function object: std::divides<double> my_divide;)
double my_divide(double x, double y) {
    return x / y;
}

struct MyPair {
    double a,b;
    double multiply() {	// member function 其实有个 argument: this
        return a * b;	
    }
};

using namespace std::placeholders;	// adds visibility of _1, _2, _3, ...

// binding functions:
auto fn_five = bind(my_divide, 10, 2);				// returns 10/2
cout << fn_five() << '\n';							// print: 5

auto fn_half = bind(my_divide, _1, 2);				// returns x/2		绑定第二个参数，第一个参数留着
cout << fn_half(10) << '\n';						// print: 5			实际调用的第一个参数就会用到 _1 这个位置

auto fn_invert = bind(my_divide, _2, _1);			// returns y/x		第一参数用 _1	第二参数用 _2
cout << fn_invert(10, 2) << '\n';					// print: 0.2

auto fn_rounding = bind<int>(my_divide, _1, _2);	// returns int(x/y)		只能指定一个模板参数，绑定返回类型
cout << fn_rounding(10, 3) << '\n';					// print: 3


// binding members:
MyPair ten_two{10, 2};							
								// member function 其实有个argument: this
auto bound_memfn = bind(&MyPair::multiply, _1);		// returns x.multiply()
cout << bound_memfn(ten_two) << '\n';				// print: 20

auto bound_memdata = bind(&MyPair::a, ten_two);		// returns ten_two.a
cout << bound_memdata() << '\n';					// print: 10

auto bound_memdata2 = bind(&MyPair::b, _1);			// returns x.b
cout << bound_memdata2(ten_two) << '\n';			// print: 2


vector<int> v{15, 37, 94, 50, 73, 58, 28, 98};
int n = count_if(v.begin(), v.end(), not1(bind2nd(less<int>(), 50)));
cout << "n= " << n << endl;		// print: 5

auto fn_ = bind(less<int>(), _1, 50);
cout << count_if(v.cbegin(), v.cend(), fn_) << endl;						// print: 3
cout << count_if(v.begin(), v.end(), bind(less<int>(), _1, 50)) << endl;	// print: 3

迭代器适配器

迭代器适配器：reverse_iterator

reverse_iterator rbegin() {		// 没指定参数类型，也有可能是同名函数模板，或者换名
    return reverse_iterator(end());
}

reverse_iterator rend() {
    return reverse_iterator(begin());
}

template <class Iterator>
class reverse_iterator
{
    protected:
    	Iterator current;	// 对应之正向迭代器
    public:
    	// 逆向迭代器的五种 associated types 都和其对应之正向迭代器相同
    	typedef typename iterator_traits<Iterator>::iterator_category iterator_category;
    	typedef typename iterator_traits<Iterator>::value_type	value_type;
    	...
        typedef Iterator iterator_type;				// 代表正向迭代器
        typedef reverse_iterator<Iterator> self;	// 代表逆向迭代器
    
    public:
    	explicit reverse_iterator(iterator_type x) : current(x) {}
    	reverse_iterator(const self& x) : current(x.current) {}
    
    	iterator_type base() const { return current; }	// 取出对应的正向迭代器
    	reference operator*() const { Iterator tmp = current;	return *--tmp; }
    	// 以上为关键所在
    	// 对逆向迭代器取值就是将对应之正向迭代器退一位取值
    	pointer operator->() const { return &(operator*()); } // 意义同上
    
    	// 前进变成后退，后退变成前进
    	self& operator++() { --current;		return *this; }
    	self& operator--() { ++current;		return *this; }
    	self& operator+(difference_type n) const { return self(current - n); }
    	self& operator-(difference_type n) const { return self(current + n); }
};

迭代器适配器：inserter

template <class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last, OurputIterator result)
{
    while(first != last) {
        *result = *first;
        ++result;
        ++first;
    }
    return result;
}

int myints[]={10, 20, 30, 40, 50, 60, 70};
vector<int> myvec(7);

copy(myints, myints+7, myvec.begin());

list<int> foo, bar;
for(int i=1; i<=5; i++)
{
    foo.push_back(i);
    bar.push_back(i*10);
}

list<int>::iterator it = foo.begin();
advance(it, 3);

copy(bar.begin(), bar.end(), inserter(foo, it));		// inserter 申请一个空间来放复制的元素

// 辅助函数，帮助 user 使用 insert_iterator
template <class Container, class Iterator>
inline insert_iterator<Container> inserter(Container& x, Iterator i) {
    typedef typename Container::iterator iter;
    return insert_iterator<Container>(x, iter(i));
}

// 这个 adapter 将 iterator 的赋值（assign）操作改变为安插（insert）操作，并将 iterator 右移一个位置
// 如此便可让 user 连续执行表面上 assign 而实际上 insert 的行为
template <class Container>
class insert_iterator {
    protected:
    	Container* container;	// 底层容器
    	typename Container::iterator iter;
    public:
    	typedef output_iterator_tag iterator_category;	// 注意类型
    	
    	insert_iterator(Container& x, typename Container::iterator i) : container(&x), iter(i) {}
    
    	insert_iterator<Container>& operator=(const typename Container::value_type& value) {
            iter = container->insert(iter, value);	// 关键：转调用 insert()
            ++iter;		// 令 insert iterator 永远随其 target 贴身移动
            return *this;
        }
};

X（未知）适配器

X（未知）适配器：ostream_iterator

// ostream_iterator example
#include <iostream>		// std::cout
#include <iterator>		// std::ostream_iterator
#include <vector>		// std::vector
#include <algorithm>	// std::copy

int main(){
    std::vector<int> myvector;
    for(int i=1; i<10; ++i) myvector.push_back(i*10);
    
    std::ostream_iterator<int> out_it(std::cout, ",");	// 第二个参数为字符串，作为分隔符
    std::copy(myvector.begin(), myvector.end(), out_it);
    return 0;
}

template <class InputIterator, class OutputIterator> 
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result)
{
    while(first != last) {
        *result = *first;	// = 重载，这就相当于 cout << *first;	cout << ", ";
        ++result;
        ++first;
    }
    return result;
}

template <class T, class charT=char, class traits=char_traits<charT> >
class ostream_iterator : public iterator<output_iterator_tag, void, void, void, void>
{
    basic_ostream<charT, traits>* out_stream;
    const charT* delim;
    
    public:
    	typedef charT char_type;
    	typedef traits traits_type;
    	typedef basic_ostream<charT, traits> ostream_type;
    	ostream_iterator(ostream_type& s) : out_stream(&s), delim(0) {}
    	ostream_iterator(ostream_type& s, const charT* delimiter) : out_stream(&s), delim(delimiter) { }
    	ostream_iterator(const ostream_iterator<T, charT, traits>& x) : out_stream(x.out_stream), delim(x.delim) {}
    	~ostream_iterator() {}
    	ostream_iterator<T, charT, traits>& operator=(const T& value) {
            *out_stream << value;
            if(delim!=0) *out_stream << delim;
            return *this;
        }
    
    ostream_iterator<T, charT, traits>& operator*() { return *this; }
    ostream_iterator<T, charT, traits>& operator++() { return *this; }
    ostream_iterator<T, charT, traits>& operator++(int) { return *this; }
};

X（未知）适配器：istream_iterator

template <class T, class charT=char, class traits=char_traits<charT>, class Distance=ptrdiff_t>
class istream_iterator : public iterator<input_iterator_tag, T, Distance, const T*, const T&>
{
    basic_istream<charT, traits>* in_stream;
    T value;
    public:
    	typedef charT char_type;
    	typedef traits traits_type;
    	typedef basic_istream<charT, traits> istream_type;
    	istream_iterator() : in_stream(0) {}
    	istream_iterator(istream_type& s) : in_stream(&s) { ++*this; }	// 一旦创建立刻 read，可能令 user 吃惊
    	istream_iterator(const istream_iterator<T, charT, traits, Distance>& x) 
            : in_stream(x.in_stream), value(x.value) {}
    	~istream_iterator() {}
    	const T& operator*() const { return value; }
    	const T* operator->() const { return &value; }
    	istream_iterator<T, charT, traits, Distance>& operator++() {
            if(in_stream && !(*in_stream >> value)) in_stream=0;
            return *this;
        }
    	istream_iterator<T, charT, traits, Distance> operator++(int) {
            istream_iterator<T, charT, traits, Distance> tmp = *this;
            ++*this;
            return tmp;
        }
};

// 例1
// istream_iterator example
#include <iostream>		// std::cin, std::cout
#include <iterator>		// std::istream_iterator

int main() {
    double value1, value2;
    std::cout << "Please, insert two values: ";
    std::istream_iterator<double> eos;		// 没有参数就代表 end-of-stream iterator
    std::istream_iterator<double> iit(std::cin);	// stdin iterator，这就相当于 cin >> value;
    if(iit!=eos) value1=*iit;	// 这就相当于 return value;
    
    ++iit;
    if(iit!=eos) value2=*iit;
    
    std::cout << value1 << "*" << value2 << "=" << (value1*value2) << '\n';
    return 0;
}

template <class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result)
{
    while(first != last) {
        *result = *first;
        ++result;
        ++first;
    }
    return result;
}
// 例2
{
    istream_iterator<int> iit(cin), eos;		// 当创建第一个对象，就已经在读第一个数据
    // 如果在两行之间加入提示语句，如：请输入数据，那么这句话永远不会出现，因为在等待输入第一个数据
    
    copy(iit, eos, inserter(c, c.begin()));
}

阅读 C++ 标准库源代码——意义与价值

使用一个东西，却不明白它的道理，不高明！

一个万用的 hash function

// 型式1
#include <functional>
class Customer {
    ...
};

class CustomerHash
{
    public:
    	std::size_t operator()(const Customer& c) const {
            return ...		// 该怎么做？
        }
};

unordered_set<Customer, CustomerHash> custset;

// 型式2
size_t customer_hash_func(const Customer& c) {
    return ...		// 该怎么做？
};

unordered_set<Customer, size_t(*)(const Customer&)>	custset(20, customer_hash_func);	// 第二个模板参数是函数类型

// a naive approach: simply add all hash values for those attributes that are relevant for the hash function
class CustomerHash {
    public:
    	std::size_t operator()(const Customer& c) const {
            // 简单将所有类型的 hash code 相加太过天真
            return std::hash<std::string>()(c.fname) + std::hash<std::string>()(c.lname) + std::hash<long>()(c.no);
        }
};

using variadic templates allows calling hash_val() with an arbitrary number of elements of any type to process a hash value out of all these values

// TR1 版本
#include <functional>
// from boost (functional/hash):
template <typename T>
inline void hash_combine(size_t& seed, const T& val) {		// seed 传递的是 reference
    seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed<<6) + (seed>>2);	// 0x9e3779b9 黄金比例
}

// auxiliary generic functions to create a hash value using a seed
template <typename T>
inline void hash_val(size_t& seed, const T& val) {		// seed 传递的是 reference
    hash_combine(seed, val);	// last
}

template <typename T, typename... Types>
inline void hash_val(size_t& seed, const T& val, const Types&... args) {	// seed 传递的是 reference
    hash_combine(seed, val);
    hash_val(seed, args...);	// recursive
    // 逐一取 val	改变 seed（pass by reference）
}

// auxiliary generic functions
template <typename... Types>
inline size_t hash_val(const Types&... args) {
    size_t seed = 0;
    hash_val(seed, args...);		// seed 传递的是 reference
    return seed;
}

class CustomerHash {
    public:
    	std::size_t operator()(const Customer& c) const {
            return hash_val(c.fname, c.lname, c.no);	// 第一个参数不符合 size_t，先调用第三个 hash_val()
        }
};

{
    // G4.9
    unordered_set<Customer, CustomerHash> set3;
    set3.insert( Customer("Ace",	"Hou",	1L) );
    set3.insert( Customer("Sabri",	"Hou",	2L) );
    set3.insert( Customer("Stacy",	"Chen",	3L) );
    set3.insert( Customer("Mike",	"Tseng", 4L) );
    set3.insert( Customer("Paili",	"Chen",	5L) );
    set3.insert( Customer("Light",	"Shiau", 6L) );
    set3.insert( Customer("Shally", "Hwung", 7L) );
    cout << "set3 current bucket_count: " << set3.bucket_count() << endl;	// print: 11
    
    CustomerHash hh;
    cout << "bucket position of Ace = "		<< hh(Customer("Ace",	"Hou",	1L)) % 11 << endl;	// print: 2
    cout << "bucket position of Sabri = "	<< hh(Customer("Sabri",	"Hou",	2L)) % 11 << endl;	// print: 4
    cout << "bucket position of Stacy = "	<< hh(Customer("Stacy", "Chen",	3L)) % 11 << endl;	// print: 10
    cout << "bucket position of Mike = "	<< hh(Customer("Mike", "Tseng", 4L)) % 11 << endl;	// print: 2
    cout << "bucket position of Paili = "	<< hh(Customer("Paili",	"Chen", 5L)) % 11 << endl;	// print: 9
    cout << "bucket position of Light = "	<< hh(Customer("Light",	"Shiau", 6L)) % 11 << endl;	// print: 6
    cout << "bucket position of Shally = "	<< hh(Customer("Shally", "Hwung", 7L)) % 11 << endl; // print: 2
    
    for(unsigned i=0; i<set3.bucket_count(); ++i) {
        cout << "bucket #" << i << " has " << set3.bucket_size(i) << " elements.\n";
    }
    // print:
    // bucket #0 has 0 elements.
    // bucket #1 has 0 elements.
    // bucket #2 has 3 elements.
    // bucket #3 has 0 elements.
    // bucket #4 has 1 elements.
    // bucket #5 has 0 elements.
    // bucket #6 has 1 elements.
    // bucket #7 has 0 elements.
    // bucket #8 has 0 elements.
    // bucket #9 has 1 elements.
    // bucket #10 has 1 elements.
}

以 struct hash 偏特化形式 实现 Hash Function

// G4.9
template <typename T, typename Hash = hash<T>, typename EqPred = equal_to<T>, typename Allocator = allocator<T> >
class unordered_set;

template <typename T, typename Hash = hash<T>, typename EqPred = equal_to<T>, typename Allocator = allocator<T> >
class unordered_multiset;

template <typename Key, typename T, 
		typename Hash = hash<T>, 
		typename EqPred = equal_to<T>, 
		typename Allocator = allocator<pair<const Key, T> > >
class unordered_map;

template <typename Key, typename T, 
		typename Hash = hash<T>, 
		typename EqPred = equal_to<T>, 
		typename Allocator = allocator<pair<const Key, T> > >
class unordered_multimap;

class MyString {
    private:
    	char* _data;
    	size_t _len;
    ...
};

namespace std	// 必须放在 std 内
{
    template<>
    struct hash<MyString>	// 为了 unordered containers
    {
        size_t operator()(const MyString& s) const noexcept
        {
            return hash<string>()(string(s.get()));		// 借用 hash<string>
        }
    };
}

// ...\4.9.2\include\c++\bits\basic_string.h
/// std::hash specialization for string
template<>
struct hash<string> : public __hash_base<size_t, string>
{
    size_t operator()(const string& __s) const noexcept
    {
        return std::_Hash_impl::hash(__s.data(), __s.length());
    }
};

Tuple

tuple, 用例

cout << "string, sizeof= " << sizeof(string) << endl;				// print: 4
cout << "double, sizeof= " << sizeof(double) << endl;				// print: 8
cout << "float, sizeof= " << sizeof(float) << endl;					// print: 4
cout << "int, sizeof= " << sizeof(int) << endl;						// print: 4
cout << "complex<double>, sizeof=" << sizeof(complex<double>) << endl;	// print: 16

// tuples
// create a four-element tuple
// -elements are initialized with default value (0 for fundamental types)
tuple<string, int, int, complex<double>> t;
cout << "sizeof= " << sizeof(t) << endl;			// print: 32, why not 28?	原因未知

// create and initialize a tuple explicitly
tuple<int, float, string> t1(41, 6.3, "nico");
cout << "tuple<int, float, string>, sizeof= " << sizeof(t1) << endl;		// print: 12
// iterate over elements:
cout << "t1: " << get<0>(t1) << ' ' << get<1>(t1) << ' ' << get<2>(t1) << endl;	// get<0>(t1) 拿出 t1 第0个元素 

// create tuple with make_tuple()
auto t2 = make_tuple(22, 44, "stacy");	// 做一个 tuple，类型编译器进行实参推导

// assign second value in t2 to t1
get<1>(t1) = get<1>(t2);

// comparison and assignment
// - including type conversion from tuple<int, int, const char*> to tuple<int, float, string>
if(t1 < t2) {	// compares value for value
    cout << "t1 < t2" << endl;
} else {
    cout << "t1 >= t2" << endl;
}
t1 = t2;	// OK, assigns value for value
cout << "t1: " << t1 << endl;	// 需要为 tuple 设计操作符 << 重载

tuple<int, float, string> t3(77, 1.1, "more light");
int i1;
float f1;
string s1;
tie(i1, f1, s1) = t3;	// assigns values of t to i, f, and s	把 t3 的三个元素依次赋值给 i1 f1 s1

typedef tuple<int, float, string> TupleType;
cout << tuple_size<TupleType>::value << endl;		// yields 3		问 tuple 有几个成分
tuple_element<1, TupleType>::type f1;
typedef tuple_element<1, TupleType>::type T;

tuple 元之组合，数之组合

详细介绍见 C++2.0新特性C++2.0新特性 | tiny_star_blog

// G4.8 节录并简化
template <typename... Values> class tuple;

template<> class tuple<> {};

template<typename Head, typename... Tail>
class tuple<Head, Tail...> : private tuple<Tail...>
{
    typedef tuple<Tail...> inherited;
    public:
    	tuple() {}											// 注意这是 initialization list
    	tuple(Head v, Tail... vtail) : m_head(v), inherited(vtail...) {}	// 呼叫 base ctor 并予参数（不是创建 temp object）
    	
    	typename Head::type head() { return m_head; }
    	inherited& tail() { return *this; }	// return 后转型为 inherited，获得的是 tuple<float, string>
    protected:
    	Head m_head;
};

{
    tuple<int, float, string> t(41, 6.3, "nico");
    t.head();	// 获得 41
    t.tail();	// 获得 tuple<float, string>
    t.tail().head();	// 获得 6.3
    &(t.tail());	// 获得 tuple<float, string> 地址
}

type traits

// G2.9
struct __true_type { };
struct __false_type { };
// 泛化
template <class type>
struct __type_traits {
    typedef __true_type		this_dummy_member_must_be_first;
    typedef __false_type	has_trivial_default_constructor;
    typedef __false_type	has_trivial_copy_constructor;
    typedef __false_type	has_trivial_assignment_operator;
    typedef __false_type	has_trivial_destructor;
    typedef __false_type	is_POD_type;	// Plain Old Data	指 C 里面的 struct，里面没有 function，只有 data
};
// 特化
template<> struct __type_traits<int> {
    typedef __true_type		has_trivial_default_constructor;
    typedef __true_type		has_trivial_copy_constructor;
    typedef __true_type		has_trivial_assignment_operator;
    typedef __true_type		has_trivial_destructor;
    typedef __true_type		is_POD_type;
};
template<> struct __type_traits<double> {
    typedef __true_type		has_trivial_default_constructor;
    typedef __true_type		has_trivial_copy_constructor;
    typedef __true_type		has_trivial_assignment_operator;
    typedef __true_type		has_trivial_destructor;
    typedef __true_type		is_POD_type;
};

__type_traits<Foo>::has_trivial_destructor	// 算法提问 destructor 重不重要，算法来决定最有效的运算过程
// 自建类型需要写特化版本

Since C++11

cplusplus.com/reference/type_traits/?kw=type_traits
自建类型不需要写特化版本

Primary type categories
is_array	Is array (class template)
is_class	Is non-union class (class template)
is_enum	Is enum (class template)
is_floating_point	Is floating point (class template)
is_function	Is function (class template)
is_integral	Is integral (class template)
is_lvalue_reference	Is lvalue reference (class template)
is_member_function_pointer	Is member function pointer (class template)
is_member_object_pointer	Is member object pointer (class template)
is_pointer	Is pointer (class template)
is_rvalue_reference	Is rvalue reference (class template)
is_union	Is union (class template)
is_void	Is void (class template)

Composite type categories
is_arithmetic	Is arithmetic type (class template)
is_compound	Is compound type (class template)
is_fundamental	Is fundamental type (class template)
is_member_pointer	Is member pointer type (class template)
is_object	Is object type (class template)
is_reference	Is reference type (class template)
is_scalar	Is scalar type (class template)

Type properties
is_abstract	Is abstract class (class template)
is_const	Is const-qualified (class template)
is_empty	Is empty class (class template)
is_literal_type	Is literal type (class template)
is_pod	Is POD type (class template)
is_polymorphic	Is polymorphic (class template)
is_signed	Is signed type (class template)
is_standard_layout	Is standard-layout type (class template)
is_trivial	Is trivial type (class template)
is_trivially_copyable	Is trivially copyable (class template)
is_unsigned	Is unsigned type (class template)
is_volatile	Is volatile-qualified (class template)

Type features
has_virtual_destructor	Has virtual destructor (class template)
is_assignable	Is assignable (class template)
is_constructible	Is constructible (class template)
is_copy_assignable	Is copy assignable (class template)
is_copy_constructible	Is copy constructible (class template)
is_destructible	Is destructible (class template)
is_default_constructible	Is default constructible (class template)
is_move_assignable	Is move assignable (class template)
is_move_constructible	Is move constructible (class template)
is_trivially_assignable	Is trivially assignable (class template)
is_trivially_constructible	Is trivially constructible (class template)
is_trivially_copy_assignable	Is trivially copy assignable (class template)
is_trivially_copy_constructible	Is trivially copy constructible (class template)
is_trivially_destructible	Is trivially destructible (class template)
is_trivially_default_constructible	Is trivially default constructible (class template)
is_trivially_move_assignable	Is trivially move assignable (class template)
is_trivially_move_constructible	Is trivially move constructible (class template)
is_nothrow_assignable	Is assignable throwing no exceptions (class template)
is_nothrow_constructible	Is constructible throwing no exceptions (class template)
is_nothrow_copy_assignable	Is copy assignable throwing no exceptions (class template)
is_nothrow_copy_constructible	Is copy constructible throwing no exceptions (class template)
is_nothrow_destructible	Is nothrow destructible (class template)
is_nothrow_default_constructible	Is default constructible throwing no exceptions (class template)
is_nothrow_move_assignable	Is move assignable throwing no exception (class template)
is_nothrow_move_constructible	Is move constructible throwing no exceptions (class template)

trivial 琐碎的，平凡的，平淡无奇的，无关痛痒的，无价值的，不重要的

type traits，测试

// global function template
template <typename T>
void type_traits_output(const T& x)
{
    cout << "\ntype traits for type : " << typeid(T).name() << endl;
    
    cout << "is_void\t" << is_void<T>::value << endl;
    cout << "is_integral\t" << is_integral<T>::value << endl;
    cout << "is_floating_point\t" << is_floating_point<T>::value << endl;
    cout << "is_arithmetic\t" << is_arithmetic<T>::value << endl;
    cout << "is_signed\t" << is_signed<T>::value << endl;
    cout << "is_unsigned\t" << is_unsigned<T>::value << endl;
    cout << "is_const\t" << is_const<T>::value << endl;
    cout << "is_volatile\t" << is_volatile<T>::value << endl;
    cout << "is_class\t" << is_class<T>::value << endl;
    cout << "is_function\t" << is_function<T>::value << endl;
    cout << "is_reference\t" << is_reference<T>::value << endl;
    cout << "is_lvalue_reference\t" << is_lvalue_reference<T>::value << endl;
    cout << "is_rvalue_reference\t" << is_rvalue_reference<T>::value << endl;
    cout << "is_pointer\t" << is_pointer<T>::value << endl;
    cout << "is_member_pointer\t" << is_member_pointer<T>::value << endl;
    cout << "is_member_object_pointer\t" << is_member_object_pointer::value << endl;
    cout << "is_member_function_pointer\t" << is_member_function_pointer::value << endl;
    cout << "is_fundamental\t" << is_fundamental<T>::value << endl;
    cout << "is_scalar\t" << is_scalar<T>::value << endl;
    cout << "is_object\t" << is_object<T>::value << endl;
    cout << "is_compound\t" << is_compound<T>::value << endl;
    ...
}

/// A string of @c char
typedef basic_string<char>	string;

/// A string of @c wchar_t
typedef basic_string<wchar_t> wstring;

/// A string of @c char16_t
typedef basic_string<char16_t> u16string;

/// A string of @c char32_t
typedef basic_string<char32_t> u32string;

// 21.3		Template class basic_string
template <typename _CharT, typename _Traits, typename _Alloc>
class basic_string
{
    ...
    basic_string(const basic_string& __str);
    
    basic_string(basic_string&& __str)
#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
    noexcept // FIXME C++11: should always be noexcept
#endif
    : _M_dataplus(__str._M_dataplus)
    { ... }
    
    ~basic_string() _GLIBCXX_NOEXCEPT		// string 内有指针，所以要写析构函数，因为不会被当为父类，所以没有虚析构函数
    { _M_rep()->_M_dispose(this->get_allocator()); }
    
    basic_string& operator=(const basic_string& __str)
    { return this->assign(__str); }
    
    operator=(basic_string&& __str)
    {
        // NB: DR 1204
        this->swap(__str);
        return *this;
    }
    ...
};

// print:
// type traits for type : Ss
// is_void	0
// is_integral		0
// is_floating_point	0
// is_arithmetic	0
// is_signed		0
// is_unsigned		0
// is_const			0
// is_volatile		0
// is_class			1
// is_function		0
// is_reference		0
// is_lvalue_reference	0
// is_rvalue_reference	0
// is_pointer		0
// is_member_pointer	0
// is_member_object_pointer		0
// is_member_function_pointer	0
// is_fundamental	0
// is_scalar		0
// is_object		1
// is_compound		1
// is_standard_layout	1
// is_pod	0
// is_literal_type	0
// is_empty			0
// is_polymorphic	0
// is_abstract		0
// has_virtual_destructor	0
// is_default_constructible	1
// is_copy_constructible	1
// is_move_constructible	1
// is_copy_assignable		1
// is_move_assignable		1
// is_destructible	1
// is_trivial		0
// __has_trivial_assign		0
// __has_trivial_copy		0
// __has_trivial_constructor	0
// __has_trivial_destructor		0
// is_trivially_destructible	0
// is_nothrow_default_constructible	0
// is_nothrow_copy_constructible	0
// is_nothrow_move_constructible	0
// is_nothrow_copy_assignable		0
// is_nothrow_move_assignable		0
// is_nothrow_destructible	1

class Foo
{
    private:
    	int d1, d2;
};

type_traits_output(Foo());

// print:
// type traits for type : N4jj243FooE
// is_void	0
// is_integral		0
// is_floating_point	0
// is_arithmetic	0
// is_signed		0
// is_unsigned		0
// is_const			0
// is_volatile		0
// is_class			1
// is_function		0
// is_reference		0
// is_lvalue_reference	0
// is_rvalue_reference	0
// is_pointer		0
// is_member_pointer	0
// is_member_object_pointer		0
// is_member_function_pointer	0
// is_fundamental	0
// is_scalar		0
// is_object		1
// is_compound		1
// is_standard_layout	1
// is_pod	1
// is_literal_type	1
// is_empty			0
// is_polymorphic	0
// is_abstract		0
// has_virtual_destructor	0
// is_default_constructible	1
// is_copy_constructible	1
// is_move_constructible	1
// is_copy_assignable		1
// is_move_assignable		1
// is_destructible	1
// is_trivial		1
// __has_trivial_assign		1
// __has_trivial_copy		1
// __has_trivial_constructor	1
// __has_trivial_destructor		1
// is_trivially_destructible	1
// is_nothrow_default_constructible	1
// is_nothrow_copy_constructible	1
// is_nothrow_move_constructible	1
// is_nothrow_copy_assignable		1
// is_nothrow_move_assignable		1
// is_nothrow_destructible	1

class Goo
{
    public:
    	virtual ~Goo() { }
    private:
    	int d1, d2;
};

type_traits_output(Goo());

// print:
// type traits for type : N4jj253GooE
// is_void	0
// is_integral		0
// is_floating_point	0
// is_arithmetic	0
// is_signed		0
// is_unsigned		0
// is_const			0
// is_volatile		0
// is_class			1
// is_function		0
// is_reference		0
// is_lvalue_reference	0
// is_rvalue_reference	0
// is_pointer		0
// is_member_pointer	0
// is_member_object_pointer		0
// is_member_function_pointer	0
// is_fundamental	0
// is_scalar		0
// is_object		1
// is_compound		1
// is_standard_layout	0
// is_pod	0
// is_literal_type	0
// is_empty			0
// is_polymorphic	1		// A polymorphic class is a class that declares or inherits a virtual function 
// is_abstract		0
// has_virtual_destructor	1
// is_default_constructible	1
// is_copy_constructible	1
// is_move_constructible	1
// is_copy_assignable		1
// is_move_assignable		1
// is_destructible	1
// is_trivial		0
// __has_trivial_assign		0
// __has_trivial_copy		0
// __has_trivial_constructor	0
// __has_trivial_destructor		0
// is_trivially_destructible	0
// is_nothrow_default_constructible	1
// is_nothrow_copy_constructible	1
// is_nothrow_move_constructible	1
// is_nothrow_copy_assignable		1
// is_nothrow_move_assignable		1
// is_nothrow_destructible	1

class Zoo
{
    public:
    	Zoo(int i1, int i2) : d1(i1), d2(i2) { }	// 写了构造函数，编译器就不会再给默认构造函数
    	Zoo(const Zoo&) = delete;	// delete 不要
    	Zoo(Zoo&&) = default;		// default 默认
    	Zoo& operator=(const Zoo&) = default;
    	Zoo& operator=(const Zoo&&) = delete;
    	virtual ~Zoo() { }
    private:
    	int d1, d2;
};

type_traits_output(Zoo(1, 2));

// print:
// type traits for type : N4jj263ZooE
// is_void	0
// is_integral		0
// is_floating_point	0
// is_arithmetic	0
// is_signed		0
// is_unsigned		0
// is_const			0
// is_volatile		0
// is_class			1
// is_function		0
// is_reference		0
// is_lvalue_reference	0
// is_rvalue_reference	0
// is_pointer		0
// is_member_pointer	0
// is_member_object_pointer		0
// is_member_function_pointer	0
// is_fundamental	0
// is_scalar		0
// is_object		1
// is_compound		1
// is_standard_layout	0
// is_pod	0
// is_literal_type	0
// is_empty			0
// is_polymorphic	1
// is_abstract		0
// has_virtual_destructor	1
// is_default_constructible	0
// is_copy_constructible	0
// is_move_constructible	1
// is_copy_assignable		1
// is_move_assignable		0
// is_destructible	1
// is_trivial		0
// __has_trivial_assign		0
// __has_trivial_copy		0
// __has_trivial_constructor	0
// __has_trivial_destructor		0
// is_trivially_destructible	0
// is_nothrow_default_constructible	0
// is_nothrow_copy_constructible	0
// is_nothrow_move_constructible	1
// is_nothrow_copy_assignable		1
// is_nothrow_move_assignable		0
// is_nothrow_destructible	1

type_traits_output(complex<float>());

// print:
// type traits for type : St7complexIfE
// is_void	0
// is_integral		0
// is_floating_point	0
// is_arithmetic	0
// is_signed		0
// is_unsigned		0
// is_const			0
// is_volatile		0
// is_class			1
// is_function		0
// is_reference		0
// is_lvalue_reference	0
// is_rvalue_reference	0
// is_pointer		0
// is_member_pointer	0
// is_member_object_pointer		0
// is_member_function_pointer	0
// is_fundamental	0
// is_scalar		0
// is_object		1
// is_compound		1
// is_standard_layout	1
// is_pod	0
// is_literal_type	1
// is_empty			0
// is_polymorphic	0
// is_abstract		0
// has_virtual_destructor	0
// is_default_constructible	1
// is_copy_constructible	1
// is_move_constructible	1
// is_copy_assignable		1
// is_move_assignable		1
// is_destructible	1
// is_trivial		0
// __has_trivial_assign		1
// __has_trivial_copy		1
// __has_trivial_constructor	0
// __has_trivial_destructor		1
// is_trivially_destructible	1
// is_nothrow_default_constructible	1
// is_nothrow_copy_constructible	1
// is_nothrow_move_constructible	1
// is_nothrow_copy_assignable		1
// is_nothrow_move_assignable		1
// is_nothrow_destructible	1

type_traits_output<list<int>());

// print:
// type traits for type : St4listIiSaIiEE
// is_void	0
// is_integral		0
// is_floating_point	0
// is_arithmetic	0
// is_signed		0
// is_unsigned		0
// is_const			0
// is_volatile		0
// is_class			1
// is_function		0
// is_reference		0
// is_lvalue_reference	0
// is_rvalue_reference	0
// is_pointer		0
// is_member_pointer	0
// is_member_object_pointer		0
// is_member_function_pointer	0
// is_fundamental	0
// is_scalar		0
// is_object		1
// is_compound		1
// is_standard_layout	1
// is_pod	0
// is_literal_type	0
// is_empty			0
// is_polymorphic	0
// is_abstract		0
// has_virtual_destructor	0
// is_default_constructible	1
// is_copy_constructible	1
// is_move_constructible	1
// is_copy_assignable		1
// is_move_assignable		1
// is_destructible	1
// is_trivial		0
// __has_trivial_assign		0
// __has_trivial_copy		0
// __has_trivial_constructor	0
// __has_trivial_destructor		0
// is_trivially_destructible	0
// is_nothrow_default_constructible	1
// is_nothrow_copy_constructible	0
// is_nothrow_move_constructible	1
// is_nothrow_copy_assignable		0
// is_nothrow_move_assignable		0
// is_nothrow_destructible	1

type traits, 实现, is_void

/// remove_const		移除 const 关键字
template<typename _Tp>
struct remove_const
{
    typedef _Tp		type;
};

template<typename _Tp>
struct remove_const<_Tp const>	// const 关键字放在类型前面和后面，意义一样
{
    typedef _TP		type;
};

/// remove_volatile		移除 volatile 关键字，volatile 多线程时用到
template<typename _Tp>
struct remove_volatile
{
    typedef _Tp		type;
};

template<typename _Tp>
struct remove_volatile<_Tp volatile>
{
    typedef _Tp		type;
};

/// remove_cv
template<typename _Tp>
struct remove_cv
{
    typedef typename remove_const<typename remove_volatile<_Tp>::type>::type	type;
};

/// add_const
template<typename _Tp>
struct add_const
{
    typedef _Tp const	type;
};

template<typename> struct __is_void_helper : public false_type { };

template<> struct __is_void_helper<void> : public true_type { };

/// is_void
template<typename _Tp> struct is_void : public __is_void_helper<typename remove_cv<_Tp>::type>::type { };

type traits, 实现 is_integral

template<typename>
struct __is_integral_helper : public false_type { };

template<>
struct __is_integral_helper<bool> : public true_type { };

template<>
struct __is_integral_helper<char> : public true_type { };

template<>
struct __is_integral_helper<signed char> : public true_type { };

template<>
struct __is_integral_helper<unsigned char> : public true_type { };

...

template<>
struct __is_integral_helper<int> : public true_type { };

template<>
struct __is_integral_helper<unsigned int> : public true_type { };

template<>
struct __is_integral_helper<long> : public true_type { };

template<>
struct __is_integral_helper<unsigned long> : public true_type { };

template<>
struct __is_integral_helper<long long> : public true_type { };

template<>
struct __is_integral_helper<unsigned long long> : public true_type { };

...

/// is_integral
template<typename _Tp>
struct is_integral : public __is_integral_helper<typename remove_cv<_Tp>::type>::type { };

type traits, 实现 is_class, is_union, is_enum, is_pod

/// is_enum
template<typename _Tp>
struct is_enum : public integral_constant<bool, __is_enum(_Tp)> { };

/// is_union
template<typename _Tp>
struct is_union : public integral_constant<bool, __is_union(_Tp)> { };

/// is_class
template<typename _Tp>
struct is_class : public integral_constant<bool, __is_class(_Tp)> { };

/// is_pod
// Could use is_standard_layout && is_trivial instead of the builtin
template<typename _Tp>
struct is_pod : public integral_constant<bool, __is_pod(_Tp)> { };

__is_enum() __is_union() __is_class() __is_pod() 这些 _is_xxx 未曾出现于 C++ 标准库源代码，可能是编译器实现

type traits, 实现 is_move_assignable

// Utility to detect referenceable types ([defns.referenceable])
template<typename _Tp>
struct __is_referenceable : public __or_<is_object<_Tp>, is_reference<_Tp>>::type { };

template<typename _Res, typename... _Args>
struct __is_referenceable<_Res(_Args...)> : public true_type { };

template<typename _Res, typename... _Args>
struct __is_referenceable<_Res(_Args......)> : public true_type { };

...

template<typename _Tp, bool = __is_referenceable<_Tp>::value>
struct __is_move_assignable_impl;

template<typename _Tp>
struct __is_move_assignable_impl<_Tp, false> : public false_type { };

template<typename _Tp>
struct __is_move_assignable_impl<_Tp, true> : public is_assignable<_Tp&, _Tp&&> { };

/// is_move_assignable
template<typename _Tp>
struct is_move_assignable : public __is_move_assignable_impl<_Tp> { };

__is_referenceable() 未曾出现于 C++ 标准库源代码，可能是编译器实现

cout

// G2.9 iostream.h
class ostream : virtual public ios
{
    public:
    	ostream& operator<<(char c);	// cout 已对基本类型进行重载，除此之外凡是用 cout 的类型都要写操作符<< 重载
    	ostream& operator<<(unsigned char c) { return (*this) << (char)c; }
    	ostream& operator<<(signed char c) { return (*this) << (char)c; }
    	ostream& operator<<(const char *s);
    	ostream& operator<<(const unsigned char *s) { return (*this) << (const char*)s; }
    	ostream& operator<<(const signed char *s) { return (*this) << (const char*)s; }
    	ostream& operator<<(const void *p);
    	ostream& operator<<(int n);
    	ostream& operator<<(unsigned int n);
    	ostream& operator<<(long n);
    	ostream& operator<<(unsigned long n);
    ...
};

// G2.9 iostream.h
class _IO_ostream_withassign : public ostream 
{
	public:
    	_IO_ostream_withassign& operator=(ostream&);
    	_IO_ostream_withassign& operator=(_IO_ostream_withassign& rhs)
        { return operator=(static_cast<ostream&>(rhs)); }
};

extern _IO_ostream_withassign cout;		// extern 修饰变量，这个变量可以被外界使用，这个文件之外的也都能看到它

// G4.9		其他类型操作符重载
template<typename _CharT, typename _Traits, typename _Alloc>
inline basic_ostream<_CharT, _Traits>& 
	operator<<(basic_ostream<_CharT, _Traits>& __os, const basic_string<_CharT, _Traits, _Alloc>& __str)
{ ... }

template<typename _Tp, typename _CharT, class _Traits>
basic_ostream<_CharT, _Traits>&
    operator<<(basic_ostream<_CharT, _Traits>& __os, const complex<_Tp>& __x)
{ ... }

template<class _CharT, class _Traits>
inline basic_ostream<_CharT, Traits>&
    operator<<(basic_ostream<_CharT, _Traits>& __out, thread::id __id)
{ ... }

template<typename _Ch, typename _Tr, typename _Tp, _Lock_policy _Lp>
inline std::basic_ostream<_Ch, _Tr>&
	operator<<(std::basic_ostream<_Ch, _Tr>& __os, const __shared_ptr<_Tp, _Lp>& __p)
{ ... }

/**
 * @brief Inserts a matched string into an output stream
 */
template<typename _Ch_type, typename _Ch_traits, typename _Bi_iter>
inline basic_ostream<_Ch_type, _Ch_traits>&		// 对于正则表达式里面抓到的一些东西的一个输出
	operator<<(basic_ostream<_Ch_type, _Ch_traits>& __os, const sub_match<_Bi_iter>& __m)	
{ ... }

template<class _CharT, class _Traits, size_t _Nb>
std::basic_ostream<_CharT, _Traits>&
    operator<<(std::basic_ostream<_CharT, _Traits>& __os, const bitset<_Nb>& __x)
{ ... }

movable 元素

详细介绍见 C++2.0新特性C++2.0新特性 | tiny_star_blog

{
    M c1;
    ...
    M c11(c1);		// copy
    M c12(std::move(c1));		// move
    c11.swap(c12);
    
    for(long i=0; i<value; ++i) {
        snprintf(buf, 10, "%d", rand());
        auto ite = c1.end();
        c1.insert(ite, V1type(buf));	// 测试的5个容器都要提供 insert，红黑树 哈希表 insert 也可以指定一个位置，但这个位置只是一个提示，提示不对还是会落到该落到的位置
    }
}

movable 元素对于 vector 速度效能的影响

// print:
// test, with moveable elements
// construction, milli-seconds : 8547		// 1 差别很大，有时候更是巨大得多	// 因为连续，扩充容量要搬移元素到另一个空间
// size()= 3000000
// 8MyString --				// vector 扩充容量要把元素复制到另一个空间，所以 MCtor 和 Dtor 次数大于3000000
// CCtor=0 MCtor=7194303 CAsgn=0 MAsgn=0 Dtor=7194309 Ctor=3000006 DCtor=0	
// copy, milli-seconds : 3500			// 2 差别巨大
// move copy, milli-seconds : 0			// 2 差别巨大
// swap, milli-seconds : 0


// test, with non-moveable elements
// construction, milli-seconds : 14235		// 1 差别很大，有时候更是巨大得多
// size()= 3000000
// 11MyStrNoMove --			// vector 扩充容量要把元素复制到另一个空间，所以 CCtor 和 Dtor 次数大于3000000
// CCtor=7194303 MCtor=0 CAsgn=0 MAsgn=0 Dtor=7194307 Ctor=3000004 DCtor=0
// copy, milli-seconds : 2468			// 3 差别巨大
// move copy, milli-seconds : 0			// 3 差别巨大
// swap, milli-seconds : 0

movable 元素对于 list 速度效能的影响

// print:
// test, with moveable elements
// construction, milli-seconds : 10765		// 1 差别不大	// 因为是一个个节点，增长不需要两倍扩充
// size()= 3000000
// 8MyString --
// CCtor=0 MCtor=3000000 CAsgn=0 MAsgn=0 Dtor=3000006 Ctor=3000006 DCtor=0
// copy, milli-seconds : 4188			// 2 差别巨大
// move copy, milli-seconds : 0			// 2 差别巨大
// swap, milli-seconds : 0


// test, with non-moveable elements
// construction, milli-seconds : 11016		// 1 差别不大
// size()= 3000000
// 11MyStrNoMove --
// CCtor=3000000 MCtor=0 CAsgn=0 MAsgn=0 Dtor=3000004 Ctor=3000004 DCtor=0
// copy, milli-seconds : 3906			// 3 差别巨大
// move copy, milli-seconds : 0			// 3 差别巨大
// swap, milli-seconds : 0

movable 元素对于 deque 速度效能的影响

// print:
// test, with moveable elements
// construction, milli-seconds : 9078		// 1 差别不大	// 因为是一个个节点，增长不需要两倍扩充
// size()= 3000000
// 8MyString --
// CCtor=0 MCtor=3000000 CAsgn=0 MAsgn=0 Dtor=3000006 Ctor=3000006 DCtor=0
// copy, milli-seconds : 3031			// 2 差别巨大
// move copy, milli-seconds : 0			// 2 差别巨大
// swap, milli-seconds : 0


// test, with non-moveable elements
// construction, milli-seconds : 9844		// 1 差别不大
// size()= 3000000
// 11MyStrNoMove --
// CCtor=3000000 MCtor=0 CAsgn=0 MAsgn=0 Dtor=3000004 Ctor=3000004 DCtor=0
// copy, milli-seconds : 2437			// 3 差别巨大
// move copy, milli-seconds : 0			// 3 差别巨大
// swap, milli-seconds : 0

moveable 元素对于 multiset 速度效能的影响

// print:
// test, with moveable elements
// construction, milli-seconds : 74125		// 1 差别不大	// 因为是一个个节点，增长不需要两倍扩充
// size()= 3000000
// 8MyString --
// CCtor=0 MCtor=3000000 CAsgn=0 MAsgn=0 Dtor=3000006 Ctor=3000006 DCtor=0
// copy, milli-seconds : 5438			// 2 差别巨大
// move copy, milli-seconds : 0			// 2 差别巨大
// swap, milli-seconds : 0


// test, with non-moveable elements
// construction, milli-seconds : 74297		// 1 差别不大
// size()= 3000000
// 11MyStrNoMove --
// CCtor=3000000 MCtor=0 CAsgn=0 MAsgn=0 Dtor=3000004 Ctor=3000004 DCtor=0
// copy, milli-seconds : 4765			// 3 差别巨大
// move copy, milli-seconds : 0			// 3 差别巨大
// swap, milli-seconds : 0

moveable 元素对于 unordered_multiset 速度效能的影响

// print:
// test, with moveable elements
// construction, milli-seconds : 23891		// 1 差别不大	// 因为是一个个节点，增长不需要两倍扩充
// size()= 3000000
// 8MyString --
// CCtor=0 MCtor=3000000 CAsgn=0 MAsgn=0 Dtor=3000006 Ctor=3000006 DCtor=0
// copy, milli-seconds : 7812			// 2 差别巨大
// move copy, milli-seconds : 0			// 2 差别巨大
// swap, milli-seconds : 0


// test, with non-moveable elements
// construction, milli-seconds : 24672		// 1 差别不大
// size()= 3000000
// 11MyStrNoMove --
// CCtor=3000000 MCtor=0 CAsgn=0 MAsgn=0 Dtor=3000004 Ctor=3000004 DCtor=0
// copy, milli-seconds : 7188			// 3 差别巨大
// move copy, milli-seconds : 0			// 3 差别巨大
// swap, milli-seconds : 0

写一个 moveable class

class MyString {
    public:
    	static size_t DCtor;	// 累计 default-ctor 呼叫次数
    	static size_t Ctor;		// 累计 ctor 呼叫次数
    	static size_t CCtor;	// 累计 copy-ctor 呼叫次数
    	static size_t CAsgn;	// 累计 copy-asgn 呼叫次数
    	static size_t MCtor;	// 累计 move-ctor 呼叫次数
    	static size_t MAsgn;	// 累计 move-asgn 呼叫次数
    	static size_t Dtor;		// 累计 dtor 呼叫次数
    private:
    	char* _data;
    	size_t _len;
    	void _init_data(const char *s) {	// 深拷贝
            _data = new char[_len+1];
            memcpy(_data, s, _len);
            _data[_len] = '\0';
        }
    public:
    	// default ctor
    	MyString() : _data(NULL), _len(0) { ++DCtor; }
    
    	// ctor
    	MyString(const char* p) : _len(strlen(p)) {
            ++Ctor;
            _init_data(p);
        }
    
    	// copy ctor
    	MyString(const MyString& str) : _len(str._len) {
            ++CCtor;
            _init_data(str._data);	// COPY
        }
    
    	// move ctor, with "noexcept"		// 浅拷贝
    	MyString(MyString&& str) noexcept : _data(str._data), _len(str._len) {
            ++MCtor;
            str._len = 0;
            str._data = NULL;	// 避免 delete(in dtor)
        }
    
    	// copy assignment
    	MyString& operator=(const MyString& str) {
            ++CAsgn;
            if (this != &str) {
                if(_data) delete _data;
                _len = str._len;
                _init_data(str._data);	// COPY!
            }else{
            }
            return *this; 
        }
    	
    	// move assignment
    	MyString& operator=(MyString&& str) noexcept {
            ++MAsgn;
            if(this != &str) {
                if(_data) delete _data;
                _len = str._len;
                _data = str._data;		// MOVE!
                str._len = 0;
                str._data = NULL;		// 避免 delete(in dtor)
            }
            return *this;
        }
    
    	// dtor
    	virtual ~MyString() {
            ++Dtor;
            if(_data) {		// 判断一个指针是否已经被 delete
                delete _data;
            }
        }
    
    	bool operator<(const MyStirng& rhs) const	// 为了 set
        {
            return std::string(this->_data) < std::string(rhs._data);
            // 借用现成事实：string 已能比较大小
        }
    
    	bool operator==(const MyString& rhs) const	// 为了 set
        {
            return std::string(this->_data) == std::string(rhs._data);
            // 借用现成事实：string 已能判断相等
        }
    
    	char* get() const { return _data; }
};

size_t MyString::DCtor=0;
size_t MyString::Ctor=0;
size_t MyString::CCtor=0;
size_t MyString::CAsgn=0;
size_t MyString::MCtor=0;
size_t MyString::MAsgn=0;
size_t MyString::Dtor=0;

namespace std // 必须放在 std 内
{
    template<>
    struct hash<MyString> {		// 这是为了 unordered containers
        size_t operator()(const MyString& s) const noexcept
        { return hash<string>()(string(s.get())); }
        // 借用现有的 hash<string>
        // (在 ...\4.9.2\include\c++\bits\basic_string)
    };
}

测试函数

#include <typeinfo>		// typeid()
template<typename T>
void output_static_data(const T& myStr)
{
    cout << typeid(myStr).name() << "--" << endl;
    cout << " CCtor= " << T::CCtor << " MCtor= " << T::MCtor << " CAsgn= " << T::CAsgn << " MAsgn= " << T::MAsgn
         << " Dtor= " << T::Dtor << " Ctor= " << T::Ctor << " DCtor= " << T::DCtor << endl;
}

template<typename M, typename NM>
void test_moveable(M c1, NM c2, long& value)
{
    char buf[10];
    
    // 测试 moveable		vector<MyString>()
    typedef typename iterator_traits<typename M::iterator>::value_type V1type;
    clock_t timeStart = clock();
    for(long i=0; i<value; ++i) {
        snprintf(buf, 10, "%d", rand());	// 随机数，放进 buf（转换为字符串）
        auto ite = c1.end();				// 定位尾端
        c1.insert(ite, V1type(buf));		// 安插于尾端（对 RB-tree 和 HT 这只是 hint），临时对象右值自动调用move版本
    }
    cout << "construction, milli-seconds: " << (clock()-timeStart) << endl;
    cout << "size()= " << c1.size() << endl;
    output_static_data(*(c1.begin()));
    
    M c11(c1);	// 不是临时对象，左值，不敢调用move版本，调用copy版本
    M c12(std::move(c1));	// 关于 std::move，要求编译器调用move版本			必须确保接下来不会再用到 c1
    c11.swap(c12);
    
    // 测试 non-moveable		vector<MyStrNoMove>()
    ...
}

test_moveable(vector<MyString>(), vector<MyStrNoMove>(), value);

// print:
// test, with moveable elements
// construction, milli-seconds : 8547		// 1 差别很大，有时候更是巨大得多
// size()= 3000000
// 8MyString --
// CCtor=0 MCtor=7194303 CAsgn=0 MAsgn=0 Dtor=7194309 Ctor=3000006 DCtor=0
// copy, milli-seconds : 3500			// 2 差别巨大
// move copy, milli-seconds : 0			// 2 差别巨大
// swap, milli-seconds : 0


// test, with non-moveable elements
// construction, milli-seconds : 14235		// 1 差别很大，有时候更是巨大得多
// size()= 3000000
// 11MyStrNoMove --
// CCtor=7194303 MCtor=0 CAsgn=0 MAsgn=0 Dtor=7194307 Ctor=3000004 DCtor=0
// copy, milli-seconds : 2468			// 3 差别巨大
// move copy, milli-seconds : 0			// 3 差别巨大
// swap, milli-seconds : 0

vector 的 copy ctor

/**
 * @brief %Vector copy constructor
 * @param __x A%vector of identical element and allocator types
 *
 * The newly-created %vector uses a copy of the allocation
 * object used by @a __x. All the elements of @a __x are copied
 * but any extra memory in
 * @a __x (for fast expansion) will not be copied
 */
vector(const vector& __x) : _Base(__x.size(), _Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator()))
{
    this->_M_impl._M_finish = std::__uninitialized_copy_a(__x.begin(), __x.end(), 
                                                          this->_M_impl._M_start, 
                                                          _M_get_Tp_allocator());
}

{
    M c11(c1);
    M c12(std::move(c1));
}

vector 的 move ctor

void _M_swap_data(_Vector_impl& __x)
{
    std::swap(_M_start, __x._M_start);
    std::swap(_M_finish, __x._M_finish);
    std::swap(_M_end_of_storage, __x._M_end_of_storage);
}

_Vector_base(_Vector_base&& __x) noexcept : _M_impl(std::move(__x._M_get_Tp_allocator()))
{
    this->_M_impl._M_swap_data(__x._M_impl);
}

/**
  * @brief %Vector move constructor
  * @param __x A %vector of identical element and allocator types
  *
  * The newly-created %vector contains the exact contents of @a __x
  * The contents of @a __x are a valid, but unspecified %vector
  */
vector(vector&& __x) noexcept : _Base(std::move(__x)) { }

std::string 是否 moveable

template<typename _CharT, typename _Traits, typename _Alloc>
basic_string<_CharT, _Traits, _Alloc>::basic_string(const basic_string& __str)
    : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(__str.get_allocator()), 
                                          __str.get_allocator()), __str.get_allocator)
{ }

/**
 *  @brief Construct string with copy of value of @a str
 *  @param __str Source string
 */
basic_string(const basic_string& __str);

#if __cplusplus >= 201103L
		/**
		 *  @brief Move construct string ...
		 *  @param __str Source string
		 * 
		 *  The newly-created string contains the exact contents of @a __str
		 *  @a __str is a valid, but unspecified string
		 **/
        basic_string(basic_string&& __str)
#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
        noexcept	// FIXME C++11: should always be noexcept
#endif
        : _M_dataplus(__str._M_dataplus)
        {
#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
            __str._M_data(_S_empty_rep()._M_refdata());
#else
            __str._M_data(_S_construct(size_type(), _CharT(), get_allocator()));
#endif
        }

/**
 *  @brief Assign the value of @a str to this string
 *  @param __str Source string
 */
basic_string& operator=(const basic_string& __str)
{ return this->assign(__str); }

#if __cplusplus >= 201103L
        /**
         *  @brief Move assign the value of @a str to this string
         *  @param __str Source string
         *
         *  @The contents of @a str are moved into this string (without copying)
         *  @a str is a valid, but unspecified string
         **/
        // PR 58265, this should be noexcept
        basic_string& operator=(basic_string&& __str)
        {
            // NB: DR 1204
            this->swap(__str);
            return *this;
        }