C++ 标准库容器没有实现吗？

Question

我正在重新实现 C++ std 容器。

在“Marc Gregoire 的专业 C++”中我读了这句话

c++ standard specify the interface but not the implementation, of each container

实施意味着只是容器中的“模板 class”代码？

C++ 标准容器库中的实现是什么？

Answer 1

那句话意味着 c++ 标准规定了应该做什么，但没有规定应该如何做。例如，如果标准说“函数 sum 必须 return 对其参数求和的结果”，那么编译器可以轻松地以任何可用方式实现此行为，因此每个下一个实现都是合法的，并且选择哪个实现放入特定的编译器仅取决于编译器开发人员

template<typename T>
T sum(T a, T b)
{
    return a+b;
}

template<typename T>
T sum(T a, T b)
{
    return -(-a - b);
}

template<typename T>
T sum(T a, T b)
{
    return ("some random string" > 0)*a + b;
}

Answer 2

您可以在线找到所有 C++ 标准的草案。我建议看一看其中的一个。你可以在那里找到具体的例子，所以我可以使用一些假设

 void foo(int* a,int* b);

现在，例如 foo 的规范将说明以下内容：

前提：a和b指向同一个数组中的元素。
后置条件：[a,b) 范围内的所有元素都被 fooed。
复杂度：O(distance(a,b)).

就是这样。用户阅读标准并知道它的作用。实施者也阅读标准并且需要实施那里写的东西。例如，标准保证 foo 具有线性复杂度。如何实现取决于 foo.

的实施者

Answer 3

C++ 标准规定了功能。它不关心该功能是如何实现的。这类似于编码作业问题。教师指定学生代码所需的功能，而学生决定如何实现该功能。通常，正确答案不止一个。

让我们以std::vector为例。该标准规定 std::vector::size() 必须 return 常数时间内容器中的元素数。这意味着容器将在某处存储该大小，但由实现决定在哪里存储该大小。

一个实现可能会决定将该信息直接存储在 vector class 中，如下所示。（请接受我删减了一些细节以专注于相关部分。）

class vector<T> {
    T * data;
    size_type capacity;
    size_type size;      // <-- directly in the class

  public:
    // Public interface goes here.
    size_type size() const noexcept { return size; }
};

另一个实现可能决定最小化每个 vector 对象的大小，而是将 size 存储在动态分配的内存中。

struct vector_data<T> {
    size_type capacity;
    size_type size;
    T * data;   // Advanced techniques could avoid this extra layer of indirection
};

class vector<T> {
    std::unique_ptr<vector_data<T>> data;  // <-- Typically, the same size as a raw pointer

  public:
    // Public interface goes here.
    size_type size() const noexcept { return data->size; }
};

两种实现都符合标准的接口要求（嗯，C++ 17 标准，之前 size() 必须是 constexpr）。前者针对速度进行了优化，而后者针对（本地）space进行了优化。就 C++ 标准而言，任何一种方法都是可以接受的。

C++ 标准库容器没有实现吗？

Is c++ standard library containers have no implementation?

c++

containers

c++-standard-library