c++ - 数据结构设计模式

Question

这个问题已经回答了，所以下面是对我想要实现的目标的解释。

我想创建一个表格数据结构，旨在允许通过可能被散列的主列高效访问任何行条目。我认为解决这个问题的最佳方法是维护一个双向链表的 vector ，每个链表代表一列，以及一个包含主列条目哈希到节点的映射的映射。现在，我犯的第一个错误是认为我需要创建自己的双向链表实现以便能够存储指向节点的指针，而实际上标准规定迭代器到 std::list 做不会因插入或拼接而失效(请参阅 larsmans 的回答)。这里有一些伪代码来说明我之前想做的事情。假设存在表示条目类型的类型名 T，并且存在 dlist 和节点类，如前所述。

typedef dlist<T> column_type;
typedef vector<T> row_type;
typedef ptr_unordered_map<int32_t, row_type> hash_type;

shared_ptr<ptr_vector<column_type> > columns;
shared_ptr<hash_type> hashes;

现在，在阅读了 larsmans 的回答后，我了解到我不需要任何这些，因为 Boost.MultiIndex 可以满足我的所有需求。即使我这样做了，Boost.Intrusive 也提供了更高效的数据结构来完成我所描述的。

感谢所有对这个问题感兴趣或提供帮助的人!如果您还有其他问题，请添加另一条评论，我会尽力进一步澄清问题。

Answer 1

front() should return a reference to a node containing the value_type

在 STL/Boost 术语中，听起来您认为 begin 而不是 front，除了 begin 方法通常返回迭代器而不是引用.

How would I be able to use a map of key hashes to std::list::iterator types and allow for addition of rows without having the entries in the map get outdated

随便做； “list 具有重要的属性，即插入和拼接不会使列表元素的迭代器失效，即使删除也只会使指向被移除元素的迭代器失效”(STL docs)。

如果需要，您可以为整个表维护一个 std::list，并在其中维护一个迭代器的 vector 以表示行的起点。

此外，你看过Boost.Intrusive了吗？和 Boost.MultiIndex ？ 您是否知道哈希的 std::map(红黑树)是表示哈希表的一种非常次优的方式？