【Cpp】第十七章-unordered版本关联式容器

发表于 2019-11-03 | 分类于 Cpp

字数统计: 6.5k

unordered系列关联式容器

什么是unordered系列

unordered系列的关联式容器有unordered-map/unordered-set/unordered-multimap/unordered-multiset，这些版本的关联式容器和普通版本的又有什么区别呢？我们简单使用下和普通版本的做一个对比。

#include <iostream>
#include <map>
#include <unordered_map>
int main()
{
    std::map<int, int> m;
    m.insert(std::make_pair(1, 1));
    m.insert(std::make_pair(4, 4));
    m.insert(std::make_pair(2, 2));
    m.insert(std::make_pair(4, 4));
    m.insert(std::make_pair(6, 6));
    std::cout << "map:" << std::endl;
    for(auto e : m)
    {
        std::cout << e.first << " " << e.second << std::endl;
    }
    std::unordered_map<int, int> um;
    um.insert(std::make_pair(1, 1));
    um.insert(std::make_pair(4, 4));
    um.insert(std::make_pair(2, 2));
    um.insert(std::make_pair(4, 4));
    um.insert(std::make_pair(6, 6));
    std::cout << "unordered-map:" << std::endl;
    for(auto e : um)
    {
        std::cout << e.first << " " << e.second << std::endl;
    }

}


map:
1 1
2 2
4 4
6 6
unordered-map:
6 6
2 2
1 1
4 4

对比结果很明显，我们发现map往往会将插入的键值对按照key的大小比较排序，因此打印出来的数据是有序的，因为其底层是一棵红黑树，因此这样的结果也是理所应当的，但是unordered-map就如它的名字一样遍历出来的数据是无序的，但是依然能完成键值对的查找功能，unordered-map与map最为显著的差距就在这里，看上去unordered-map并不如map强大，那为什么还要存在unordered系列呢？因为其查找索引能够达到O1的时间复杂度，比红黑树更快，因为其底层数据结构是一个哈希桶，关于底层实现我们之后再讨论，我们解析来首先介绍一下unordered系列的使用。

unordered系列的使用

unordered系列共有四种关联式容器，与普通版本的互相对应，除了数据在内部存储及遍历结果无序外，其他的使用方法与普通版本的几乎没有区别，因此这里不再详细讨论接口的使用，我们这里主要要关心的是为什么unordered系列可以在舍弃有序的情况下变得更快，其底层的数据结构又是怎么样的。

底层结构

虽然看上去unordered系列关联式容器的使用方法与普通版本的关联式容器使用没有太大区别，但他们两个的底层实现却完全不一样，这也是导致为什么unordered可以更快，并且不能有序的原因。

哈希表

什么是哈希表

哈希表是一种根据映射来存储数据的结构，我们可以自定义一个哈希函数，通过key和哈希函数算出各个value实际在空间中存储的位置，然后进行value的存储，我们想要查找某个数据的时候也只需要通过同样的方法找到对应位置就可以拿到value。
举个例子，我们现在有个数组，我们约定数组对应下标就存储对应key的数据value。如arr[1] = value1, arr[2] = value2, ... , arr[n] = valuen。由此一来我们想要根据key查找某个value就直接访问数组中对应下标的元素arr[key]即可。例如我们要找key == 1时value的值，我们直接访问arr[1]就可以直接拿到value1，这就是通过哈希建立映射的方法，并且这里的查找速度只需要O1，这就是典型的以空间换时间的做法，因为这里可能会出现空间的大量浪费。如果发生这么一种情况，key的上限过大，几千万或者几亿，但是中间的数据可能十分零散，此时我们为了继续建立映射不得不创建一个长度为几千万甚至几忆的数组，并且由于数据十分零散，会导致中间可能会有很多空间根本没有映射来存value，例如现在要存储两个映射key == 1, key == 10000000，我们发现这两个映射之间在没有其他映射了，那么这一个长度为10000000的数组中就只存了两个值，由此就算我们节省了时间却浪费了过多的空间，这也是哈希所要解决的一个问题。总之哈希表就是这么一种通过哈希函数建立key和value之间映射的结构。

哈希函数

正如刚才所说，我们的value得通过哈希函数和key来确定数据存放位置并且也能找到对应数据，因此哈希函数的确定十分重要，向我们刚刚所举的例子中我们采用的哈希函数就是直接导致我们造成大量空间浪费的原因，因此在适当的时机选取何时的哈希函数也是十分重要的，接下来简单介绍几种哈希函数。

直接定址法

取关键字的某个线性函数为散列地址：Hash(key) = A * key + b。这种哈希函数的优点也很明显，十分简单，均匀，但是它只适用于key的范围确定，且值较小还比较连续的情景，一但key过大，或者不连续就会出现大量空间被浪费的情况。

除留余数法

这种方法是最为常用的哈希函数。假设我们散列表中允许的最大地址为m，我们可以取一个小于等于m的质数p作为除数，然后执行哈希函数Hash(key) = key % p(p <= m)，将余数作为地址进行定址。一般来说我们为了使得哈希表可以增容都会将除数设置为随着哈希表总长度而改变的变量，并且在不考虑其他因素的情况下，除数==容量的情况可以最大程度的利用空间。

平方取中法

假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；再比如关键字为 4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况。

折叠法

折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况。
初次之外还有很多哈希方法，但是除了直接定址法和除留余数法外其他都不常用，所以可以仅作了解。

哈希冲突

我们在利用哈希函数进行寻址的时候，很容易发生一种情况，就是两个数同时可能会寻到同一块地址，例如我们使用除留余数法进行寻址，除数为11，现在有key为11和22，余数都为0，我们都要存在地址为0的位置上，此时该怎么办呢，我们一个位置又不能存储两个数啊，于是这里就牵扯到了如何解决哈希冲突。哈希冲突的解决可以分为两大类，闭散列和开散列。

负载因子

在具体讨论哈希冲突解决方法前我们还要关心一个概念即负载因子，一会我们就会知道无论是采用哪种哈希函数使用闭散列解决哈希冲突还是开散列解决哈希冲突，哈希表总会有被存满的时候，尤其是采用闭散列的时候，如果存放数据越多，就会发生越来越多的冲突，我们在解决起来可能就要遍历整张表，使得哈希表的性能下降，因此我们要尽可能避免一张哈希表被存满，不过这种情况虽然对于开散列来说可能还好，但是一段哈希表为了维持性能也一定是有它的负载上限的，这里就要对哈希表进行扩容，那么什么时候扩容怎么扩容就成了问题。我们先说如何解决什么时候扩容的难题。
假设我们现在使用除留余数法在一段长为c的线性空间上进行散列，此时为了充分利用空间和使得可以增容，我们的除数不定，与容量保持一致也为c，于是此时的哈希函数为Hash(key) = key % c；我们所采用的冲突解决方法为线性探测法。为了避免大面积冲突降低性能，我们引入负载因子的概念，负载因子 = _size / c,(_size为哈希表中有效结点的个数)。这个公式可知负载因子是不可能大于1的，等于1时则哈希表已满，那么我们必须选取一个合适的值，当哈希表还没满，性能降低还不太明显的时候就进行增容，当然增容也不能太过频繁，因为哈希表的增容也会付出很大代价，一般来说对于闭散列我们的负载因子要求其大于等于0.8就可以开始增容了。
说完什么时候增容，再说怎么增容。假如增容一次容量扩大一倍，可以知道的是，增容一次除数就会改变一次，那么原本算好地址的元素在新的哈希表中的地址也许就会改变，我们不得不遍历所有元素重新计算他们的地址然后再放到新的哈希表中，这也是为什么不能过于频繁的增容会有极大消耗的原因。

闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去，于是问题就变成了如何找到一个合适的空位置让我们存储当前数据，还能保证我们在查找时能够再次准确的找到当前位置。

线性探测再散列

线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。例如除留余数法除数为11，key为11和22，当11先散列要存储在地址为0的位置时，22再进行散列的时候发现地址为0的位置已经存储过11的数据了，则它就继续向后线性探索，直到找到第一个空位置就将22的数据存储进去。

二次探测再散列

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为： Hi= (H0 + i ^ 2) % m, 或者：H0 = (Hi - i ^ 2) % m。其中： i = 1,2,3… ， H0是通过散列函数Hash(x)对元素的关键码key进行计算得到的位置，m是表的大小。

基于闭散列实现哈希表

这里使用除留余数法+线性探测法实现哈希表。在实现时要注意为了标记散列表一个位置当前是否已经存在元素，我们要给每个结点都附加一个状态值，空/存在/删除三种状态，空和存在状态很好理解，删除状态的定义是为了方便再哈希表中删除结点所定义的状态，因为如果我们直接删除一个结点的话可能会影响其他结点的查找，因此我们一般删除都是采用该表状态为删除状态的这种伪删除法。

hash.hpp:
#pragma once
#include <iostream>
#include <vector>
#include <utility>

//定义三种状态，DELETE状态是为了方便我们对结点进行删除
enum STATE
{
    EMPTY,
    EXIST,
    DELETE
};

template<class K, class V>
struct HashNode
{
    //为了更好的可以找到映射，哈希表往往存的是一个K-V结构
    std::pair<K, V> _data;
    //状态默认为空
    STATE _state = EMPTY;
};

template<class K, class V>
class HashTable
{
public:
    typedef HashNode<K, V> Node;
    HashTable(const size_t n = 10)
        :_size(n)
    {
        _ht.resize(n);
    }
    bool Insert(const std::pair<K, V>& data)
    {
        //检查容量
        checkCapacity();
        //计算索引，进行散列
        int index = data.first % _ht.size();
        //1、判断当前地方是否有元素，没有直接插入
        //元素可以放在EMPTY和DELETE
        while(_ht[index]._state == EXIST)
        {
            //2、如果有，判断当前位置的元素的key是否和插入的相同，如果相同则插入失败直接返回
            if (_ht[index]._data.first == data.first)
            {
                //插入失败
                return false;
            }
            //3、如果有，且key不同则利用哈希冲突解决方法解决哈希冲突
            ++index;
            if(index == _ht.size())
            {
                index = 0;
            }
        }
        //元素插入
        _ht[index]._data = data;
        _ht[index]._state = EXIST;
        ++_size;
        return true;
    }
    //检查容量，负载因子超过阈值则扩容
    void checkCapacity()
    {
        //这里选取负载因子大于等于0.8扩容
        if(_ht.size() == 0 || _size * 10 / _ht.size() >= 8)
        {
            //增容
            int newC = _ht.size() == 0 ? 10 : 2 * _ht.size();
            HashTable<K, V> newHt(newC);
            //旧元素插入到新表
            for(int i = 0; i < _ht.size(); i++)
            {
                if(_ht[i]._state == EXIST)
                {
                    newHt.Insert(_ht[i]._data);
                }
            }
            //_ht = newHt._ht;深拷贝，太慢了，直接交换值比较快
            std::swap(_ht, newHt._ht);
        }
    }
    //搜索
    Node* Find(const K& key)
    {
        int index = key % _ht.size();
        while(_ht[index]._state != EMPTY)
        {
            if(_ht[index]._state == EXIST)
            {
                if(_ht[index]._data.first == key)
                {
                    return &_ht[index];
                }
            }
            index++;
            if(index == _ht.size())
            {
                index = 0;
            }
        }
        return nullptr;
    }
    //删除
    bool Erase(const K& key)
    {
        Node* pos = find(key);
        if(pos)
        {
            pos->_state = DELETE;
            --_size;
            return true;
        }
        return false;
    }
private:
    //散列表
    std::vector<Node> _ht;
    size_t _size;
};

test.cpp:
#include "hash.hpp"
void test()
{
    HashTable<int, int> ht;
    ht.Insert(std::make_pair(5, 5));
    ht.Insert(std::make_pair(1, 1));
    ht.Insert(std::make_pair(0, 0));
    ht.Insert(std::make_pair(10, 10));
    ht.Insert(std::make_pair(30, 30));
    ht.Insert(std::make_pair(32, 32));
    ht.Insert(std::make_pair(8, 8));
    ht.Insert(std::make_pair(110, 110));
    ht.Insert(std::make_pair(23, 23));
    ht.Insert(std::make_pair(24, 23));
    ht.Insert(std::make_pair(25, 23));
    ht.Insert(std::make_pair(26, 23));
    HashNode<int, int>* node =  ht.Find(32);
    if(node != nullptr)
    {
        std::cout << (node->_data.first) << " " << node->_data.second;
    }
    else
    {
        std::cout << "nullptr" << std::endl;
    }
    std::cout << std::endl;
    node =  ht.Find(110);
    if(node != nullptr)
    {
        std::cout << (node->_data.first) << " " << node->_data.second;
    }
    else
    {
        std::cout << "nullptr" << std::endl;
    }
    
}
int main()
{
    test();
}


32 32
110 110

开散列

开散列：也叫哈希桶或拉链法。开散列相比闭散列，可以更加有效的解决哈希冲突，因为其的结构是在哈希表的每一个节点上添加一个链表，所有经过哈希函数计算得出地址的结点直接添加到对应的链表上即可，这样一个地址上就不止可以存放一个元素，而是可以存放无限个，更好的处理了哈希冲突。其结构如下：

要注意虽然哈希桶每个结点下面可以挂无数个结点，但是这里的单链表不易过长，否则每次查找结点都要遍历单链表，性能又会有很大程度的降低，于是我们还是需要利用负载因子进行扩容处理。
对于开散列来说我们还是不得不遍历所有结点然后重新计算地址，但是有一种可以减少消耗的方法。本来我们需要遍历完原哈希表所有结点，然后依次释放原哈希表上每个链表的空间，再在新的哈希表上开辟新空间插入结点，但是这样一释放一申请的举动无异于脱裤子放屁，我们可以直接将原哈希表上的结点连接到新哈希表上，省去释放空间再申请空间的步骤，毕竟链表结点与结点之间本来就不一定是连续的，所以这样的操作替我们节省了很多开销。
这里使用除留余数法实现哈希桶。

#pragma once
#include <iostream>
#include <utility>
#include <vector>
template<class K, class V>
//这里现在存的就是链表结点
//这里我们使用单链表就行了
struct HashNode
{
    HashNode(const std::pair<K, V>& data = std::pair<K, V>())
        :_data(data)
        ,_next(nullptr)
    {
    }
    std::pair<K, V> _data;
    HashNode<K, V>* _next;
};
template<class K, class V>
class HashTable
{
public:
    typedef HashNode<K, V> Node;
    HashTable(size_t n = 10)
        :_size(0)
    {
        _ht.resize(n);
    }
    //插入
    bool Insert(const std::pair<K, V>& data)
    {
        //检查负载因子，超过阈值进行扩容
        CheckCapacity();
        //计算位置
        int index = data.first % _ht.size();
        //遍历单链表
        Node* cur = _ht[index];
        while(cur)
        {
            if(cur->_data.first == data.first)
            {
                return false;
            }
            cur = cur->_next;
        }
        //插入，这里用头插其实比较方便，尾插也可以
        cur = new Node(data);
        cur->_next = _ht[index];
        _ht[index] = cur;
        ++_size;
        return true;
    }
    //查找
    Node* Find(const K& key)
    {
        int index = key % _ht.size();
        Node* cur = _ht[index];
        while(cur)
        {
            if(cur->_data.first == key)
            {
                return cur;
            }
            cur = cur->_next;
        }
        return nullptr;
    }
    //删除
    bool Erase(const K& key)
    {
        int index = key % _ht.size();
        Node* cur = _ht[index];
        Node* parent = nullptr;
        while(cur)
        {
            if(cur->_data.first == key)
            {
                //删除
                if(parent == nullptr)
                {
                    _ht[index] = cur->_next;
                }
                else
                {
                    parent->_next = cur->_next;
                }
                delete cur;
                --_size;
                return true;
            }
            parent = cur;
            cur = cur->_next;
        }
        return false;
    }
    void CheckCapacity()
    {
        //这里的阈值可以设置的稍微高一些，毕竟哈希桶的冲突不会像闭散列呢样严重
        //这里我们设定为插入元素数 >= 哈希表总长度时扩容
        if(_size >= _ht.size())
        {
            //扩容
            size_t newC = _ht.size() == 0 ? 10 : 2 * _ht.size();
            std::vector<Node*> newHt;
            newHt.resize(newC);
            //搬运数据，将原哈希表中的结点连接到新哈希表上
            for(int i = 0; i < _ht.size(); i++)
            {
                Node* cur = _ht[i];
                while(cur)
                {
                    int index = cur->_data.first % newHt.size();
                    Node* next = _ht[i]->_next;
                    //头插进新表
                    cur->_next = newHt[index];
                    newHt[index] = cur;
                    cur = next;
                }
                _ht[i] = nullptr;
            }
            //_ht = newHt;   //这里会进行深拷贝，消耗很大，为了防止深拷贝我们直接交换
            std::swap(_ht, newHt);
        }
    }

private:
    //此时哈希表就相当于一个链表指针数组
    std::vector<Node*> _ht;
    size_t _size;
};

封装

最后我们再将我们写好的哈希桶封装为unordered_map/unordered_set。

hash_bucketMod.hpp:
#pragma once
#include <iostream>
#include <utility>
#include <vector>
//这里现在存的就是链表结点
//这里我们使用单链表就行了
//这里依然为了更好的封装对原有的哈希桶进行了修改
template<class V>
struct HashNode
{
    HashNode(const V& data = V())
        :_data(data)
        ,_next(nullptr)
    {
    }
    V _data;
    HashNode<V>* _next;
};
template<class K, class V, class KeyOfCalue>
class HashTable;
template<class K, class V, class KeyOfValue>
class _HashIterator
{
public:
    typedef HashNode<V> Node;
    typedef _HashIterator<K, V, KeyOfValue> Self;
    typedef HashTable<K, V, KeyOfValue> HTable;
    _HashIterator(Node* node, HTable* pht)
        :_node(node)
        ,_pht(pht)
    {
    }
    V& operator*()
    {
        return _node->_data;
    }
    V* operator->()
    {
        return &_node->_data;
    }
    bool operator!=(const Self& it)
    {
        return _node != it._node;
    }
    Self& operator++()
    {
        if(_node->_next)
        {
            _node = _node->_next;
        }
        else
        {
            KeyOfValue kov;
            //找到下一个非空链表头
            //1、首先确定当前迭代器在哈希表中的位置
            int index = kov(_node->_data) % _pht->_ht.size();
            ++index;
            while(index < _pht->_ht.size())
            {
                if(_pht->_ht[index])
                {
                    _node = _pht->_ht[index];
                    break;
                }
                ++index;
            }
            if(index == _pht->_ht.size())
            {
                _node = nullptr;
            }
        }
        return *this;
    }
private:
    Node* _node;
    HTable* _pht;
};
template<class K, class V, class KeyOfValue>
class HashTable
{
    friend class _HashIterator<K, V, KeyOfValue>;
public:
    typedef HashNode<V> Node;
    typedef _HashIterator<K, V, KeyOfValue> iterator;
    //迭代器相关
    iterator begin()
    {
        for(int i = 0; i < _ht.size(); i++)
        {
            if(_ht[i] != nullptr)
            {
                return iterator(_ht[i], this);
            }
        }
        return iterator(nullptr, this);
    }
    iterator end()
    {
        return iterator(nullptr, this);
    }
    HashTable(size_t n = 10)
        :_size(0)
    {
        _ht.resize(n, nullptr);
    }
    //插入
    std::pair<iterator, bool> Insert(const V& data)
    {
        //检查负载因子，超过阈值进行扩容
        CheckCapacity();
        //计算位置
        KeyOfValue kov;
        int index = kov(data) % _ht.size();
        //遍历单链表
        Node* cur = _ht[index];
        while(cur)
        {
            if(kov(cur->_data) == kov(data))
            {
                return std::make_pair(iterator(cur, this), false);
            }
            cur = cur->_next;
        }
        //插入，这里用头插其实比较方便，尾插也可以
        cur = new Node(data);
        cur->_next = _ht[index];
        _ht[index] = cur;
        ++_size;
        return std::make_pair(iterator(cur, this), true);
    }
    //查找
    Node* Find(const K& key)
    {
        KeyOfValue kov;
        int index = key % _ht.size();
        Node* cur = _ht[index];
        while(cur)
        {
            if(kov(cur->_data) == key)
            {
                return cur;
            }
            cur = cur->_next;
        }
        return nullptr;
    }
    //删除
    bool Erase(const K& key)
    {
        int index = key % _ht.size();
        Node* cur = _ht[index];
        Node* parent = nullptr;
        KeyOfValue kov;
        while(cur)
        {
            if(kov(cur->_data) == key)
            {
                //删除
                if(parent == nullptr)
                {
                    _ht[index] = cur->_next;
                }
                else
                {
                    parent->_next = cur->_next;
                }
                delete cur;
                --_size;
                return true;
            }
            parent = cur;
            cur = cur->_next;
        }
        return false;
    }
    void CheckCapacity()
    {
        //这里的阈值可以设置的稍微高一些，毕竟哈希桶的冲突不会像闭散列呢样严重
        //这里我们设定为插入元素数 >= 哈希表总长度时扩容
        if(_size >= _ht.size())
        {
            //扩容
            size_t newC = _ht.size() == 0 ? 10 : 2 * _ht.size();
            std::vector<Node*> newHt;
            newHt.resize(newC);
            KeyOfValue kov;
            //搬运数据，将原哈希表中的结点连接到新哈希表上
            for(int i = 0; i < _ht.size(); i++)
            {
                Node* cur = _ht[i];
                while(cur)
                {
                    int index = kov(cur->_data) % newHt.size();
                    Node* next = _ht[i]->_next;
                    //头插进新表
                    cur->_next = newHt[index];
                    newHt[index] = cur;
                    cur = next;
                }
                _ht[i] = nullptr;
            }
            //_ht = newHt;   //这里会进行深拷贝，消耗很大，为了防止深拷贝我们直接交换
            std::swap(_ht, newHt);
        }
    }

private:
    //此时哈希表就相当于一个链表指针数组
    std::vector<Node*> _ht;
    size_t _size;
};

