侯捷STL标准库和泛型编程

STL基础知识介绍

STL六大部件

• 容器
• 分配器
• 算法
• 迭代器
• 适配器
• 仿函数
  
  
  

容器结构与分类

• 顺序容器
  • Array
  • Vector
  • Deque
  • List
  • ForwardList
• 关联容器（红黑树）
  • Set(键和值相同)
  • Multiset
  • Map
  • Multimap
• 无序容器(Hash table)
  • Unordered Set
  • Unordered Multiset
  • Unordered Map
  • Unordered Multimap
    
    
    

序列式容器

array

1. array 容器以类模板的形式定义在 头文件，并位于命名空间 std 中

namespace std{
    template <typename T, size_t N>
    class array;
}

1. 初始化

2. array 容器不会做默认初始化操作

    array<int,10> array1;
    for(auto x:array1)
        cout<<x<<ends;
//    4200080 0 24 0 0 0 0 0 8 0
//使用该语句，容器中所有的元素都会被初始化为 0
std::array<double, 10> values {};

2. 成员函数

4. C++ 11 标准库还新增加了 begin() 和 end() 这 2 个函数，既可以操作是容器，还可以是普通数组。如果操作对象是普通数组，则 begin() 函数返回的是指向数组第一个元素的指针
5. 在 头文件中还重载了 get() 全局函数，该重载函数的功能是访问容器中指定的元素，并返回该元素的引用

cout<<get<2>(array1);

3. 访问元素

1. 通过[],但是没有做任何边界检查
2. at() 成员函数,当传给 at() 的索引是一个越界值时，程序会抛出 std::out_of_range 异常
3. get 模板函数，参数的实参必须是一个在编译时可以确定的常量表达式，所以它不能是一个循环变量。也就是说，它只能访问模板参数指定的元素，编译器在编译时会对它进行检查。
4. data() 成员函数
5. 通过迭代器

    //访问第三个元素
    cout<<array1[2]<<ends;
    cout<<array1.at(2)<<ends;
    cout<<get<2>(array1)<<ends;
    cout<<*(array1.data()+2)<<ends;

4. 实现机制

5. 注意事项

vector

1. array 实现的是静态数组（容量固定的数组），而 vector 实现的是一个动态数组
2. 该容器擅长在尾部插入或删除元素,而对于在容器头部或者中部插入或删除元素，则花费时间要长一些（移动元素需要耗费时间）
3. ector 容器以类模板 vector（ T 表示存储元素的类型）的形式定义在 头文件中，并位于 std 命名空间中。
   
   
   
   

1. 初始化

vector<double> values;
// 这是一个空的 vector 容器，因为容器中没有元素，所以没有为其分配空间。当添加第一个元素（比如使用 push_back() 函数）时，vector 会自动分配内存。

vector<int> primes {2, 3, 5, 7, 11, 13, 17, 19};


vector<double> values(20);
//指定元素个数： 也可以:vector<double> values(20, 1.0);
//圆括号 () 中的 2 个参数，既可以是常量，也可以用变量来表示
int num=20;
double value =1.0;
vector<double> values(num, value);


int array[]={1,2,3};
vector<int>values(array, array+2);//values 将保存{1,2}
std::vector<int>value1{1,2,3,4,5};
std::vector<int>value2(std::begin(value1),std::begin(value1)+3);//value2保存{1,2,3}

2. 成员函数

1. 全局的函数:begin()和end(),swap()

3. 访问元素

1. 小标[]
2. at()
3. front() 和 back() 它们分别返回 vector 容器中第一个和最后一个元素的引用
4. data() 成员函数，该函数的功能是返回指向容器中首个元素的指针
5. 迭代器

5. 实现机制

4. 注意事项

1. 初始化空的 vector 容器时，不能使用迭代器
2. 添加元素:emplace_back() 和 push_back() 的区别，就在于底层实现的机制不同。push_back() 向容器尾部添加元素时，首先会创建这个元素，然后再将这个元素拷贝或者移动到容器中（如果是拷贝的话，事后会自行销毁先前创建的这个元素）；而 emplace_back() 在实现时，则是直接在容器尾部创建这个元素，省去了拷贝或移动元素的过程。
3. 指定位置添加元素:insert()和emplace()
   

