Re: [boost] [Intrusive] [MultiIndex] Random Access mental model?

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