C++ 映射——自引用迭代器

Question

有没有办法声明一个std::map谁的值类型是自身的迭代器？

map<string, map<string, (#)>::iterator> myMap;

上面的代码片段不会工作，因为迭代器类型需要知道第二个模板参数，标记为 (#) . (这就是它本身)。

目的是避免做不必要的事情find访问另一个元素指向的元素的操作——与使用 map<string, string> 相反.

Answer 1

这样的定义是不可能的，因为值类型和迭代器类型将相互无限递归。

可以使用一些间接的方法来解决这个问题。甚至可以避免 std::any 的动态分配。 ，以及 std::map<K,V> 的事实未定义，除非 V完成了。

但解决方案有点棘手，它依赖于一些合理的假设，但标准没有规定。请参阅实现中的评论。主要技巧是将成员变量类型的定义推迟到封装类定义之后。这是通过重用原始存储来实现的。

用法优先:

int main()
{
    Map map;
    auto [it, _] = map.emplace("first", iter_wrap{});
    map.emplace("maps to first", conv::wrap(it));
    // erase first mapping by only looking
    // up the element that maps to it
    map.erase(conv::it(map.find("maps to first")));
}

定义

struct NoInitTag {} noInitTag;

class iter_wrap
{
public:
    iter_wrap();
    ~iter_wrap();
    iter_wrap(const iter_wrap&);
    iter_wrap(iter_wrap&&);
    const iter_wrap& operator=(const iter_wrap&);
    const iter_wrap& operator=(iter_wrap&&);

private:
    // We rely on assumption that all map iterators have the same size and alignment.
    // Compiler should hopefully warn if our allocation is insufficient.
    using dummy_it = std::map<int, int>::iterator;
    static constexpr auto it_size = sizeof(dummy_it);
    static constexpr auto it_align = alignof(dummy_it);
    alignas(it_align) std::byte store[it_size];

    explicit iter_wrap(NoInitTag){}
    friend struct conv;
};

using Map = std::map<std::string, iter_wrap>;
using It = Map::iterator;

struct conv {
    static constexpr It&
    it(iter_wrap&& wrap) noexcept {
        return *std::launder(reinterpret_cast<It*>(wrap.store));
    }
    static constexpr const It&
    it(const iter_wrap& wrap) noexcept {
        return *std::launder(reinterpret_cast<const It*>(wrap.store));
    }
    template<class It>
    static const iter_wrap
    wrap(It&& it) {
        iter_wrap iw(noInitTag);
        create(iw, std::forward<It>(it));
        return iw;
    }
    template<class... Args>
    static void
    create(iter_wrap& wrap, Args&&... args) {
        new(wrap.store) It(std::forward<Args>(args)...);
    }
    static constexpr void
    destroy(iter_wrap& wrap) {
        it(wrap).~It();
    }
};

iter_wrap::iter_wrap() {
    conv::create(*this);
}
iter_wrap::iter_wrap(const iter_wrap& other) {
    conv::create(*this, conv::it(other));
}
iter_wrap::iter_wrap(iter_wrap&& other) {
    conv::create(*this, std::move(conv::it(other)));
}
const iter_wrap& iter_wrap::operator=(const iter_wrap& other) {
    conv::destroy(*this);
    conv::create(*this, conv::it(other));
    return *this;
}
const iter_wrap& iter_wrap::operator=(iter_wrap&& other) {
    conv::destroy(*this);
    conv::create(*this, std::move(conv::it(other)));
    return *this;

}
iter_wrap::~iter_wrap() {
    conv::destroy(*this);
}

---

旧答案；这假设在遍历存储的映射时避免查找不是一个重要的特征。

您尝试表示的数据结构似乎是一组键(字符串)，其中每个键都映射到该组中的另一个键。更简单的表示方法是将这两个方面分开:

using Set = std::set<std::string>;
using Map = std::map<Set::iterator, Set::iterator>;

请注意，这两个数据结构不会自动保持同步。添加到集合中的元素不会自动映射到另一个元素，从集合中删除的元素会在映射中留下悬垂的迭代器。因此，编写一个强制执行必要的不变量的自定义容器类是明智的。