• emplace() 每次只能插入一个元素，而不是多个。用于在 vector 容器指定位置之前插入一个新的元素。

4. 删除元素:除了可以借助本身提供的成员函数，还可以借助一些全局函数。
   

• std::remove(demo.begin(), demo.end(), 3);remove() 的实现原理是，在遍历容器中的元素时，一旦遇到目标元素，就做上标记，然后继续遍历，直到找到一个非目标元素，即用此元素将最先做标记的位置覆盖掉，同时将此非目标元素所在的位置也做上标记，等待找到新的非目标元素将其覆盖。既然通过 remove() 函数删除掉 demo 容器中的多个指定元素，该容器的大小和容量都没有改变，其剩余位置还保留了之前存储的元素。我们可以使用 erase() 成员函数删掉这些 “无用” 的元素。

vector<int>demo{ 1,3,3,4,3,5 };
    //交换要删除元素和最后一个元素的位置
    auto iter = std::remove(demo.begin(), demo.end(), 3);
    demo.erase(iter, demo.end());
    cout << "size is :" << demo.size() << endl;
    cout << "capacity is :" << demo.capacity() << endl;

deque

• deque 是 double-ended queue 的缩写，又称双端队列容器。
• deque 容器也擅长在序列尾部添加或删除元素（时间复杂度为O(1)），而不擅长在序列中间添加或删除元素。
• deque 容器也可以根据需要修改自身的容量和大小
• • deque 容器中存储元素并不能保证所有元素都存储到连续的内存空间中。
    
    
    
    
    
• deque如何模拟连续空间
  
  
• 后++调用前++
  
  
  
  

1. 初始化

std::deque<int> d;


std::deque<int> d(10);
std::deque<int> d(10, 5)


std::deque<int> d2(d1);


std::deque<int>d(arr.begin()+2, arr.end());

2. 成员函数

3. 访问元素

 deque<int>d{ 1,2,3,4 };

cout << d[1] << endl;


cout << d.at(1) << endl;

  d.front() = 10;
    cout << "deque 新的首元素为：" << d.front() << endl;
    //修改尾元素
    d.back() = 20;
    cout << "deque 新的尾元素为：" << d.back() << endl;

4. 实现机制

• 分段连续

5. 注意事项

• 迭代器不能用来初始化空的 deque 容器。
  

list

• 注意后置++返回不是引用，因为连续两次的后C++对于int类型不允许的。而前置++返回的是引用，因为对于int前++两次是允许的

• G2.9->G4.9
• 
  

• 双向链表容器，list 容器中的元素可以分散存储在内存空间里，而不是必须存储在一整块连续的内存空间中。
• 其中第一个元素的前向指针总为 null，因为它前面没有元素；同样，尾部元素的后向指针也总为 null。
• 它可以在序列已知的任何位置快速插入或删除元素

1. 初始化

list<int> values;
list<int> values(10);
//通过此方式创建 values 容器，其中包含 10 个元素，每个元素的值都为相应类型的默认值
int a[] = { 1,2,3,4,5 };
std::list<int> values(a, a+5);

• 全局的 begin() 和 end()，swap()

2. 成员函数

3. 访问元素

1. 使用 front() 和 back() 成员函数
2. 迭代器

4. 实现机制

5. 注意事项

• list 容器在进行插入（insert()）、接合（splice()）等操作时，都不会造成原有的 list 迭代器失效，甚至进行删除操作，而只有指向被删除元素的迭代器失效，其他迭代器不受任何影响。
• push_front()：向 list 容器首个元素前添加新元素；
  push_back()：向 list 容器最后一个元素后添加新元素；
  emplace_front()：在容器首个元素前直接生成新的元素；
  emplace_back()：在容器最后一个元素后直接生成新的元素；
  emplace()：在容器的指定位置直接生成新的元素；
  insert()：在指定位置插入新元素；
  splice()：将其他 list 容器存储的多个元素添加到当前 list 容器的指定位置处。

• splicehanshu
  
• 删除
  

forward_list

• forward_list 使用的是单链表
• • 效率高是选用 forward_list 而弃用 list 容器最主要的原因，换句话说，只要是 list 容器和 forward_list 容器都能实现的操作，应优先选择 forward_list 容器。

