💻 CSC3200 Final Revision C++ 数据结构(线性)

November 21, 2025

C++ 数据结构(线性) ：链表、栈、队列、映射、集合

数组、向量和链表是 C++ 比较基础的数据结构，可以简单的从零建立；树和映射则为 STD 中有实现的复杂数据结构。

栈和队列是对“线性表”操作受限后的抽象（LIFO/FIFO），实现可以用数组或链表；而集合可以用四种基础数据结构实现。

数组已在先前阐释过，故在本文中，我们将先着重于线性数据结构的理解。在下半部分，我们学习树、图、堆三个非线性数据结构。

一、链表 LinkedList：“数组 vs 链表”与指针操作

抽象定义

单链表是用指针单向连起来的离散内存块：每个节点都存储着下个节点的指针。

目标：存一串数据，支持比数组更简单地插入或删除，可以做到遍历
数组和向量的特点：访问快、插删难。连续内存，O(1) 随机访问，但中间插入删除要整体移动，长度不易动态改变
链表的特点：插删快、访问慢。每个结点单独 new 出来，用 next 串起来，内存不连续。插入/删除只改指针，O(1)；但随机访问变成 O(n)

核心代码模板

结点与基本表体：

template <typename T>
class Node {  // 节点
public:
    T element;  // 成员变量：任意数据类型的数据
    Node *next;  // 成员变量：指向节点类的空指针

    Node(const T& e = T(), Node *n = nullptr)  // 类构造函数
    // 节点里装着数据 element，以及指向“下一个节点”的指针 next
        : element(e), next(n) {}  
        // 初始化成员变量，调用时比如：new Node<int>(5, nullptr)
};

template <typename T>
class List {  // 表体
private:
    Node<T> *dummyHead;  // 空占位头结点
public:
    List() {  // 无参数构造
        dummyHead = new Node<T>(T(), nullptr);
    }
    Node<T>* zeroth() { return dummyHead; }
    Node<T>* first()  { return dummyHead->next; }  // 指针用箭头访问成员
    bool isEmpty() const { return first() == nullptr; }  //判断表是否空
};

带 dummy head 的好处：

dummyHead 是一个 Node<T> 的实例，作为链表的表头，其数据为T()也就是空字符/0，其指针默认为空指针
保证新建立的链表永远有头结点 (即使实际为空)，后续代码可兼容 dummyHead
链表 “是否为空” 只需判断 dummyHead->next == nullptr

复习点：

Node<T> *nPtr = new Node<T>(…) 不是说 Node<T> 是指针类，而是说创建一个实例后直接获得其指针 nPtr
指针对应数据在内存中的位置：T *ptr = &a，*ptr 等价于 a，&a 等价于 ptr
ptr->member 与 (*ptr).member 等价，指针只能通过 -> 访问成员变量和方法
模版类可以让代码段兼容不同数据类型：

template <typename T>  // 或写 class T，等价
T add(T a, T b) { return a + b; }
auto x = add(1, 2);  // 类型自动推导 -> add<int>
auto y = add<double>(1, 2.5);  // 显式指明模板实参
// 以及在模板类外，调用模板：
template <typename T>
struct Stack { void push(const T&); };  // 类内成员函数不需重申 template
template <typename T>  // 在类外的成员函数必须再写一次 template
void Stack<T>::push(const T& x) { /*...*/ }

典型成员函数

在结点 p 之后插入 data

template <typename T>
void List<T>::insert(const T& data, Node<T>* p) {
// p 是老节点的内存位置（插在哪）
    Node<T>* newNode = new Node<T>(data, p->next);
    // 此刻 新节点的 next 被初始化为“插入前 p 的 next 指针的原本值”。如果新节点插在 p、q 间，那么 newNode->next 指向 q；如果 p 后原本没有节点，就指向 nullptr
    p->next = newNode;  // 将老节点的 next 改指向这个新节点，完成插入
}

链表的基本结构如下 (实际中节点都是直接指针传参，& 不用写在代码中)：

<头> DH(null, &N1)→N1(e1, &N2)→N2(e2, nullptr) <尾>

注意：

“新建”和“改指”两行顺序不能反，否则会链表会断，但是两行可以合并成：p->next = new Node<T>(data, p->next);。这是因为赋值符号优先级较低，右边的运算会先进行，所以 new 去到的 p->next 是老的值。
dummyHead 也可以用这个插入函数
需保证 p != nullptr 且 p 属于这条链表
用了裸指针 + new，别忘记在 List 析构函数遍历 delete 所有结点

