[multi_index] modify_range?

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

[multi_index] modify_range?

Jeff Flinn
It would be nice to have a modify_range/modify_key_range that would apply a
function object to each deref'd iterator in the range. Since the multi_index
iterator derefences to a const value_type&, one can not use std::for_each in
particular to apply modifications. Or am I missing something.

Thanks, Jeff



_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: [multi_index] modify_range?

Joaquin M LópezMuñoz
Jeff Flinn wrote:
> It would be nice to have a modify_range/modify_key_range that would
apply a
> function object to each deref'd iterator in the range. Since the
multi_index
> iterator derefences to a const value_type&, one can not use
std::for_each in
> particular to apply modifications. Or am I missing something.

Hello Jeff,

I think it is possible to have what you want
without requiring that a new facility be provided
by Boost.MultiIndex itself. For you can write:

  template<typename Index,typename Modifier>
  void modify_range(
    Index& i,typename Index::iterator first,typename Index::iterator
last,
    Modifier mod)
  {
    while(first!=last)i.modify(first++,mod);
  }

and use it as in the following example:

  struct adder
  {
    adder(int n):n(n){}
    void operator()(int& x)const{x+=n;}
   
  private:
    int n;
  };

  typedef multi_index_container<
    int,
    indexed_by<
      ordered_non_unique<boost::multi_index::identity<int> >
    >
  > multi_index_type;
   
  multi_index_type m;
  for(int i=0;i<10;++i)m.insert(i);
 
  modify_range(m,m.begin(),m.end(),adder(-2));

or with Boost.Lambda if you prefer:

  modify_range(m,m.begin(),m.end(),_1-=2);

There is a problem, though: consider the following:

// buggy call ro modify_range
modify_range(m,m.begin(),m.end(),adder(2));

What's the problem with this? Well, after *increasing*
the value of an element, this is repositioned
further to the end of the container, and consequentely
modify_range will visit it again and engage in a
neverending loop (modulo overflows.) For this situations
you can use a special (albeit slower) variation that
records the range before starting modifying the
elements:

  template<typename Index,typename Modifier>
  void modify_unstable_range(
    Index& i,typename Index::iterator first,typename Index::iterator
last,
    Modifier mod)
  {
    typedef std::vector<typename Index::iterator> buffer_type;
    buffer_type v;
    while(first!=last)v.push_back(first++);
 
    for(typename buffer_type::iterator it=v.begin(),it_end=v.end();
        it!=it_end;i.modify(*it++,mod));
  }

  // calling modify_unstable_range is now OK
  modify_unstable_range(m,m.begin(),m.end(),adder(2));

I hope my explanations are clear enough. Does this satisfy
your needs? You can find attached a complete example
exercising these little utilities. modify_key_range would
be a simple variation on this stuff.

HTH,

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

_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users

