[CMU-15445/645]P0 - C++ Primer

实验说明

这个实验的要求是实现 Count-min sketch，代码中给出了定义，需要填写部分函数的实现，整体难度不大，主要是需要熟悉 C++ 的语法。

项目的编译环境通过 Docker 进行配置和管理，以下为 Dockerfile 内容:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
FROM ubuntu:24.04

ENV DEBIAN_FRONTEND=noninteractive
ENV CLANG_VERSION=15

RUN set -eux; \
    . /etc/os-release; \
    if [ "$VERSION_ID" != "24.04" ] && [ "$VERSION_ID" != "22.04" ]; then \
        echo "Unsupported Ubuntu version: $VERSION_ID"; \
        exit 1; \
    fi; \
    apt-get -y update; \
    apt-get -y install \
        build-essential \
        clang-${CLANG_VERSION} \
        clang-format-${CLANG_VERSION} \
        clang-tidy-${CLANG_VERSION} \
        cmake \
        doxygen \
        git \
        pkg-config \
        zlib1g-dev \
        libelf-dev \
        libdwarf-dev; \
    apt-get clean; \
    rm -rf /var/lib/apt/lists/*

Count-min sketch

这是一种利用哈希函数进行计数的数据结构，用少量的开销对重复出现的目标进行计算，但会损失部分精确度。查看 SPEC 可以很清楚地搞明白其工作原理。

在具体实现中遇到的几个问题耗时较多：

  1. 在添加了新的数据结构后，忘了在移动构造和移动赋值函数中进行相应处理

  2. hash_function_ 捕获 this 导致无法通过 std::move 移动

    1
    2
    3
    4
    5
    6
    /** @fall2025 PLEASE DO NOT MODIFY THE FOLLOWING */
    // Initialize seeded hash functions
    hash_functions_.reserve(depth_);
    for (size_t i = 0; i < depth_; i++) {
      hash_functions_.push_back(this->HashFunction(i));
    }

    这导致两个后果：

    (1) lambda 的捕获结构里包含原对象的 this

    即使对整个 hash_functions_ 执行：

    1
    std::move(hash_functions_);

    lambda 内部捕获的 this 依然指向原对象，不会发生语义上的“移动”。

    (2) 移动后 hash 函数依旧引用旧对象，导致未定义行为（UB)

    因此正确做法是：

    🟦 在移动构造 / 移动赋值中必须重新构造 hash_functions_，而不是简单移动。

  3. TopK(k, &candidates) 这个函数的理解出了问题

    ❌ 错误理解：

    以为 TopK 会先把 candidates 插入 sketch 再计算 top-k。

    ✔️ 正确含义：

    candidates 早已被插入并计数完毕，

    TopK 只是从这些候选项中根据当前 sketch 的估计值选出计数最高的 k 个。