Fl0w3r

carpe diem

STL&基础数据结构

Posted on In
3.8k 7 mins.

引言

简单介绍 Vector 向量、List 链表、Queue 队列、Stack 栈、Priority_Queue 优先队列的原 理，以及 C++ STL 中这些数据结构的使用，以及笔试和面试的一些应用场景。


STL容器

STL容器简介

  • 容器(Containers)是用于保存一系列对象的对象。

  • 例如，std::vector, std::liststd::string, std::queue<std::vector>;*

  • 分类:

    • Sequence container
    • Associative container
    • 另外还有 Container adaptor 和 Almost container

  • 你也可以设计自己的容器，只要它满足通用的标准和接又

*注:在使用 C++98 标准编译时，需要在两个 > 中间添加空格。

迭代器(Iterator)

  • 对指针的抽象。
  • 因此需要重载 * 运算符。
  • 指针的运算是基于使用连续的内存空间，但是对于一些容器来说并非如此。
  • 基于能够进行的运算类型，迭代器可以分为下列几类:
    • 所有的迭代器都支持解引用运算符(*)和自增运算符(++)
    • Input iterator 在此基础上支持 ==, !=, 单次读取，->; Output Iterator 仅支持单次写入(课后:查阅 I/O 库相关内容，了解它们的使用场景)
    • Forward iterator 在 Input iterator 基础上支持重复访问及读写
    • Bidirectional iterator 在 Forward iterator 基础上支持自减运算符(–)
    • Random-access iterator 在 Bidirectional iterator 基础上支持 [], +, +=, −, −=, <, <=, >, >= 运算符(和普通指针功能相同)

为了保证通用性，标准库中还提供了一些库函数

  • #include
  • std::advance(iter, n) 迭代器 iter 自增 n 次
  • std::distance(iter1, iter2) 返回迭代器 iter1 和 iter2 间的距离
  • std::next(iter, n=1), std::prev(iter, n=1) 返回 “iter + n” 或 “iter – n” 对应的迭代器(c++11)
  • 注意如果不是 Random-access iterator ，这些方法的复杂度可能是线性的，或者行为未定义，或者无法通过编 译。

容器的 begin() 和 end() 方法可以获得首尾迭代器

  • for (auto it = c.begin(); it != c.end(); ++it)
  • for (auto & x: c)
  • 迭代器的类型为 ContainerType::iterator

另外 cbegin() 和 cend() 方法可以返回首尾的常量迭代器(类似于常量指针)

  • for (auto it = c.cbegin(); it != c.cend(); ++it)
  • for (const auto &x: c)
  • 迭代器的类型为 ContainerType::const_iterator

课后:查询反向迭代器的相关资料，解释 rbegin(), rend(); crbegin(), crend() 的用法。

接口

C++ 标准在设计的过程中，就有意地让这些标准容器共享接又，从而发挥模板多态的特性。

例如，常见的构造函数:

  • ContainerType c(num)
  • ContainerType c(num, x)
  • ContainerType c(beg, end)

容量相关的方法:

  • int s = c.size(); bool b = c.empty();
  • c.resize(num); c.resize(num, x);
  • c.clear();

Reference: Bjarne Stroustrup. The C++ Programming Language, 4th edition. §31.3

栈

std::stack<T, Container>

  • 属于 Container Adapter，需要基于某个 Sequence container
  • 不能使用迭代器访问
  • push(x)
  • pop()
  • top()
  • 课后:了解 initializer_list，理解 emplace() 方法的使用。

如何实现一个栈?

  • 方便起见，假设数据的总量为 N，数据类型为 int.
  • int stack[N], top; 数据存放在 [0, top) 区间内。

一些基本操作:

  • push: stack[top++] = x;
  • pop: int y = stack[–top];
  • size: return top;
  • empty: return top == 0;

Catalan数

队列

如何实现一个队列

int queue[N], head, tail; 其中元素存放在 [head, tail) 区间。

基本操作

  • push: queue[tail++] = x;
  • pop: int y = queue[head++];
  • size: return tail – head;
  • empty: return head == tail;

循环队列

练习

if (stack2.empty()) { 
    while(!stack1.empty())
        stack2.push(stack1.top()), stack1.pop(); }
    return stack2.top();

向量

  • 之前我们假设了数据量是已知的，那么当我们的数据量未知时?
  • 不定长数组
    • #includestd::vector
    • Sequence Container
    • Random-access iterator
    • 随机访问: operator [], at(x), front(), back()
    • insert(iter, x), push_back(x)
    • erase(iter), pop_back()

如何实现一个向量？

收缩

性能分析

列表

列表与链表

  • 另外一种实现动态性的方式是不采用数组，而是每增加一个元素，新开辟一块空间
  • 但是我们依然需要保存一些额外信息来保存它们之间的顺序关系——指针!
  • 这种链状的数据结构称为链表(linked list)。
  • 例子:火车车厢
  • #includestd::list
    • Sequence container, Bidirectional iterator
    • front(), back()
    • insert(iter, x), push_back(x), push_front(x),
    • erase(iter), pop_back(), pop_front()

链表的结构

哨兵节点

基本操作

插入

Node* insert(Node* pos, int value) {
    Node* n = new Node(value);
    n->next = pos->next;
    pos->next = n;
    return n;
}

Node* insert(Node *pos, int value) { 
    Node *n = new Node(value); 
    n->next = pos->next;
    n->prev = pos;
    pos->next->prev = n; 
    pos->next = n;
    return n;
}
删除

void erase(Node *pos) { 
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;
    delete pos;
}

void erase2(Node *pos) {
    Node *tmp = pos->next;
    pos->next = pos->next->next;
    delete tmp;
}
遍历

  • for (Node* x = head->next; x != tail; x = x->next);
  • 对比迭代器的 begin() 和 end()
  • “下标”访问?
  • 单向链表查询上一个元素?
  • size()?

性能分析

优先级队列

std::priority_queue

  • Container Adaptor, 无迭代器
  • push(x), pop(), top()
  • std:priority_queue<T, Container=std::vector, Compare=std::less>
    • the Compare parameter is defined such that it returns true if its first argument comes before its second argument in a weak ordering. But because the priority queue outputs largest elements first, the elements that “come before” are actually output last
    • 需要定义小于号
    • std::greater(需要定义大于号)

Reference: std::priority_queue - cppreference.com

如何实现优先级队列?(选讲)

  • 多种实现方式，最简单的一种——二叉堆
  • 堆:满足父亲结点优先级不小于孩子结点的二叉树
  • 为了方便实现，可以采用完全二叉树
  • 向上调整过程 up, push()
  • 向下调整过程 down, pop()

一些应用

单调栈 单调队列

表达式求值

  • 为了简化问题，假设我们只有 + - * / () 这几种运算
  • 观察:1+23 和 12+3。我们什么时候可以确定计算顺序?
  • 第一个等式需要到最末尾，第二个等式在扫描到 + 的时候就发现可以计算前面的内容
  • 无法判断的式子优先级大小递增
  • 类似单调队列的单调栈。同时需要维护没有计算的数
  • 括号?将括号也纳入优先级比较的范围，或者每遇到一层括号，括号内优先级增加一档

Huffman编码

  • (问题的最后一步)有一个长度为 n 的序列，进行 n – 1 次操作，每次将值最小的两个元素取出，再将它们的和放回序列。求每步操作取出的两个数是多少
  • 对比优先队列的定义和接口
Related Posts