unordered_map.hpp:
#pragma once
#include "hash_bucketMod.hpp"
template<class K, class V>
class Unordered_Map
{
    struct MapKeyOfValue
    {
        const K& operator()(const std::pair<K, V>& data)
        {
            return data.first;
        }
    };
public:
    typedef typename HashTable<K, std::pair<K, V>, MapKeyOfValue>::iterator iterator;
    iterator begin()
    {
        return _ht.begin();
    }
    iterator end()
    {
        return _ht.end();
    }
    std::pair<iterator, bool> Insert(const std::pair<K, V>& data)
    {
        return _ht.Insert(data);
    }
    V& operator[](const K& key)
    {
        return (_ht.Insert(std::make_pair(key, V())).first)->second;
    }
private:
    HashTable<K, std::pair<K, V>, MapKeyOfValue> _ht;
};

unordered_set.hpp:
#pragma once
#include "hash_bucketMod.hpp"
template<class K>
class Unordered_set
{
    struct SetKeyOfValue
    {
        const K& operator()(const K& data)
        {
            return data;
        }
    };
public:
    typedef typename HashTable<K, K, SetKeyOfValue>::iterator iterator;
    iterator begin()
    {
        return _ht.begin();
    }
    iterator end()
    {
        return _ht.end();
    }
    std::pair<iterator, bool> Insert(const K& data)
    {
        return _ht.Insert(data);
    }
private:
    HashTable<K, K, SetKeyOfValue> _ht;
};

test.cpp:
#include "unordered_map.hpp"
#include "unordered_set.hpp"
void test3()
{
    Unordered_Map<int, int> umap;
    umap.Insert(std::make_pair(1, 1));
    umap.Insert(std::make_pair(5, 5));
    umap.Insert(std::make_pair(6, 6));
    umap.Insert(std::make_pair(9, 9));
    for(auto e : umap)
    {
        std::cout << e.first << " " << e.second << std::endl;
    }
    umap[6] = 11;
    umap[10] = 10;
    umap[25] = 1;
    std::cout << std::endl;
    for (auto e : umap)
    {
        std::cout << e.first << " " << e.second << std::endl;
    }
    Unordered_set<int> uset;
    uset.Insert(1);
    uset.Insert(5);
    uset.Insert(6);
    uset.Insert(9);
    std::cout << std::endl;
    for (auto e : uset)
    {
        std::cout << e << std::endl;
    }
}
int main()
{
    test3();
}


1 1
5 5
6 6
9 9

10 10
1 1
25 1
5 5
6 11
9 9

1
5
6
9

从结果上来看我们的实现目前成功了。

总结

通过这两章对关联式容器两种底层原理的探索和实现我们可以总结出以下结论。
1、普通版本的map/set底层使用的红黑树可以将搜索、插入和删除的操作时间复杂度优化为OlogN。
2、要求map/set中的key必须是可以比较的，不然就无法达成二叉搜索树中需要比较大小的操作，那么就无法成立红黑树。
3、unordered系列的map/set底层结构是一个哈希桶，可以将搜索、插入和删除的操作优化为O1，但是在每次需要增容的时候则不得不需要执行一次On的遍历操作，代价极大。
4、unordered系列的map/set插入数据的key要求必须有合适的哈希函数能够对其进行哈希，否则将无法计算出合适的下标存储数据，例如我们实现的时候写死了哈希函数，因此其只能存储key可以取模的数据，而如果key是一个字符串我们将束手无策，不过也有字符串的哈希方法，会将字符串转为整数在进行哈希，这里不再深入讨论。
5、map/set可以对数据根据key进行排序，且每次操作的事件复杂度十分平均都为OlogN；unordered_map/unordered_set不会对数据进行排序，虽然大多数情况下的操作都是O1的，但是一旦在插入时遇到增容的情况，则会造成极大消耗从而变成ON的时间复杂度，同时unordered系列有可能会消耗更多的内存空间。

【DS】栈的压入、弹出序列

发表于 2019-10-25 | 分类于数据结构

字数统计: 553

栈的压入、弹出序列

题目

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

题解

这道题我们可以使用笨点的方法列举出所有弹出序列然乎一一比较判断，但是这样的实现方法事件复杂度很高，并不高效，于是采用以下的解法，只需要O(n)的时间复杂度。

1、首先我们初始化入栈序列和出栈序列和一个空栈，并用两个指针ptr1 ptr2首先指向两个序列的第一个元素。

2、只要栈为空或者当前栈顶元素与出栈序列中ptr2所指的元素不相同，则将入栈序列中ptr1所指的元素压入栈，并将ptr1后移。

3、如果当前栈顶元素与出栈序列中ptr2所指元素相同，则将当前栈顶元素出栈，并将ptr2后移。

4、重复第2第3步，如果ptr2可以遍历完出栈序列，则说明出栈序列是该栈的一个弹出顺序。如果ptr1中的入栈元素已经全部压入栈但是栈顶元素依然与出栈序列中ptr2所指元素不相同，还需要入栈，则说明出栈序列不是该栈的一个弹出顺序。

代码实现

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        int pushi = 0, popi = 0;
        stack<int> sta;
        while(popi < popV.size())
        {
            if(sta.empty() || (sta.top() != popV[popi]))
            {
                if(pushi < pushV.size())
                {
                    sta.push(pushV[pushi]);
                    pushi++;
                }
                else
                {
                    return false;
                }
            }
            else
            {
                sta.pop();
                popi++;
            }
        }
        return true;
    }
};

【Linux】请问下面的程序一共输出多少个“-”？

发表于 2019-10-24 | 分类于 Linux

字数统计: 1.1k

请问下面的程序一共输出多少个“-”？

int main(void)
{
    int i;
    for (i = 0; i < 2; i++) { 
        fork(); 
        printf("-"); 
    } 
    return 0; 
}

运行结果

1 2	[misaki@localhost test]$ ./main --------

结果分析

为啥会有8个’-‘呢？我们把这个程序稍微修改一下再看下结果。

#include <stdio.h>
#include <unistd.h>
int main(void)
{
  int i;
  for (i = 0; i < 2; i++) 
  {                          
    fork();      
    printf("-");   
    fflush(stdout);
  }        
  sleep(1);
  return 0;
} 



[misaki@localhost test]$ ./main
------

现在又变成了6个’-‘，我们先从以上这段程序开始分析。我们分别打印各个进程的pid和他们的ppid来让我们看的更清楚一些，并且查看以下进程树。

#include <stdio.h>
#include <unistd.h>
int main(void)
{
  int i;
  for (i = 0; i < 2; i++)
  {
    fork();
    printf("ppid:%d, pid:%d\n", getppid(), getpid());
    fflush(stdout);
  }
  sleep(10);                                         
  return 0;
}


[misaki@localhost test]$ ./main
ppid:2221, pid:4846
ppid:4846, pid:4847
ppid:2221, pid:4846
ppid:4846, pid:4848
ppid:4846, pid:4847
ppid:4847, pid:4849


[misaki@localhost ~]$ pstree -ap misaki
sshd,2220
  ├─bash,2221
  │   └─main,4846
  │       ├─main,4847
  │       │   └─main,4849
  │       └─main,4848
  └─bash,3571
      └─pstree,4850 -ap misaki

fork()执行后子进程会赋值父进程的代码段，以及PCB中的部分数据其中包括程序计数器，上下文数据等来保证自己会按照父进程当前的执行流和代码继续执行下去。
我们的父进程4846进入循环后首先创建了子进程4847然后打印一次，然后再次执行一次循环有创建了一个子进程4848然后又打印一次，至此父进程执行完毕循环进入sleep()，于是父进程会打印两次。
子进程4847在创建后先打印一次，然后继续执行流再次执行循环又会创建一个子进程4849，然后再打印一次，随后循环结束，于是子进程4847也会打印两次。
子进程4848是在父进程4846第二次循环创建出来的，于是只打印一次退出循环，子进程4848只会打印一次。
孙子进程4849是在子进程4847第二次循环创建出来的，于是也只打印一次便结束了循环，子进程4849也只打印一次。
至此一共打印六次全部完毕。
我们回到最初的问题，那么这道题为什么会是8次，而我每次打印后刷新一次缓冲区结果就变成了6次.
其实我们的子进程会复制父进程的缓冲区。关于缓冲区，Unix下的设备块设备和字符设备的概念，所谓块设备，就是以一块一块的数据存取的设备，字符设备是一次存取一个字符的设备。磁盘、内存都是块设备，字符设备如键盘和串口。块设备一般都有缓存，而字符设备一般都没有缓存。
程序遇到“\n”，或是EOF，或是缓冲区满，或是文件描述符关闭，或是主动flush，或是程序退出，就会把数据刷出缓冲区。需要注意的是，标准输出是行缓冲，所以遇到“\n”的时候会刷出缓冲区，但对于磁盘这个块设备来说，“\n”并不会引起缓冲区刷出的动作，那是全缓冲，你可以使用setvbuf来设置缓冲区大小，或是用fflush刷缓存。
我们的子进程在创建时复制了父进程的缓冲区，而此时的父进程的标准输入的缓冲区并没有刷新，就会导致在printf后面创建的子进程复制的缓冲区中还存有父进程打印的’-‘，以上的例子中的4848和4849这两个进程如果在没有刷新缓冲区的情况下就会复制上父进程输出的’-‘导致多打出两个’-‘，于是这样就解释的通为什么会打印8个了。
这道题还是有一点坑的，需要对fork()创建子进程的底层实现有清楚的认识和了解，也需要对缓冲区相关的知识有一定了解。

【Cpp】第十六章-关联式容器

发表于 2019-10-21 | 分类于 Cpp

字数统计: 12.6k

关联式容器

STL中关联式容器有以下几种map/set/multimap/multiset/unordered_map/unordered_set/unordered_multimap/unordered_multiset，所谓关联式容器即他们内部存储的是具有关联性的key-value形式的键值对。本文先从他们的基础使用开始讲起，逐渐深入到底层实现原理，并且最后从二叉搜索树到红黑树再到哈希桶逐步手动实现各个版本的关联式容器，~~我已经预感到了这将是一篇非常之长的博客，但是为了知识的连贯性我并不打算将他们分开。~~

pair

关联式容器中诸如map都可以通过一个key来查找value，十分类似于查字典，这就得益于关联式容器中所存储的数据结构都是由一个一个键值对组成，因此我们对其的操作就更像是在查字典，要了解关联式容器我们就得先了解其内部存储的键值对的结构pair。
我们首先看一下SGI版本中对键值对pair的定义。

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) 
    {}
};

pair的结构非常简单，简单来说其中就是存储了一个键值对，first对应key值，second对应value，同时提供了两个构造函数，仅此而已，不过不要忘记这个结构，在关联式容器的使用中，pair的使用也是必不可少。通常我们可以使用make_pair()函数快速帮助我们构造一个pair。

map

map方便我们存储映射，并且会自动帮助我们根据key排序。

模板参数

template <class Key,                                  // key的类型
          class T,                                    // value的类型
          class Compare = less<Key>,                  // 比较器
          class Alloc = allocator<pair<const Key, T>> // 空间配置器
          >
class map;

Key和T很好理解，那么这里的比较器和空间配置器是什么呢？Compare比较器是用来使用在容器内部辅助完成数据排序的，默认按照小于来比较，一般情况下不需要特殊比较方式的话不需要传入，我们也可以利用仿函数自定义比较方式。对于比较器我们之前在priority_queue中也有使用过。关于空间配置器我们会发现很多容器模板中都存在这个参数，容器通过使用空间配置器申请底层空间，我们会在之后的章节进行整理，一般情况下也不需要我们手动传入。

构造函数

explicit map(const key_compare &comp = key_compare(),
             const allocator_type &alloc = allocator_type());//创建一个空map

template <class InputIterator>
map(InputIterator first, InputIterator last,
    const key_compare &comp = key_compare(),
    const allocator_type &alloc = allocator_type());//用一个迭代器区间中的数据构造map
    
map (const map& x);//拷贝构造

迭代器相关

iterator begin();                      //返回第一个元素的位置
iterator end();                        //返回最后一个元素的下一个位置
const_iterator begin() const;          //返回第一个元素的const迭代器
const_iterator end() const;            //返回最后一个元素下一个位置的const迭代器
reverse_iterator rbegin();             //返回第一个元素位置的反向迭代器即rend
reverse_iterator rend();               //返回最后一个元素下一个位置的反向迭代器即 rbegin
const_reverse_iterator rbegin() const; //返回第一个元素位置的const反向迭代器即rend
const_reverse_iterator rend() const;   //返回最后一元素下一个位置的反向迭代器即rbegin

元素修改

pair<iterator, bool> insert(const value_type &x);        //在map中插入键值对x，注意x是一个键值对，返回 值也是键值对：iterator代表新插入元素的位置， bool代表释放插入成功
iterator insert(iterator position, const value_type &x); //在position位置插入值为x的键值对，返回该键值对 在map中的位置，注意：元素不一定必须插在 position位置，该位置只是一个参考
template <class InputIterator>
void insert(InputIterator first, InputIterator last); //在map中插入[ﬁrst, last)区间中的元素
void erase(iterator position);                        //删除position位置上的元素
size_type erase(const key_type &x);                   //删除键值为x的元素
void erase(iterator ﬁrst, iterator last);             //删除[ﬁrst, last)区间中的元素
void swap(map<Key, T, Compare, Allocator> &mp);       //交换两个map中的元素
void clear();                                         //将map中的元素清空
iterator ﬁnd(const key_type &x);                      //在map中插入key为x的元素，找到返回该元素的位 置的迭代器，否则返回end
const_iterator ﬁnd(const key_type &x) const;          //在map中插入key为x的元素，找到返回该元素的位 置的const迭代器，否则返回cend
size_type count(const key_type &x) const;             //返回key为x的键值在map中的个数，注意map中 key是唯一的，因此该函数的返回值要么为0，要么 为1，因此也可以用该函数来检测一个key是否在 map中

要注意map中一个key值仅存在一份，如果我们重复插入key相同的键值对，则会插入失败，并且insert的第一个重载要求插入的元素是一个pair并且返回的也是一个pair，返回的pair的类型为std::pair<std::map::iterator, bool>，第一个迭代器参数标识了结点插入的位置，如果已经存在该节点，则返回map中该节点的迭代器，如果不存在则插入新结点后返回新插入的结点的迭代器，bool标识了插入是否成功，也就是说无论如何当我们插入一个节点时返回的pair中都会给我们返回一个key对应的节点的迭代器。

容量及元素访问

1
2
3

bool empty() const;                         //检测map中的元素是否为空，是返回true，否则 返回false
size_type size() const;                     //返回map中有效元素的个数
mapped_type &operator[](const key_type &k); //返回去key对应的value

这里要注意map也重载了operator[]，那么如果我们去访问一个不存在的值会怎样呢？

#include <iostream>
#include <string>
#include <map>
int main()
{
    std::map<std::string, int> map;//空map
    //访问不存在的key值
    map["1"] = 1;
    map["2"] = 2;
    for(auto e : map)
    {
        std::cout << e.first << " " << e.second << std::endl;
    }
}


1 1
2 2

我们会发现map自动在找不到这个节点的时候会自动插入新的节点，并且返回其value的应用，这里贴出其底层实现。

1	(*((this->insert(make_pair(k,mapped_type()))).first)).second

对只有这么一句话，我们应该就已经明白了为什么它可以帮助我们插入新节点了，因为它在底层调用了insert方法，insert方法之前已经说过他的返回值是一个特定的pair，其中的key包含了对应结点的迭代器，因此我们也就可以方便的取到对应结点的value并将其返回出来。

总结

1、map中的元素是键值对的形式存在的。
2、map中key值是唯一的，并且不能修改key只。
3、map底层是一个红黑树，因此查找效率较高OlogN。
4、map会自动根据key进行排序，当然这也是因为底层是一个红黑树。
5、默认按照小于的方式进行排序，排序结果升序。
6、支持[]操作，在底层调用insert方法。

multimap

map中的元素key值不允许相同，由此便延伸出了multimap，multimap中允许元素key值相同，其他与map并没有太大区别。因此接口不再介绍，不过唯一要注意的是insert相关的接口永远都会插入新的元素，并不会存在因为key值存在而插入失败的情况。

set

set在上层使用时我们很容易将其看成是一个会自动排序和去重的vector但是实际上在底层实现大有不同，这也是它被称为关联式容器的原因。其底层依然存储着一个pair不过其中key值和value值都是相同的即<value, value>，并且和map一样它的key一样是不允许修改的，这也就导致了set中的元素是不可修改的，只允许插入和删除。set插入元素时也是只需提供value即可。

模板参数

template <class T,                   // value类型
          class Compare = less<T>,   // 比较器
          class Alloc = allocator<T> // 空间配置器
          >
class set;

构造函数

1
2
3

set(const Compare &comp = Compare(), const Allocator & = Allocator());                                         //构造空的set
set(InputIterator ﬁrst, InputIterator last, const Compare &comp = Compare(), const Allocator & = Allocator()); //用[ﬁrst, last)区间 中的元素构造set
set(const set<Key, Compare, Allocator> &x);

迭代器相关