1. 初始化

同list

2. 成员函数

3. 访问元素

4. 实现机制

5. 注意事项

• forward_list 容器中是不提供 size() 函数的，但如果想要获取 forward_list 容器中存储元素的个数，可以使用头文件 中的 distance() 函数。

int count = std::distance(std::begin(my_words), std::end(my_words));

关联式容器(红黑树实现)

• 关联式容器所具备的这些特性，归咎于 STL 标准库在实现该类型容器时，底层选用了 「红黑树」这种数据结构来组织和存储各个键值对。
• 除此之外，序列式容器中存储的元素默认都是未经过排序的，而使用关联式容器存储的元素，默认会根据各元素的键值的大小做升序排序。
• 除此之外，C++ 11 还新增了 4 种哈希容器，即 unordered_map、unordered_multimap 以及 unordered_set、unordered_multiset。严格来说，它们也属于关联式容器，但由于哈希容器底层采用的是哈希表，而不是红黑树

rb_tree

pair

• 考虑到“键值对”并不是普通类型数据，C++ STL 标准库提供了 pair 类模板，其专门用来将 2 个普通元素 first 和 second（可以是 C++ 基本数据类型、结构体、类自定的类型）创建成一个新元素<first, second>。
• pair 类模板定义在头文件中，

#1) 默认构造函数，即创建空的 pair 对象
pair();
#2) 直接使用 2 个元素初始化成 pair 对象
pair (const first_type& a, const second_type& b);
#3) 拷贝（复制）构造函数，即借助另一个 pair 对象，创建新的 pair 对象
template<class U, class V> pair (const pair<U,V>& pr);
#4) 移动构造函数
template<class U, class V> pair (pair<U,V>&& pr);
#5) 使用右值引用参数，创建 pair 对象
template<class U, class V> pair (U&& a, V&& b);

set

• 要求键 key 和值 value 必须相等。
• 使用 set 容器存储的各个元素的值必须各不相同

template < class T,                        // 键 key 和值 value 的类型
           class Compare = less<T>,        // 指定 set 容器内部的排序规则
           class Alloc = allocator<T>      // 指定分配器对象的类型
           > class set;

1. 初始化

std::set<std::string> myset;

std::set<std::string> myset{"http://c.biancheng.net/java/",                         "http://c.biancheng.net/stl/",                         "http://c.biancheng.net/python/"};


std::set<std::string> copyset(myset);
//等同于
//std::set<std::string> copyset = myset


//C++ 11 标准还为 set 类模板新增了移动构造函数，其功能是实现创建新 set 容器的同时，利用临时的 set 容器为其初始化
set<string> retSet() {
    std::set<std::string> myset{ "http://c.biancheng.net/java/",
                            "http://c.biancheng.net/stl/",
                            "http://c.biancheng.net/python/" };
    return myset;
}
std::set<std::string> copyset(retSet());
//注意，由于 retSet() 函数的返回值是一个临时 set 容器，因此在初始化 copyset 容器时，其内部调用的是 set 类模板中的移动构造函数，而非拷贝构造函数。



std::set<std::string> myset{ "http://c.biancheng.net/java/",
                    "http://c.biancheng.net/stl/",
                    "http://c.biancheng.net/python/" };
std::set<std::string> copyset(++myset.begin(), myset.end());

2. 成员函数

3. 访问元素

4. 实现机制

5. 注意事项

• 对于初学者来说，切勿尝试直接修改 set 容器中已存储元素的值，这很有可能破坏 set 容器中元素的有序性，最正确的修改 set 容器中元素值的做法是：先删除该元素，然后再添加一个修改后的元素。

multiset

1. 初始化

2. 成员函数

3. 访问元素

4. 实现机制

5. 注意事项

• 也就是说，multiset 容器和 set 容器唯一的差别在于，multiset 容器允许存储多个值相同的元素，而 set 容器中只能存储互不相同的元素

map

• map中的[]
• 

1. 初始化

2. 成员函数

3. 访问元素

4. 实现机制

5. 注意事项

multimap