查找值为 data 的节点(的指针)

template <typename T>
Node<T>* List<T>::find(const T& data) {
    Node<T>* p = first();  // 指向 dummyHead 后的第一个实节点
    while (p) {  // 遍历，直到 nullptr (等价于 false) 断开
        if (p->element == data) return p;
        p = p->next;  // 改指向下一个节点
    }
    return nullptr;  // 没找到
}

删除值为 data 的节点，先需要先找到前驱结点

template <typename T>
Node<T>* List<T>::findPrevious(const T& data) {  // 找前一项才能得到指针
    Node<T>* p = zeroth();
    while (p->next) {
        if (p->next->element == data) return p;
        // “当前项指向下一项的指针”访问下一项的数据，符合就传回这个“指向下一项的指针”
        p = p->next;
    }
    return nullptr;
}
template <typename T>
void List<T>::remove(const T& data) {
    Node<T>* p = findPrevious(data);
    if (p) {  // 之前没找到 data 就不会删任何东西，因为指针为空
        Node<T>* tmp = p->next;  // 指向 data 再后面一项
        p->next = tmp->next;  // 前一项跳过 data 指向再后面一项
        delete tmp;
    }
}

注意：其实并没有“删除”数据本身，只是将相邻项指针连起来，把这一项移出链表而已

同时要实现：

析构函数 ~List()：从 zeroth() 开始删除所有节点
拷贝构造、赋值运算符：深拷贝每个结点，不能只拷贝指针

和数组的对比复杂度

数组：

访问 a[i]：O(1)
头插、头删：O(n)（需要整体移动）

单链表：

顺序访问第 k 个：O(k)
已知指针 p 的前提下，在 p 后插入 / 删除：O(1)

典型考点：什么时候用数组，什么时候用链表？

需要大量随机访问 → 数组 / vector
经常在中间插入/删除，长度不确定 → 链表

注意点

插入/删除顺序：先接再断或者先接再删，否则会丢链
带 dummy head 的版本 vs 不带版本的差异
深拷贝/析构：避免内存泄漏与浅拷贝问题

二、栈 Stack：LIFO、数组 & 链表版

抽象定义

接口：push(x), pop(), peek(), isEmpty()
特性：后进先出 (LIFO)。类似于牌堆，后放上去的先被抽走。只有单向操作 (在栈顶)。所有基本操作时间复杂度都是 O(1)。

栈类的结构模板

头文件：

template <typename T>
class Stack {
public:
    Stack();
    bool isEmpty() const;
    void push(const T& x);
    T& pop();   // 删除并返回栈顶
    T& peak();  // 只读栈顶
};

数组实现 (顺序栈)

const int MAX_STACK = 1000;  // 固定容量

template <typename T>
class Stack {
private:
    T items[MAX_STACK];  // “数组”栈
    int top;  // top == 当前占用位数 == 下次插入位置(当前栈顶以上一项)

public:
    Stack() : top(0) {}  // 初始化：top=0，数组为空
    bool isEmpty() const { return top == 0; }

    void push(const T& x) {
        if (top >= MAX_STACK)
            throw StackException("stack full");
        items[top++] = x;  // 先写入，再把 top 加 1
    }
    T& pop() {
        if (isEmpty())
            throw StackException("stack empty");
        return items[--top];
        // 先将 top-1 ，然后返回这个值(顶项值)。下一次push 会占用 top-1，盖掉这个原本的值
    const T& peek() {  // 不能改变栈
        if (isEmpty())
            throw StackException("stack empty");
        return items[top - 1];  // 返回顶项指
    }
};

数组栈从底到顶的结构如下：

<底> [i_0, i_1,......, i_n] <顶>, top=n+1

问题：容量固定，可能溢出；可以改用动态数组 std::vector（new T[capacity] 并在满时扩容）
复习：++x 先自增后调用；x++ 先调用后自增

链表实现 (链栈)

需要实现：指向栈顶的成员指针变量 topPtr、next 指针指向旧节点

template <typename T>
class StackNode {  // 节点类
public:
    T item;
    StackNode *next;
    StackNode(const T& e = T(), StackNode* n = nullptr)
        : item(e), next(n) {}
};

template <typename T>
class Stack {
private:
    StackNode<T> *topPtr;
public:
    Stack() : topPtr(nullptr) {}  // 初始化：topPtr指向空，链表为空
    bool isEmpty() const { return topPtr == nullptr; }