iterator begin();                       //返回set中起始位置元素的迭代器
iterator end();                         //返回set中最后一个元素后面的迭代器
const_iterator cbegin() const;          //返回set中起始位置元素的const迭代器
const_iterator cend() const;            //返回set中最后一个元素后面的const迭代器
reverse_iterator rbegin();              //返回set第一个元素的反向迭代器，即end
reverse_iterator rend();                //返回set最后一个元素下一个位置的反向迭代器，即 rbegin
const_reverse_iterator crbegin() const; //返回set第一个元素的反向const迭代器，即cend
const_reverse_iterator crend() const;   //返回set最后一个元素下一个位置的反向const迭代器， 即crbegin

容量和修改

bool empty() const;                                      //检测set是否为空，空返回true，否则返回true
size_type size() const;                                  //返回set中有效元素的个数
pair<iterator, bool> insert(const value_type &x);        //在set中插入元素x，实际插入的是<x, x>构成的键值对， 如果插入成功，返回<该元素在set中的位置，true>,如果 插入失败，说明x在set中已经存在，返回<x在set中的位 置，false>
iterator insert(iterator position, const value_type &x); //在set的position位置插入x，实际插入的是<x, x>构成的 键值对，注意：position位置只是参考，x最终不一定在该 位置
template <class InputIterator>
void insert(InputIterator ﬁrst, InputIterator last); //在set中插入[ﬁrst, last)区间中的元素
void erase(iterator position);                       //删除set中position位置上的元素
size_type erase(const key_type &x);                  //删除set中值为x的元素，返回删除的元素的个数
void erase(iterator ﬁrst, iterator last);            //删除set中[ﬁrst, last)区间中的元素
void swap(set<Key, Compare, Allocator> &st);         //交换set中的元素
void clear();                                        //将set中的元素清空
iterator ﬁnd(const key_type &x) const;               //返回set中值为x的元素的位置
size_type count(const key_type &x) const;            //返回set中值为x的元素的个数

set的接口与map的接口几乎没有差别，不同的是set的迭代器取值直接*it即可，并没有map中first和second的取值方式了。取消了[]操作，因为set的key和value一致并且不允许修改于是这个接口也不再有存在的必要。

总结

1、set和map几乎一致，不同是value和key值相同，因此不能修改。
2、底层依然是一个红黑树进行实现，因此可以实现自动排序，查找速度也较快能够达到OlogN>
3、set插入元素只需提供value即可。
4、set中的元素不可重复，因此可以达到驱虫的效果。
5、set中的元素默认按照小于的方式排序，结果升序。
6、set中的依然存储键值对pair，知识key值与value值相同。

multiset

multiset与set的区别与multimap与map的区别相同，set中不允许存储相同的元素而multiset中允许存储，仅此而已。

底层实现

以上介绍的几种关联式容器底层都是一颗红黑树，什么是红黑树呢，这就得从BS树说起，于是接下来我们着重底层实现，从BS Tree开始逐步升级直到最终实现红黑树，并用其封装成map/set。

BS Tree

什么是BS Tree

BS Tree即二叉搜索树，在一个二叉树的基础上使其满足某些要求，让其更加便于搜索。那么一棵二叉搜索树要满足哪些要求呢？
1、若它的左子树不为空，则左子树上所有节点的值都小于根节点的值。
2、若它的右子树不为空，则右子树上所有节点的值都大于根节点的值。
3、它的左右子树也分别为二叉搜索树。
中序遍历二叉搜索树结果即为有序序列。如下即为一颗二叉搜搜树。

BS Tree

二叉搜索树的插入思路就是用一个cur结点和parent结点找到目标插入位置和其夫结点插入即可，位置的找法就是key值比cur的key大则往左子树走，小则往右子树走，相等则失败，查找也是相同的思路，而删除略微麻烦一些，要分为三种情况进行删除，有两个孩子的结点较难删除，需要找到合适的值进行替换再删除。

实现

#pragma once
#include <iostream>
#include <utility>
template<class K, class V>
//结点
struct BSTreeNode
{
    BSTreeNode(const std::pair<K, V>& kv)
        :_left(nullptr)
        ,_right(nullptr)
        ,_parent(nullptr)
        ,_kv(kv)
    {

    }
    std::pair<K, V> _kv;
    BSTreeNode<K, V>* _left;
    BSTreeNode<K, V>* _right;
    //BSTree可以暂时先不使用_parent
    BSTreeNode<K, V>* _parent;
};
//二叉搜索树
template<class K, class V>
class BSTree
{
    typedef BSTreeNode<K, V> Node;
public:
    //这里先暂时忽略拷贝构造，析构，赋值的问题
    BSTree()
        :_root(nullptr)
    {
    }
    //插入结点
    bool Insert(const std::pair<K, V>& kv)
    {
        //插入第一个结点
        if(_root == nullptr)
        {
            _root = new Node(kv);
            return true;
        }
        Node* parent = nullptr;
        Node* cur = _root;
        while(cur)
        {
            //比当前结点小，插在左边
            if(cur->_kv.first > kv.first)
            {
                //记录上一个结点
                parent = cur;
                cur = cur->_left;
            }
            //比当前结点大，插在右边
            else if(cur->_kv.first < kv.first)
            {
                //记录上一个结点
                parent = cur;
                cur = cur->_right;
            }
            //相等则说明已存在，插入失败
            else
            {
                return false;
            }
        }
        cur = new Node(kv);
        if(parent->_kv.first < kv.first)
        {
            parent->_right = cur;
        }
        else
        {
            parent->_left = cur;
        }
        return true;
    }
    //查找，返回结点的指针
    Node* Find(const K& key)
    {
        Node* cur = _root;
        while(cur)
        {
            if(cur->_kv.first < key)
            {
                cur = cur->_right;
            }
            else if(cur->_kv.first > key)
            {
                cur = cur->_left;
            }
            else
            {
                return cur;
            }
        }
        return nullptr;
    }
    //删除结点
    bool Remove(const K& key)
    {
        //1、叶子结点，直接删除，父结点对应指针指向空
        //2、有一个孩子，如果左为空，父结点对应指针指向右，如果右为空，父结点对应指针指向左
        //3、找右子树最左结点或左子树最右结点替代他，然后删除替代结点
        Node* cur = _root;
        Node* parent = nullptr;
        while(cur)
        {
            if(cur->_kv.first < key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if(cur->_kv.first > key)
            {
                parent = cur;
                cur = cur->_left;
            }
            //找到相等可以删除此结点了
            else
            {
                //只有0/1个孩子
                //对于只有一个孩子或者没有孩子的结点来说要删除的结点就是cur
                Node* del = cur;
                //要删除的结点左孩子为空
                if(cur->_left == nullptr)
                {
                    
                    //如果要删除的是根结点，父结点为空
                    if(parent == nullptr)
                    {
                        //直接改变根
                        _root = cur->_right;
                        return true;
                    }
                    //判断要删除的结点是其父结点的左孩子还是右孩子
                    if(cur == parent->_left)
                    {
                        parent->_left = cur->_right;
                    }
                    else
                    {
                        parent->_right = cur->_right;
                    }
                }
                //要删除的结点右孩子为空
                else if(cur->_right == nullptr)
                {
                    //如果要删除的是根结点，父结点为空
                    if(parent == nullptr)
                    {
                        _root = cur->_left;
                        return true;
                    }
                    //判断要删除的结点是其父结点的左孩子还是右孩子
                    if(cur == parent->_left)
                    {
                        parent->_left = cur->_left;
                    }
                    else
                    {
                        parent->_right = cur->_left;
                    }
                }
                //有两个孩子，找右树的最左结点
                else
                {
                    //找到右树的最左结点和其父结点
                    Node* rpParent = cur;
                    Node* replace = cur->_right;
                    while(replace->_left)
                    {
                        rpParent = replace;
                        replace = replace->_left;
                    }
                    //此时要释放的结点是替代结点
                    del = replace;
                    //找到后开始替换
                    cur->_kv = replace->_kv;
                    //替换结点不一定一定是其父结点的左结点，因此做一次判断
                    if(rpParent->_left == replace)
                    {
                        rpParent->_left = replace->_right;
                    }
                    else
                    {
                        rpParent->_right = replace->_right;
                    }
                    
                }
                //释放结点
                delete del;
                std::cout << "del success" << std::endl;
                return true;
            }
        }
        return false;
    }
    //中序遍历
    void InOrder()
    {
        _InOrder(_root);
        std::cout << std::endl;
    }
private:
    void _InOrder(Node* root)
    {
        if(root == nullptr)
        {
            return;
        }
        _InOrder(root->_left);
        std::cout << root->_kv.first << " ";
        _InOrder(root->_right);
    }
private:
    Node* _root;

};

二叉搜索树的搜索速度在理想状况下可以达到OlogN，此时二叉树为一棵完全二叉树，如果是一颗满二叉树更好，因为每次搜索都可以淘汰一半的数据。但是往往并不是理想的，如果插入的树本身就是有序的，则使二叉树可能会变成一条链，二叉树会完全失去平衡，此时的搜索便是ON的。为了让二叉树尽可能保持平衡，使其尽可能成为一颗完全二叉树，所有状况下都能达到理想状态，优化时间复杂度，于是我们需要在改变树的状态的时候维持它自身的平衡，便出现了AVLTree。

AVLTree

什么是AVLTree

AVLTree也叫高度平衡二叉搜索树，其是对BSTree的一个改进，为了保证其在高度上的平衡性，使其可以尽可能的达到理想状态中的完全二叉树的形式，AVLTree引入了平衡因子的概念，平衡因子即左右子树的高度差。AVLTree要求树上每一个结点的平衡因子都不能大于1，其它要求与BSTree一致。
这样一来AVLTree上任何状态下的操作都将与理想状态下BSTree的操作有着同样的时间复杂度OlogN，可以说AVLTree的存在就是为了任何时候都可以将BSTree限定在理想状态。

AVLTree平衡因子的更新

我们这里都先假设平衡因子bf = 右子树高度 - 左子树高度。AVLTree引入平衡因子概念后我们在插入一个节点后必须要更新整棵树的平衡因子，那么我们该如何更新才能让整棵树的平衡因子能重新回到正确的状态下呢？
以下是一棵AVLTree，我用蓝色标识了每个结点的bf。

AVLTree

接下来我们假设插入7.5，或者任意一个比7大比8小的值，我们可以发现新插入的结点bf == 0，因为其没有左右孩子，所以并不受影响。新结点的插入只会影响它的祖先们，因此我们必须依次去更新他们的祖先。这里我们首当其冲更新了插入结点的父亲。更新其父亲的bf规律很好总结，如果我们插入在父亲的左则bf = bf - 1，插入在父亲的右则bf = bf + 1。此时其父亲bf == 0。

AVLTree

在一次更新后我们是否还应该继续更新？当然，我们必须迭代上去继续更新，让cur = parent, parent = parent->parent。但是我们再次按照刚才的规律更新会发现7这个元素结点的平衡因子会被更新为2，但是这样的更新明显是错误的，因为虽然插入的新节点但7的右子树高度并没有增高，我们并不应该更新它，那么我们的更新该到何时为止呢？

AVLTree

经过实验我们可以总结出以下几种parent更新bf后的情况，由此来判断是否需要进一步更新或者执行其他操作：
1、|bf| == 0则说明此时当前父结点所在的子树高度并没有增加，我们自然也不需要再迭代上去继续更新其他祖先。
2、parent == nullptr，此时父结点已经指向空说明我们已经更新完了插入结点的所有祖先，没有祖先可以继续更新，这是更新的最坏情况。
3、|bf| == 1，此时当前父结点所在子树的高度增加了，但是父结点bf依然符合AVLTree的要求，我们需要继续向上迭代更新其祖先。
4、|bf| == 2，此时当前父结点所在子树的高度增加了，并且父结点bf不再符合AVLTree的要求，我们就此停止不再更新，并且利用旋转来解决眼下的问题。

AVLTree的旋转

我们在更新平衡因子的过程中难免会遇到bf == 2的情况，此时这棵树不再满足AVLTree的要求，当然我们也有方法可以使其继续成为一棵AVLTree，就是旋转。
旋转分为一共四种情况，以下一一列举。

左单旋

使用场景：

AVLTree

AVLTree

由此我们可以归纳出这种情况的抽象图来。
AVLTree

右单旋

右单旋与左单旋类似：

AVLTree

抽象图。
AVLTree

先右旋再左旋

使用场景：

AVLTree

抽象图：

AVLTree

但是这里要注意，两次旋转后结点的平衡因子更新并不像单旋呢么简单，需要根据实际情况进行判断，具体请看代码中的实现。

先左旋再右旋

与先右旋再左旋类似，直接给出抽象图：

AVLTree

但是这里要注意，两次旋转后结点的平衡因子更新并不像单旋呢么简单，需要根据实际情况进行判断，具体请看代码中的实现。

旋转场景

四种旋转搞明白后，AVLTree的调整就只剩最后一件事要考虑，那就是我们什么情况下应该使用哪种旋转来调整呢？
回到我们用cur和parent来更新插入结点祖先的平衡因子。以下我们分为四种情况：
1、parent->_bf == 2 && cur->_bf == 1说明parent右子树高，并且cur的右子树也高，说明此时结点插入在了parent右子树的外侧，我们左单旋即可。
2、parent->bf == 2 && cur->bf == -1说明parent右子树高，但是cur左子树高，说明此时结点插入在了parent右子树的内侧，我们要先右旋再左旋。
3、parent->bf == -2 && cur->bf == -1说明此时parent左子树高，cur也是左子树高，则结点插入在了parent左子树的外侧，右单旋即可。
4、parent->bf == -2 && cur->bf == 1说明此时parent左子树高，但是cur右子树高，说明此时结点插入在了parent左子树的内侧，我们要先左旋再右旋。

实现

这里仅仅实现了AVLTree的插入，删除与插入类似，需要用到BSTree的删除思想并且和AVLTree的插入中的调整平衡的思想相结合来实现。
直接上代码。

#pragma once
#include <iostream>
#include <utility>
#include <assert.h>
//结点
template<class K, class V>
struct AVLTreeNode
{
    AVLTreeNode(const std::pair<K, V>& kv)
        :_kv(kv)
        ,_left(nullptr)
        ,_right(nullptr)
        ,_parent(nullptr)
        ,_bf(0)
    {}
    std::pair<K, V> _kv;
    AVLTreeNode<K, V>* _left;
    AVLTreeNode<K, V>* _right;
    AVLTreeNode<K, V>* _parent;
    int _bf; //平衡因子 = 右子树高度 - 左子树高度
};
template<class K, class V>
class AVLTree
{
    typedef AVLTreeNode<K, V> Node;
public:
    bool Insert(const std::pair<K, V>& kv)
    {
        //插入结点，思路与BSTree一致，额外需要加入更新平衡因子
        //插入的为第一个结点
        if(_root == nullptr)
        {
            _root = new Node(kv);
            _root->_bf = 0;
            return true;
        }
        Node* cur = _root;
        Node* parent = nullptr;
        while(cur)
        {
            if(cur->_kv.first < kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if(cur->_kv.first > kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return false;
            }
        }
        cur = new Node(kv);
        if(parent->_kv.first < kv.first)
        {
            cur->_parent = parent;
            parent->_right = cur;
        }
        else
        {
            cur->_parent = parent;
            parent->_left = cur;
        }
        //调整平衡
        //1、更新平衡因子
        //新增在左，父亲bf - 1，新增在右，父亲bf + 1
        //如果父亲的更新后|bf|:
        //|bf| == 0 || 父结点为空时停止更新
        //因为bf更新为0则说明当前父亲所在子树此时的高度并未发生变化，父结点为空说明此时更新完了整棵树
        //|bf| == 2也停止更新，及时调整，旋转处理
        //|bf| == 1则继续向上更新
        while(parent)
        {
            if(cur == parent->_right)
            {
                parent->_bf++;
            }
            else
            {
                parent->_bf--;
            }
            //|bf| == 0
            if(parent->_bf == 0)//更新完成
            {
                break;
            }
            else if(abs(parent->_bf) == 1)//继续向上更新
            {
                cur = parent;
                parent = parent->_parent;
            }
            else if(abs(parent->_bf) == 2)//不满足AVLTree要求及时旋转调整
            {
                //2、旋转
                if(parent->_bf == 2)
                {
                    if(cur->_bf == 1)
                    {
                        RotateL(parent);
                    }
                    else if(cur->_bf == -1)
                    {
                        RotateRL(parent);
                    }
                }
                else if(parent->_bf == -2)
                {
                    if(cur->_bf == -1)
                    {
                        RotateR(parent);
                    }
                    else if(cur->_bf == 1)
                    {
                        RotateLR(parent);
                    }
                }
                break;//调整完一定要记着break
            }
            else//在三种情况外，说明出现问题
            {
                assert(false);
            }
        }
        return true;
    }
    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = parent->_right->_left;

        parent->_right = subRL;
        if(subRL)
        {
            subRL->_parent = parent;
        }
        subR->_left = parent;
        Node* ppNode = parent->_parent;
        parent->_parent = subR;
        //根
        if(ppNode == nullptr)
        {
            _root = subR;
            subR->_parent = nullptr;
        }
        else
        {
            if(ppNode->_right == parent)
            {
                ppNode->_right = subR;
            }
            else
            {
                ppNode->_left = subR;
            }
            subR->_parent = ppNode;
        }
        //更新平衡因子
        subR->_bf = parent->_bf = 0;
    }
    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = parent->_left->_right;

        parent->_left = subLR;
        if(subLR)//subLR可能会为空，当h == 0时subLR为空
        {
            subLR->_parent = parent;
        }

        subL->_right = parent;//subL不可能为空
        //记录下parent原来的父结点，为了方便parent移动可以找到这棵子树的父结点
        Node* ppNode = parent->_parent;
        parent->_parent = subL;
        //更新这棵子树的新父结点subL与其父结点的连接
        if(ppNode == nullptr)//如果子树的父结点为空则说明parent原本是整棵树的根节点
        {
            _root = subL;
            _root->_parent = nullptr;
        }
        else
        {
            if(ppNode->_right == parent)
            {
                ppNode->_right = subL;
            }
            else
            {
                ppNode->_left = subL;
            }
            subL->_parent = ppNode;
        }
        parent->_bf = subL->_bf = 0;
    }
    //先左旋再右旋
    void RotateLR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        //保存subRL的平衡因子，之后要根据这个判断parent和subR的平衡因子分别更新为多少
        int bf = subLR->_bf;

        RotateL(parent->_left);
        RotateR(parent);
        //注意这里双旋过后父结点的平衡因子不一定会为0
        if(bf == 0)
        {
            parent->_bf = subLR->_bf = subL->_bf = 0;
        }
        else if(bf == 1)
        {
            subL->_bf = -1;
            parent->_bf = 0;
            subLR->_bf = 0;
        }
        else if(bf == -1)
        {
            parent->_bf = 1;
            subL->_bf = 0;
            subLR->_bf = 0;
        }

    }
    //先右旋再左旋
    void RotateRL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        //保存subRL的平衡因子，之后要根据这个判断parent和subR的平衡因子分别更新为多少
        int bf = subRL->_bf;
        RotateR(parent->_right);
        RotateL(parent);
        //注意这里双旋过后父结点的平衡因子不一定会为0
        //这里三个结点的平衡因子更新要根据新节点到底插在哪里来决定
        if(bf == 0)//此时说明subRL为新增结点
        {
            parent->_bf = subRL->_bf = subR->_bf = 0;
        }
        else if(bf == 1)//此时说明新增节点插在c树上
        {
            subR->_bf = 0;
            parent->_bf = -1;
            subRL->_bf = 0;
        }
        else if(bf == -1)//此时说明新增结点插在b树上
        {
            parent->_bf = 0;
            subR->_bf = 1;
            subRL->_bf = 0;
        }
    }
    //中序
    void InOrder()
    {
        _InOrder(_root);
        std::cout << std::endl;
    }
    //为了判定它是一棵平衡树我们写一个求树高度的函数
    int _Height(Node* root)
    {
        if(root == nullptr)
        {
            return 0;
        }
        int leftHeight = _Height(root->_left);
        int rightHeight = _Height(root->_right);
        return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
    }
    //判断这是否是一颗平衡二叉树
    bool IsBalance()
    {
        return _IsBalance(_root);
    }
    bool _IsBalance(Node* root)
    {
        if(root == nullptr)
        {
            return true;
        }
        int leftHeight = _Height(root->_left);
        int rightHeight = _Height(root->_right);
        //也有可能会出现平衡因子更新错误的情况，这里再做二次判断
        if(rightHeight - leftHeight != root->_bf)
        {
            std::cout << root->_kv.first << " is error" << std::endl;
        }
        return (abs(leftHeight - rightHeight) < 2) && _IsBalance(root->_left) && _IsBalance(root->_right);
    }