• multimap 不可用[]添加元素(只能通过insert(pair<int,int>(1,2))),但是map可以通过[]添加元素

1. 初始化

2. 成员函数

3. 访问元素

4. 实现机制

5. 注意事项

• 不能使用[]做insert操作

hashtable

• modulus(余数)运算

  • 落在哪个篮子
    

• 篮子个数一定大于元素个数，当两者相等时就会rehash

unordered_map/hash_set(hashtable实现)

1. 初始化

2. 成员函数

3. 访问元素

4. 实现机制

5. 注意事项

unordered_multimap /hash_multimap（hashtable实现）

• 篮子一定比元素多。
• unordered_multimap 不可用[]添加元素

1. 初始化

2. 成员函数

3. 访问元素

4. 实现机制

5. 注意事项

unordered_set/hash_set（hashtable实现）

1. 初始化

2. 成员函数

3. 访问元素

4. 实现机制

5. 注意事项

unordered_multiset/hash_multiset（hashtable实现）

1. 初始化

2. 成员函数

3. 访问元素

4. 实现机制

5. 注意事项

适配器

• 容器适配器也是同样的道理，简单的理解容器适配器，其就是将不适用的序列式容器（包括 vector、deque 和 list）变得适用
• 容器适配器本质上还是容器，只不过此容器模板类的实现，利用了大量其它基础容器模板类中已经写好的成员函数。当然，如果必要的话，容器适配器中也可以自创新的成员函数。
  

stack

• 不会提供迭代器，会破坏其特性
  

1. 初始化

std::stack<int> values; //采用默认的 deque 基础容器


//stack<T,Container=deque<T>>
std::stack<std::string, std::list<int>> values;

//可以用一个基础容器来初始化 stack 适配器，只要该容器的类型和 stack 底层使用的基础容器类型相同即可
std::list<int> values {1, 2, 3};
std::stack<int,std::list<int>> my_stack (values);


//还可以用一个 stack 适配器来初始化另一个 stack 适配器，只要它们存储的元素类型以及底层采用的基础容器类型相同即可

2. 成员函数

3. 访问元素

4. 实现机制

5. 注意事项

queue

• 不会提供迭代器，会破坏其特性
  
  
  

1. 初始化

//底层使用的基础容器选择默认的 deque 容器
std::queue<int> values;


//在手动指定基础容器的类型时，其存储的数据类型必须和 queue 容器适配器存储的元素类型保持一致
std::queue<int, std::list<int>> values;

//同stack

2. 成员函数

3. 访问元素

4. 实现机制

5. 注意事项

priority_queue

• 指的就是先进队列的元素并不一定先出队列，而是优先级最大的元素最先出队列。
• 为了保证每次从队头移除的都是当前优先级最高的元素，每当有新元素进入，它都会根据既定的排序规则找到优先级最高的元素，并将其移动到队列的队头；同样，当 priority_queue 从队头移除出一个元素之后，它也会再找到当前优先级最高的元素，并将其移动到队头。
• priority_queue 容器适配器“First in，Largest out”的特性，和它底层采用堆结构存储数据是分不开的。有关该容器适配器的底层实现

template <typename T,
        typename Container=std::vector<T>,
        typename Compare=std::less<T> >
class priority_queue{
    //......
}

• typename Compare：指定容器中评定元素优先级所遵循的排序规则，默认使用std::less按照元素值从大到小进行排序，还可以使用std::greater按照元素值从小到大排序，但更多情况下是使用自定义的排序规则。
• 其中，std::less 和 std::greater 都是以函数对象的方式定义在 头文件中

1. 初始化

std::priority_queue<int> values;


//使用普通数组
int values[]{4,1,3,2};
std::priority_queue<int>copy_values(values,values+4);//{4,2,3,1}
//使用序列式容器
std::array<int,4>values{ 4,1,3,2 };
std::priority_queue<int>copy_values(values.begin(),values.end());//{4,2,3,1}


int values[]{ 4,1,2,3 };
std::priority_queue<int, std::deque<int>, std::greater<int> >copy_values(values, values+4);//{1,3,2,4}

2. 成员函数

3. 访问元素

4. 实现机制

5. 注意事项

分配器

简介

