C++实现编译期容器（`ct::vector`/`ct::map`）：确保所有操作在编译时完成

C++ 编译期容器：ct::vector 和 ct::map 的设计与实现

大家好，今天我们来探讨一个高级 C++ 主题：编译期容器，特别是 ct::vector 和 ct::map 的设计与实现。 目标是创建一个能够在编译时执行所有操作的容器，这意味着容器的创建、修改、查询都必须在编译期间完成，而不是在运行时。 这需要我们深入了解 C++ 的模板元编程能力。

为什么要使用编译期容器？

编译期容器的主要优势在于性能。 通过在编译时计算结果，我们可以避免运行时的开销，从而提高程序的执行效率。 此外，编译期容器可以增强代码的安全性，因为许多错误可以在编译时被检测出来。例如，尝试访问超出 ct::vector 范围的元素会导致编译错误，而不是运行时错误。

核心概念：模板元编程

实现编译期容器的关键技术是模板元编程 (Template Metaprogramming, TMP)。 TMP 允许我们使用模板在编译时执行计算。 我们利用模板特化、递归模板和 constexpr 函数来实现编译期逻辑。

ct::vector 的设计与实现

首先，我们从 ct::vector 开始。 ct::vector 应该具备以下基本功能：

• 编译期创建
• 编译期元素访问
• 编译期大小查询

1. 基本框架

我们使用模板来定义 ct::vector，并使用一个 std::array 作为底层存储。

#include <array>
#include <utility> // std::index_sequence, std::make_index_sequence

namespace ct {

template <typename T, size_t N, typename IndexSequence = std::make_index_sequence<N>>
struct vector;

template <typename T, size_t N, size_t... I>
struct vector<T, N, std::index_sequence<I...>> {
  private:
    std::array<T, N> data;

  public:
    constexpr vector(T const (&init)[N]) : data{{init[I]...}} {}

    constexpr size_t size() const { return N; }

    constexpr T const& at(size_t index) const {
      static_assert(index < N, "Index out of bounds");
      return data[index];
    }

    constexpr T const& operator[](size_t index) const {
        return data[index];
    }

    // ... 更多功能将在后面添加 ...
};

} // namespace ct

说明：

• ct::vector<T, N> 是一个模板类，接受元素类型 T 和大小 N 作为模板参数。
• std::array<T, N> 是底层存储，它是一个固定大小的数组，在编译时确定大小。
• std::index_sequence 和 std::make_index_sequence 用于生成一个编译时索引序列，方便我们进行初始化和其他操作。
• 构造函数使用数组初始化列表，在编译时初始化 data。
• size() 函数返回向量的大小，它是一个 constexpr 函数，可以在编译时调用。
• at() 函数提供安全的访问方式，如果索引越界，会触发编译时错误。
• operator[] 提供直接访问，但不会进行边界检查。

2. 编译期初始化

为了在编译时初始化 ct::vector，我们需要使用 constexpr 构造函数。

constexpr int init_data[] = {1, 2, 3, 4, 5};
constexpr ct::vector<int, 5> my_vector(init_data);
static_assert(my_vector.size() == 5, "Size mismatch");
static_assert(my_vector.at(0) == 1, "Value mismatch");
static_assert(my_vector[1] == 2, "Value mismatch");

说明：

• init_data 是一个 constexpr 数组，用于初始化 ct::vector。
• my_vector 是一个 constexpr ct::vector，它在编译时被初始化。
• static_assert 用于在编译时检查条件，如果条件不满足，则会触发编译错误。

3. 编译期修改 (有限制的)

由于 std::array 本身是不可变的，因此我们不能直接修改 ct::vector 中的元素。 但是，我们可以通过创建一个新的 ct::vector 来实现类似修改的效果。

template <typename T, size_t N, size_t... I>
struct vector<T, N, std::index_sequence<I...>> {
  // ... 之前的代码 ...