private:
    void _InOrder(Node* parent)
    {
        if(parent == nullptr)
        {
            return;
        }
        _InOrder(parent->_left);
        std::cout << parent->_kv.first << " ";
        _InOrder(parent->_right);
    }
    Node* _root = nullptr;
};
void TestAVLTree()
{
    AVLTree<int, int> t;
    int a[] = {16, 3, 7, 11, 9, 26, 18, 14, 15};
    int b[] = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14};
    for(auto e : b)
    {
        t.Insert(std::make_pair(e, e));
    }
    t.InOrder();
    //验证是否平衡
    std::cout << t.IsBalance() << std::endl;
}


在主函数中调用TestAVLTree()
1 2 3 4 5 6 7 14 15 16
1

因为AVLTree总能通过旋转来调节自身的平衡，使自己变成一棵近完全二叉树以追求搜索二叉树的理想状态，因此它在搜索上的时间复杂度确实得到了极大的改进，可以一直维持在OlogN，但是这棵树它虽然近乎完美但是依然达不到要求，首先的原因就是它的调整，可以说调整虽然加快了它的搜索过程，但是也正是调整使它变得更为复杂。我们在根部插入新结点时，最坏情况下我们要从叶子调整到根，它的调整实在是太多了。其次，它的实现也因为调整变得十分复杂繁琐，虽然我们希望一棵BSTree搜索起来尽可能追求理想状态，但是这样的调整未免付出的代价也有点过大了。于是便有了接下来的RBTree的诞生。

RBTree

什么是RBTRee

RBTree即红黑树，它相比AVLTree更为简单，并且它大大减少了要调整的次数，在追求理想状态的过程中与调整次数达成了妥协，这也使得它成为STL中map/set/multimap/multiset的底层数据结构。
一棵树要是红黑树必须满足以下几条规则：
1、每个结点不是红色就是黑色的。
2、根节点是黑色的。
3、如果一个结点时红色的，则它两个孩子结点是黑色的。
4、对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑结点。
5、每个叶子结点都是黑色的（此处的叶子结点指空结点）。

RBTree的调整

我们在插入新节点的时候要考虑的就是新节点的颜色默认应该为什么颜色。我们首先分析如果新节点颜色如果为黑色，那么就意味着当前叶子的祖先路径上黑色必然会多出来一个，为了维持第4条规则，必然要对树进行调整，这就意味着如果新插入结点默认为黑色那么我们必然要进行调整，因为黑色结点对整棵树整体的影响是比较大的。那么如果新插入结点默认为红色呢？如果为红色只要它的父结点不为红色，那么此时我们是不需要进行调整的，因此调整的几率从必然要调整降低到了有可能不会需要调整，因此我们默认新插入的结点颜色为红色是最优的选择。
新插入结点默认为红色也有可能会遇到需要调整的情况，比如它的父结点也为红色那么此时该如何调整呢？这里的情况判断相比AVLTree更为复杂一些。
为了方便讨论，这里约定cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点。

情况一

cur为红，p为红，g为黑，u存在且为红。

AVLTree

这种情况下肯定是要调整了，这种情况下要做的操作也很简单，变色即可。为了让红色不连续我们将p变为黑色，为了维持每条路径上黑色结点数量一致，我们将u也变为黑色，而g变为红色。如果g调整后和它的父结点再次出现了连续红色则再次根据情况进行调整。

情况二

cur为红，p为红，g为黑，u不存在或为黑。

AVLTree

这种情况下调整方式为：如果p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反， p为g的右孩子，cur为p的右孩子，则进行左单旋转。最后p变黑，g变红。这里的旋转方法和AVLTree的相同。

情况三

cur为红，p为红，g为黑，u不存在或u为黑
。
AVLTree

p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反， p为g的右孩子，cur为p的左孩子，则针对p做右单旋转则转换成了情况2 。
这种情况与AVLTree中的双旋场景类似，cur在了内侧，因此我们必须旋转两次，好在这里旋转一次就可以变为情况二我们可以很方便的处理这种问题。要注意的是，旋转一次完毕后我们要交换cur和parent来让当前结点的情况和情况二完全一致。

实现

直接上代码，这里暂且没有实现删除。

#pragma once
#include <iostream>
#include <utility>
enum Color
{
    RED,
    BLACK
};
template<class K, class V>
struct RBTNode
{
    RBTNode(const std::pair<K, V>& data = std::pair<K, V>())
        :_data(data)
        ,_left(nullptr)
        ,_right(nullptr)
        ,_parent(nullptr)
        ,_color(RED)
    {
    }
    std::pair<K, V> _data;
    RBTNode<K, V>* _left;
    RBTNode<K, V>* _right;
    RBTNode<K, V>* _parent;
    Color _color;
};

template<class K, class V>
class RBTree
{
    typedef RBTNode<K, V> Node;
public:
    RBTree(const std::pair<K, V>& data = std::pair<K, V>())
        :_header(new Node(data))
    {
        _header->_left = _header;
        _header->_right = _header;
        _header->_parent = nullptr;
    }
    bool Insert(const std::pair<K, V>& data)
    {
        //空树，插入的为根结点
        if(_header->_parent == nullptr)
        {
            Node* root = new Node(data);
            //根节点颜色必须为黑色
            root->_color = BLACK;
            _header->_parent = root;
            root->_parent = _header;
            _header->_left = root;
            _header->_right = root;
            return true;
        }
        Node* cur = _header->_parent;
        Node* parent = _header;
        while(cur)
        {
            if(cur->_data.first < data.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if(cur->_data.first > data.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return false;
            }
        }
        cur = new Node(data);
        if(parent->_data.first < data.first)
        {
            parent->_right = cur;
        }
        else
        {
            parent->_left = cur;
        }
        cur->_parent = parent;
        //_header->_left = cur;
        //调整：修改颜色，旋转
        while(cur != _header->_parent && cur->_parent->_color == RED)
        {
            Node* parent = cur->_parent;
            Node* gParent = parent->_parent;
            if(gParent->_left == parent)
            {
                Node *uncle = gParent->_right;
                //情况一
                if(uncle && uncle->_color == RED)
                {
                    //更新颜色
                    parent->_color = uncle->_color = BLACK;
                    gParent->_color = RED;
                    //向上继续更新
                    cur = gParent;
                }
                //情况二/三
                else
                {
                    //叔叔不存在或者叔叔为黑色
                    //判断这里是否存在双旋的场景
                    if(cur = parent->_right)
                    {
                        //情况三
                        //此时就是一个折现的形态就需要两次旋转了
                        RotateL(parent);
                        //左旋后，父亲变子，子变父亲，重回情况er
                        std::swap(cur, parent);
                    }
                    else
                    {
                        //情况二
                        RotateR(gParent);
                        //更改颜色
                        parent->_color = BLACK;
                        gParent->_color = RED;
                        //此时这课子树的根为黑色，所以不需要再继续向上调整
                        break;
                    }
                }
            }
            else
            {
                Node* uncle = gParent->_left;
                if(uncle && uncle->_color == RED)
                {
                    parent->_color = uncle->_color = BLACK;
                    gParent->_color = RED;
                    cur = gParent;
                }
                else
                {
                    if(cur == parent->_left)
                    {
                        RotateR(parent);
                        std::swap(cur, parent);
                    }
                    else
                    {
                        RotateL(gParent);
                        parent->_color = BLACK;
                        gParent->_color = RED;
                        break;
                    }
                }
            }
        }
        //根结点的颜色必须为黑色
        _header->_parent->_color = BLACK;
        //更新头节点
        _header->_left = LeftMost();
        _header->_right = RightMost();
        return true;
    }
    //左旋
    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = parent->_right->_left;

        parent->_right = subRL;
        if(subRL)
        {
            subRL->_parent = parent;
        }
        subR->_left = parent;
        Node* ppNode = parent->_parent;
        parent->_parent = subR;
        //根
        if(ppNode == _header)
        {
            _header->_parent = subR;
            subR->_parent = _header;
        }
        else
        {
            if(ppNode->_right == parent)
            {
                ppNode->_right = subR;
            }
            else
            {
                ppNode->_left = subR;
            }
            subR->_parent = ppNode;
        }
    }
    //右旋
    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = parent->_left->_right;

        parent->_left = subLR;
        if(subLR)//subLR可能会为空，当h == 0时subLR为空
        {
            subLR->_parent = parent;
        }

        subL->_right = parent;//subL不可能为空
        //记录下parent原来的父结点，为了方便parent移动可以找到这棵子树的父结点
        Node* ppNode = parent->_parent;
        parent->_parent = subL;
        //更新这棵子树的新父结点subL与其父结点的连接
        if(ppNode == _header)//如果子树的父结点为空则说明parent原本是整棵树的根节点
        {
            _header->_parent= subL;
            subL->_parent = _header;
        }
        else
        {
            if(ppNode->_right == parent)
            {
                ppNode->_right = subL;
            }
            else
            {
                ppNode->_left = subL;
            }
            subL->_parent = ppNode;
        }
    }
    //找到当前树的最左结点
    Node* LeftMost()
    {
        Node* cur = _header->_parent;
        while(cur && cur->_left)
        {
            cur = cur->_left;
        }
        return cur;
    }
    //找到当前树的最有结点
    Node* RightMost()
    {
        Node* cur = _header->_parent;
        while(cur && cur->_right)
        {
            cur = cur->_right;
        }
        return cur;
    }
    //中序遍历
    void Inorder()
    {
        _Inorder(_header->_parent);
    }
    void _Inorder(Node* root)
    {
        if(root == nullptr)
        {
            return;
        }
        _Inorder(root->_left);
        std::cout << root->_data.first << " ";
        _Inorder(root->_right);
    }
    //判断是否是一个红黑树
    bool IsRBTree()
    {
        Node* root = _header->_parent;
        if(root == nullptr)
        {
            return true;
        }
        if(root->_color == RED)
        {
            return false;
        }
        //统计一条路径黑结点的数量
        int blackCount = 0;
        Node* cur = root;
        while(cur)
        {
            if(cur->_color == BLACK)
            {
                blackCount++;
            }
            cur = cur->_left;
        }
        //前序遍历
        return _IsRBTree(root, blackCount, 0);
    }
    bool _IsRBTree(Node* root, int blackCount, int curBlackCount)
    {
        if(root == nullptr)
        {
            if(curBlackCount != blackCount)
            {
                return false;
            }
            return true;
        }
        //统计黑色结点的数量
        if(root->_color == BLACK)
        {
            curBlackCount++;
        }
        //判断是否有红色连续
        if(root->_parent->_color == RED && root->_color == RED)
        {
            return false;
        }
        return _IsRBTree(root->_left, blackCount, curBlackCount) 
        && _IsRBTree(root->_right, blackCount, curBlackCount);
    }
private:
    //Node* _root;
    //这里为了方便后续封装成map/set我们将其结构改造成一棵带头结点的环形树
    //这里的头和环形类似于实现过的带头双向环形链表
    //头节点的右孩子连接最右结点，左孩子连接最左结点，用头指向树真正的根结点
    //相当于这个头结点是倒过来的，和真正的根结点头连着头，连个孩子和最左最右结点构成两个环
    //封装成这种结构都是为了方便我们后续进一步封装，尽量和库中的保持一致
    Node* _header;
};
void TestRBTree()
{
    RBTree<int, int> rbt;
    rbt.Insert(std::make_pair(1, 1));
    rbt.Insert(std::make_pair(10, 1));
    rbt.Insert(std::make_pair(2, 1));
    rbt.Insert(std::make_pair(5, 1));
    rbt.Insert(std::make_pair(3, 1));
    rbt.Insert(std::make_pair(4, 1));
    rbt.Insert(std::make_pair(7, 1));
    rbt.Inorder();
    std::cout << std::endl;
    //验证
    std::cout << (rbt.IsRBTree()) << std::endl;
}

执行TestRBTree:
1 2 3 4 5 7 10 
1

RBTree相比AVLTree性能更好，降低了需要旋转的次数，并且RBTree实现起来相比AVLTree较简单。

封装

STL库中的map/set的底层数据结构就是一棵红黑树，到了这一步我们从最基本的BSTree一路过关斩将最终实现了RBTree的基本功能，接下来我们要做的就是对RBTree进一步封装，使其完成map/set的基本功能。

RBTreeMod.hpp:
#pragma once
#include <iostream>
#include <utility>
//为了方便封装进行的修改版本的红黑树
enum Color
{
    RED,
    BLACK
};
template<class V>
struct RBTNode
{
    RBTNode(const V& data = V())
        :_data(data)
        ,_left(nullptr)
        ,_right(nullptr)
        ,_parent(nullptr)
        ,_color(RED)
    {
    }
    V _data;
    RBTNode<V>* _left;
    RBTNode<V>* _right;
    RBTNode<V>* _parent;
    Color _color;
};

//每个容器都有自己的迭代器，我们的Map/Set也必须有！
//在这里封装实现迭代器，Map/Set结构都是一致的，所以是现在RBTree的头文件中
template<class V>
class _RBTreeIterator
{
    //封装红黑树的结点
    typedef RBTNode<V> Node;
    typedef _RBTreeIterator<V> Self;
public:
    _RBTreeIterator(Node* node)
        :_node(node)
    {
    }
    V& operator*()
    {
        return _node->_data;
    }
    V* operator->()
    {
        return &_node->_data;
    }
    bool operator!=(const Self& it)
    {
        return _node != it._node;
    }
    bool operator==(const Self& it)
    {
        return _node == it._node;
    }
    //我们之前更改红黑树的结构使其变成带头的就是为这里迭代器的遍历做铺垫
    //1、_node->_right存在，走到右子树的最左结点
    //2、_node->_right不存在，向上回溯，只要_node == parent->_right就继续向上回溯，不满足条件则停止回溯，更新_node的值为parent
    Self& operator++()
    {
        if(_node->_right)
        {
            //找到右子树最左结点
            _node = _node->_right;
            while(_node->_left)
            {
                _node = _node->_left;
            }
        }
        else
        {
            Node* parent = _node->_parent;
            while(_node == parent->_right)
            {
                _node = parent;
                parent = parent->_parent;
            }
            //这个判断是为了避免树中没有右子树导致死循环的情况
            if(_node->_right != parent)
            {
                _node = parent;
            }
        }
        return *this;
    }
    //1、_node->_left存在，找左子树的最有结点
    //2、_node->_left不存在，只要_node != parent->_right，向上回溯，条件不满足则更新_node为parent
    Self& operator--()
    {
        if(_node->_left)
        {
            _node = _node->_left;
            while(_node->_right)
            {
                _node = _node->_right;
            }
        }
        else
        {
            Node* parent = _node->_parent;
            while(_node != parent->_right)
            {
                _node = parent;
                parent = parent->_parent;
            }
            _node = parent;
        }
        return *this;
    }
private:
    Node* _node;
};
//此时的结构仿照STL中的内容，K依然代表Key，而V代表节点中data的类型
//如果是map则V->std::pair<K, V>，如果是set则V->K
//这样实现的原因是为了方便红黑树更为灵活的可以分别实现map和set
template<class K, class V, class KeyOfValue>
class RBTree
{
    typedef RBTNode<V> Node;
public:
    typedef _RBTreeIterator<V> iterator;
    //中序遍历的头即树中的最左结点
    iterator begin()
    {
        return iterator(_header->_left);
    }
    //尾注意是它本身
    iterator end()
    {
        return iterator(_header);
    }
    RBTree(const V& data = V())
        :_header(new Node(data))
    {
        _header->_left = _header;
        _header->_right = _header;
        _header->_parent = nullptr;
    }
    std::pair<iterator, bool> Insert(const V& data)
    {
        //空树，插入的为根结点
        if(_header->_parent == nullptr)
        {
            Node* root = new Node(data);
            //根节点颜色必须为黑色
            root->_color = BLACK;
            _header->_parent = root;
            root->_parent = _header;
            _header->_left = root;
            _header->_right = root;
            return std::make_pair(iterator(root), true);
        }
        Node* cur = _header->_parent;
        Node* parent = _header;
        KeyOfValue kov;
        while(cur)
        {
            //修改
            if(kov(cur->_data) < kov(data))
            {
                parent = cur;
                cur = cur->_right;
            }
            else if(kov(cur->_data) > kov(data))
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                //return false;
                return std::make_pair(iterator(cur), false);
            }
        }
        cur = new Node(data);
        if(kov(parent->_data) < kov(data))
        {
            parent->_right = cur;
        }
        else
        {
            parent->_left = cur;
        }
        cur->_parent = parent;
        Node* newNode = cur;
        //_header->_left = cur;
        //调整：修改颜色，旋转
        while(cur != _header->_parent && cur->_parent->_color == RED)
        {
            Node* parent = cur->_parent;
            Node* gParent = parent->_parent;
            if(gParent->_left == parent)
            {
                Node *uncle = gParent->_right;
                //情况一
                if(uncle && uncle->_color == RED)
                {
                    //更新颜色
                    parent->_color = uncle->_color = BLACK;
                    gParent->_color = RED;
                    //向上继续更新
                    cur = gParent;
                }
                //情况二/三
                else
                {
                    //叔叔不存在或者叔叔为黑色
                    //判断这里是否存在双旋的场景
                    if(cur = parent->_right)
                    {
                        //情况三
                        //此时就是一个折现的形态就需要两次旋转了
                        RotateL(parent);
                        //左旋后，父亲变子，子变父亲，重回情况er
                        std::swap(cur, parent);
                    }
                    else
                    {
                        //情况二
                        RotateR(gParent);
                        //更改颜色
                        parent->_color = BLACK;
                        gParent->_color = RED;
                        //此时这课子树的根为黑色，所以不需要再继续向上调整
                        break;
                    }
                }
            }
            else
            {
                Node* uncle = gParent->_left;
                if(uncle && uncle->_color == RED)
                {
                    parent->_color = uncle->_color = BLACK;
                    gParent->_color = RED;
                    cur = gParent;
                }
                else
                {
                    if(cur == parent->_left)
                    {
                        RotateR(parent);
                        std::swap(cur, parent);
                    }
                    else
                    {
                        RotateL(gParent);
                        parent->_color = BLACK;
                        gParent->_color = RED;
                        break;
                    }
                }
            }
        }
        //根结点的颜色必须为黑色
        _header->_parent->_color = BLACK;
        //更新头节点
        _header->_left = LeftMost();
        _header->_right = RightMost();
        //return true;
        return std::make_pair(iterator(newNode), true);
    }
    //左旋
    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = parent->_right->_left;

        parent->_right = subRL;
        if(subRL)
        {
            subRL->_parent = parent;
        }
        subR->_left = parent;
        Node* ppNode = parent->_parent;
        parent->_parent = subR;
        //根
        if(ppNode == _header)
        {
            _header->_parent = subR;
            subR->_parent = _header;
        }
        else
        {
            if(ppNode->_right == parent)
            {
                ppNode->_right = subR;
            }
            else
            {
                ppNode->_left = subR;
            }
            subR->_parent = ppNode;
        }
    }
    //右旋
    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = parent->_left->_right;

        parent->_left = subLR;
        if(subLR)//subLR可能会为空，当h == 0时subLR为空
        {
            subLR->_parent = parent;
        }

        subL->_right = parent;//subL不可能为空
        //记录下parent原来的父结点，为了方便parent移动可以找到这棵子树的父结点
        Node* ppNode = parent->_parent;
        parent->_parent = subL;
        //更新这棵子树的新父结点subL与其父结点的连接
        if(ppNode == _header)//如果子树的父结点为空则说明parent原本是整棵树的根节点
        {
            _header->_parent= subL;
            subL->_parent = _header;
        }
        else
        {
            if(ppNode->_right == parent)
            {
                ppNode->_right = subL;
            }
            else
            {
                ppNode->_left = subL;
            }
            subL->_parent = ppNode;
        }
    }
    //找到当前树的最左结点
    Node* LeftMost()
    {
        Node* cur = _header->_parent;
        while(cur && cur->_left)
        {
            cur = cur->_left;
        }
        return cur;
    }
    //找到当前树的最有结点
    Node* RightMost()
    {
        Node* cur = _header->_parent;
        while(cur && cur->_right)
        {
            cur = cur->_right;
        }
        return cur;
    }
    //中序遍历
    void Inorder()
    {
        _Inorder(_header->_parent);
    }
    void _Inorder(Node* root)
    {
        if(root == nullptr)
        {
            return;
        }
        _Inorder(root->_left);
        std::cout << root->_data.first << " ";
        _Inorder(root->_right);
    }
    //判断是否是一个红黑树
    bool IsRBTree()
    {
        Node* root = _header->_parent;
        if(root == nullptr)
        {
            return true;
        }
        if(root->_color == RED)
        {
            return false;
        }
        //统计一条路径黑结点的数量
        int blackCount = 0;
        Node* cur = root;
        while(cur)
        {
            if(cur->_color == BLACK)
            {
                blackCount++;
            }
            cur = cur->_left;
        }
        //前序遍历
        return _IsRBTree(root, blackCount, 0);
    }
    bool _IsRBTree(Node* root, int blackCount, int curBlackCount)
    {
        if(root == nullptr)
        {
            if(curBlackCount != blackCount)
            {
                return false;
            }
            return true;
        }
        //统计黑色结点的数量
        if(root->_color == BLACK)
        {
            curBlackCount++;
        }
        //判断是否有红色连续
        if(root->_parent->_color == RED && root->_color == RED)
        {
            return false;
        }
        return _IsRBTree(root->_left, blackCount, curBlackCount) 
        && _IsRBTree(root->_right, blackCount, curBlackCount);
    }
