David Abrahams wrote:
on Sat Nov 01 2008, Ion Gaztañaga <igaztanaga-AT-gmail.com> wrote:
and that you avoid copies (what happens if the key is already in the map in your example?):
C'mon, it was just an untested sketch. Obviously I can handle that case.
I know ;-), it was just to show if you could benefit from insert_check/insert_commit trick and avoid building a full value in that case.
// push a value for the given key onto the FIFO void push(Key const& k, Value const& v) { typename map_type::insert_commit_data data; //Test if the key is there without constructing //the value if(!map.insert_check(key, key_hasher() , key_mapped_compare(), data).second){ //Already present, return return; } //Success guaranteed, now commit mapped_type *m= new mapped_type(k, v); //Nothrow map.insert_commit(*m, data); //If slist is implemented with cachelast<true> option //you have O(1) push_back() fifo->push_back(*m); }
Is that Boost.Intrusive code or...?
I'm on a trip, so I won't be able to follow the thread in the Newsgroup. Please write me directly if you want more explanations. Here is a full example compiled with Visual 7.1: #include <boost/intrusive/set.hpp> #include <boost/intrusive/slist.hpp> #include <string> using namespace boost::intrusive; template <class Value> struct fifo_value : public slist_base_hook<> { fifo_value() : next(0) {} fifo_value(Value v) : value(v) {} Value value; }; template <class Key, class Value> struct fifo_mapped_value : public set_base_hook<> { typedef fifo_value<Value> value_type; Key key_; value_type fifo_value_; fifo_mapped_value(const Key &k, const Value &v) : key_(k), fifo_value_(v) {} template<class ConvertibleKey, class ConvertibleValue> fifo_mapped_value( const ConvertibleKey &k , const ConvertibleValue &v) : key_(k), fifo_value_(v) {} friend bool operator<( const fifo_mapped_value &l , const fifo_mapped_value &r) { return l.key_ < r.key_; } }; template <class Key, class Value> class fifo_map { typedef fifo_mapped_value<Key, Value> mapped_type; typedef multiset<mapped_type > map_type; typedef fifo_value<Value> value_type; typedef slist< value_type , cache_last<true> > fifo_type; fifo_map(const fifo_map &); fifo_map & operator=(const fifo_map &); public: fifo_map() {} struct deleter { void operator()(mapped_type *m) const { delete m; } }; struct key_mapped_compare { bool operator()(const Key &k, const mapped_type &v) const { return k < v.key_; } bool operator()(const mapped_type &v, const Key &k) const { return v.key_ < k; } }; ~fifo_map() { //Unlink all elements fifo.clear(); //Unlink and destroy map.clear_and_dispose(deleter()); } // Has the value been pushed onto the FIFO? bool has_value(const Key &k) const { typename map_type::const_iterator pos = map.find(k, key_mapped_compare()); return pos != map.cend(); } // 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 template<class ConvertibleKey, class ConvertibleValue> void push(ConvertibleKey const& k, ConvertibleValue const& v) { mapped_type *m= new mapped_type(k, v); map.insert(*m); fifo.push_back(m->fifo_value_); } // Pop the first value off of the FIFO void pop() { value_type &v = fifo.front(); value_type mapped_type::*ptr_to_mem = &mapped_type::fifo_value_; //Yes, this in detail namespace, but I plan to make it public //and I don't have time to think something to avoid this ;-) mapped_type &m = *detail::parent_from_member <mapped_type, value_type>(&v, ptr_to_mem); fifo.pop_front(); map.erase(map.iterator_to(m)); delete &m; } private: map_type map; fifo_type fifo; }; int main() { fifo_map<int, std::string> f_map; f_map.push(0, "asdf"); if(!f_map.has_value(0)) return 1; f_map.pop(); if(f_map.has_value(0)) return 1; return 0; }
Wow, that's a cool library! I didn't know it had avl trees, splay trees, scapegoat trees, ... etc.
Planning treaps for Boost 1.38 ;-)
Cheers,
Regards, Ion