    void push(const T& x) {
        auto *newPtr = new StackNode<T>(x, topPtr);  // 自动推导指针类型
        topPtr = newPtr;  // 下一个节点会指向现在的节点：后进先出
    }
    const T& peek() {
        if (isEmpty()) throw StackException("empty");
        return topPtr->item;
    } 
    T& pop() {
        T& stackTop = T();
        if (!isEmpty()) {
	        stackTop = topPtr->item;
	        StackNode<T> *tmp = topPtr;
	        topPtr = topPtr->next;
	        delete tmp;  // 将顶项的指针移出了链表
	    }
		return stackTop;
	}
};

链栈类似于一个反过来的链表，next 指针朝向老节点，从底到顶结构如下 (N 代表 StackNode)：

<底> N1(nullptr, i1)←N2(&N1, i2)←N3(&N2, i3)←N4(&N3, i4)←...

注意点

栈一般用于：

括号/HTML 标签匹配、表达式求值（运算符栈、操作数栈）
回溯算法（数独、全排列、路径搜索中的状态回退）这些撤销、反推类问题。

三、队列 Queue：FIFO、循环数组 & 链表版

抽象定义

接口：enqueue(x) 入队 (从尾部)、dequeue() 出队 (从头部)、getFront() 查看队头、isEmpty()。
特性：先进先出 FIFO。类似于水管，先流入的也先流出。常用于排队、任务调度、缓冲区。和栈的明显区别是：首尾双向操作。和栈的相同点：基本操作时间复杂度都是 O(1)。

链表实现 (带 front/back 指针)

需要实现：指向首尾项的成员指针变量——用于插入和踢出、next 指针指向新节点

template <typename T>
class QueueNode {
public:
    T item;
    QueueNode *next;
    QueueNode(const T& e = T(), QueueNode* n = nullptr)
        : item(e), next(n) {}
};
template <typename T>
class Queue {
private:
    QueueNode<T> *frontPtr;  // 双向检索
    QueueNode<T> *backPtr;
public:
    Queue() : frontPtr(nullptr), backPtr(nullptr) {}
    bool isEmpty() const { return frontPtr == nullptr; }

    void enqueue(const T& x) {
        auto* newPtr = new QueueNode<T>(x, nullptr);  // 指向新节点
        if (isEmpty()) frontPtr = newPtr;
        else backPtr->next = newPtr;  // 原本队尾的 next 指向新节点
        backPtr = newPtr;  // 队尾变成这个新节点
    }
	void dequeue() {
	    if (isEmpty()) throw QueueException("empty");
	    auto* old = frontPtr;              // 旧队头
	    frontPtr = frontPtr->next;         // 前移指针，将旧队头移出队列范围
	    if (!frontPtr) backPtr = nullptr;  // 若队列被删空，把尾指针也置空
	    delete old;                        // 释放旧队头
	}
    void getFront(T& x) const {
        if (isEmpty()) throw QueueException("empty");
        x = frontPtr->item;
    }
};

所有基本操作都 O(1)，与栈类似。
链队列和链栈不同，是正向的链表，next 指针朝向新节点 (队尾)，从头到尾结构如下 (N 代表 QueueNode)：

<头> N1(&N2, i1)→N2(&N3, i2)→N3(&N4, i3)→N4(nullptr, i4) <尾>

循环数组实现 (顺序队列)

需要实现：有限数组首尾相连成环，即使数组容量固定也永远不会溢出，这样删除队首时就无需整体前移一位，而是在超出索引范围后绕回 0(数组开头)。这种数组的首项位置是不固定的，如图：

const int MAX_QUEUE = 1000;

template <typename T>
class Queue {
private:
    T items[MAX_QUEUE];
    int front;  // 队头下标，注意不一定是 0
    int back;   // 队尾下标
    int count;  // 当前元素数
public:
    Queue() : front(0), back(MAX_QUEUE-1), count(0) {}
    bool isEmpty() const { return count == 0; }