  template <size_t Index, typename U>
  constexpr vector set(U const& value) const {
    static_assert(Index < N, "Index out of bounds");
    std::array<T, N> new_data = data;
    new_data[Index] = static_cast<T>(value);
    return vector(new_data);
  }
};

constexpr int init_data[] = {1, 2, 3, 4, 5};
constexpr ct::vector<int, 5> my_vector(init_data);
constexpr ct::vector<int, 5> new_vector = my_vector.set<2>(10); // Set element at index 2 to 10
static_assert(new_vector[2] == 10, "Value mismatch");
static_assert(my_vector[2] == 3, "Original vector should not be modified");

说明：

• set() 函数接受一个索引 Index 和一个新值 value 作为参数。
• 它创建一个新的 std::array，并将索引 Index 处的元素设置为 value。
• 它返回一个新的 ct::vector，其中包含修改后的数据。
• 原始的 ct::vector 不会被修改。

4. 其他操作

我们还可以添加其他有用的操作，例如：

• empty()：检查向量是否为空。
• front()：返回第一个元素。
• back()：返回最后一个元素。

template <typename T, size_t N, size_t... I>
struct vector<T, N, std::index_sequence<I...>> {
  // ... 之前的代码 ...

  constexpr bool empty() const { return N == 0; }

  constexpr T const& front() const {
    static_assert(N > 0, "Vector is empty");
    return data[0];
  }

  constexpr T const& back() const {
    static_assert(N > 0, "Vector is empty");
    return data[N - 1];
  }
};

constexpr int init_data[] = {1, 2, 3, 4, 5};
constexpr ct::vector<int, 5> my_vector(init_data);
static_assert(!my_vector.empty(), "Vector should not be empty");
static_assert(my_vector.front() == 1, "Front value mismatch");
static_assert(my_vector.back() == 5, "Back value mismatch");

constexpr ct::vector<int, 0> empty_vector({});
static_assert(empty_vector.empty(), "Vector should be empty");

ct::map 的设计与实现

接下来，我们来实现 ct::map。 ct::map 是一个键值对的集合，其中键是唯一的。 我们需要实现以下基本功能：

• 编译期创建
• 编译期插入
• 编译期查找
• 编译期删除 (有限制的，类似 ct::vector 的修改方式)
• 编译期大小查询

1. 基本框架

我们使用两个 ct::vector 分别存储键和值。

#include <tuple>

namespace ct {

template <typename Key, typename Value, size_t N>
struct map {
private:
    ct::vector<Key, N> keys;
    ct::vector<Value, N> values;
    size_t current_size;

    template <size_t... I>
    constexpr map(const Key (&key_init)[N], const Value (&value_init)[N], std::index_sequence<I...>)
      : keys({key_init[I]...}), values({value_init[I]...}), current_size(N) {}

public:
    constexpr map(const Key (&key_init)[N], const Value (&value_init)[N]) : map(key_init, value_init, std::make_index_sequence<N>()) {}

    constexpr size_t size() const { return current_size; }

    // ... 更多功能将在后面添加 ...
};

} // namespace ct

说明：

• ct::map<Key, Value, N> 是一个模板类，接受键类型 Key、值类型 Value 和最大容量 N 作为模板参数。
• keys 和 values 是两个 ct::vector，分别存储键和值。
• current_size 记录当前map的大小。
• 构造函数接受两个数组，分别用于初始化键和值。

2. 编译期插入

插入操作需要检查键是否已经存在。 如果键不存在，则将其添加到 keys 向量，并将相应的值添加到 values 向量。 如果键存在，则返回原始map。由于编译期容器无法动态增长，所以我们简单的返回原始的map。

template <typename Key, typename Value, size_t N>
struct map {
private:
    ct::vector<Key, N> keys;
    ct::vector<Value, N> values;
    size_t current_size;

    template <size_t... I>
    constexpr map(const Key (&key_init)[N], const Value (&value_init)[N], std::index_sequence<I...>)
      : keys({key_init[I]...}), values({value_init[I]...}), current_size(N) {}

public:
    constexpr map(const Key (&key_init)[N], const Value (&value_init)[N]) : map(key_init, value_init, std::make_index_sequence<N>()) {}

