STL学习

作者: dounine | 来源:发表于2019-02-20 12:26 被阅读0次

title: STL学习
date: 2018-11-23 19:49:39

0. 前言

STL是C++中的一个类库，提供常用的数据结构(如栈、队列等)和算法(如排序、查找等)。

灵活运用STL中的数据结构，可以帮助你有效解决很多算法问题。

简单记载STL中的常用内容。

1. #include<stack> 栈

先进后出

1.1. 创建

stack<int> s: 声明一个栈，以整型为基本单位。也可以用其它数据类型为基本单位，包括结构体类型。

1.2. 增

s.push(num): 入栈

参数：num，与声明栈时的数据类型相同
返回值：无

1.3. 删

s.pop(): 出栈

参数：无
返回值：无

1.4. 查

s.top(): 获取栈顶元素

参数：无
返回值：栈顶元素的值，与声明栈时的数据类型相同

s.empty(): 判断栈是否为空

参数：无
返回值：bool类型，空为真，反之为假

s.size(): 获取栈长度

参数：无
返回值：栈中元素个数，数据类型为无符号整型（要注意：若 size()-1<0 ，则为无符号整型的最大值）

#include<iostream>
#include<stack>
using namespace std;

int main() {
  stack<int> s; // 定义一个栈，基本单位为int类型
  s.push(1); // push一个元素进栈
  cout << s.size()-2 << endl; // 按常理 s.size()-2 应为-1
}

输出：18446744073709551615

2. #include<queue> 队列

先进先出

2.1. 创建

queue<int> q: 声明一个队列，以整型为基本单位。也可以用其它数据类型为基本单位，包括结构体类型。

2.2. 增

q.push(num): 队尾进队列

参数：num，与声明队列时的数据类型相同
返回值：无

2.3. 删

s.pop(): 队头出队列

参数：无
返回值：无

2.4. 查

q.front(): 获取队头元素

参数：无
返回值：队头元素的值，与声明队列时的数据类型相同

q.back(): 获取队尾元素

参数：无
返回值：队尾元素的值，与声明队列时的数据类型相同

q.empty(): 判断队列是否为空

参数：无
返回值：bool类型，空为真，反之为假

q.size(): 获取队列长度

参数：无
返回值：队列中元素个数，数据类型为无符号整型(同上)

3. #include<vector> 动态数组

优点：

动态数据个数
访问数据方便

缺点：

在中间插入删除不方便

3.1. 创建

vector<int> v: 声明一个vector(其存储空间是连续的，类似于动态数组)，以整型为基本单位。

注意：vector v的内存是分配在栈上的，而v中的元素是分配在堆上的。

3.2. 增

v.push_back(num): 将元素追加到vector结尾

参数：num，与声明队列时的数据类型相同
返回值：无

注意：v.push_back()采用的是深拷贝。参考网上案例，代码如下：

class Solution {
public:
  vector<vector<int>> generate(int numRows) {
    vector<vector<int>> result;
    for (int i=0; i<numRows; ++i) {
      vector<int> temp(i+1,1);
      cout<<&temp<<endl;
      result.push_back(temp);
    }
    for (int i=0; i<numRows; ++i) {
      cout<<&result[i]<<endl;
    }
    return result;
  }
};

输出如下：

0x7fff5fbff5f0
0x7fff5fbff5f0
0x7fff5fbff5f0
0x100105540
0x100105558
0x100105570

由此可知，push_back()函数不是借用传入元素的地址，而是将元素所指的内容(堆上的数据)都复制到自己的堆上。

3.3. 删

pop_back(): 删除容器尾部的元素

v.clear(): 清空vector

参数：无
返回值：无

3.4. 改

v[n] = 1: 与数组元素赋值方式相同

v1 = v2: 将数组v1赋值给数组v2

3.5. 比较

v1 == v2: 判断两个数组是否相等。此外 !=、<、<=、>、>= 也可以使用

3.5. 查

v[n]: 获取下标为n的元素

v.size()

v.empty()

3.6. 遍历

v.begin()

参数：无
返回值：指向vector首地址的指针

