设计回顾

你把问题复杂化了

你称它为映射，并且你谈到使用整数作为键。但是……实际上，由于你的键很小，你只是使用索引。所以你想要的实际上只是一个简单的数组，以及一种跟踪哪些索引是“活动的”的方法。

让我告诉你我的意思。

。它打印一年中至少有一个生日的每一天以及生日的数量。

现在，，我已将您的“map”类型替换为……一个简单的std::array。显然我必须更改一些东西，因为类型的迭代器返回一对，而std::array的迭代器返回单个值。但实际上我所要做的就是添加一个views::enumerate来重新创建“键”并获取“键值对”，以及一个过滤器以不打印生日为零的日期（即过滤掉“不活跃”的项目）。看，我得到了相同的输出，只是顺序不同。（顺便说一句，您的版本是错误的，因为关联容器应该按顺序返回结果。。）

当然，我稍微简化了一下，因为您真正想要的是array和某种方法来跟踪哪些索引是“活动的”（因此您不需要过滤器）。因此，基本上，一个带有 的类型array，加上一个bitset标志。

（或者，如果添加类型的顺序很重要，那么您需要一秒钟array或vector来跟踪它。但那样做很愚蠢，因为创建类型的顺序没有意义。）

无界面

如果你正在制作一个容器，那么最重要的事情就是遵循标准的容器接口。如果你不这样做，你的容器至少会很难使用，而且在实践中，几乎毫无用处。

就您而言，您正在制作一个关联容器，因此您应该尝试遵循。如您所见，那里有很多东西，但您不需要支持所有内容。显然，如果某些东西不适用于您的容器，则不要将其包括在内。

但是，您的类型有一个极其简单的接口……简单到我认为它通常无用。也许它适用于您心中的特定用例，但它绝对不是通用类型。

例如…我可以向地图“添加”项目（有点）…但我如何从地图中删除一个项目？目前我能想到的唯一方法是：

1. 创建一个全新的空白地图。
2. 循环遍历现有映射的元素。a. 如果键/值是我想要删除的，则不执行任何操作。b. 否则，将其复制到新映射。
3. 将新地图复制到旧地图上。

这太疯狂了。（而且由于我们将要遇到的 bug，它无法工作。）

不要将迭代器与其容器分开

该类型Iterator本身完全没有意义。它应该与容器相关联……但事实并非如此；它是一个完全独立的类型。

事实上，我可以这样做：

auto p = std::pair<int, double>{0, 0.0};
auto it = Iterator<int, double>{&p};    // whut?

没错，我可以创建一个“随机对的迭代器”……甚至不是一个容器，甚至不是一个对的序列，而只是内存中某处的一对随机对。

Iterator应该是 … 内的嵌套类型Container，并且不可能在容器之外构造迭代器（除非迭代器应该是默认可构造的 – 而您的不是 – 顺便说一下它应该被命名为iterator，而不是Iterator）。

因此，更像这样：

template <typename T, std::size_t N, typename K = std::size_t>
class MyContainer
{
public:
    class iterator
    {
    public:
        using iterator_concept  = std::contiguous_iterator_tag;
        using iterator_category = std::random_access_iterator_tag;

        using difference_type = std::ptrdiff_t;
        using value_type      = std::pair<K, T>;

        using pointer   = value_type *;
        using reference = value_type &;

        constexpr iterator() noexcept = default;

    private:
        constexpr explicit iterator(pointer pointer) noexcept
            : m_pointer(pointer)
        {}

        pointer m_pointer = nullptr;

        friend class MyContainer;
    };

    // ...
};

请注意，您还需要…const_iterator并且，const_iterator不仅仅是。const iterator

引发担忧

容器该如何命名

这是一张地图。

寻找现有的库而不是重新发明轮子

任何人都不可能建议任何现有的图书馆去做你需要做的事情，原因很简单，你没有说出你需要做什么。

性能提高了吗？

在开始担心性能之前，你真的应该先担心正确性。因为，剧透警告，这种类型使用起来非常危险，而且很容易被破坏。事实上，它确实充满了错误。

迭代器是否有可能生成 std​​::pair<const K, T> 而不会引入 UB 和影响性能？

是的，很简单。

template <typename T, typename K>
struct Iterator
{
    using iterator_category = std::random_access_iterator_tag;
    using difference_type = std::ptrdiff_t;
    using value_type = std::pair<const K, T>;
    using pointer = value_type*;
    using reference = value_type&;

    Iterator(pointer pointer) : m_pointer(pointer) {}

    reference operator*() const { return _val; }

    pointer operator->() { return &_val; }

    Iterator &operator++()
    {
        m_pointer++;
        _val = *m_pointer;
        return *this;
    }

    // ... and so on...

private:
    pointer m_pointer;
    std::pair<const K, T> _val;
};

这不是唯一的方法，我略过了某些复杂情况（T没有默认构造？结束迭代器取消引用？），但这就是要点。（更好的解决方案可能是保留optional值类型，并且仅在取消引用时使用它。但是，再次重申，这就是要点。）

