Re: [Boost-users] Multi Index: Nested std::pair

Subject: Re: [Boost-users] Multi Index: Nested std::pair
From: joaquin_at_[hidden]
Date: 2009-04-27 05:42:35

Etienne Philip Pretorius escribió:
>> Hi Etienne,
>>
>> Could you please elaborate on what is meant by "unique values"? This is 
>> not clear to
>> me from the explanations on your previous posts. It might help to state 
>> your requirements
>> in the reverse way: what kind of duplications involving value should be 
>> banned from the
>> container? For instance, the ordered_unique index you show us above bans 
>> duplicate
>> elements having the same form (x,*,value), where * indicates that the y 
>> member is
>> immaterial here.
>>
>>     
> Hello Joaquín,
>
> I am doing a matrix operation where I need to know the number of unique 
> values per x co-ordinate and number of unique values per y co-ordinate.
>
> N-th row, x=N, but how many unique "values" are there in this row?
> N-th column, y=N, but how many unique "values" are there in the column?
>   

Hi Etienne,

I'm not compleetely sure I'm getting you, but let me try. If by unique 
values you simply mean
all the elements with given x coordinate, you can write:

  std::size_t values_with_x(const matrix_t& m,unsigned char x)
  {
    return m.get<1>().count(x);
  }

However, if you're after elements with a given x coordinate having 
*distinct* values,
you can define your container as

  typedef boost::multi_index_container<
      element_t,
      boost::multi_index::indexed_by<
          /*value*/
          boost::multi_index::ordered_non_unique<
              boost::multi_index::member<
                  element_t,
                  unsigned char,
                  &element_t::value
              >
          >,
          /*x co-ordinate*/
          boost::multi_index::ordered_non_unique<
              boost::multi_index::composite_key<
                  element_t,
                  boost::multi_index::member<
                      element_t,
                      unsigned char,
                      &element_t::x
                  >,
                  boost::multi_index::member<
                      element_t,
                      unsigned char,
                      &element_t::value
                  >
              >
          >,
          /*y co-ordinate*/
          boost::multi_index::ordered_non_unique<
              boost::multi_index::composite_key<
                  element_t,
                  boost::multi_index::member<
                      element_t,
                      unsigned char,
                      &element_t::y
                  >,
                  boost::multi_index::member<
                      element_t,
                      unsigned char,
                      &element_t::value
                  >
              >
          >
      >
  > matrix_t;

and write the following:

  std::size_t distinct_values_with_x(const matrix_t& m,unsigned char x)
  {
    typedef matrix_t::nth_index<1>::type index_t;
    typedef index_t::iterator            iterator;

    std::pair<iterator,iterator> p=m.get<1>().equal_range(x);
    std::size_t res=0;
    while(p.first!=p.second){
      ++res;
      p.first=m.get<1>().
        upper_bound(boost::make_tuple(p.first->x,p.first->value));
    }
    return res;
  }

Does this approach your goal? Please find attached a complete test
program.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo


#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/composite_key.hpp>
#include <iostream>

struct element_t {
    element_t(
        unsigned char value,
        unsigned char x,
        unsigned char y
    ):value(value),x(x),y(y){}
    unsigned char value;
    unsigned char x;
    unsigned char y;
};

typedef boost::multi_index_container<
    element_t,
    boost::multi_index::indexed_by<
        /*value*/
        boost::multi_index::ordered_non_unique<
            boost::multi_index::member<
                element_t,
                unsigned char,
                &element_t::value
            >
        >,
        /*x co-ordinate*/
        boost::multi_index::ordered_non_unique<
            boost::multi_index::composite_key<
                element_t,
                boost::multi_index::member<
                    element_t,
                    unsigned char,
                    &element_t::x
                >,
                boost::multi_index::member<
                    element_t,
                    unsigned char,
                    &element_t::value
                >
            >
        >,
        /*y co-ordinate*/
        boost::multi_index::ordered_non_unique<
            boost::multi_index::composite_key<
                element_t,
                boost::multi_index::member<
                    element_t,
                    unsigned char,
                    &element_t::y
                >,
                boost::multi_index::member<
                    element_t,
                    unsigned char,
                    &element_t::value
                >
            >
        >
    >
> matrix_t;

std::size_t values_with_x(const matrix_t& m,unsigned char x)
{
  return m.get<1>().count(x);
}

std::size_t distinct_values_with_x(const matrix_t& m,unsigned char x)
{
  typedef matrix_t::nth_index<1>::type index_t;
  typedef index_t::iterator            iterator;

  std::pair<iterator,iterator> p=m.get<1>().equal_range(x);
  std::size_t res=0;
  while(p.first!=p.second){
    ++res;
    p.first=m.get<1>().
      upper_bound(boost::make_tuple(p.first->x,p.first->value));
  }
  return res;
}

int main()
{
  matrix_t m;
  m.insert(element_t(0,0,0));
  m.insert(element_t(0,0,0));
  m.insert(element_t(1,0,0));
  m.insert(element_t(1,0,0));
  m.insert(element_t(2,0,0));
  m.insert(element_t(4,0,0));

  std::cout<<values_with_x(m,0)<<std::endl;
  std::cout<<distinct_values_with_x(m,0)<<std::endl;
}