[Boost-users] boost::multi_index_container vector-like O(1) time indexing question

Subject: [Boost-users] boost::multi_index_container vector-like O(1) time indexing question
From: zap.foster (zap.foster_at_[hidden])
Date: 2009-08-29 23:15:05

I originally posted this to the wrong group, but I intended it for this 
group.

I have a boost::multi_index question.

My current container has looked like the following for a very long time:

   typedef
       std::map<double,int>
   mtype_t;

What I am looking for is a way to index the mtype_t::value_type.first 
value so that, syntactically,
it appears like a vector.  For example, the container I need would let 
me do something like:

     {
       container_t  c;

       c.insert( container_t::value_type( keycount_t(  1.414,88) ));
       c.insert( container_t::value_type( keycount_t(  3.141,77) ));
       c.insert( container_t::value_type( keycount_t( 23.000,99) ));

       for(int index=0; index<c.size(); ++index)
         printf("%d\n",c[index].second);
     }

You can see that I want to be able to index into the container much like 
one would do with a vector.
But I want my indexing to be O(1) and not O(n).  Now I still need to be 
able to iterate the container,
and I need to be able to do efficient insertions, and yes, the contents 
of the container will get
bigger and smaller and the values vary quite a lot.

A basic sketch of the multi_index container (but without the vector-like 
index) would be:

   typedef struct
   {
     double  key;
     int     count;
   } keycount_t;

   struct by_key{};

   typedef
     boost::multi_index_container<
       keycount_t,
       boost::multi_index::indexed_by <
         boost::multi_index::ordered_unique <
           boost::multi_index::tag<by_key>, 

           boost::multi_index::member<
             keycount_t,double,&keycount_t::key
           >
         >
       >
   > container_t;

This gives me the basics.  But I cannot think of a way to add a 
secondary index that would give me the O(1) vector-like indexing.  A 
use-case of the grammar I am after would be something like the following:

   void useless_function(container_t& c)
   {
     for(container_t::iterator i = c.begin(); i!=c.end(); ++i)
       print("key=%f\tval=%d\n",i->first,i->second);

     for(index=0; index<c.size(); ++index)
       print("key=%f\tval=%d\n",c[index].first,c[index].>second);
   }

Here's WHY I need this:  I have a stream of floating point values coming 
in (fixed to 5 significant digits).  I need to keep count of how often
any one of the floating point values is repeated.  Very often I need to
respond to requests as to the contents of the container at the Nth
position.  The slow O(n) method would be:

   const keycount_t& get_nth_record(int index,const container_t& c)
   {
     container_t::const_iterator i;
     for(i=c.begin(); i!=c.end(); ++i)
       if(--index==0 )
         break;
     return( *i );
   }

But again, I need O(1) time, so I need some sort of index added to my 
container_t.

Has anyone done this sort of thing before, and met the O(1) positional 
index requirement?

Many thanks!

-zap