v.end()

参数：无
返回值：指向vector最后一个元素的下一个位置的指针

vector<int> v;
vector<int>::iterator it;
for(it = v.begin(); it != v.end(); it++){
  cout << *it << endl;
}

4. #include<list> 链表

内部实现：双向链表

优点：

中间插入删除方便
动态数据个数

缺点：

访问数据不方便

4.1. 创建

list<int> l

4.2. 增

l.push_back(num): 在链表尾部增加一个元素

参数：与定义时相同的数据类型
返回值：无

l.push_front(num): 在开始位置增加一个元素。参数同上

l.insert(iter, num): 在指定位置插入元素

参数：
- iter: 迭代器 list<int>::iterator it
- num: 定义链表时指定的数据类型的变量
返回值：无

4.3. 删

l.pop_back(): 删除末尾的元素

l.pop_front(): 删除第一个元素

l.erase(iter): 删除指定位置的元素

参数：
- iter: 迭代器，类型为list<int>::iterator it
返回值：无

l.clear(): 清空

4.4. 查

l.front()

l.back()

l.empty()

l.size()

4.5. 遍历

l.begin()

l.end()

list<int> l;
list<int>::iterator it;
for(it = l.begin(); it != l.end(); it++){
  cout << *it << endl;
}

4.6. 排序

l.sort() \ l.sort(cmp): 排序，cmp是自定义的排序函数。示例：

#include<iostream>
#include<list>
using namespace std;

class A{
  public:
  int a,b;
  A(int t1,int t2){a=t1,b=t2;}
};

bool compare(A a1, A a2){
  return a1.a < a2.a;  //会产生升序排列，若改为>，则会产生降序
}

int main() {
  list<A> list_a;
  A a1(1,2), a2(4,6), a3(2,8);
  list_a.push_back(a1);
  list_a.push_back(a2);
  list_a.push_back(a3);

  list_a.sort(compare); // 排序操作

  list<A>::iterator it;
  it = list_a.begin();
  for(int i=0;i<3;i++)  {cout<<it->a<<endl; it++;}

  return 0;
}

5. #include<map> 映射

数据间的映射关联，有序键值对。

内部实现：红黑树，插入、删除、查找的时间复杂度都是 $O(logN)$ 。

5.1. 创建

map<string, int> people: 键值类型都可以是结构体。但是，需要重载比较运算符（因为map内部需要排序），如下：

struct Node {
  int x;
  int y;
  bool operator < (const Node n) const {
    return x < n.x || (x == n.x && y < n.y);
  }
};

map<Node, int> nodes;
nodes[Node{1,2}] = 1;

map中的元素都是pair<const K, T>类型的，pair类型可以通过first成员访问键、second成员访问值。

5.2. 增

people["dou"] = 20: 运算符重载。当使用["dou"]时，若"dou"不存在，则会创建键值对："dou":0。然后，将20设为"dou"的值。

people.insert(make_pair("Bill", 48)): 插入一个不存在的键值对。

参数：
- pair<K, T>: 一个键值对，K类型为映射定义时的键类型、T类型为映射定义时的值类型。
返回值：
- pair<map<string, int>::iterator, bool>: pair对象的first成员是一个迭代器，它要么指向插入元素，要么指向阻止插入的元素（元素已存在）；second成员是布尔值，表示是否成功，即该键是否存在。

示例：

pair<string, int> peo = make_pair("Bill", 48); // c++11: auto peo = make_pair("Bill", 48);
pair<map<string, int>::iterator, bool> ret_pr = people.insert(peo); // c++11: auto ret_pr = people.insert(peo);
cout << ret_pr.first->first << " " << ret_pr.first->second << " " << ret_pr.second << "\n";

5.3. 删

people.erase(key): 删除键对应的键值对

参数：
- key: 键类型的变量
返回值：所移除元素的个数，map 容器的返回值只可能是 0 或 1。

5.4. 改

people[key] = newValue: 将新值赋给对应的键。如果键不存在，将创建该键值对。

5.5. 查

people[key]: 返回键对应的值