• 用于分配管理内存空间
• allocator的特点是将内存分配(allocate)与对象构造(construct)分离，这样使得对内存的管理更加灵活，性能较高。
• C++编译器默认已经使用了内置的std::allocator
• #include //用于标准库中的STL containers
• 它提供一种类型感知的内存分配方法，它分配的内存是原始的、未构造的。
  

GNU

• G2.9实际上不用上面的用下面的alloc
  
  

• G4.9 却没用alloc

• 

迭代器

traits(迭代器的traits)

• 通过traits来萃取取迭代器的特性

• 例子: 算法rotate需要问iterator的三个属性

  • category 移动性质(是否可以前++，后++，跳步吗)
  • value_type：所指元素的类型
  • difference_type:两个元素之间的距离
    

• 迭代器必须回答5个问题

  • 算法直接问iterator

• 迭代器可以设置为类但是指针了？指针可以看作退化的iterator。间接问

• 
  

STL内核分析

OOP VS GP(Generic Programming)

• why list提供自己的sort版本而不能使用全局的sort，因为其底层是数组实现，全局的sort需要的容器必须是随机访问容器，可以跳跃，而list只能按顺序访问
  
  

操作符重载 模板

• 模板的类型

  • 函数模板

  • 类模板

    • (全)特化

    • 偏特化

      • 

  • 成员模板

    • 允许在类中定义模板成员函数或模板成员类

    • 模板成员函数

    • 模板成员类

    • 

• 类模板必须通过<>显示指明类型即类模板必须在实例化时显式指定类型。。函数模板则可以不显示指明，因为其有类型推导

traits 机制

C++ 中的 traits 机制是一种元编程技术，用于在编译时获取类型的信息或执行类型相关的操作。Traits 通常以模板类的形式出现，提供了一种静态的方式查询或修改类型的属性。Traits 机制广泛应用于标准库中，如 std::iterator_traits 和 std::numeric_limits，以及自定义的类型特性类。

什么是 Traits？

Traits 是一种将类型信息与类型本身分离的技术。通过 Traits，可以在编译时获取类型的各种属性，如大小、对齐方式、是否有某种操作等。Traits 通常以模板类的形式定义，提供一系列静态成员函数和常量来描述类型的信息。

标准库中的 Traits

std::iterator_traits

std::iterator_traits 用于获取迭代器的类型信息。它定义了几个类型别名，如 value_type、difference_type、pointer、reference 和 iterator_category。

#include <iterator>

template <typename Iterator>
struct iterator_traits {
    using value_type = typename Iterator::value_type;
    using difference_type = typename Iterator::difference_type;
    using pointer = typename Iterator::pointer;
    using reference = typename Iterator::reference;
    using iterator_category = typename Iterator::iterator_category;
};

// 特化版本，用于原生指针
template <typename T>
struct iterator_traits<T*> {
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    using pointer = T*;
    using reference = T&;
    using iterator_category = std::random_access_iterator_tag;
};

template <typename T>
struct iterator_traits<const T*> {
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    using pointer = const T*;
    using reference = const T&;
    using iterator_category = std::random_access_iterator_tag;
};

std::numeric_limits

std::numeric_limits 用于获取数值类型的属性，如最小值、最大值、精度等。

#include <limits>

template <typename T>
struct numeric_limits {
    static constexpr T min() noexcept;
    static constexpr T max() noexcept;
    static constexpr int digits;
    static constexpr bool is_signed;
    // 其他成员
};

// 特化版本，用于 int
template <>
struct numeric_limits<int> {
    static constexpr int min() noexcept { return INT_MIN; }
    static constexpr int max() noexcept { return INT_MAX; }
    static constexpr int digits = 31; // 31 bits for signed int
    static constexpr bool is_signed = true;
    // 其他成员
};

自定义 Traits

你也可以定义自己的 traits 类，以满足特定的需求。例如，假设我们有一个自定义的容器类，需要在编译时获取容器的某些属性。

示例：自定义容器的 Traits

#include <iostream>

// 定义一个自定义容器
template <typename T>
class MyContainer {
public:
    using value_type = T;
    using size_type = std::size_t;
    using reference = T&;
    using const_reference = const T&;
    using iterator = T*;
    using const_iterator = const T*;