private:
    //Node* _root;
    //这里为了方便后续封装成map/set我们将其结构改造成一棵带头结点的环形树
    //这里的头和环形类似于实现过的带头双向环形链表
    //头节点的右孩子连接最右结点，左孩子连接最左结点，用头指向树真正的根结点
    //相当于这个头结点是倒过来的，和真正的根结点头连着头，连个孩子和最左最右结点构成两个环
    //封装成这种结构都是为了方便我们后续进一步封装，尽量和库中的保持一致
    Node* _header;
};
//void TestRBTree()
//{
//    RBTree<int, int> rbt;
//    rbt.Insert(std::make_pair(1, 1));
//    rbt.Insert(std::make_pair(10, 1));
//    rbt.Insert(std::make_pair(2, 1));
//    rbt.Insert(std::make_pair(5, 1));
//    rbt.Insert(std::make_pair(3, 1));
//    rbt.Insert(std::make_pair(4, 1));
//    rbt.Insert(std::make_pair(7, 1));
//    rbt.Inorder();
//    std::cout << std::endl;
//    //验证
//    std::cout << (rbt.IsRBTree()) << std::endl;
//}

Map.hpp:
#include "RBTreeMod.hpp"
template<class K, class V>
class Map
{
    //为了让红黑树可以根据调用它的不同类型得以确定比较条件
    //我们这里用内部类创建一个反函数用域返回当前结构下的Key值
    struct MapKeyOfValue
    {
        const K& operator()(const std::pair<K, V>& data)
        {
            return data.first;
        }
    };
public:
    //这里为了能够动态识别这是一个类型要在前面加上typename关键字
    typedef typename RBTree<K, std::pair<K, V>, MapKeyOfValue>::iterator iterator;
    std::pair<iterator, bool> Insert(const std::pair<K, V>& data)
    {
       return  _rbt.Insert(data);
    }

    //实现迭代器
    iterator begin()
    {
        return _rbt.begin();
    }

    iterator end()
    {
        return _rbt.end();
    }
    
    V& operator[](const K& key)
    {
        std::pair<iterator, bool> ret = _rbt.Insert(std::make_pair(key, V()));
        return ret.first->second;
    }
private:
    RBTree<K, std::pair<K, V>, MapKeyOfValue> _rbt;
};

Set.hpp:
#include "RBTreeMod.hpp"
template<class K>
class Set
{
    struct SetKeyOfValue
    {
        const K& operator()(const K& data)
        {
            return data;
        }
    };
public:
    typedef typename RBTree<K, K, SetKeyOfValue>::iterator iterator;
    std::pair<iterator, bool> Insert(const K& data)
    {
        return _rbt.Insert(data);
    }

    //实现迭代器
    iterator begin()
    {
        return _rbt.begin();
    }

    //实现迭代器
    iterator end()
    {
        return _rbt.end();
    }
    

private:
    RBTree<K, K, SetKeyOfValue> _rbt;
};

test.cpp:
#include "Map.hpp"
#include "Set.hpp"
void TestMapSet()
{
    Map<int, int> M;
    M.Insert(std::make_pair(10, 1));
    M.Insert(std::make_pair(3, 1));
    M.Insert(std::make_pair(9, 1));
    M.Insert(std::make_pair(2, 1));
    M.Insert(std::make_pair(1, 1));
    for(auto e : M)
    {
        std::cout << e.first << " " << e.second << std::endl;
    }
    M[1] = 100;
    M[500] = 50;
    std::cout << std::endl;
    for(auto e : M)
    {
        std::cout << e.first << " " << e.second << std::endl;
    }
    Set<int> S;
    S.Insert(1);
    S.Insert(3);
    S.Insert(5);
    S.Insert(6);
    S.Insert(2);
    S.Insert(6);
    std::cout << std::endl;
    for(auto e : S)
    {
        std::cout << e << " ";
    }
}
int main()
{
    //TestBsTree1();
    //TestAVLTree()m
    //TestRBTree();
    TestMapSet();
}


1 1 
2 1 
3 1
9 1
10 1

1 100
2 1
3 1
9 1
10 1
500 50

1 2 3 5 6

map/set这种链式容器，也存在迭代器失效问题，但其的插入不会造成迭代器失效，删除会造成删除结点的迭代器失效。
由此一来，我们就完全实现了map/set两个容器，我们一路从BSTree到最终的RBTree，~~中间充满了坎坷和艰辛~~，不过这一趟学习下来，我们对map/set及其multi版本的底层实现有了进一步的理解，我们今后对其的使用也会变得更加得心应手。
但是至此我们的关联式容器部分还并没有完全结束，我们接下来会讨论unordered版本的关联式容器，他们的底层与普通版本的底层数据结构大相径庭，用到了哈希有关知识。

【DS】第二章-顺序表和链表

发表于 2019-10-20 | 分类于数据结构

字数统计: 2.4k

第二章顺序表和链表

顺序表

什么是顺序表

顺序表是物理地址全部连续的存储数据的方式。顺序表分为动态顺序表以及动态的顺序表，静态的顺序表一般很少使用，因为其大小一旦固定不能再进行改变。

顺序表在开发中十分经常使用，因为其方便简单，并且易于操作。数组就是顺序表的一种，因为其在逻辑结构上是线性的，在物理结构上是连续的。由于十分常用在Cpp的STL库中封装了以顺序表为数据结构的vector容器供我们使用。

实现

顺序表的实现十分类似于vector类的实现。

#include <iostream>
#include <stdlib.h>
#include <assert.h>
#include <stdlib.h>
#include <Windows.h>
using namespace std;
#define N 100
//顺序表的实现
//十分类似于我们实现过的vector类，毕竟vector就是顺序表
template<class T>
class SeqList
{
public:
    //构造函数
    SeqList()
    :_array(nullptr)
    ,_size(0)
    ,_capacity(0)
    {}
    //析构函数
    ~SeqList()
    {
        if(_array != nullptr)
        {
            delete _array;
        }
    }
    //pos前插入
    void Insert(size_t pos, const T& value)
    {
        //判断pos是否合法
        if(pos > _size || pos < 0)
        {
            return;
        }
        //扩容
        Expend();
        for(size_t i = _size; i > pos; i--)
        {
            _array[i] = _array[i - 1];
        }
        _array[pos] = value;
        _size++;
    }
    //尾插
    void Push_back(const T& value)
    {
        //扩容
        Expend();
        _array[_size] = value;
        _size++;
    }
    //头插
    void Push_front(const T& value)
    {
        //扩容
        Expend();
        //所有元素向后挪一个位置
        for(size_t i = _size; i > 0; i--)
        {
            _array[i] = _array[i - 1];
        }
        _array[0] = value;
        _size++;
    }
    //尾删
    void Pop_back()
    {
        //删除前要先判断，有元素才能删
        if(_size > 0)
        {
            _size--;
        }
    }
    //头删
    void Pop_front()
    {
        //有元素才能删
        if(_size > 0)
        {
            for (size_t i = 1; i < _size; i++)
            {
                _array[i - 1] = _array[i];
            }
            _size--;
        }
    }
    //删除pos当前位置数据
    void Erase(size_t pos)
    {
        //pos不合法
        if(pos >= _size || pos < 0)
        {
            return;
        }
        for(size_t i = pos; i < _size - 1; i++)
        {
            _array[pos] = _array[pos + 1];
        }
        _size--;
    }
    //查找
    size_t Find(const T& value)
    {
        for(size_t i = 0; i < _size; i++)
        {
            if(_array[i] == value)
            {
                return i;
            }
        }
        return -1;
    }
    //二分查找
    size_t BinaryFind(const T& value)
    {
        //左闭右开区间
        size_t high = _size, low = 0;
        while(high > low)
        {
            size_t mid = (high + low) / 2;
            if(_array[mid] == value)
            {
                return mid;
            }
            else if(_array[mid] > value)
            {
                high = mid;    
            }
            else
            {
                low = mid + 1;
            }
        }
    }
    //修改
    void Modify(size_t pos, const T& value)
    {
        if(pos < 0 || pos >= _size)
        {
            return;
        }
        _array[pos] = value;
    }
    //打印
    void Print()
    {
        for(size_t i = 0; i < _size; i++)
        {
            cout << _array[i] << " ";
        }
        cout << endl;
        //cout << _size << endl;
    }
    //当前元素个数
    size_t Size()
    {
        return _size;
    }
    //某个位置的值
    T& operator[](size_t pos)
    {
        assert(pos >=0 && pos < _size);
        return _array[pos];
    }
    //冒泡排序
    void BubbleSort()
    {
        for(int i = 0; i < _size - 1; i++)
        {
            bool flag = false;
            for(int j = 0; j < _size - i - 1; j++)
            {
                if(_array[j] > _array[j + 1])
                {
                    swap(_array[j], _array[j + 1]);
                    flag = true;
                }
            }
            if(flag == false)
            {
                break;
            }
        }
    }
    void RemoveAll()
    {
        _size = 0;
    }
private:
    //T _array[N];//静态顺序表，利用数组，不可变，十分不灵活
    T* _array;//动态顺序表，利用指针动态开辟
    size_t _size;//长度
    size_t _capacity;//容量
    //扩容
    void Expend()
    {
        if(_size == _capacity)//满了
        {
            size_t newCapacity = (_capacity == 0 ? 5 : 2 * _capacity);
            //创建更大空间，拷贝，释放原有空间
            _array = (T*)realloc(_array, newCapacity * sizeof(T));
            //申请失败
            assert(_array);
            //更新容量
            _capacity = newCapacity;
        }
    }
};

顺序表的优缺点

顺序表优点：
1、根据下标随机访问时间复杂度O(1)。
2、不会产生内存碎片。
3、代码简单。
4、在尾插时事件复杂度为O1。
顺序表缺点：
1、在中间插入时时间复杂度为On，最坏情况下要移动整个顺序表完成头插。
2、增容申请新空间进行数据拷贝再释放旧空间，有这不小消耗。
3、增容一次空间为原有空间两倍，可能会造成空间大量浪费。

链表

什么是链表

顺序表是物理地址连续的数据存储方式，而链表与之相反，链表存储数据的物理地址不一定连续，因此它不能像顺序表那样通过直接寻址的方式访问到数据，它通过指针来连接和组织数据，因此也使得它和顺序表有着截然不同的特征，并且相比顺序表来说或许更难理解一些。

链表有着以下几种种类：
1、带头链表，不带头链表。
2、单向链表，双向链表。
3、循环链表，不循环链表。
他们组合搭配起来一共有8种组合，
由于链表的特性它可以很好地结局一些顺序表的缺点，比如他不需要扩容，并且更方便插入等等，但是在一些方面上它也有着不如顺序表的地方，关于优缺点我们放在最后再进行分析，接下来实现一个简单的带头单向不循环链表。

实现

在Cpp的STL中有一个list容器，其中实现了一个带头双向循环链表，这里我们简化进行实现带头单向不循环链表，思路更加简单（带头双向循环链表在Cpp章节中在模拟实现list时也有实现）。

#include <iostream>
using std::cout;
using std::endl;
template<class T>
struct ListNode
{
    //构造函数
    ListNode(const T& value = T())
        :data(value)
        ,next(nullptr)
    {

    }
    T data;//数据域
    ListNode* next;//指针域，指向下一个节点
};
template<class T>
class List
{
public:
    //构造函数
    List()
        :_head(new ListNode<T>)
        ,_size(0)
    {
    }
    ~List()
    {
        //依次删除所有节点以释放所有空间
        while(_size > 0)
        {
            Pop_Front();
        }
        delete _head;
    }
    //头插
    void Push_Front(const T& value)
    {
        InsertPos(0, value);
    }
    //尾插
    void Push_Back(const T& value)
    {
        InsertPos(_size, value);
    }
    //打印所有数据
    void PrintAll()
    {
        ListNode<T>* temp = _head->next;
        while(temp != nullptr)
        {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }
    //在下标为pos的元素前进行插入
    void InsertPos(size_t pos, const T& value)
    {
        if(pos < 0 || pos > _size)
        {
            cout << "InsertPos: pos error" << endl;
            return;
        }
        //这里的插入时间复杂度本应是O1，但是由于链表不便于寻址因此又需要线性的时间进行寻址
        ListNode<T>* node = FindForPos(pos);
        if(node == nullptr)
        {
            return;
        }
        ListNode<T>* newNode = new ListNode<T>(value);
        newNode->next = node->next;
        node->next = newNode;
        _size++;
    }
    //删除下标为pos的元素
    void ErasePos(size_t pos)
    {
        if(pos < 0 || pos >= _size)
        {
            cout << "ErasePos: pos error" << endl;
            return;
        }
        ListNode<T>* node = FindForPos(pos);
        if(node == nullptr)
        {
            return;
        }
        ListNode<T>* temp = node->next;
        node->next = temp->next;
        delete temp;
        _size--;
    }
    //尾删
    void Pop_Back()
    {
        ErasePos(_size - 1);
    }
    //头删
    void Pop_Front()
    {
        ErasePos(0);
    }
    //返回链表长度
    size_t Size()
    {
        return _size;
    }
private:
    //返回下标为pos的元素的前一个元素，下标为0的元素则返回头节点
    ListNode<T>* FindForPos(size_t pos)
    {
        ListNode<T> *temp = _head;
        for(int i = 0; i < pos; i++)
        {
            //不存在，长度不够
            if(temp == nullptr)
            {
                cout << "FindForPos: pos error" << endl;
                return nullptr;
            }
            temp = temp->next;
        }
        return temp;
    }
private:
    ListNode<T>* _head;
    size_t _size;
};

链表的优缺点

链表的优点：
1、链表在任意位置插入和删除时时间复杂度都能达到O1。
2、插入一个节点开辟一个空间，不牵扯扩容问题。
链表的缺点：
1、以节点为单位存储数据，并且还要存储指针可能会浪费更多空间。
2、不支持随机访问，因此在某一位置插入尽管插入只需要O1但是找到这个位置需要On。
3、思路实现略复杂。

链表反转问题

给一个单链表，反转这个单链表。

https://leetcode-cn.com/problems/reverse-linked-list/description/

反转链表有很多种方式，我们可以尾删所有结点并同时将他们重新头插回链表，但这样的思路消耗实在太高，我们每次尾插都不得不遍历整张单链表去找到尾，因此对其简化，这里提供两种思路，
第一种，后插头删法。这种方法是通过从第二个节点开始遍历整个链表，依次将节点移向头部的方法。图解如下：

题解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL)
        {
            return head;
        }
        ListNode* oldHead = head;
        ListNode* temp = oldHead->next;
        while(oldHead->next != NULL)
        {
            oldHead->next = temp->next;
            temp->next = head;
            head = temp;
            temp = oldHead->next;
        }
        return head;
    }
};

2、第二种：向后转法。第二种思路更为直观，我们就直接将每个结点中的next的指向改变即可。

题解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL)
        {
            return head;
        }
        ListNode* prev = head;
        ListNode* cur = head->next;
        ListNode* next = cur;
        head->next = NULL;
        while(cur != NULL)
        {
            next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
};

链表有多种多样的问题，我会另开章节逐个归纳，就不再此继续罗列了。

【Cpp】第十五章-类型转换

发表于 2019-10-18 | 分类于 Cpp

字数统计: 1.3k

类型转换

C中的类型转换

C语言中的类型转换分为隐式类型转换和强制类型转换两种。

#include <stdio.h>
int main()
{
    //隐式类型转换
    int i = 10;
    double d = i;
    printf("%d, %.2lf\n", i, d);
    //强制类型转换
    i = (int)d;
    printf("%d, %.2lf\n", i, d);
}

这种从C中继承而来的类型转换方式十分不直观，可视性较差，不便于我们在发生错误时查找错误。
为了解决这种问题，于是Cpp中新诞生了四种更加直观更加安全的类型转换操作。

Cpp中的类型转换

static_cast

static_cast用于非多态类型的转换（静态转换），编译器隐式执行的任何类型转换都可用static_cast，但它不能用于两个不相关的类型进行转换。

#include <iostream>
int main()
{
    double d = 10.2;
    int i = static_cast<int>(d);
    std::cout << "d:" << d << " i:" << i << std::endl;
}


d:10.2 i:10

static_cast是一个模板函数，如上使用就可以完成类型的转换，

#include <iostream>
int main()
{
    //double d = 10.2;
    //int i = static_cast<int>(d);
    //std::cout << "d:" << d << " i:" << i << std::endl;
    int i = 10;
    int *p = &i;
    int address = static_cast<int>(p);
}


invalid static_cast from type 'int*' to type 'int'

