on Sat Nov 01 2008, Ion Gaztañaga <igaztanaga-AT-gmail.com> wrote:
David Abrahams wrote:
on Sat Nov 01 2008, JOAQUIN M. LOPEZ MUÑOZ <joaquin-AT-tid.es> wrote:
Actually, MultiIndex could give me *almost* everything I need by threading a singly-linked list through the hash nodes (instead of doubly-linked). That's enough for a FIFO queue. You can do that with Boost.Intrusive, and that will indeed save you one pointer per node as compared with the Boost.MultiIndex-based solution. If you're resorting to manually combining a hash_map and a slist<pointer> then you'd begaining nothing, as in the hash_map+ deque<pointer> case described in my previous post.
Turns out I need a little more than that; I essentially need a bool that tells me whether the node is in the FIFO queue yet. Since I can use a NULL queue pointer for that purpose, it looks like I'll be rolling my own.
I handn't looked at Boost.Intrusive before. While it looks interesting, it seems pretty complicated and I can't quite see any point in using it when I could just use Boost.Unordered with a value_type that holds an additional pointer. Maybe I'm missing something; I don't know.
The point of using Intrusive is that you only allocate once instead of one for every container.
I know. I think you must misunderstand me. When I wrote of using "a value_type that holds an additional pointer" I meant that I would build the FIFO queue using the hash nodes, roughly: // Totally untested!! // My values happen to be default constructible; if they // weren't and Boost.Intrusive could help, I might take // advantage of it. Otherwise, I know how to take care of // it myself but I am trying to keep this posting simple. template <class Key, class Value> struct fifo_value { fifo_value() : next(0) {} fifo_value(Value v, Key* next = 0) : value(v), next(next) {} Value value; Key* next; }; template <class Key, class Value> struct fifo_hashmap { fifo_hashmap() : head(&last), tail(&head) {} // Insert the key with no value void insert_key(Key k) { map[k]; } // Has the value been pushed onto the FIFO? bool has_value(Key k) const { typename map_type::iterator pos = map.find(k); return pos != map.end() && pos->second.next; } // Has the key been inserted in the map? bool mapped(Key k) const { return map.find(k) != map.end(); } // push a value for the given key onto the FIFO void push(Key const& k, Value const& v) { typename map_type::iterator pos = map.insert(k, fifo_value(v, &last)); *tail = &pos->first; tail = &pos->second.next; } // Pop the first value off of the FIFO void pop() { Key* h = head; typename map_type::iterator pos = map.find(*h); head = pos->second.next; map.erase(pos); } private: typedef unordered_map<key, fifo_value<key, value> > map_type; map_type map; Key* head; Key** tail; static Key last; }; That implements pretty much all the operations I need.
When we use two STL-like containers we are allocating dynamic memory so we have a size payload for each allocation from the memory allocator (usually 1 or 2 pointers).
I know. -- Dave Abrahams BoostPro Computing http://www.boostpro.com