    // 其他成员函数
};

// 定义一个 traits 类
template <typename Container>
struct ContainerTraits {
    using value_type = typename Container::value_type;
    using size_type = typename Container::size_type;
    using reference = typename Container::reference;
    using const_reference = typename Container::const_reference;
    using iterator = typename Container::iterator;
    using const_iterator = typename Container::const_iterator;
};

// 使用 traits 获取容器的类型信息
int main() {
    MyContainer<int> container;
    ContainerTraits<MyContainer<int>> traits;

    using value_type = typename traits::value_type;
    using size_type = typename traits::size_type;
    using reference = typename traits::reference;
    using const_reference = typename traits::const_reference;
    using iterator = typename traits::iterator;
    using const_iterator = typename traits::const_iterator;

    std::cout << "value_type: " << typeid(value_type).name() << std::endl;
    std::cout << "size_type: " << typeid(size_type).name() << std::endl;
    std::cout << "reference: " << typeid(reference).name() << std::endl;
    std::cout << "const_reference: " << typeid(const_reference).name() << std::endl;
    std::cout << "iterator: " << typeid(iterator).name() << std::endl;
    std::cout << "const_iterator: " << typeid(const_iterator).name() << std::endl;

    return 0;
}

#include <iostream>

// 定义一个简单的类
class MyClass {
public:
    void doSomething() const {
        std::cout << "Doing something" << std::endl;
    }
};

// 定义一个 Traits 类
template <typename T>
struct HasDoSomething {
    // 默认情况下，假设类型没有 doSomething 方法
    static const bool value = false;
};

// 特化 Traits 类，针对 MyClass
template <>
struct HasDoSomething<MyClass> {
    static const bool value = true;
};

template <typename T>
void callDoSomething(const T& obj) {
    if (HasDoSomething<T>::value) {
        obj.doSomething();
    }
    else {
        std::cout << "Type does not have doSomething method" << std::endl;
    }
}

int main() {
    MyClass myObj;
    int x = 42;

    callDoSomething(myObj);  // 调用 MyClass 的 doSomething 方法
    callDoSomething(x);      // 输出 "Type does not have doSomething method"
    return 0;
}

Traits 的优势

1. 编译时信息：Traits 提供了在编译时获取类型信息的能力，这有助于优化性能和提高代码的健壮性。
2. 类型安全：通过 Traits，可以在编译时进行类型检查，确保类型的安全性和一致性。
3. 代码复用：Traits 机制允许你编写通用的模板代码，减少重复代码，提高代码的复用性。
4. 灵活性：Traits 可以用于各种类型，包括自定义类型，提供了高度的灵活性。
   总结
   Traits 机制是 C++ 中一种强大的元编程技术，用于在编译时获取类型的信息或执行类型相关的操作。通过 Traits，可以在编译时进行类型检查和优化，提高代码的健壮性和性能。标准库中提供了许多常用的 Traits 类，如 std::iterator_traits 和 std::numeric_limits，你也可以根据需要定义自己的 Traits 类。

算法

迭代器

• array，vector，deque（随机访问迭代器）random_access_iterator_tag
• list 双向迭代器(bidirectional_iterator_tag)
• forward_list(forward_iteator_tag)
• associative container(bidirectional_iterator_tag) 本质上是通过红黑树实现，即链表指针实现
• unordered container(hash_table实现)
  • 需要根据篮子下面的链表类型决定是forward_iteator_tag或bidirectional_iterator_tag

• 大于迭代器
  
  

迭代器对算法的影响

• distance
  
• advance
  
  
  
  
  
  

算法

accumulate

for_each

replace

count

find

sort

• 注意关联式容器不带sort成员函数,自身在插入的时候就带顺序插入着。
• list，forward_list自身带有sort不能使用std中的sort函数，因为std中sort函数要求迭代器必须为random的可以跳的，但是他俩的是双向迭代器
  

reverse

binary_search

仿函数functors

• 三种类型

  • 算术类
  • 逻辑运算类
  • 相对关系类
    

• GNU C独有的

  • 

• sort

  • 

• 仿函数应该继承，为了让适配器去修饰和改造

  • 
    

适配器

• 函数适配器(bind2nd)