但是如上的类型转换就报错了，说明static_cast是无法将int*转为int的，如果两个类型毫无关系则无法进行转换。

reinterpret_cast

reinterpret_cast是一种十分危险的类型转换，它用于指针，引用以及可以容纳指针的整数类型之间的转换，之所以说它危险是你甚至可以将一个类型指针任意转换为其他类型的指针，比如将int*转换为string*，于是这个指针的命运由此就彻底改变了，使用不当就内存访问越界程序崩溃。

#include <iostream>
int main()
{
    int i = 10;
    double d;
    int* p = &i;
    //将指针强转为整形
    long long address = reinterpret_cast<long long>(p);
    std::cout << p << " " << address;
}


0x61fe0c 6422028

const_cast

const_cast可以完成从const对象到non-const对象的转换.

#include <iostream>
int main()
{
    const int i = 10;
    std::cout << i << std::endl;
    int& r = const_cast<int&>(i); 
    r = 11;
    std::cout << i << std::endl;
    std::cout << r << std::endl;
    const int a = 2;
    int *p = const_cast<int*>(&a);
    *p = 3;

    std::cout << a << std::endl;
    std::cout << *p << std::endl;
}

经过类型强转后我们发现确实可以更改指向常量的引用或指针了，但是通过输出对比我们发现，引用和指针指向的数据被改变了但是原数据并没有被改变，这是因为编译器的优化导致的，导致编译器并没有实际从内存中去取这块内存，而是重新分配了一块内存，我们可以使用volatile关键字来防止编译器的优化。

dynamic_cast

dynamic_cast可以完成从父类到子类的指针或者引用的强制类型转换。从子类到父类的转换我们有切割帮我们进行隐式类型转换，但是从父类到子类是不能自动转换的，我们只能通过dynamic_cast来强制转换引用和指针，并且只能在有虚函数的类中进行转换。dynamic_cast在转换前会先进行转换实验，如果能转换成功则转换，转换不成功则返回0。
Cpp之所以可以完成类型的转换，多亏与Cpp的RTTI机制，即运行时类型识别。虽然源文件中存储着类型以及之间的继承关系，但是其只用于编译，在程序运行时是无法拿到这些信息，于是Cpp为了可以在运行时获取数据对象的类信息以及继承关系便诞生了RTTI，dynamic_cast和typeid是RTTI的典型应用。

#include <iostream>
class Parent
{
public:
    virtual void Func()
    {

    }
    int s = 10;
};
class Son : public Parent
{
public:
    int s = 11;
};
int main()
{
    Parent* p = new Parent;
    std::cout << p->s << std::endl;
    Son* s = dynamic_cast<Son*>(p);
    if(s == nullptr)
    {
        std::cout << "change error" << std::endl;
        return -1;
    }
    std::cout << s->s << std::endl;
}


11
change error

explicit

这个参数之前已经在类和对象中讲解过了，这个参数加在类的构造函数前用于禁用构造函数函数参数的隐式转换。
未禁用:

#include <iostream>
class Test
{
public:
    Test(int test)
        :_test(test)
    {
        std::cout << "construct" << std::endl;
    }
private:
    int _test;
};
int main()
{
    Test test = 10;
}



construct

禁用:

#include <iostream>
class Test
{
public:
    explicit Test(int test)
        :_test(test)
    {
        std::cout << "construct" << std::endl;
    }
private:
    int _test;
};
int main()
{
    Test test = 10;//编译不过
}

【Cpp】第十四章-智能指针

发表于 2019-10-17 | 分类于 Cpp

字数统计: 5.7k

智能指针

基础概念

为什么要有智能指针

首先先看一段程序，看看这段程序可能会出现什么问题。

#include <iostream>
using namespace std;
void Func()
{
    int* ptr = new int[10];
    //...假设这其中有很多代码
    throw "error!";
    // delete[] ptr;
}
int main()
{
    try
    {
        Func();
    }
    catch(const char* str)
    {
        cout << str;
    }
}

首先这个代码中我们由于可能因为代码过于复杂而忘记释放空间，导致内存泄露，其次如果我们在这段代码中抛出异常，导致函数终止也会导致无法释空间，内存泄露，这种问题也被称为异常安全问题。作为Cpp程序猿，我们最烦也是最应该提防的一个问题就是内存泄露。那么针对这种情况我们象让我们动态分配的内存空间可以在生命周期结束后自动释放该怎么办呢？

什么是智能指针

智能指针是一个用于管理和存储指针的类，它利用对象出了作用域自动调用析构函数的特性帮助我们释放空间。接下来模拟实现一个简单的智能指针类。

#include <iostream>
#include <string>
#include <memory>
template<class T>
class SmartPtr
{
public:
    SmartPtr(T* ptr)
        :_ptr(ptr)
    {
        std::cout << "construct smartptr" << std::endl;
    }
    ~SmartPtr()
    {
        if(_ptr)
        {
            delete _ptr;    
        }
        std::cout << "destory smartptr" << std::endl;
    }
private:
    T* _ptr;
};
void Func()
{
    std::string* ptr = new std::string;
    SmartPtr<std::string> smartPtr(ptr);
}
int main()
{
    Func();
}


construct smartptr
destory smartptr

以上这个智能指针类就已经基本实现了帮助我们在指针声明周期结束后自动释放内存空间的功能，这种与之类似的功能实现在Cpp中称之为RAII(Resource Acquisition Is Initialization)，资源获取即初始化，是Cpp中常用的用于管理资源的方法，由这套方法产生了智能指针，当然还有智能锁，几乎所有我们在使用完必须释放资源的类型都可以使用这套方法进行资源管理。这套资源管理的方法使得我们不需要显示的释放资源，并且使资源在其生命周期内长期有效，出了作用域后自动帮助我们释放资源防止出现内存泄露的问题。
我们之前实现的只能发指针类并没有实现完全，因为作为智能指针我们必须要求它能够像指针一样进行使用。

#include <iostream>
#include <string>
#include <memory>
template<class T>
class SmartPtr
{
public:
    //资源管理
    SmartPtr(T* ptr)
        :_ptr(ptr)
    {
        std::cout << "construct smartptr" << std::endl;
    }
    ~SmartPtr()
    {
        if(_ptr)
        {
            delete _ptr;    
        }
        std::cout << "destory smartptr" << std::endl;
    }
    //使其可以像指针一样使用
    T& operator*()
    {
        return *_ptr;
    }
    T* operator->()
    {
        return _ptr;
    }
private:
    T* _ptr;
};
void Func()
{
    std::string* ptr = new std::string("Hello");
    SmartPtr<std::string> smartPtr(ptr);
    std::cout << *smartPtr << std::endl;
    std::cout << smartPtr->size() << std::endl;
}
int main()
{
    Func();
}


construct smartptr
Hello
5
destory smartptr

这样就可以称为一个较为完整的智能指针了，但是单单这样还不够，因为这个类中最重要的也是最难处理的两个默认函数还没有书写，即拷贝构造函数和赋值运算符重载函数，这两个函数的处理也苦恼了Cpp标准库中的多种智能指针，接下来我们就要着重讨论标准库中对这两个函数的处理。

库中的智能指针

早在C++98的版本中就已经出现了智能指针，它叫auto_ptr，但是由于十分不好用于是后面在C++11中出现了unique_ptr和shared_ptr。不同的智能指针除了拷贝构造和赋值运算符重载函数的实现外其他都是大同小异，我们这里着重讨论他们在拷贝构造函数和赋值运算符重载函数上的不同。
为什么不同的智能指针在这两个默认成员函数上实现区别会很大呢？我们稍微思索即可发现，指针的拷贝和赋值往往和资源何时释放而挂钩。如果一个智能指针A拷贝了另一个智能指针B，而当B出了声明周期此时要不要释放资源呢？如果释放资源那么我们再次使用指针A就会有未定义行为的发生。但如果不是放那么何时又该释放资源呢？这些问题的处理上使得智能指针有了差别。

auto_ptr

auto_ptr诞生在C++98的标准库中，但是这也是问题最多的智能指针，他对拷贝构造即赋值运算符重载的处理我们可以用一句话总结，即管理权限转移，我们以下作个简单的例子。注意：auto_ptr在C++11中已经被删除，因此我们可以依照文档自己实现一个进行试验。

#include <iostream>
#include <string>
#include <memory>
template<class T>
class auto_ptr
{
public:
    //资源管理
    auto_ptr(T* ptr)
        :_ptr(ptr)
    {
        std::cout << "construct smartptr" << std::endl;
    }
    ~auto_ptr()
    {
        if(_ptr)
        {
            delete _ptr;    
        }
        std::cout << "destory smartptr" << std::endl;
    }
    //使其可以像指针一样使用
    T& operator*()
    {
        return *_ptr;
    }
    T* operator->()
    {
        return _ptr;
    }
    //拷贝构造和赋值运算符重载
    auto_ptr(auto_ptr& ptr)
    {
        _ptr = ptr._ptr;
        ptr._ptr = nullptr;
        std::cout << "copy construct" << std::endl;
    }
    auto_ptr& operator=(auto_ptr& ptr)
    {
        if(this != &ptr)
        {
            if(_ptr)
            {
                delete _ptr;
            }
            _ptr = ptr._ptr;
            ptr._ptr = nullptr;
        }
        std::cout << "operator=()" << std::endl;
    }
private:
    T* _ptr;
};
void Func()
{
    std::string* ptr = new std::string("Hello");
    auto_ptr<std::string> autoptr(ptr);
    auto_ptr<std::string> copy(autoptr);
    std::cout << *copy << std::endl;
    std::cout << copy->size() << std::endl;
    std::cout << *autoptr << std::endl;
    std::cout << autoptr->size() << std::endl;
}
int main()
{
    Func();
}


construct smartptr
copy construct
Hello
5
崩溃...

在这个模拟实验中可以看出auto_ptr管理权限转移的意义，它会在赋值或者拷贝后将原本的智能指针中所管理指针置空，如果我们再去访问原来的智能指针，结果就是未定义行为，程序崩溃，~~这指针真的太恶劣了~~。因此强烈不建议使用auto_ptr，不过好在库中已经删除了他，想用也没的用了，皆大欢喜。

unique_ptr

unique_ptr是C++11中智能指针的改进版本，它解决了auto_ptr可能会导致程序崩溃的问题，但是他解决的方法略为粗暴，即禁用拷贝构造和赋值。不让拷贝不就不会出现问题了，简单粗暴。

#include <iostream>
#include <memory>
#include <string>
int main()
{
    std::string* ptr = new std::string("Hello");
    std::unique_ptr<std::string> uniqueptr(ptr);
    std::cout << *uniqueptr << std::endl;
    std::cout << uniqueptr->size() << std::endl;
    //拷贝构造和赋值被禁用，防拷贝
    std::unique_ptr<std::string> copy(uniqueptr);//编译不通过
    std::unique_ptr<std::string> copy2 = uniqueptr;//编译不通过
}

防拷贝很好的解决了auto_ptr的残留问题，我们也模拟实现一个unique_ptr。

#include <iostream>
#include <memory>
#include <string>
template<class T>
class Unique_Ptr
{
public:
    Unique_Ptr(T* ptr)
        :_ptr(ptr)
    {
        std::cout << "construct Unique_ptr" << std::endl;
    }
    ~Unique_Ptr()
    {
        if(_ptr)
        {
            delete _ptr;
        }
        std::cout << "destroy Unique_ptr" << std::endl;
    }
    //使其可以像指针一样使用
    T* operator->()
    {
        return _ptr;
    }
    T& operator*()
    {
        if(_ptr)
        {
            return *_ptr;
        }
    }
private:
    //禁用拷贝构造和赋值运算符重载
    Unique_Ptr(Unique_Ptr& ptr);
    Unique_Ptr& operator=(Unique_Ptr& ptr);
    T* _ptr;
};
void Func()
{
    std::string* ptr = new std::string("Hello");
    Unique_Ptr<std::string> uniqueptr(ptr);
    std::cout << *uniqueptr << std::endl;
    std::cout << uniqueptr->size() << std::endl;
    //Unique_Ptr<std::string> copy(uniqueptr);//编译不通过
    //Unique_Ptr<std::string> copy2 = uniqueptr;//编译不通过
}
int main()
{
    Func();
}


construct Unique_ptr
Hello
5
destroy Unique_ptr

这个版本的智能指针十分好用，因为简单方便因此很少出问题，而且我们本来就不建议让智能指针出现拷贝，因为可能会引发一系列问题，所以这个版本的智能指针也是最为推荐使用的版本，如果要求必须可以进行拷贝那么还得考虑接下来的版本。

shared_ptr

shared_ptr是标准库中的支持拷贝和赋值的智能指针。

#include <iostream>
#include <memory>
#include <string>
int main()
{
    std::string* ptr = new std::string("Hello");
    std::string* ptr2 = new std::string("World");
    std::shared_ptr<std::string> sharedptr(ptr);
    //拷贝构造
    std::shared_ptr<std::string> copy(sharedptr);
    std::shared_ptr<std::string> copy2(ptr2);
    std::cout << *copy2 << std::endl;
    //赋值
    copy2 = copy;
    std::cout << *sharedptr << std::endl;
    std::cout << copy->size() << std::endl;
    std::cout << *copy2 << std::endl;
}


World
Hello
5
Hello

以上例子可以看出三个通过通过不同方式得来的智能指针都可以正常使用，虽然他们都指向相同的资源但是也可以很好的进行资源管理。shared_ptr之所以可以支持拷贝和赋值，是因为它对智能指针拷贝的处理是通过一个引用计数，引用计数用来保存当前资源被几个智能指针共享。
当新增一个智能指针指向某个资源时则引用计数+1，一个智能指针不再指向某个资源则引用计数-1，当引用计数为0时则说明已经没有智能指针指向这个资源则释放资源，否则不释放资源。
但是由于可能会有好几个智能指针共同维护同一份引用计数的情况，于是如果在多线程中引用计数可能会同时被多个线程进行操作，称为临界资源，于是就要考虑线程安全问题，为了解决这些问题就需要在适当的地方加锁，或者让其成为原子操作。
同样的这里模拟实现一份shared_ptr了解原理。

#include <iostream>
#include <memory>
#include <string>
#include <thread>
#include <mutex>
#include <vector>
template<class T>
class Shared_ptr
{
public:
    //构造函数，应该初始化引用计数为1，并且初始化互斥锁
    Shared_ptr(T* ptr)
        :_ptr(ptr)
        ,_refCount(new int(1))
        ,_mtx(new std::mutex)
    {
        std::cout << "construct" << std::endl;
    }
    //拷贝构造
    Shared_ptr(const Shared_ptr<T>& temp)
        :_ptr(temp._ptr)
        ,_refCount(temp._refCount)
        ,_mtx(temp._mtx)
    {
        std::cout << "copy construct" << std::endl;
        AddRefCount();
    }
    //赋值运算符重载
    Shared_ptr& operator=(const Shared_ptr<T>& temp)
    {
        std::cout << "operator=" << std::endl;
        if(&temp != this)
        {
            Release();
            _ptr = temp._ptr;
            _refCount = temp._refCount;
            _mtx = temp._mtx;
            AddRefCount();
        }
        return *this;
    }
    //析构函数
    ~Shared_ptr()
    {
        std::cout << "destroy" << std::endl;
        Release();
    }
    //返回当前引用计数
    int RefCount()
    {
        return *_refCount;
    }
    //像指针一样使用
    T& operator*()
    {
        return *_ptr;
    }
    T* operator->()
    {
        return _ptr;
    }
private:
    //指针不再指向当前资源
    void Release()
    {
        //操作临界资源，加锁
        bool isRelease = false;
        _mtx->lock();
        //已经没有指针在控制当前资源
        if(--(*_refCount) <= 0)
        {
            //释放资源以及引用计数
            std::cout << "free resouce" << std::endl;
            delete _ptr;
            delete _refCount;
            isRelease = true;
        }
        _mtx->unlock();
        //锁不能在加锁中释放，因此要在锁中判断是否需要释放
        //最后在锁外释放锁的资源
        if(isRelease == true)
        {
            delete _mtx;
        }
    }
    //有新的智能指针指向当前资源，增加引用计数
    void AddRefCount()
    {
        //同样操作临界资源加锁
        _mtx->lock();
        ++(*_refCount);
        _mtx->unlock();
    }
private:
    T* _ptr;
    int* _refCount;
    std::mutex* _mtx;//互斥锁
};
void Test1()
{
    std::cout << "Test1:" << std::endl;
    std::string* str = new std::string("Hello");
    std::string* str2 = new std::string("World");
    Shared_ptr<std::string> sharedPtr(str);
    Shared_ptr<std::string> sharedPtr2(sharedPtr);
    sharedPtr2 = Shared_ptr<std::string>(str2);
    std::cout << *sharedPtr << std::endl;
    std::cout << *sharedPtr2 << std::endl;
}

void thr_start()
{
    std::string* str = new std::string("Hello");
    std::vector<Shared_ptr<std::string>> sharedPtr(10, str);
    std::cout << sharedPtr[0].RefCount() << std::endl;
}
void Test2()
{
    std::cout << "Test2:" << std::endl;
    std::thread thr1(thr_start);
    std::thread thr2(thr_start);
    thr1.join();
    thr2.join();
}
int main()
{
    Test1();
    Test2();
}


Test1:        
construct     
copy construct
construct     
operator=     
destroy
Hello
World
destroy
free resouce
destroy
free resouce
Test2:
construct
copy construct
copy construct
copy construct
copy construct
copy construct
copy construct
copy construct
copy construct
copy construct
copy construct
destroy
construct
copy construct
copy construct
copy construct
copy construct
copy construct
copy construct
copy construct
copy construct
copy construct
copy construct
destroy
10
destroy
destroy
destroy
destroy
destroy
destroy
destroy
destroy
destroy
destroy
free resouce
10
destroy
destroy
destroy
destroy
destroy
destroy
destroy
destroy
destroy
destroy
free resouce

shared_ptr在何种情况下乃至多线程的情况下都可以很好的管理和释放资源。

shared_ptr的线程安全问题

shared_ptr的线程安全要从两方面说起。
1、shared_ptr自身的线程安全。这里的线程安全指的是指针内部的引用计数这个临界资源的访问的安全问题，为了让指针知道何时该释放资源我们不得不在其中开辟一块供多个shared_ptr访问的引用计数，但如果在多线程中，就会发生线程安全问题。我们可以试着把上面模拟实现的代码中的增加和减少引用计数部分的锁删除掉，然后利用多线程多创建几个shared_ptr指向同一块资源，就会发现如果引用计数的改变不是原子操作，就会发生多个线程同时更改引用计数但由于资源不同步导致部分更改丢失从而使得智能指针管理的资源要么没有释放，要么提前释放，不过这点我们已经通过给临界资源的访问加锁从而得以解决，因此我们可以说 shared_ptr自身是线程安全的。
2、shared_ptr管理的资源的线程安全问题。不得不说如果智能指针所管理的资源本身就是临界资源的话，那么所有的智能指针在对这块资源的访问上都是线程不安全的，就像我们使用普通的指针访问临界资源一样，并不会因为我们使用了智能指针而使得原本临界资源的访问就受到了保护。这里的解决方法只能是从外部或者所管理的资源上添加访问保护才能解决，这与智能指针本身无关。但也不得不提 shared_ptr所管理的资源是有线程安全问题存在的。

shared_ptr的循环引用问题

shared_ptr的循环引用问题是一类非常经典的问题，它通常会出现在shared_ptr的使用中，导致资源无法正确被释放，看以下这个例子。