jeff.cpp (2K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [multi_index] modify_range?

Jeff Flinn
JOAQUIN LOPEZ MU?Z wrote:

> Jeff Flinn wrote:
>> It would be nice to have a modify_range/modify_key_range that would
>> apply a function object to each deref'd iterator in the range. Since
>> the multi_index iterator derefences to a const value_type&, one can
>> not use std::for_each in particular to apply modifications. Or am I
>> missing something.
>
> Hello Jeff,
>
> I think it is possible to have what you want
> without requiring that a new facility be provided
> by Boost.MultiIndex itself. For you can write:

[snipped code]

> There is a problem, though: consider the following:
>
> // buggy call ro modify_range
> modify_range(m,m.begin(),m.end(),adder(2));
>
> What's the problem with this? Well, after *increasing*
> the value of an element, this is repositioned
> further to the end of the container, and consequentely
> modify_range will visit it again and engage in a
> neverending loop (modulo overflows.)

Would modifying a non_key(or non_derived_key dependency) ever cause
repositioning?

> For this situations
> you can use a special (albeit slower) variation that
> records the range before starting modifying the
> elements:
>
>   template<typename Index,typename Modifier>
>   void modify_unstable_range(
>     Index& i,typename Index::iterator first,typename Index::iterator
> last,
>     Modifier mod)
>   {
>     typedef std::vector<typename Index::iterator> buffer_type;
>     buffer_type v;
>     while(first!=last)v.push_back(first++);
>
>     for(typename buffer_type::iterator it=v.begin(),it_end=v.end();
>         it!=it_end;i.modify(*it++,mod));
>   }
>
>   // calling modify_unstable_range is now OK
>   modify_unstable_range(m,m.begin(),m.end(),adder(2));

Doesn't this actually provide modify_key_range functionality?

> I hope my explanations are clear enough. Does this satisfy
> your needs? You can find attached a complete example
> exercising these little utilities. modify_key_range would
> be a simple variation on this stuff.

Yes this clearly explains the issues. From this it becomes clear that the
best choice is to only insert objects with fully defined keys into
multi_index containers. I was trying to avoid copies where possible.

In my case, I'm creating a container of objects, from a(n idiotic) stream
format that spreads object members across disparate tables. So I've first
created a vector of objects, modify all of their members as the data comes
in. Then copy these to a multi_index container, and clear the vector. From
that point, I only need access to the const interface of the objects,
accessible by the various indices.

Thanks for the help,

Jeff




_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: [multi_index] modify_range?

Joaquin M LópezMuñoz
Jeff Flinn ha escrito:

> JOAQUIN LOPEZ MU?Z wrote:
>
> > There is a problem, though: consider the following:
> >
> > // buggy call ro modify_range
> > modify_range(m,m.begin(),m.end(),adder(2));
> >
> > What's the problem with this? Well, after *increasing*
> > the value of an element, this is repositioned
> > further to the end of the container, and consequentely
> > modify_range will visit it again and engage in a
> > neverending loop (modulo overflows.)
>
> Would modifying a non_key(or non_derived_key dependency) ever cause
> repositioning?

I'm not sure if you mean this, but modifying a part of an object from which no

key extractor depends results in no repositioning. For instance

struct element{
 int x,y,z
};

typedef multi_index_container<
  element,
  indexed_by<
    ordered_unique<member<element,int,&element::x>,
    ordered_non_unique<member<element,int,&element::y>,
  >
> multi_index_t;

modifying element::z in the example above does not cause repositioning
ever. Is this what you were referring to?

> >   // calling modify_unstable_range is now OK
> >   modify_unstable_range(m,m.begin(),m.end(),adder(2));
>
> Doesn't this actually provide modify_key_range functionality?

No, to provide such functionality just replace the occurences
of .modify(...) with .modify_key(...);


> > I hope my explanations are clear enough. Does this satisfy
> > your needs? You can find attached a complete example
> > exercising these little utilities. modify_key_range would
> > be a simple variation on this stuff.
>
> Yes this clearly explains the issues. From this it becomes clear that the
> best choice is to only insert objects with fully defined keys into
> multi_index containers. I was trying to avoid copies where possible.
>
> In my case, I'm creating a container of objects, from a(n idiotic) stream
> format that spreads object members across disparate tables. So I've first
> created a vector of objects, modify all of their members as the data comes
> in. Then copy these to a multi_index container, and clear the vector. From
> that point, I only need access to the const interface of the objects,
> accessible by the various indices.

I agree with you it's probably simpler to have an intermediate vector and
dump to the multi-index container after full loading --working directly
with the multi-index container is probably slower and can pose very
difficult problems: for instance, if you have a unique index it might not
be possible to insert several elements for which their unique key have
not yet arrived from the data stream.

Good luck with your project,

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

_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: [multi_index] modify_range?

Jeff Flinn
Joaquín Mª López Muñoz wrote:

> Jeff Flinn ha escrito:
>
>> JOAQUIN LOPEZ MU?Z wrote:
>>
>>> There is a problem, though: consider the following:
>>>
>>> // buggy call ro modify_range
>>> modify_range(m,m.begin(),m.end(),adder(2));
>>>
>>> What's the problem with this? Well, after *increasing*
>>> the value of an element, this is repositioned
>>> further to the end of the container, and consequentely
>>> modify_range will visit it again and engage in a
>>> neverending loop (modulo overflows.)
>>
>> Would modifying a non_key(or non_derived_key dependency) ever cause
>> repositioning?
>
> I'm not sure if you mean this, but modifying a part of an object from
> which no
>
> key extractor depends results in no repositioning. For instance
>
> struct element{
>  int x,y,z
> };
>
> typedef multi_index_container<
>   element,
>   indexed_by<
>     ordered_unique<member<element,int,&element::x>,
>     ordered_non_unique<member<element,int,&element::y>,
>   >
>> multi_index_t;
>
> modifying element::z in the example above does not cause repositioning
> ever. Is this what you were referring to?
Yes, that's what I was referring to. So in the above case, there's no need
for the 'stable' version.

>>>   // calling modify_unstable_range is now OK
>>>   modify_unstable_range(m,m.begin(),m.end(),adder(2));
>>
>> Doesn't this actually provide modify_key_range functionality?
>
> No, to provide such functionality just replace the occurences
> of .modify(...) with .modify_key(...);

So wouldn't the only use of modify_unstable_range be for modifying keys and
indirect members? So only a single modify_unstable_range calling .modify_key
would suffice? Just thinking out loud here, until I have access to the docs.

Thanks for your library and your help. :)

Jeff




_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: [multi_index] modify_range?

Joaquin M LópezMuñoz
In reply to this post by Jeff Flinn
----- Mensaje original -----
De: Jeff Flinn <[hidden email]>
Fecha: Jueves, Marzo 16, 2006 11:09 pm
Asunto: Re: [Boost-users] [multi_index] modify_range?

> Joaquín Mª López Muñoz wrote:
>
> So wouldn't the only use of modify_unstable_range be for modifying
> keys and
> indirect members? So only a single modify_unstable_range calling
> .modify_key
> would suffice? Just thinking out loud here, until I have access to
> the docs.

I'm not sure I'm making my point. There are two orthogonal
issues to consider here:

1 Whether you are modyfing whole elements (A) or keys (B).
2 Whether the modification is "stable" (1) or not (2).

The four combinations are actual possibilities:

A1: modify_range
A2: modify_unstable_range
B1: modify_key_range
B2: modify_key_unstable_range

where B1 and B2 (which are not given in my previous
snippet) are written exactly as A1 and A2, respectively,
except that where it read .modify(...) you've got to
write .modify_key(...).

"Stability" is not dependant on whether you're modifying
elements or keys: you can get stable and unstable
range modifications both ways. What defines a stable
range modification of the form
modify[_key]_range(i,first,last,mod) is that,
after modifying an element pointed to by iterator it,
the resulting repositioning does not lie inside [++it,last),
i.e. we're sure we won't visit the element again.
You can see in my previous snippets examples
of stable and unstable range modifications.

>
> Thanks for your library and your help. :)
>
> Jeff

You're welcome, thank you for using the Boost.MultiIndex.

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

_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users

_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users