Cpp算法-STL标准库

模板

---

template <typename T>
/**
 * 写函数/结构体
 */

例

template <typename T>
struct Point
{
    T x, y;
    Point(T x = 0, T y = 0):x(x), y(y) {}
};

template <typename T>
Point<T> operator + (const Point<T>& A, const Point<T>& B)
{
    return Point<T>(A.x + B.x, A.y + B.y);
}

template <typename T>
ostream& operator << (ostream& out, const Point<T>& p)
{
    out << "(" << p.x << "," << p.y << ")";
    return out;
}

vector(不定长数组)

---

声明

vector<数据类型> 名; 例 vector<int> a;

简单用法

a.size();读取大小

a.resize();改变大小

a.push_back(x);尾部添加元素x

a.pop_back();删除最后一个元素

a.clear();清空

a.empty()询问是否为空(bool类型)

a[]访问元素(可修改)

priority_queue(优先队列/堆)

---

声明

头文件: #include <queue>

参数: priority_queue<Type, Container, Functional>

 Type数据类型 不可省

 Container容器(vector,deque)默认vector

 Functional比较方式,默认operator <大根堆

使用

与queue类似

小根堆

priority_queue<int, vector<int>, greater<int> > q;使用仿函数greater<>

自定义类型(struct)

struct Node
{
    int x, y;
    Node(int a = 0, int b = 0):x(a), y(b){}
};

重载operator <

bool operator < (Node a, Node b)
{
    if (a.x == b.x) return a.y > b.y;
    return a.x > b.x;
}

priority_queue<Node> q;

x值大的优先级低,排在队前

x相等,y大的优先级低

重写仿函数

struct cmp
{
    bool operator () (Node a, Node b)
    {
        if (a.x == b.x) return a.y > b.y;
        return a.x > b.x;
    }
}

priority_queue<Node, vector<Node>, cmp> q;