但是，我的意思是，你可以重新考虑这个问题。你希望键为非的唯一原因const是因为你让它们变得无序。你可以简单地将数组初始化为{{0, defaultValue}, {1, defaultValue}, ...}，并跟踪哪些索引是“活动的”。然后键值就永远不需要改变。

代码审查

没有命名空间。您的所有代码都应位于命名空间中。污染全局命名空间是不礼貌的。

namespace delgan是一个不错的选择。

template <typename T, typename K>
struct Iterator;

这不应该是一个独立的类。它在容器之外没有任何意义。而且，容器和迭代器之间没有任何关联。

template <typename T, size_t N, typename K = size_t>
class MyContainer

因此，首先，没有这样的类型size_t。它是std::size_t，并且您必须包含。

由于历史原因，您的代码现在似乎只能正常工作。在不久的将来，这种情况将不再存在。

现在，我完全搞不懂为什么你允许将键类型作为模板参数。除了 之外，它还能是什么std::size_t？它必须可以从 转换0（参见构造函数），并且必须可以转换为std::size_t（参见括号运算符中的索引操作）。因此，它必须是某种整数，并且应该是无符号的（以避免负值的转换怪异）。

我认为理论上可以使用unsigned int或unsigned short类似的东西，但是……为什么？为什么允许这样做？它实际上并没有带来很多新的选择，但确实带来了新的风险。

无论如何，这些模板参数需要一些约束。K 必须是std::unsigned_integral。（实际上，应该只应该是std::size_t。）T必须至少是默认可初始化和可复制的（否则您无法创建内部数组）。这意味着它应该是std::semiregular。

    MyContainer(const T &defaultValue)
    {
        m_values.fill({0, defaultValue});
        m_lookUpTable.fill(nullptr);
    }

好吧，这里确实有很多错误。

首先，。因为你还没有这样做，所以你的容器现在可以从它所包含的任何类型构造。例如：

auto func(MyContainer<std::string, 10> const&);

func("whut?");

接下来，const T &defaultValue不是我们如何编写 C++。在 C++ 中，。换句话说：

• const T &defaultValue：这是 C 风格
• const T& defaultValue：这是 C++ 风格
• T const& defaultValue：也是 C++ 风格

现在，让我们来谈谈问题的核心。你主要关心的是效率（以至于它似乎胜过了功能）。然而，这种类型在很多地方效率极低，其中大部分是由于使用了std::array。

std::array不是一种高效的类型。一旦考虑到动态分配，几乎在所有实际用例中它都比它好。但这与此无关，因为您事先（显然在编译时）就知道最大大小std::vector是多少。因此，您只需预先保留内存，无需再次分配。由于没有分配成本，通常会比它好很多。std::vectorstd::array

使用std::array，复制或移动的成本是线性的。使用std::vector，复制成本仍然是线性的，但实际上你可以避免大多数复制，只需一直移动……而且vector移动速度非常快。

如果同时 std::array使用和std::vector，你的构造成本将非常高，因为两者都需要初始化整个数组。std::vector 还必须进行分配，因此它似乎std::array是赢家。只不过……你只构造一次对象……但你可以多次移动它。 这里根本没有竞争；vector移动比“移动”快得多。array

因此，底线是：您关心性能吗？std::array糟透了。std::vector在现实世界的实际使用中，几乎总是会击败它很多倍。是的，std::vector必须分配而不std::array需要，但即使如此，从整体上看，在实际用例中，std::vector它仍然表现优异std::array。

    T &operator[](const K key)
    {
        auto &ptr = m_lookUpTable[key];
        if (ptr == nullptr)
        {
            ptr = &m_values[m_size++];
            ptr->first = key;
        }
        return ptr->second;
    }

好的，这是整个代码库的核心，也是大多数问题出现的地方。

这种类型的主要问题是它使用指向自身的指针来跟踪内容。这是一个糟糕的想法。

考虑一下这里发生的事情：

auto a = new MyContainer<std::string, 4>{"foo"};

// So:
//  a->m_values      = {{0, "foo"}, {0, "foo"}, {0, "foo"}, {0, "foo"}}
//  a->m_lookUpTable = {nullptr, nullptr, nullptr, nullptr}

(*a)[2] = "bar";    // This line sets a->m_values[0] to {2, "bar"},
                    // and a->m_lookUpTable[2] to &(a->m_values[0])

// So now:
//  a.m_values      = {{3, "bar"}, {0, "foo"}, {0, "foo"}, {0, "foo"}}
//  a.m_lookUpTable = {nullptr, nullptr, &(a->m_values[0]), nullptr}

auto b = a; // Copy construction.

// So now:
//  a->m_values      = {{3, "bar"}, {0, "foo"}, {0, "foo"}, {0, "foo"}}
//  a->m_lookUpTable = {nullptr, nullptr, &(a->m_values[0]), nullptr}
//
//  b.m_values      = {{3, "bar"}, {0, "foo"}, {0, "foo"}, {0, "foo"}}
//  b.m_lookUpTable = {nullptr, nullptr, &(a->m_values[0]), nullptr}
//                                       ^^^^^^^^^^^^^^^^^

// !!!!!!!! DO YOU SEE THE PROBLEM? !!!!!!!!