#include <iostream>
#include <memory>
//链表节点
struct ListNode
{
    //ListNode* _next;
    //ListNode* _prev;
    //统一交给智能指针管理，也方便后面链表节点之间互相连接
    std::shared_ptr<ListNode> _next;
    std::shared_ptr<ListNode> _prev;
    int _data;
    ~ListNode()
    {
        std::cout << "destroy" << std::endl;
    }
};
int main()
{
    //ListNode* node1 = new ListNode;
    //ListNode* node2 = new ListNode;
    //为了防止抛异常无法释放空间，将其交给智能指针管理
    std::shared_ptr<ListNode> node1(new ListNode);
    std::shared_ptr<ListNode> node2(new ListNode);
    node1->_next = node2;
    node2->_prev = node1;
    //异常抛出操作
    //...
    //delete node1;
    //delete node2;
    std::cout << "program will over" << std::endl;
}


program will over

程序运行结束我们发现资源并没有被释放，为什么呢。

#include <iostream>
#include <memory>
//链表节点
struct ListNode
{
    //ListNode* _next;
    //ListNode* _prev;
    //统一交给智能指针管理，也方便后面链表节点之间互相连接
    std::shared_ptr<ListNode> _next;
    std::shared_ptr<ListNode> _prev;
    int _data;
    ~ListNode()
    {
        std::cout << "destroy" << std::endl;
    }
};
int main()
{
    //ListNode* node1 = new ListNode;
    //ListNode* node2 = new ListNode;
    //为了防止抛异常无法释放空间，将其交给智能指针管理
    std::shared_ptr<ListNode> node1(new ListNode);
    std::shared_ptr<ListNode> node2(new ListNode);
    //node1->_next = node2;
    //node2->_prev = node1;
    //异常抛出操作
    //...
    //delete node1;
    //delete node2;
    std::cout << "program will over" << std::endl;
}

program will over
destroy
destroy

以上我们屏蔽掉了两行互相指向，也就是链表节点连接起来的代码，发现又可以正常释放资源了，为什么呢？以上这种现象就是循环引用，接下来图解以上过程说明为什么资源无法释放以及如何造成了循环引用。

循环引用的典型场景就是一个shared_ptr指向一块内存空间A，空间A中还有一个shared_ptr指向另一块空间B，而空间B也由一个shared_ptr管理并且其中又有一个shared_ptr指向空间A，这样在释放时就会发生循环引用的问题，导致空间无法释放。那么如何避免循环引用呢？
造成循环引用的根结问题就是一个两个使用shared_ptr互相指向的空间使得对方空间的引用计数多加了一次，才造成了循环引用，只要我们让由shared_ptr管理的空间中的shared_ptr指向另一块由shared_ptr管理的空间时另一块空间的引用计数不增加就好了，简单来说就是避免一次引用计数的增加，就可以避免卡死。但是shared_ptr指向一块空间时此空间的引用计数必然会+1，这该怎么办呢？
在标准库中未我们提供了另一个智能指针weak_ptr，这个指针是专门提供给我们解决循环引用问题的，我们将代码修改一下先看效果。

#include <iostream>
#include <memory>
//链表节点
struct ListNode
{
    //ListNode* _next;
    //ListNode* _prev;
    //统一交给智能指针管理，也方便后面链表节点之间互相连接
    //std::shared_ptr<ListNode> _next;
    //std::shared_ptr<ListNode> _prev;
    std::weak_ptr<ListNode> _next;
    std::weak_ptr<ListNode> _prev;
    int _data;
    ~ListNode()
    {
        std::cout << "destroy" << std::endl;
    }
};
int main()
{
    //ListNode* node1 = new ListNode;
    //ListNode* node2 = new ListNode;
    //为了防止抛异常无法释放空间，将其交给智能指针管理
    std::shared_ptr<ListNode> node1(new ListNode);
    std::shared_ptr<ListNode> node2(new ListNode);
    node1->_next = node2;
    node2->_prev = node1;
    //异常抛出操作
    //...
    //delete node1;
    //delete node2;
    std::cout << "program will over" << std::endl;
}


program will over
destroy
destroy

资源完美的释放了。那么是如何解决的呢？
首先可以将shared_ptr赋值给weak_ptr，因为weak_ptr就是专门为解决shared_ptr的问题产生的，并且weak_ptr指向某一shared_ptr管理的资源时它并不会增加该资源的引用计数，这完全符合我们解决循环引用的要求，避免了多增加的一次引用计数，于是问题解决了。

智能指针自定制deleter

之前我们的智能指针都是在单一的管理一块new出来的对象，那么如下产生的空间智能指针是否能进行管理呢？

#include <iostream>
#include <memory>
#include <string>
int main()
{
    std::shared_ptr<std::string> sp1(new std::string[10]);
    std::shared_ptr<std::string> sp2((std::string*)malloc(sizeof(std::string)));
}

智能指针无关版本默认释放资源都会去delete资源，然而我们new[]和malloc的资源必须通过delete[]和free才能完全释放或者不造成程序崩溃（malloc没有对对象初始化，如果对象内含有指针，使用delete释放资源调用析构函数可能会造成程序崩溃），因此我们想要正确释放资源就需要正确的deleter，也就是释放资源的方法，这样的方法被称为*删除器，当然智能指针也为我们留下了这样的接口，
我们可以通过传递一个仿函数去更改默认的delete方法。

#include <iostream>
#include <memory>
#include <string>
//自定义删除器
template<class T>
class FreeDeleter
{
public:
    void operator()(T* ptr)
    {
        free(ptr);
    }
};
template<class T>
class ArrayDeleter
{
public:
    void operator()(T* ptr)
    {
        delete[] ptr;
    }
};
int main()
{
    //ArrayDeleter<std::string> ad;
    std::shared_ptr<std::string> sp1(new std::string[10], ArrayDeleter<std::string>());
    //FreeDeleter<std::string> fd;
    std::shared_ptr<std::string> sp2((std::string*)malloc(sizeof(std::string)), FreeDeleter<std::string>());
}

这样就可以完成删除器的自定义。那么删除器是如何作用于智能指针内的资源的呢？在在智能指针准备释放资源时，他会调用仿函数删除器来释放资源，因此删除器也是一个回调函数，通过对删除器的自定义即可完成自定义释放资源。

RAII的扩展

RAII技术不光能使用在指针的资源管理上，一切需要我们手动释放的资源都可以使用RAII管理，比如锁。在库中有一套量身设计的用RAII来管理锁的类，叫做锁守卫，它可以帮助我们在锁超出作用域的时候自动解锁，防止我们中间抛出异常却没有解锁导致临界资源再也无法访问。
模拟实现一个锁守卫。

#include <iostream>
#include <mutex>
#include <thread>
template<class T>
class LockGuard
{
public:
    LockGuard(T& lock)
        :_lock(lock)
    {
        //std::cout << "lock" << std::endl;
        _lock.lock();
    }
    ~LockGuard()
    {
        //std::cout << "unlock" << std::endl;
        _lock.unlock();
    }
private:
    //禁用拷贝构造和赋值运算符重载
    LockGuard(const LockGuard& lck);
    LockGuard<T>& operator=(const LockGuard& lck);
    //这里的锁必须是引用形式的，因为要所在同一个锁上，不能拷贝
    T& _lock;
};
std::mutex mtx;
int num = 0;
void thr_start()
{
    //互斥锁力度越大越好，消耗会小很多
    LockGuard<std::mutex> lck(mtx); //使用守卫锁
    for(int i = 0; i < 1000000; i++)
    {
        ++num;
    }
}
int main()
{
    //开启两个线程分别加num一百万次
    std::thread thr1(thr_start);
    std::thread thr2(thr_start);
    thr1.join();
    thr2.join();
    std::cout << "num:" << num << std::endl;
}


num:2000000

库中的锁守卫。

#include <iostream>
#include <mutex>
#include <thread>
int main()
{
    //std::mutex mtx;
    //mtx.lock();
    ////...抛异常
    //mtx.unlock();
    //交给守卫锁
    std::mutex mtx;
    std::lock_guard<std::mutex> guard(mtx);
}

库中还有另一个锁守卫unique_lock，用法和lock_guard一致，那么两者有什么区别呢？
lock_guard只实现了RAII，因此加锁和解锁都由lock_guard控制，而unique_lock实现了更多的功能，它可以允许我们自己手动加锁，也可以手动解锁，也可以不阻塞地加锁。

【项目】快备

发表于 2019-10-14 | 分类于项目

字数统计: 1.8k

快备

开发环境

本项目开发完全在Centos7.2版本下使用C/Cpp进行开发，gcc版本5.3.1，用到的库有httplib，boost及zlib，工具有gcc,gdb,makefile,git。

项目介绍

功能介绍

“快备”可以让Windows用户安全可靠的将文件上传到云端进行备份，并且可以随时下载下来。“快备”通过在用户本地创建一个共享文件夹，只要用户将需要备份的文件放入文件夹内，启动程序快备即可自动完成备份，并且如果共享文件夹中文件有了修改则会再次自动备份文件。在云端，文件会存储在指定目录下，如果一个文件长期未被下载则会被自动标记为低热度文件，“快备”会将其自动打包压缩存储起来以节省空间，如果用户下载此文件则会自动将其解压，恢复为高热度文件。用户想要下载文件只需要打开浏览器访问服务器即可得到文件列表，点击对应文件即可下载。

功能模块

客户端

客户端主要负责文件信息的监控来判断需要备份的文件和将文件传输到服务端，具有以下功能：
1、文件监控功能。这个功能主要时为了辨别共享文件夹中有哪些文件需要备份。客户端会实时对共享文件夹进行循环监控，监控时会在内存中临时生成一个映射，用于存储文件名及其对应的文件信息，文件信息由最后修改时间和文件大小组成，而每轮监控都会遍历目录获取每个文件的文件信息与存储在内存中的文件信息进行对比，如果内存中没有此文件信息或文件信息不符则说明文件是新增的或者是修改过的需要进行备份。在每轮遍历结束时会将所有文件信息写入一个.list文件进行存储，用于下次启动程序时获取相应的文件信息。
2、文件上传功能。当检测出有文件需要备份时则会组织HTTP协议将文件传输到服务器上。传输过程中，考虑到传输的速度我选择利用多线程分块并行对文件进行传输，以提高传输速度。分块传输是利用多线程分别读取文件的不同部分来实现的，同时将分块信息通过HTTP协议中的range发送给服务端方便服务端进行接收。

服务端

服务端主要负责文件的接收存储，低热度文件压缩及文件在浏览器显示下载。其具有以下功能：
1、文件接收功能。当客户端发送HTTP请求要求服务端接收文件数据时，由于是分块对文件进行传输，因此服务端也需要对文件分块进行接收，只需要结合客户端发送的range信息将数据写入文件即可。
2、低热度文件压缩存储功能。对文件热度检测需要对文件进行监控，为了文件接收下载与文件监控两不误我采用多线程的方式对文件进行监控。监控中遍历存储文件的文件夹，获取文件夹中每个文件的最后修改时间用于判断是否是地热度文件，如果是低热度文件则需要进行压缩存储。文件压缩存储在另一个文件夹中，为了能够通过原文件找到压缩后的文件于是建立映射，并将映射存储在一个.list文件中。映射的添加在接收文件成功后就会添加映射，而压缩文件后才会添加具体压缩文件位置到映射。
3、文件列表获取功能。文件列表获取是为了方便用户在浏览器上查看所有可下载文件。文件列表只需要遍历存储文件映射的.list文件即可获取压缩后的及未压缩的所有文件名，通过HTTP协议返回给浏览器即可。
4、文件数据获取功能。如果要获取的是一个未压缩的高热度文件则读取所有文件信息返回给浏览器即可，如果是低热度且已经是压缩文件则需要通过原文件名和映射信息找到压缩文件并且解压缩回原文件再读取文件信息返回给浏览器进行下载。

项目中遇到的问题

在客户端如何检测文件是否需要备份

客户端要分辨出哪些文件需要备份哪些不需要备份，这是必然要有的功能。这里我采用存储大小和最后修改时间的方式进行解决这个问题，并且为了下次启动这个程序依然可以读取到上次备份的文件信息我将文件信息写入一个文件中。

在服务端如何检测低热度文件并且进行压缩

为了完成低热度文件压缩必须能够检测出哪些是地热度文件，在这里我通过开启多线程获取文件信息对文件是否是低热度文件进行判断，并且利用zlib库对文件进行压缩存储，然后将原文件与压缩文件建立映射来保证可以通过原文件找到压缩文件来解决这个问题。

多线程的线程安全问题

由于用了多线程，就有可能出现同时读写临界资源的情况发生。为了解决这个问题我用读写锁来控制程序中临界资源多读少写的问题。用文件锁来防止多个一个文件同时被读写的问题。

项目效果预览

客户端上传文件。

服务端对低热度文件进行压缩存储。

用户下载文件。

下载后文件解压缩恢复为原文件。

项目扩展方向

可以进一步实现用户登录功能，不同用户拥有不同的用户空间，每个用户只能下载自己上传的文件。
目前文件上传大小是有限的，主要是因为内存不足无法将数据全部到内存中，但是可以采用并行和串行结合的方式对文件进行分块上传。

项目发布

GitHub:https://github.com/MisakiFx/Cloud-Backup

【网络】第七章-典型IO模型

发表于 2019-09-29 | 分类于网络

字数统计: 4.5k

典型IO模型

IO的种类

IO模型根据特性可以分为以下几个种类：阻塞IO，非阻塞IO，信号驱动IO，异步IO，多路转接IO。

阻塞IO

为了IO发起IO调用，若IO条件不满足则一直等待，直到条件具备。

非阻塞IO

为了IO发起IO调用，若条件不满足则直接报错返回，执行其他指令。之后再次发起IO调用，条件不满足则继续报错返回，条件满足则直接进行数据拷贝后调用返回。
阻塞与非阻塞的区别在与发起一个调用是否能够立即返回。

信号驱动IO

自定义IO信号，如果IO条件具备则发送IO信号，收到信号后则打断其他操作进行信号处理，执行IO操作进行数据拷贝，结束后调用返回。

异步IO

自定义IO信号，发起IO调用，然后让操作系统进行等待条件满足，满足后操作系统进行数据拷贝，拷贝完后通知进程，进程收到后直接处理数据。
与之对应的是同步的操作同步与异步的区别在于功能的完成是否由自身完成。
那么是同步好还是异步好呢？答案是视使用场景而定。同步的流程控制更加简单，但是不管是否阻塞都会浪费CPU资源，因此对CPU的利用率不足。而异步对CPU的利用率更高，但是流程控制更加复杂，并且IO调用越多，同一时间占用的空间资源越多。
从以上IO种类来看，IO效率越来越高，但是流程控制越来越复杂，资源占用也越来越多。

多路转接IO

多路转接IO对大量描述符进行事件监控，能够让用户只对事件就绪的描述符进行操作。在网络通信中，如果用户仅仅对就绪的描述符进行操作，则流程在一个执行流中就不会阻塞，可以实现在一个执行流中对多个描述符进行并发操作。多路转接IO的实现主要是通过几种多路转接模型实现：select/poll/epoll。

select模型

工作原理

select模型对大量描述符进行几种事件监控，让用户能够仅仅针对事件就绪的描述符进行操作，对就绪事件的判断主要有以下几个标准：
1、可读事件：接收缓冲区中数据大小大于等于低水位标记（默认一个字节）。
2、可写事件：发送缓冲区中空闲空间的大小大于等于低水位标记（默认一个字节）。
3、异常事件：描述符是否发生了某些异常。

实现流程

1、用户首先定义事件集合，一共三种事件集合可读/可写/异常，每一个集合实际是一个位图，将某个事件集合中描述符对应的位置1用于标记用户关心该描述符的某些事件。
2、将集合拷贝到内核进行监控。对集合中所有描述符进行遍历判断，判断是否事件就绪。
3、若有某个描述符就绪了用户关心的事件，则该返回给用户结果了。返回的时候分别从各个事件集合中将没有就绪该事件的描述符对应的位置0，返回给用户三种表示就绪的描述符事件集合。
4、用户拿到就绪描述符事件集合后，通过分别遍历三种事件集合找到哪些描述符还在集合中，来判断哪些描述符已经就绪了指定事件，然后进行操作。

接口

int select(int nfds, fd_set *readfds, fd_set *writefds,
           fd_set *exceptfds, struct timeval *timeout);
    //nfds:集合中最大的描述符+1
    //readfds:可读事件集合
    //writefds:可写事件集合
    //exceptfds:异常事件集合
    //timeout:NULL表示永久阻塞，timeout.tv_sec表示限时阻塞
    //返回值:>0表示就绪的描述符个数;==0表示没有描述符就绪;<0监控出错
void FD_CLR(int fd, fd_set *set);//将指定的fd描述符从set集合中删除
int  FD_ISSET(int fd, fd_set *set);//判断某个fd描述符是否在set集合中
void FD_SET(int fd, fd_set *set);//将指定的fd描述符添加到set集合中
void FD_ZERO(fd_set *set);//清空set集合内容

用select模型实现tcp服务器

按照以下步骤实现：
1、搭建tcp服务器。
2、在accept之前创建select监控集合，并且将监听socket添加到可读事件集合中。
3、进行select监控，当select返回并且有就绪描述符。
4、若有事件就绪，判断就绪的描述符是否是监听socket，如果是则accept新的socket添加监控，否则recv数据。
每处理完一遍之后，都要再次对所有描述符进行监控，而每次系统都会将没有就绪的描述符剔除，因此每次监控前我们都得先重新添加一遍所有要监控的描述符。

//用select模型实现并发服务器                                                                     
//对select进行封装
#include <iostream>
#include <vector>
#include <unistd.h>
#include <string>
#include <stdlib.h>
#include <sys/select.h>
#include "tcp_socket.hpp"
class Select
{
  public:
    Select():_maxfd(-1)
    {
      FD_ZERO(&_rfds);
    }
    //添加要监听的套接字
    bool Add(TcpSocket& sock)
    {
      int fd = sock.GetFd();
      FD_SET(fd, &_rfds);
      _maxfd = _maxfd > fd ? _maxfd : fd;
      return true;
    }
    //监听，list返回就绪的描述符，sec为默认等待时间
    bool Wait(std::vector<TcpSocket>& list, int sec = 3)
    {
      struct timeval tv;
      tv.tv_sec = sec;
      tv.tv_usec = 0;
      fd_set tmp_set = _rfds;//每次定义新的集合进行监控，为了避免原有的监控集合被修改
      int count = select(_maxfd + 1, &tmp_set, NULL, NULL, &tv);
      if(count < 0)
      {
        std::cout << "select error" << std::endl;
        return false;
      }
      else if(count == 0)
      {
        std::cout << "wait timeout" << std::endl;
        return false;
      }
      for(int i = 0; i <= _maxfd; i++)
      {
        if(FD_ISSET(i, &tmp_set))
        {
          TcpSocket sock;
          sock.SetFd(i);
          list.push_back(sock);
        }
      }
      return true;
    }
    //删除不用再监听的套接字
    bool Del(TcpSocket& sock)
    {
      int fd = sock.GetFd();
      FD_CLR(fd, &_rfds);
      for(int i = _maxfd; i >= 0; i--)
      {
        if(FD_ISSET(i, &_rfds))
        {
          _maxfd = i;
          return true;
        }
      }
      _maxfd = -1;
      return true;
    }
  private:
    fd_set _rfds;//读事件描述符集合
    int _maxfd;//最大描述符
};
int main(int argc, char* argv[])
{
  if(argc != 3)
  {
    std::cout << "./tcpselect ip port" << std::endl;
    return -1;
  }
  TcpSocket sock;
  std::string srv_ip = argv[1];
  uint16_t srv_port = atoi(argv[2]);                     
  CHECK_RET(sock.Socket());
  CHECK_RET(sock.Bind(srv_ip, srv_port));
  CHECK_RET(sock.Listen());
  Select s;
  s.Add(sock);
  while(1)
  {
    std::vector<TcpSocket> list;
    if(!s.Wait(list))
    {
      sleep(1);
      continue;
    }
    for(auto clisock : list)
    {
      if(clisock.GetFd() == sock.GetFd())//监听套接字
      {
        TcpSocket socktmp;
        if(sock.Accept(socktmp) == false)
        {
          continue;
        }
        s.Add(socktmp);
      }
      else //通信套接字
      {
        std::string buf;
        if(clisock.Recv(buf) == false)
        {
          s.Del(clisock);
          clisock.Close();
          continue;
        }
        std::cout << "client say:" << buf << std::endl;
        buf.clear();
        std::cin >> buf;
        if(clisock.Send(buf) == false)
        {
          s.Del(clisock);
          clisock.Close();
          continue;
        }
      }
    }
  }
  sock.Close();
}

