Boost logo

Boost :

Subject: Re: [boost] [Intrusive] [MultiIndex] Random Access mental model?
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2008-11-02 08:56:43

David Abrahams wrote:
> on Sat Nov 01 2008, Ion Gaztañaga <> 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

>> // 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 &);



    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; }

       //Unlink all elements
       //Unlink and destroy

    // 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);

    // 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);
       delete &m;

    map_type map;
    fifo_type fifo;

int main()
    fifo_map<int, std::string> f_map;
    f_map.push(0, "asdf");
       return 1;
       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,



Boost list run by bdawes at, gregod at, cpdaniel at, john at