    void enqueue(const T& x) {
        if (count == MAX_QUEUE) throw QueueException("full");
        back = (back + 1) % MAX_QUEUE;  // *核心逻辑*
        // back 一旦超出 MAX_QUEUE 就从 0 开始回填，保证索引不溢出 (上一行的 throw Exception 确保这种“回填”绝对不会覆盖掉 front，因为超出 MAX_QUEUE 了)
        items[back] = x;
        ++count;
    }
    void dequeue() {
        if (isEmpty())
            throw QueueException("empty");
        front = (front + 1) % MAX_QUEUE;  // 同理，防止索引向负数溢出
        --count;
    }
    T& getFront() const {
        if (isEmpty())
            throw QueueException("empty");
        return items[front];
    }
};

注意：对于一个长度 1000 的数组，索引在 0～999 范围。因为 dequeue 时数组首项被移出队列范围 (还在数组中)，为了防止 enqueue 到 1000 时索引溢出，用求余 MAX_QUEUE 实现“循环数组”，即数组首尾成环：1000≡0、1001≡1 …。这样就无需 dequeue 时所有元素整体向前移动。所以说，back 完全可能在 front 之前。

注意点

循环数组下标更新公式：

   back = (back + 1) % MAX_QUEUE; ++count;    //  enqueue 扩容
   front = (front + 1) % MAX_QUEUE; --count;  // dequeue 减容

链表 vs 数组队列的比较：

链表不需要固定容量；

数组实现需处理「满 vs 空」区分问题，但常数因子小。
队列一般用于：操作系统任务队列、网络包缓冲队列、打印队列等。

四、映射 Map：键值对、哈希函数与桶

抽象定义

Map (字典类) 维护一组 (key, value) 键值对。类似于数学中的函数映射，两组元素必须有某种映射关系，不一定满足双射 (键值对完美一一对应)。
典型操作：操作符 operator[]：既可插入也可查找；put(key, value)：插入或更新；get(key)：根据 key 查 value；containsKey(key)；remove(key)；size() / isEmpty()。

在标准 C++ 库中已经存在两种实现方法：

std::map<K,V>：基于平衡 BST 红黑树，有序；O(log n)。
std::unordered_map<K,V>：基于HashMap 哈希表，无序；平均 O(1)。

向量 (动态数组) 实现：线性查找 / 二分查找

简单地实现 string → string 映射字典：

struct KeyValuePair {
    std::string key;
    std::string value;  // 键值对 {key, value}
};

class StringMap {
public:
    StringMap() {}
    ~StringMap() {}
    // 构造/析构都没自定义逻辑，vector 类会自己管理元素生命周期
    std::string get(const std::string& key) const {
        int index = findKey(key);  // 见 private 域，获取索引
        return (index == -1) ? "" : bindings[index].value;
        // 找不到则返回空字符串
    }
    void put(const std::string& key, const std::string& value) {
        int index = findKey(key);
        if (index == -1) {  //  如果当前不存在这个 key
            KeyValuePair kv{key, value};
            // 这是一个在第一行声明的键值对实例，被打包塞进 bindings
            bindings.push_back(kv);  // vector 类的成员方法（插入）
        } else {
            bindings[index].value = value;  // 存在就覆盖原本的值
        }
    }
private:
    std::vector<KeyValuePair> bindings;
    // 用动态数组 bindings 存储键值对 {key, value}
    int findKey(const std::string& k) const {
        for (int i = 0; i < (int)bindings.size(); ++i)
            if (bindings[i].key == k) return i;  // 遍历返回对应索引
        return -1;  // 找不到，返回异常状态码
    }
};

std::vector 本质是动态数组，用 .size() 看大小；用 .push_back(e) 末尾插入元素 e；用 .value / .key 分别访问键和值
bindings 动态数组中存储信息的结构：

std::vector [{key1, value1}, {key2, value2}, ... , {键值对}]
这个实现无法满射，因为 bindings 中 key 无法重复，就不能同个 key 对应多个 value；put() 给已知的 key 新 value 时会直接覆盖就 value
这个实现可以单射，因为不同 key 可以有相同 value (value 可以重复)
这段代码的查找/插入都是 O(n)，极其低效，仅用于演示
复习：上述代码中出现了用于分情况处理的“三元运算符”

return (index == -1) ? "" : bindings[index].value;
// 核心结构：<cond ? expr1 : expr2>，逻辑：cond 真就传回 expr1；假就传回 expr2

哈希表 (unordered_map) 实现

哈希表是一个 std 库中用 “哈希函数” 实现映射的方法

关键思想：

核心是哈希函数 hashCode(key)：把 key 映射为非负整数；取余得到它属于的桶下标：index = hashCode(key) % nBuckets;，如果哈希函数不优质会导致哈希表退化。
桶：可以理解为 “一个槽位 + 指向该桶第一个节点的指针” 组成的数组
链表：每个节点保存 {key, value, next}；同一桶中的节点通过 next 串起来
每个桶存一条链表（或 vector）来处理冲突（separate chaining）

哈希表的三个部件：

哈希函数 hashCode(key): 把键映成一个尽量不相同的整数。
桶数组 (bucket array): 固定长度 B 的数组，每个槽位叫“桶”。
碰撞处理: 两个不同键被哈希函数映到同一桶时的处理。unordered_map 采用分离链表 (separate chaining)：每个桶保存一条小链表。

哈希表的私有域：

class StringMap {
private:
    struct Cell {
        std::string key;
        std::string value;  // 键值对
        Cell *link;  // 链指针，指向下个键值对节点
    };
    Cell **buckets;  // 指向桶数组
    int nBuckets;    // 桶个数
    int count;       // 已存 key 数量
    Cell* findCell(int bucket, const std::string& key);
};

哈希表的结构大致为：

桶数组 → (键, 值,  next指针)
[0]   →  ("AR", "5", ptr) → ("AK", ... ) → null
[1]   →  ("AL", ... ) → null
[2]   →  null
...
[nBuckets]   →  ("NV", ... ) → ...

哈希表 std::unordered_map 的实例化

#include <unordered_map>
#include <string>
#include <iostream>

int main(){
    std::unordered_map<std::string, int> m;  // 实例化“字符串→整数”哈希表
    m.reserve(1024);              // 预留 1024 个键值对，减少 rehash 频率
    m.max_load_factor(0.7f);      // 限制装载因子，限制桶内链表长度

    m.emplace("alice", 1);   // 等价于 insert({k, v})，不会覆盖存在的键值对
    m["bob"] = 2;  // 这是操作符：operator[](k) = v，会覆盖存在的键值对

    if (auto it = m.find("alice"); it != m.end())
        std::cout << it->first << " -> " << it->second << "\n";

    std::size_t bc = m.bucket_count();
    std::size_t b  = m.bucket("alice");  // "alice" 键被哈希函数放到了哪个桶？
    std::cout << "bucket_count=" << bc
              << ", bucket(alice)=" << b
              << ", bucket_size=" << m.bucket_size(b) << "\n";
}

哈希表-键值对结构：unordered_map<first, second>

桶大小与桶扩容 (rehash)：

.size() 代表所有桶中的键值对数量；.bucket_size(i) 代表第 i 个桶的键值对数量；.bucket_count() 代表哈希表数组中桶的个数；.reserve(e) 代表预留 e 个键值对位置
装载因子=$\frac{.size()}{.bucketcount()}$，就是每个桶平均装了多少个键值对。.max_load_factor() 设定最大装载因子，超过时触发 rehash：扩容桶数组，重新分配所有 key 无论是插入还是查找，都要先用哈希函数推导出对象应该在哪个 bucket 插入项目：
不覆盖：emplace(k, v) 或 insert({k, v})
覆盖：用操作符 operator[](k) = v 比如 map[k]=v
查找项目：.find(k) 按键查找，平均 O(1)。若找到，返回指向该元素的指针；否则等于 .end()

Map 实现方式对比

平衡 BST (std::map)：(后续再讲具体操作)
- 有序（可以按 key 递增遍历）
- 操作复杂度：O(log n)
哈希表 (std::unordered_map)：
- 无序，迭代顺序不稳定
- 平均 O(1)，最坏 O(n)（当复杂因子超过 0.7，出现大量冲突）
- 关键是 hash 函数好坏、负载因子控制
教学用的 向量 + 线性/二分查找 实现：
- 性能一般（O(n)）

注意点

理解哈希表的结构：

哈希函数将 key 映射到 bucket 数组的整数下标 → 分配桶 → 装入桶中的链表

为什么冲突不可避免？不完美的哈希函数和有限的桶，导致不同 key 被映射到同个桶
负载因子与 rehash：

为什么负载因子大了性能会恶化？链表变长，导致查找/插入功能退化

rehash 的代价与摊还复杂度

五、集合 Set：集合运算 & 实现

抽象定义

集合是无序、不重复的枚举数据结构。同一组数据，插入到数组 A 和集合 S 后，可以得到数据的总重复次数：

A.size() - S.size()

集合类的接口：

add(x) / insert(x)：加入元素；remove(x)：删除元素；contains(x)：是否属于；
以及数学运算：∪（并）、∩（交）、-（差）。

四种实现方式对比

你只需要熟练掌握“链集合”的实现方法即可

1. 指针 (链表) 实现

实现方法类似 LinkedList：可以用占位空节点 (dummyHead)，每个结点对应一个元素，先找到前项再用其 next 指针 remove 后项。两者的区别是插入前要调用 contains() 防止重复。
时间：搜索、插入、删除平均 O(n)。以下是 contains() + insert() 的 “在头部插入” 实现例：

// 对于 Node {T val; Node* next;}
	bool contains(const T& x) const {
	    for(auto* p = dummyHead->next; p; p=p->next) {  // head 代表占位空节点
	        if(p->val==x) return true;
	    }
	    return false;
    }
    void insert(const T& x) {if(!contains(x)) dummyHead->next = new Node<T>(x, dummyHead->next);}  // 先查重
    // 先将 head->next 赋给 new Node，然后把 new Node 的指针赋给 head->next

这种“链集合”从头开始的结构如下：

DH(null, &N1)→ <insert 位置> →N1(v1, &N2)→N2(v2, nullptr)

优点：实现基础简便；对很小的集合 (几十个以内)足够；擅长查重。

缺点：时间复杂度高、查找慢、指针开销大、缓存 (chache) 对此不太高兴。

2. BST 实现 (标准库 std::set)：

C++ 中 BST (平衡二叉搜索树)一般用的是“红黑树”。
关键操作 insert/erase/find 平均/最坏都是 O(log n)。
支持有序遍历 (中序遍历)。具体如何实现，我们放在树之后阐述

3. 哈希函数实现 (std::unordered_set)：

哈希集合是一个 std 库中用 “哈希函数” 实现集合的方法

利用哈希函数将键映射到桶；桶内冲突用链表解决。平均 O(1) 插入/删除/查找，最坏 O(n)（装载因子过高，哈希退化）
不保证顺序；需要良好的哈希函数和 rehash 机制控制负载因子。以下是实例化哈希集合，实现储存”点“的集合：

#include <unordered_set>
struct Point { int x,y; };
struct PointHash {  // 哈希函数
    size_t operator()(const Point& p) const noexcept {
    // 把 x,y 混合成一个 64 位数，也就是把 Point 映射成 size_t
        return std::hash<long long>()(( (long long)p.x<<32 ) ^ (unsigned)p.y);
    }
};
struct PointEq {  // 相等比较函数
    bool operator()(const Point& a, const Point& b) const noexcept {
        return a.x==b.x && a.y==b.y;
    }
};
std::unordered_set<Point, PointHash, PointEq> us;
// unordered_set 要求进入其中的类型传入”元素、哈希函数、比较相等函数“
us.reserve(1024);  // 预留 1024 个点位，减少 rehash
us.insert(Point{1,2});
bool has = us.find(Point{1,2}) != us.end();  
// 判断找到的指针不等于空，返回 true

哈希集合的三个部件：

自定义的存储元素类型
优质的哈希函数
判断两个元素相等的方法

优点：大多数场景下最快的成员查询 (判断是否属于集合)；不关心顺序。

缺点：无序；对哈希函数的质量敏感；再哈希会使迭代器失效；内存碎片化。

何时选它：主要优势是在数据规模大时“判断是否在集合里”，不需要顺序。

4. 位向量集合 (std::bitset) 与集合运算：

当元素的“取值域”是有限且可编号的 (如 ASCII 字符、小范围的整数)，就可以用 1 bit 表示一个元素是否属于集合：1 表示在集合中，0 表示不在。把这一整排 bit 组成的数就叫特征向量 (characteristic vector) 或位向量。这样，集合运算就能退化为整数位运算，用 bit 运算完成集合运算——并：A | B ；交：A & B；差：A & ~B。速度极快针对「小整数 / 字符集」特别高效。注意位运算是从右到左的，如图：

单元素操作 O(1)；批量并/交/差为 O(n/word_size)。

以下是实例化位向量，实现集合运算（固定上界，用 std::bitset<N> 表示 [0,N-1]）：

#include <bitset>
std::bitset<1000> A, B;  // std::bitset 不可以在之后运算时扩容
A.set(3); A.set(10);
bool has3 = A.test(3);
A.reset(10);
auto C = A & B;        // 交集
auto D = A | B;        // 并集
auto E = A & ~B;       // 差集
auto F = A ^ B         // 异或

位操作：

置 1：.set(index)，将集合第 index 位变成 1，囊括到集合；无参数则全集合变 1
置 0：.set(index)，将集合第 index 位变成 0，剔除出集合；无参数则全集合变 0
运算符 operator[](index)：bitSet[index] = bin，将第 index 位向量变成 bin
数 1：.count()，计算集合有多少元素 (有多少 1)

以下是从零开始实现位向量集合的示例：

const int BITS_PER_BYTE = 8;
const int BITS_PER_LONG = BITS_PER_BYTE * sizeof(long);
const int requiredWords = (RANGE_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG;  // ceil(R/W) = (R+W-1)/W 是向上取整的标准形式
// requiredWords：大小为 RANGE_SIZE 的集合需要多少长整数来储存其特征向量？
struct CharacteristicVector {
   unsigned long words[requiredWords];
   // 定义”无符号长整数型“数组 words 及其容量
};
unsigned long createMask(int k) {  
    //  第 k 位掩码：只有第 k 位是 1。与它进行 AND 操作会只剩下第 k “向量维度”
   return unsigned long(1) << k % BITS_PER_LONG;
   // 强制转化 1 为长整型，然后左移 ”k 在所属 long 中的位数“，创造掩码
}
bool testBit(CharacteristicVector & cv, int k) {
    if (k < 0 || k >= RANGE_SIZE) {
       error("testBit: Bit index is out of range");
    }
    return cv.words[k / BITS_PER_LONG] & createMask(k);
    // 如果整个数组的第 k bit 为 1 就返回真
}
void setBit(CharacteristicVector & cv, int k) {
   if (k < 0 || k >= RANGE_SIZE) {
      error("setBit: Bit index is out of range");
   }
   cv.words[k / BITS_PER_LONG] |= createMask(k);
   // 将第 k bit 所在的那个 long 替换成它 OR 第 k 位掩码，也就是把它变 1
}
void clearBit(CharacteristicVector & cv, int k) {
   if (k < 0 || k >= RANGE_SIZE) {
      error("setBit: Bit index is out of range");
   }
   cv.words[k / BITS_PER_LONG] &= ~createMask(k);
   // 将第 k bit 所在的那个 long 替换成它 AND 第 k 位掩码的否定，也就是把它变 0
}

unsigned long 的长度是 32 或 64 bit，取决于计算机。复习：long() 是强制转换类型为 long 的意思，对字符(串)无效。
复习：向上取整 ceil(A/B)=(A+B-1)/B，向下取整 floor(A/B)=(A-B+1)/B
这段代码的核心是“掩码”的概念：一个通过 AND 操作掩盖掉无关的位的数。

在 bitwise calculation 的语境下，数字是从右往左读的，比如 long(3) 是 ”000…011“， long(3) << 2 是 ”000…01100“，同理 ”置 5“ 就是 long(1) << 5
k/BITS_PER_LONG 和 k%BITS_PER_LONG 分别返回 ”k 在第几个 long 里？“ 和 ”k 在所属 long 的第几位？“
words[] 的所有长整型元素代表了一个集合的特征向量，它们各自都包含 BITS_PER_LONG 个 bit 的二进制信息。

优点：极快、极省内存 (每元素 1 bit)；批量运算高效；适合字符集、稠密小整数集、图算法的“访问标记”。

缺点：需要已知且不太大的域上界；std::bitset<N> 的 N 必须是编译期常量；动态范围需用 vector<uint64_t> 或 boost::dynamic_bitset。

何时选它：元素是小范围整数（如 0..10^6 内）且集合运算很多；或需要极快的成员测试与批量并/交。

注意点

理解不同实现的时间复杂度、是否有序：

set vs unordered_set vs 位向量。
能把数学集合运算映射到实际代码：

用 bit 运算写 union/intersection/difference。
知道为什么 bitset 对「字符集合、少量小整数集合」非常高效。

CSC3200