    constexpr size_t size() const { return current_size; }

    template <typename K, typename V>
    constexpr map insert(const K& key, const V& value) const {
      for (size_t i = 0; i < current_size; ++i) {
        if (keys[i] == key) {
          return *this; // Key already exists, return original map
        }
      }

      // Key does not exist, create new map with inserted key-value pair (if space available)
      if (current_size < N) {
        Key new_keys[N];
        Value new_values[N];

        // Copy existing key-value pairs
        for (size_t i = 0; i < current_size; ++i) {
          new_keys[i] = keys[i];
          new_values[i] = values[i];
        }

        // Insert new key-value pair at the end
        new_keys[current_size] = key;
        new_values[current_size] = value;

        return map(new_keys, new_values); //creates a map of size N, with the new key value pair at the end.
      } else {
          return *this; // Map is full, return original map
      }
    }
};

constexpr int init_keys[] = {1, 2, 3};
constexpr int init_values[] = {10, 20, 30};
constexpr ct::map<int, int, 5> my_map(init_keys, init_values);
constexpr ct::map<int, int, 5> new_map = my_map.insert(4, 40);
static_assert(new_map.size() == 3, "Size mismatch"); //map 的大小始终是3， 因为构造函数是传递大小为3的数组，而不是大小为5的数组

说明：

• insert() 函数接受一个键 key 和一个值 value 作为参数。
• 它检查键是否已经存在于 keys 向量中。
• 如果键不存在，则创建一个新的 ct::map，其中包含新的键值对。
• 如果键已经存在或者map已满，则返回原始的 ct::map。

3. 编译期查找

查找操作返回与给定键相关联的值。 如果键不存在，则返回一个默认值 (例如，std::nullopt 或一个特殊的标记值)。 为了简化，这里返回一个默认构造的值。

#include <optional>

template <typename Key, typename Value, size_t N>
struct map {
private:
    ct::vector<Key, N> keys;
    ct::vector<Value, N> values;
    size_t current_size;

    template <size_t... I>
    constexpr map(const Key (&key_init)[N], const Value (&value_init)[N], std::index_sequence<I...>)
      : keys({key_init[I]...}), values({value_init[I]...}), current_size(N) {}

public:
    constexpr map(const Key (&key_init)[N], const Value (&value_init)[N]) : map(key_init, value_init, std::make_index_sequence<N>()) {}

    constexpr size_t size() const { return current_size; }

    template <typename K, typename V>
    constexpr map insert(const K& key, const V& value) const {
      for (size_t i = 0; i < current_size; ++i) {
        if (keys[i] == key) {
          return *this; // Key already exists, return original map
        }
      }

      // Key does not exist, create new map with inserted key-value pair (if space available)
      if (current_size < N) {
        Key new_keys[N];
        Value new_values[N];

        // Copy existing key-value pairs
        for (size_t i = 0; i < current_size; ++i) {
          new_keys[i] = keys[i];
          new_values[i] = values[i];
        }

        // Insert new key-value pair at the end
        new_keys[current_size] = key;
        new_values[current_size] = value;

        return map(new_keys, new_values); //creates a map of size N, with the new key value pair at the end.
      } else {
          return *this; // Map is full, return original map
      }
    }

    constexpr Value at(const Key& key) const {
      for (size_t i = 0; i < current_size; ++i) {
        if (keys[i] == key) {
          return values[i];
        }
      }
      return Value{}; // Key not found, return default value
    }
};

constexpr int init_keys[] = {1, 2, 3};
constexpr int init_values[] = {10, 20, 30};
constexpr ct::map<int, int, 5> my_map(init_keys, init_values);
static_assert(my_map.at(2) == 20, "Value mismatch");
static_assert(my_map.at(4) == 0, "Value mismatch");

说明：

• at() 函数接受一个键 key 作为参数。
• 它在 keys 向量中查找键。
• 如果找到键，则返回 values 向量中相应的值。
• 如果未找到键，则返回 Value{} (Value的默认构造值).