以上的实现用到了我们之前实现的tcp_socket.hpp，并将其类中的析构函数自动关闭套接字去掉。之后再用之前实现的tcp_cli.cpp即tcp客户端进行连接测试。

服务端：
[misaki@localhost AdvancedIO]$ ./tcpselect 192.168.239.128 9000
wait timeout
wait timeout
wait timeout
wait timeout
client say:nihao
wohenhao
wait timeout
client say:heihei
haha
wait timeout
wait timeout
wait timeout
peer shutdown
wait timeout

客户端：
[misaki@localhost AdvancedIO]$ ./tcpclient 192.168.239.128 9000
nihao    
server say: wohenhao
heihei
server say: haha

select优缺点分析

缺点：
1、select所能监控的描述符数量是有上线的，FD_SETSIZE = 1024。
2、每次监控都需要将监控集合拷贝到内核中。
3、在内核中进行轮询遍历查询，随着描述符的增多性能降低。
4、返回的是就绪集合，需要用户自己进行判断才能对描述符进行操作。
5、每次返回都会清空未就绪描述符，因此每次监控都需要重新添加到集合中。
优点：
1、POSIX标准，支持跨平台。

poll模型

工作原理

poll采用事件结构的方式对描述符进行事件监控，只需要一个事件结构数组，将要响应的描述符提交到数组的每一个结构节点的fd中，以及将用户关心的事件添加到响应节点events中。即可进行监控。

接口

int poll(struct pollfd *fds, nfds_t nfds, int timeout);
//以下这个结构体用于告诉系统需要监控哪些描述符以及所需监控的状态
struct pollfd
{
    int   fd;         /* file descriptor */
    short events;     //事件，POLLIN-可读/POLLOUT-可写
    short revents等    //这次监控返回之后这个描述符就绪的状态
}
//fds：struct pollfd数组
//nfds：数组的大小
//timeout：超时时间，单位ms
//返回值：小于0出错，等于0超时，大于零有描述符就绪

使用流程

1、用户定义一个事件结构数组，然后将关心的描述符以及事件添加到数组中。
2、将数组拷贝到内核进行监控。在内核中会轮询遍历监控。
3、当事件数组中有描述符事件就绪/等待超时则poll返回，poll返回时将每个描述符就虚的事件添加到相应节点revents中。
4、用户对数组中的每个节点的revents进行判断之后进行操作。

优缺点分析

缺点：
1、无法跨平台。
2、依然需要将监控的描述符事件数组拷贝到内核中。
3、
在内核中同样是轮询遍历监控，性能会随着描述符的增多而下降。
4、只是将就绪的事件放到了结构的revents中，需要用户轮询查找就绪的描述符。
优点：
1、没有描述符监控的数量上限。
2、采用事件结构进行监控，简化了select三种事件集合的操作流程。
3、不需要每次重新向集合中添加事件数组。

epoll模型

epoll模型是为了处理大批量句柄而做了改进的poll，它几乎具备了所需的一切优点，是Linux下性能最好的多路I/O模型。

接口

int epoll_create(int size);
//在内核中创建eventpoll结构，结构中主要信息：双向链表，红黑树，具体作用看下文。返回一个操作句柄描述符
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);
//向内核中的eventpoll结构中的红黑树添加用户关心的描述符事件结构
//epfd:epoll操作句柄
//op:工作模式，EPOLL_CTL_ADD/EPOLL_CTL_MOD/EPOLL_CTL_DEL
//fd:用户关心的描述符
//event:对于fd描述符所要监控的事件，结构体参考如下
struct epoll_event {
    uint32_t     events; //要监听的事件EPOLLIN可读/EPOLLOUT可写
    epoll_data_t data; //就绪的描述符，这个值通常与fd一致
};

int epoll_wait(int epfd, struct epoll_event *events,
               int maxevents, int timeout);
//epfd:epoll操作句柄
//events:就绪事件数组，返回就绪的描述符和对应的描述符
//maxevents:最大节点数
//timeout:超时事件，单位ms，-1阻塞，0非阻塞

工作原理

epoll监控是一个异步阻塞操作。对描述符的监控由操作系统完成，当描述符就绪之后，则将就绪的描述符对应的epoll_event结构添加到双向链表list中，而当前进程只是每隔一段时间判断以下list是否为空，即可知道是否有描述符就绪。
操作系统完成监控，对于每一个描述符所关心的事件都定义了一个事件回调，当描述符就绪事件的时候就会调用回调函数，这个回调函数负责将事件结构信息即struct epoll_event添加到双向链表中。
epoll_wait会自动检测list双向链表，检测到链表list不为空，表示有就绪事件，则将这个链表中这些epoll_event放到用户的events数组中返回出去。

用epoll模型实现tcp服务器

#include <iostream>                                                      
#include <vector>                            
#include <string>              
#include <sys/epoll.h>
#include <unistd.h>   
#include "tcp_socket.hpp"    
#define MAX_EPOLL 1024
class Epoll
{                               
  public:                    
    Epoll()
      :_epfd(-1)
    {          
     
    }                                      
    ~Epoll()
    {             
                                             
    }  
    bool Init()            
    {                                         
      _epfd = epoll_create(MAX_EPOLL);
      if(_epfd < 0)
      {  
        std::cerr << "create epoll error" << std::endl;
        return false;
      }   
      return true;
    }                   
    bool Add(TcpSocket& sock)         
    {    
      struct epoll_event ev;
      int fd = sock.GetFd();
      ev.events = EPOLLIN;
      ev.data.fd = fd;                                 
      int ret = epoll_ctl(_epfd, EPOLL_CTL_ADD, fd, &ev);
      if(ret < 0)      
      {                               
        std::cerr << "append monitor error" << std::endl;
        return false;     
      }
      return true;
    }  
    bool Del(TcpSocket& sock)
    {
      int fd = sock.GetFd();
      int ret = epoll_ctl(_epfd, EPOLL_CTL_DEL, fd, NULL);
      if(ret < 0)
      {
        std::cerr << "remove monitor error" << std::endl;
        return false;
      }
      return true;
    }
    bool Wait(std::vector<TcpSocket>& list, int timeout = 3000)
    {
      struct epoll_event evs[MAX_EPOLL];
      int nfds = epoll_wait(_epfd, evs, MAX_EPOLL, timeout);
      if(nfds < 0)
      {
        std::cerr << "epoll monitor error" << std::endl;
        return false;
      }
      else if(nfds == 0)
      {
        std::cerr << "epoll monitor timeout" << std::endl;
        return false;
      }
      for(int i = 0; i < nfds; i++)
      {
        int fd = evs[i].data.fd;
        TcpSocket sock;
        sock.SetFd(fd);
        list.push_back(sock);
      }
      return true;
    }
  private:
    int _epfd;
};
int main(int argc, char* argv[])
{
  if(argc != 3)
  {                                                                         
    std::cout << "./tcp_epoll ip port" << std::endl;
    return -1;
  }
  std::string srv_ip = argv[1];
  uint16_t srv_port = atoi(argv[2]);
  TcpSocket lst_sock;
  CHECK_RET(lst_sock.Socket());
  CHECK_RET(lst_sock.Bind(srv_ip, srv_port));
  CHECK_RET(lst_sock.Listen());
  Epoll e;
  CHECK_RET(e.Init());
  CHECK_RET(e.Add(lst_sock));
  while(1)
  {
    std::vector<TcpSocket> list;
    if(e.Wait(list) == false)
    {
      sleep(1);
      continue;
    }
    for(size_t i = 0; i < list.size(); i++)
    {
      //监听套接字
      if(list[i].GetFd() == lst_sock.GetFd())
      {
        TcpSocket cli_sock;
        if(lst_sock.Accept(cli_sock) == false)
        {
          continue;
        }
        CHECK_RET(e.Add(cli_sock));
      }
      else 
      {
        std::string buf;
        if(list[i].Recv(buf) == false)
        {
          list[i].Close();
          continue;
        }
        std::cout << "Client Say:" << buf << std::endl;
        buf.clear();                                                       
        std::cin>> buf;
        if(list[i].Send(buf) == false)
        {
          list[i].Close();
          continue;
        }
      }
    }
  }
  lst_sock.Close();
}      


//服务端
[misaki@localhost AdvancedIO]$ ./tcpepoll 192.168.239.128 9000
epoll monitor timeout
epoll monitor timeout
epoll monitor timeout
Client Say:nihao
heihei
epoll monitor timeout
Client Say:haha
xixi
peer shutdown
epoll monitor timeout

//客户端
[misaki@localhost AdvancedIO]$ ./tcpclient 192.168.239.128 9000
nihao
server say: heihei
haha
server say: xixi

在事件结构体中events字段还有另外几种事件触发模式EPOLLLT水平触发，EPOLLET边缘触发。
水平触发对于可读事件来说，只要接收缓冲区中的数据大小高于低水位标记就会触发事件。对于可写事件来说，只要发送缓冲区中剩余空间高于低水位标记时就会触发事件。总结来说就是只要缓冲区满足可读或可写要求就会触发事件。举个例子，如果你在读取缓冲区，一次没有读完，只要缓冲区中还有数据那么下一次epoll会继续触发事件告诉你有东西可读。
边缘触发对于可读和可写事件来说都是只有当缓冲区中内容改变即新数据接收到接收缓冲区或发送缓冲区数据被发送走时才会触发时间。同样举个例子，如果想要读取接收缓冲区的内容，一次没有读取完，虽然缓冲区中还有数据但是下一次epoll不会触发事件让你继续读取，知道有新的数据接收到接收缓冲区中，此时你可以连着上次的数据和新数据一起读取。
水平触发和边缘触发没有明确的性能差距，但是边缘触发一次读写只触发一次，确实比水平触发要触发的次数少，系统就不会触发一些你不关心的就绪文件描述符。因此有时使用边缘触发更好一些，但是为了一次触发就能把缓冲区中数据全部读完需要循环读取数据，知道读完位置，又为了不造成阻塞要将描述符设置为非阻塞，然后循环读取数据直到EAGAIN错误就表示一次读完了。其实实际使用中都是非阻塞循环进行数据读取，毕竟在不清楚数据到底有多少的情况下，要想一次读完就只能采用以上方法。

epoll优缺点分析

优点：
1、采用事件结构方式监控，简化多个监控集合的操作流程。
2、没有所能监控的描述符数量上限。
3、epoll监控的事件只需要向内核拷贝一次，不需要每次都拷贝。
4、监控采用异步阻塞，在内核中进行事件回调方式监控，因此性能不会随着描述符的增多而降低。
5、直接返回就绪事件结构，用户可以通过就绪事件结构中的描述符直接操作，不需要进行遍历判断。
缺点：
1、不支持跨平台。

多路转接IO适用场景

多路转接模型适用于对大量描述符进行监控，但是同一时间只有少量活跃的场景。多线程/多进程的并发处理时比较高效且公平的。但是多路转接模型的并发是轮询处理的，一个处理完才会处理下一个，如果活跃描述符很多，则会导致后面的描述符等待时间过长。
因此使用epoll往往是用其进行活跃判断，当描述符活跃再将其放到线程池中进行公平处理。这样的搭配才是较为完美的。

【网络】第六章-链路层协议及其他协议

发表于 2019-09-29 | 分类于网络

字数统计: 2.1k

链路层协议及其他协议

链路层功能

负责相邻设备之间的数据帧传输。
网络层负责主导数据传输方向，而链路层更加偏向底层，用来引导相邻主机间数据如何传输，之后由物理信号传输数据。

以太网协议

以太网协议用于在链路层组织数据，主导相邻主机之间的数据传输方向。
在以太网协议中有一个重要概念MAC地址：相邻设备定位的地址，也就是物理网卡的硬件地址，标识每一块网卡，在两块网卡之间的数据传输起到作用

协议构成

6字节目的MAC地址：标志数据发向哪块网卡。
6字节源MAC地址：标志数据从那块网卡发来。
2字节上层协议类型：及ip协议等。
46-1500字节数据：传输的数据。
4字节以太帧尾：在其中包含校验和。

ARP协议

要想在链路层进行传输我们得知道目的MAC地址，那么我们如何获得MAC地址？这里就要用到ARP协议。

协议作用

ARP协议是介于网络层与链路层之间的协议，通过IP地址获取MAC地址。

协议原理

通过发送一个ARP请求数据包，要求指定ip地址的设备将自己的MAC地址做一个应答响应回来，并且对ip地址和MAC地址的关系进行映射缓存，但是缓存时间很短，通常只有30分钟。

MTU

之前在网络层有提到过MTU，最大传输单元，即以太头包裹的数据大小（不包括头大小），IP协议头及其包裹的UDP数据如果总大于MTU则会在网络层进行数据分片，然后再通过链路层进行传输，而组织和分片数据都是在网络层，这里要讲的是MTU对TCP和UDP协议分别的影响。

对TCP协议的影响

tcp在传输层进行传输的时候因为可靠传输会自动进行数据分段传输，之前的TCP协议中的滑动窗口机制介绍也有提到过，分段大小即称为MSS。通信双方在三次握手的时候计算自身MSS = MTU - IP - TCP，双方取较小的MSS作为最大数据段传输大小。因为TCP在传输层会进行自动数据分段，所以在网络层不会进行数据分片。

对UDP协议的影响

UDP数据报在网络层如果大小大于MTU但是小于IP最大传输大小即64k则需要在网络层进行数据分片，如果分片越多由于UDP的不可靠传输则丢包可能性越大，对端重组数据失败几率就越大，意思是说如果UDP分片越多则数据丢包可能性越大。一个UDP包中的数据最大默认情况下也就是MTU(默认1500字节) - IP头(20字节) - UDP头(8字节) = 1472字节。

其他协议

DNS

DNS的诞生

DNSDomain Name System是域名系统。我们的服务器的IP地址往往是点分十进制的，十分难于记忆，于是便产生了域名，方便我们记忆查找服务器，例如www.baidu.com就是一个域名。当我们访问这个域名时，会首先将域名转换为对应的IP地址，那么要进行转换那就必须要有一个服务器存储映射关系帮助我们进行转换，这些服务器叫做域名服务器。
首先产生的是跟域名服务器，根域名服务器是最高级域名服务器，但是为了分摊访问压力进行容灾处理全世界一共有13台根域名服务器，分布在世界各地。

DNS服务器的层级划分

就算全世界有13台根域名服务器这也远远不够用，因此根域名服务器为了再次分摊压力它只向下授权，授权世界权威组织可以继续建立域名服务器，便于域名解析。
根域名服务器向下的一级授权是顶级域名服务器。例如.com/.org/.gov/.edu/.cn/.jp/.us。
顶级域名服务器还可以继续向下授权，授权出二级域名服务器。例如.baidu.com/.qq.com。以此类推还有三级域名服务器.baike.baidu.com。

域名的解析流程

通过域名访问服务器需要进行域名解析，域名解析会经过以下步骤进行解析，会以此经过以下步骤查找映射。

浏览器 -> 浏览器缓存 -> 查看本机host文件 -> 本地域名服务器
本地域名服务器查找不到对应域名则会按照以下顺序依次请求上级域名服务器查询域名：
本地域名服务器 -> 根域名服务器 
本地域名服务器 -> 顶级域名服务器
本地域名服务器 -> 二级域名服务器

这种访问方式是迭代的请求方式，即当本地域名服务器查找不到对应域名则主动请求根域名服务器，如果根域名服务器找不到对应域名则返回顶级域名服务器地址让本地域名服务器自己去请求顶级域名服务器，同理顶级域名服务器找不到会返回二级域名服务器逐层往下。还有一种递归的请求方式，当本地域名服务器向根域名服务器发出请求时如果根域名服务器无法找到域名则会自己主动去访问顶级域名服务器查找，如果找不到就继续相下级查找，如果找到则返回。

当浏览器输入url回车后发生那些事情

1、域名解析流程进行域名解析得到服务器IP地址。
2、根据url组织http协议格式的请求数据。
3、基于Socket流程搭建tcp客户端，向得到的服务器地址发送http请求数据

ICMP协议

网络层协议，主要实现网络探测功能。ping就利用到了ICMP协议，注意ping只是用了网络层协议因此不使用端口。

NAT技术

NAT的作用

网络地址转换服务。我们在向主机发送数据时举要通过网关设备，网关设备将数据发送给指定主机号还要求目标主机将返回数据依旧通过此网关返回，因此在网关中会替换IP投中的源IP地址为此网关地址，这样就能做到让数据怎么去，怎么回。但是一个网关设备上肯定有多条数据等待转发，又如何标记哪条数据属于哪个主机呢？这里利用了不同的端口向不同的目的主机发送数据，并且建立映射，不同的端口映射一个目的主机一个源主机，这样数据返回时根据端口也能找到要返回的主机。这种根据端口建立映射的技术也叫NAPT技术。
NAT一般部署在网关上。

代理服务器

乍一看NAT技术和代理服务器的功能十分相似，但实际上有着很多区别：
1、NAT是网络基础设备之一，用于解决IP地址不足的问题。代理服务器则偏向于应用。
2、NAT作用在网络层，直接替换IP地址，代理服务器作用在应用层。
3、NAT一般在局域网的出口部署，而代理服务器可以部署在局域网，也可以在广域网，也可以跨网。
4、NAT部署在防火墙，路由器等设备上，代理服务器是一个软件，部署在服务器上。

unordered系列关联式容器

什么是unordered系列

unordered系列的使用

底层结构

哈希表

什么是哈希表

哈希函数

直接定址法

除留余数法

平方取中法

折叠法

哈希冲突

负载因子

闭散列

线性探测再散列

二次探测再散列

基于闭散列实现哈希表

开散列

封装

总结

栈的压入、弹出序列

题目

题解

代码实现

请问下面的程序一共输出多少个“-”？

运行结果

结果分析

关联式容器

pair

map

模板参数

构造函数

迭代器相关

元素修改

容量及元素访问

总结

multimap

set

模板参数

构造函数

迭代器相关

容量和修改

总结

multiset

底层实现

BS Tree

什么是BS Tree

实现

AVLTree

什么是AVLTree

AVLTree平衡因子的更新

AVLTree的旋转

左单旋

右单旋

先右旋再左旋

先左旋再右旋

旋转场景

实现

RBTree

什么是RBTRee

RBTree的调整

情况一

情况二

情况三

实现

封装

第二章 顺序表和链表

顺序表

什么是顺序表

实现

顺序表的优缺点

链表

什么是链表

实现

链表的优缺点

链表反转问题

类型转换

C中的类型转换

Cpp中的类型转换

static_cast

第二章顺序表和链表