string vector list 容器

stack queue容器适配器

stack

适配 & 转换

queue

queue不使用vector头插和头删效率太低不考虑使用

Stl的stack和queue是通过容器适配转换出来的不是原生实现的是为了更好的复用

deque像List + vector

vector是单向开口的连续线性空间

deque是双向开口可在头尾两端同时进行插入和删除

vector也可以在头部进行插入和删除但是vector 效率特别差

deque是可以在常数的时间内进行数据的插入和删除动态的分段组合随时可以增加一段新的空间并连接起来

deque排序速度是vector 的1/4 为了提高效率将deque中的数据全部复制到vector中再进行排序

deque中是一段一段的定量的连续空间构成

​

#pragma once有什么作用？

​

为了避免同一个头文件被包含（include）多次，C/C++中有两种宏实现方式：一种是#ifndef方式；另一种是#pragma once方式。

//方式一：
#ifndef  __SOMEFILE_H__
#define   __SOMEFILE_H__
 ... ... // 声明、定义语句
#endif
 
//方式二：
#pragmaonce
 ... ... // 声明、定义语句 

priority_queue优先队列

底层实现是堆，c++中使用向上调整。

• 什么是堆

其实堆是有下列性质的完全二叉树

每个节点的值都大于等于其左右孩子的值大顶堆

每个节点的值都小于等于其左右孩子的值为小顶堆

• x2+1 = 左孩子

• x2+2 = 右孩子

• (-1)/2 = 父亲

大根堆代码实现

#pragma once
#include <vector>
​
using namespace std;
​
​
namespace chen
{
​
    template<class T, class Container = vector<T>>
    class priority_queue{
    public:
        void push(const T &x){
​
            _con.push_back(x);
            AdjustUp(_con.size() -1);
​
        }
        void pop(){
            swap(_con[0],_con[_con.size()-1]);
            _con.pop_back();
            AdjustDown(0);
​
        }
        T& top(){
            return _con[0];
        }
        size_t size(){
​
            return _con.size();
        }
        bool empty(){
​
            return _con.size() == 0;
        }
​
        void AdjustUp(size_t child){
            int parent = getParent(child);
            while(child > 0)
            {
                if(_con[child] > _con[parent]){
                    swap(_con[child] , _con[parent]);
​
                    child = parent;
                    parent = getParent(child);
                }else
                {
                    break;
                }
            }
​
        }
​
        void AdjustDown(size_t root)
        {
            size_t parent = root;
            size_t child = parent*2+1;
            while(child < _con.size())
            {
                if(child+1 < _con.size() && _con[child] < _con[child+1])
                {
                    ++child;
                }
                if(_con[child] > _con[parent])
                {
                    swap(_con[child] , _con[parent]);
                    parent = child;
                    child = parent*2+1;
                }else
                {
                    break;
                }
​
​
            }
​
        }
​
        size_t getParent(size_t x)
        {
            return (x-1)/2;
        }
​
    private:
        Container _con;
    };
​
    void TestHeap() {
        priority_queue<int> Heap;
        Heap.push(1);
        Heap.push(3);
        Heap.push(1);
        Heap.push(4);
        Heap.push(7);
        Heap.push(5);
        Heap.push(9);
        Heap.push(2);
        while(Heap.size()) {
            cout << Heap.top() << endl;
            Heap.pop();
        }
    }
​
​
}

实现小根堆只需要切换代码中的符号就可以实现，为了不拷贝冗余代码，C++使用仿函数实现

C++中class 和 struct 除了访问限定符不同其他地方是一样的

namepace chen
{
    //
    template<class T>
        struct less{
            bool operator(const T& x1,const T& x2){
                return x1 < x2;
            }   
        }
}
bit::less<int> lessFunc;
cout << lessFunc(2,1) << endl; // ===== lessfunc.operator()(1,2) 调用此函数

有less就有greater 默认是大堆

优先队列比较仿函数

template<class T>
struct less{bool operator()(const T& x1,const T& x2){return x1<x2;}};
template<class T>
struct greater{bool operator()(const T& x1,const T& x2){return x1>x2;}};

sort函数底层也是通过一个仿函数进行控制从大到小排序