delete a;

// So now:
//  *a no longer exists
//
//  b.m_values      = {{3, "bar"}, {0, "foo"}, {0, "foo"}, {0, "foo"}}
//  b.m_lookUpTable = {nullptr, nullptr, &(a->m_values[0]), nullptr}
//                                       ^^^^^^^^^^^^^^^^^

是的。

基本上，如果你要保留指向对象各个部分的指针：

• 您永远不能移动或复制该对象；或者
• 当对象移动/复制时，你必须非常小心地改变指针，以便它们保持同步。

一般来说，你永远不应该保留指向内部数据的指针。这太容易被破坏了。一个很好的替代方法是使用索引。让我们想象一下，不是指针数组，而是m_lookUpTable索引数组，然后重新运行相同的代码：

auto a = new MyContainer<std::string, 4>{"foo"};

// So:
//  a->m_values      = {{0, "foo"}, {0, "foo"}, {0, "foo"}, {0, "foo"}}
//  a->m_lookUpTable = {-1, -1, -1, -1}

(*a)[2] = "bar";    // This line sets a->m_values[0] to {2, "bar"},
                    // and a->m_lookUpTable[2] to 0

// So now:
//  a.m_values      = {{3, "bar"}, {0, "foo"}, {0, "foo"}, {0, "foo"}}
//  a.m_lookUpTable = {-1, -1, 0, -1}

auto b = a; // Copy construction.

// So now:
//  a->m_values      = {{3, "bar"}, {0, "foo"}, {0, "foo"}, {0, "foo"}}
//  a->m_lookUpTable = {-1, -1, 0, -1}
//
//  b.m_values      = {{3, "bar"}, {0, "foo"}, {0, "foo"}, {0, "foo"}}
//  b.m_lookUpTable = {-1, -1, 0, -1}

delete a;

// So now:
//  *a no longer exists
//
//  b.m_values      = {{3, "bar"}, {0, "foo"}, {0, "foo"}, {0, "foo"}}
//  b.m_lookUpTable = {-1, -1, 0, -1}

// b is still okay!

由于时间不够，我不得不在这里停止评论，但我会给你留下一个可供思考的替代设计：

替代设计

// Just bashing this code out quickly, probably won’t compile...

template <std::semiregular T, std::size_t N>
class MyContainer
{
public:
    using key_type    = std::size_t;
    using mapped_type = T;

    using key_compare = std::less<key_type>;

    using value_type = std::pair<key_type const, mapped_type>;

    using pointer       = value_type*;
    using const_pointer = value_type const*;

    using reference       = value_type&;
    using const_reference = value_type const&;

    using iterator       = value_type*;
    using const_iterator = value_type const*;

    using reverse_iterator       = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

    using difference_type = std::ptrdiff_t;
    using size_type       = std::size_t;

    constexpr explicit MyContainer(T const& defaultValue)
        : MyContainer{defaultValue, std::make_index_sequence<N>{}}
    {}

    constexpr auto operator[](key_type i) -> mapped_type&
    {
        _active.set(i);
        return _data[i].second;
    }

    constexpr auto size()  const noexcept { return _active.count(); }
    constexpr auto empty() const noexcept { return _active.none(); }

    constexpr auto begin() const& noexcept { return _data.begin(); }
    constexpr auto begin()      & noexcept { return _data.begin(); }
    constexpr auto end()   const& noexcept { return _data.end(); }
    constexpr auto end()        & noexcept { return _data.end(); }

    constexpr auto cbegin() const& noexcept { return _data.cbegin(); }
    constexpr auto cend()   const& noexcept { return _data.cend(); }

    constexpr auto clear() { _active.reset(); }

    constexpr auto count(key_type i) const noexcept { return _active[i] ? 1uz : 0uz; }

    constexpr auto find(key_type i) const& noexcept { return _active[i] ? (begin() + i) : end(); }
    constexpr auto find(key_type i)      & noexcept { return _active[i] ? (begin() + i) : end(); }

    constexpr auto contains(key_type i) const noexcept { return _active[i]; }

    // ... and so on ...

private:
    template <std::size_t... Is>
    constexpr MyContainer(T const& defaultValue, std::index_sequence<Is...>)
        : _data{{Is, defaultValue}...}
    {}

    std::array<value_type, N> _data;
    std::bitset<N>            _active;
};

我在那里实现了几个成员函数，希望其余的函数从那里就显而易见了。还有很多额外的复杂性我没有费心去说明。

但关键思想应该很清楚。您的数据存储在数组中pair<size_t const, T>，并且您有一个bitset<N>用于跟踪哪些项目处于“活动”状态。每当您将带有键的项目添加i到地图时，您都会设置_active.set(i)。每当您删除一个项目时，您都会执行_active.reset(i)。其他一切都是小菜一碟。

请注意，这只是一种选择。另一种选择是使用vector，而不是array，并且bitset在该向量中使用索引数组。这将允许您避免构造任何元素，直到它们实际添加到映射中。当元素被添加和移除时，需要一些额外的工作来确保索引数组保持有效……但应该不会太难。而且对于大多数用途来说，vector它可能效率更高。

祝你好运！