Design Pattern for Data Structure

This question has been answered, so what follows below is an explanation of what I wanted to achieve.

I wanted to create a tablular data structure designed to allow efficient access to any row entry through a primary column that could possibly be hashed. I thought that the best way to go about this would be to maintain a vector of doubly-linked lists, each of which would represent one column, and a map that would contain mappings of primary column entry hashes to nodes. Now, the first mistake I made is in thinking that I would need to create my own implementation of a doubly-linked list in order to be able to store pointers to nodes, when in fact the standard states that iterators to std::list do not get invalidated as a result of insertion or splicing (see larsmans's answer). Here's some pseudocode to illustrate what I wanted to do previously. Assume the existence of a typename T representing the entry type and the existence of a dlist and node class, as described previously.

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;

Now, after reading larsmans's answer, I learned that I wouldn't need any of this since Boost.MultiIndex fulfills all of my needs as it is. Even if I did, Boost.Intrusive offers more efficient data structures to accomplish what I describe.

Thanks to all who took interest in the question or offered help! If you have any more questions, add another comment and I'll do my best to clarify the question fur开发者_运维百科ther.

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

Sounds like your thinking of begin instead of front, in STL/Boost terms, except that begin methods usually return iterators instead of references.

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

Just do; "lists have the important property that insertion and splicing do not invalidate iterators to list elements, and that even removal invalidates only the iterators that point to the elements that are removed" (STL docs).

If you wanted, you could maintain a single std::list for the entire table and a vector of iterators into it to represent the starting points of rows.

Besides, have you looked at Boost.Intrusive and Boost.MultiIndex? And did you know that an std::map (red-black tree) of hashes is a very suboptimal way of representing a hash table?