互相引用的 STL 容器 typedef

Question

我有一个 std::map 和一个 std::list。我想让容器中的元素具有相反容器迭代器的类型。

我该如何对它们进行typedef？

Example:

 typedef std::map<MyKeyClass, typename MyList::iterator> MyMap;
 //                                    ^ MyList not defined.
 typedef std::list<typename MyMap::iterator> MyList;

当然，交换这两行代码不能解决问题。

我还尝试过：

 typedef std::map<MyKeyClass,
                  typename std::list<typename MyMap::iterator>::iterator> MyMap;
 typedef std::list<typename MyMap::iterator> MyList;

但那也不起作用。

更新： 我需要这个是为了通过订单的两个方面来跟踪键/值对。假设我有一个map<KEY,VALUE>，它按键排序，通过键查找值很快。但我还想通过添加值的时间来跟踪值。我想知道哪个值是最近添加的。为此，我使用列表。我需要从地图中返回迭代器，以便从容器中删除元素。当我通过键删除地图中的元素时，我还需要删除列表中的元素。我还需要相反的操作（删除最近添加的值）。 我发现我的想法是显式使用指针（如注释中所示）不起作用，因为我实际上需要一个迭代器来从容器中删除元素。

更新2： 我之所以问这个问题，是因为我觉得有点奇怪我不能做到这一点。我经常将STL容器用作基本数据结构（像每个人一样）。例如，std::map可以用作具有显式结构和指针的二叉树的实现替代品。STL容器设计得很好，我没有经历过无法使用STL容器来表达可以通过结构和指针完成的某些结构的情况。它们可能无法保证STL容器具有与结构和指针结构相同的属性。但是，对于这样的简单结构，我感到有点奇怪，我无法使用STL容器来表达它。

- Shu Suzuki

---

这就像是 struct X { Y y; }; struct Y { X x; };，不是吗？ - Kerrek SB

是的，但在这种情况下，我们可以使用前向声明。那么我该如何在我的示例中实现它呢？ 更新：抱歉，无法通过前向声明来完成，因为它不是指针。我在这里使用迭代器作为指针的一种形式。所以我想做的是类似于迭代器的前向声明...虽然可能不可能。 - Shu Suzuki

你无法控制标准库容器的内部，因此你不能断言“它就像指针”。标准规定类型必须是完整的，没有其他选择。 - Kerrek SB

@ShuSuzuki -- 在 X { Y y; }; struct Y { X x; }; 的情况下，你不能前向声明 X 或 Y -- 因为它们需要是完整的类型。前向声明只能用于指针声明，而不是完整类型。 - Soren

@Kerrek 是的，我知道。我想知道是否有一些解决这个问题的方法。显式地使用指向容器中变量的指针可能是一个可能的解决方案。但我仍然不能确定这是我们唯一能做的事情。 - Shu Suzuki

Answer 1

你可能在寻找Boost中的多重索引容器。它使得你可以通过多个键类型来对映射/集合进行排序和访问。

Boost双向映射是一个类似的工具，只有两个键/指数，它本质上允许你通过键和值来访问映射。

- Sam

---

+1：Boost Multi-index和bimap还提供了对“时间顺序”作为索引的支持（http://www.boost.org/doc/libs/1_55_0/libs/multi_index/doc/tutorial/，请查看示例）。 - Andriy Tylychko

Answer 2

最终我编写了以下代码。它由g++编译。

struct ListEntry;
typedef std::unordered_map<MyKeyClass, typename std::list<ListEntry>::iterator> KeyMap;
struct ListEntry{
   typename KeyMap::iterator it;                                                       
};
typedef std::list<ListEntry> MyList;

- Shu Suzuki

Answer 3

你尝试做的是不可能的，因为它创建了一个无限递归定义。

考虑一下在第二个例子中发生的事情：

typedef std::map<MyKeyClass,
    typename std::list<typename MyMap::iterator>::iterator> MyMap;

MyMap内部将被扩展，您将获得

typedef std::map<MyKeyClass,
    typename std::list<typename std::map<MyKeyClass,
        typename std::list<typename MyMap::iterator>::iterator>::iterator>::iterator> MyMap;

然后会有另一个MyMap来扩展。 现在你可以看到这是怎么回事了。你应该考虑你想要做什么，并查看是否有更好的建模数据结构的方法。

- Cássio Renan

Answer 4

唯一我能想到你需要循环类型的原因是因为地图存储对列表的引用，而列表存储对地图的引用。换句话说，你想在地图和列表之间共享数据。使用std::shared_ptr的映射和std::shared_ptr的列表，这使得你可以轻松地在地图和列表之间共享元素（这些元素是真正的数据）。

- Manu343726

---

我更新了问题。是的，我想在地图和列表之间共享数据。（在我的更新问题中，VALUE被共享。）但我仍然想知道如何根据需要删除容器中的元素。 - Shu Suzuki