4. 编译期删除 (有限制的)

类似于 ct::vector 的修改，我们不能直接从 ct::map 中删除元素。 但是，我们可以通过创建一个新的 ct::map 来实现类似删除的效果。

template <typename Key, typename Value, size_t N>
struct map {
private:
    ct::vector<Key, N> keys;
    ct::vector<Value, N> values;
    size_t current_size;

    template <size_t... I>
    constexpr map(const Key (&key_init)[N], const Value (&value_init)[N], std::index_sequence<I...>)
      : keys({key_init[I]...}), values({value_init[I]...}), current_size(N) {}

public:
    constexpr map(const Key (&key_init)[N], const Value (&value_init)[N]) : map(key_init, value_init, std::make_index_sequence<N>()) {}

    constexpr size_t size() const { return current_size; }

    template <typename K, typename V>
    constexpr map insert(const K& key, const V& value) const {
      for (size_t i = 0; i < current_size; ++i) {
        if (keys[i] == key) {
          return *this; // Key already exists, return original map
        }
      }

      // Key does not exist, create new map with inserted key-value pair (if space available)
      if (current_size < N) {
        Key new_keys[N];
        Value new_values[N];

        // Copy existing key-value pairs
        for (size_t i = 0; i < current_size; ++i) {
          new_keys[i] = keys[i];
          new_values[i] = values[i];
        }

        // Insert new key-value pair at the end
        new_keys[current_size] = key;
        new_values[current_size] = value;

        return map(new_keys, new_values); //creates a map of size N, with the new key value pair at the end.
      } else {
          return *this; // Map is full, return original map
      }
    }

    constexpr Value at(const Key& key) const {
      for (size_t i = 0; i < current_size; ++i) {
        if (keys[i] == key) {
          return values[i];
        }
      }
      return Value{}; // Key not found, return default value
    }

    constexpr map erase(const Key& key) const {
      Key new_keys[N];
      Value new_values[N];
      size_t new_size = 0;

      for (size_t i = 0; i < current_size; ++i) {
        if (keys[i] != key) {
          new_keys[new_size] = keys[i];
          new_values[new_size] = values[i];
          new_size++;
        }
      }

      return map(new_keys, new_values);
    }
};

constexpr int init_keys[] = {1, 2, 3};
constexpr int init_values[] = {10, 20, 30};
constexpr ct::map<int, int, 5> my_map(init_keys, init_values);
constexpr ct::map<int, int, 5> new_map = my_map.erase(2);
static_assert(new_map.size() == 3, "Size mismatch"); //构造函数限制， 实际大小为3
static_assert(new_map.at(2) == 0, "Value mismatch");

说明：

• erase() 函数接受一个键 key 作为参数。
• 它创建一个新的 ct::map，其中不包含键 key 对应的键值对。
• 它返回一个新的 ct::map，其中包含删除元素后的数据。

局限性与改进方向

目前实现的 ct::vector 和 ct::map 存在一些局限性：

• 固定大小： 容器的大小在编译时必须确定，无法动态调整。
• 有限的修改能力： 无法直接修改容器中的元素，只能通过创建新的容器来实现类似修改的效果。
• 性能： 对于大型容器，编译时间可能会很长。

为了解决这些局限性，可以考虑以下改进方向：

• 使用更高级的模板元编程技术： 例如，使用 constexpr 算法来优化编译时间。
• 支持更复杂的数据结构： 例如，使用编译期红黑树来实现 ct::map，以提高查找效率。

总结：编译期容器的优势与局限

这篇文章深入探讨了编译期容器 ct::vector 和 ct::map 的设计与实现，展示了如何利用 C++ 的模板元编程能力在编译时创建和操作容器。虽然目前实现存在固定大小和有限修改能力等局限性，但编译期容器在性能和安全性方面具有显著优势，并且可以通过更高级的模板元编程技术进行改进，未来可以应用于对性能要求极高的场景。

更多IT精英技术系列讲座，到智猿学院