people.count(key): 返回该键对应元素的个数，map 容器的返回值只可能是 0 或 1

people.find(key)

参数：
- key: 键
返回值：map<K, T>::iterator，指向该元素的迭代器，若不存在则指向people.end()。

5.6. 遍历

两种方式：

for (map<string, int>::iterator it=people.begin(); it!=people.end(); it++) {
  cout << it->first << ": " << it->second <<endl;
}
// c++11支持
for (const auto& p : people) {
  cout << p.first << ": " << p.second <<endl;
}

6. #include<set> 集合

数据间的关系，有序集合。

内部实现：红黑树。

6.1. 创建

set<int> int_set: 元素类型可以是结构体。但是，需要重载比较运算符（因为set内部需要排序），如下：

struct Node {
  int x;
  int y;
  bool operator < (const Node n) const {
    return x < n.x || (x == n.x && y < n.y);
  }
};

set<Node> node_set;

注意：重载比较运算时，要考虑结构体中的每一个元素。

6.2. 增

node_set.insert(Node{1, 2}): 增加不存在的元素

参数：
- Node{1, 2}: 符合定义类型的元素
返回值：pair<set<Node>::iterator, bool>

示例：

pair<set<Node>::iterator, bool> pr = node_set.insert(Node{1, 2});
cout << pr.first->x << "," << pr.first->y << " " << pr.second << endl;

6.3. 删

node_set.erase(): 删除迭代器指定位置的元素，或与对象匹配的元素。如下：

node_set.erase(Node{1,2});

if (node_set.count(Node{2,2})) {
  cout << "(2,2) node was found!\n";
  set<Node>::iterator it = node_set.find(Node{2,2});
  node_set.erase(it);
}

node_set.clear(): 清空

6.4. 查

node_set.find(Node{1,2}): 若未找到该元素，则返回node_set.end()。

node_set.count(Node{2,2}): 返回匹配的元素个数，0或1。

6.5. 遍历

for (set<Node>::iterator it=node_set.begin(); it!=node_set.end(); it++) {
  cout << it->x << "," << it->y <<endl;
}

7. #include<queue> 优先队列

在优先队列中，元素被赋予优先级。当访问/删除元素时，具有最高优先级的元素最先被访问/删除。

内部实现：堆。插入的时间复杂度为 $O(logN)$ ，访问头元素的时间复杂度为 $O(1)$ ，删除头元素的时间复杂度为 $O(logN)$ 。

参考：https://blog.csdn.net/CerberuX/article/details/51762357

7.1. 创建

struct node {
    int priority;
    int value;
    bool operator < (const node &a) const {
        return priority < a.priority; // 大顶堆，反之则是小顶堆
    }
};

priority_queue<node> q;

7.2. 增

q.push(node)：在堆的最后加入元素，然后向上筛选

7.3. 删

q.pop(node)：取出堆的根结点，然后最后一个元素上位，并向下筛选

7.4. 查

q.top()

q.size()

q.empty()

7.5. 自定义比较

除了定义结构体时，重载比较运算符，还可以用如下方式自定义比较：

#include <vector>
#include <queue>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 优先队列中元素的自定义比较
struct cmp {
    bool operator () (ListNode *a, ListNode *b) {
        return a->val > b->val; // 小顶堆
    }
};

priority_queue<ListNode*, vector<ListNode*>, cmp> q;

8. #include<iostream> 算法

8.1. 快速排序函数 sort()

第一种形式： sort(a, a+n) a是数组的首地址，n是要排序部分的尾地址，默认是从小到大排序

第二种形式： sort(a, a+n, cmp) cmp是一个函数名字，由使用者自己定义排序的依据。例如，你要对结构体数组排序。

结构体如下：

typedef struct {
  int from, to;
  int weight;
}Arc;

cmp函数如下（参数为结构体）：

bool cmp(Arc a, Arc b) {
  return a.weight < b.weight;
}

调用sort函数如下：

Arc arcs[100005];
sort(arcs, arcs+m, cmp);

即会按照结构体中的weight元素，从小到大排序。