 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Roshan Naik
Guest
|
 Posted: Mon Apr 25, 2005 11:08 pm Post subject: Messing with expensive objects in containers |
 |
|
Problem: You are to work with a vector<expensiveObject>. It is expensive to
make copies of the expensiveObject objects. But you want to reorder
(sort/rotate/randomize/whatever) it and print the results .So you get some
sort of reference (pointers/reference/iterators) to each of its elements and
store them in a 2nd vector and do the reordering there and then print it
from there. Lets say for simplicity you dont need to update the original
vector to reflect the reodering.
What would be a simple ( less code but readable ) and elegant (using
std::algorithms & no explicit loops ) code to go about this common pattern ?
Lets assume that
- expensiveObject supports << for printing and
- sort() followed by rotate() is the only reordering needed.
My little experiments are not very satisfactory. So i am curious to see how
others are going about this.
-Roshan
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
Uenal Mutlu
Guest
|
| Posted: Tue Apr 26, 2005 8:53 am Post subject: Re: Messing with expensive objects in containers |
|
|
"Roshan Naik" wrote
| Quote: | Problem: You are to work with a vector<expensiveObject>. It is expensive to
make copies of the expensiveObject objects. But you want to reorder
(sort/rotate/randomize/whatever) it and print the results .So you get some
sort of reference (pointers/reference/iterators) to each of its elements and
store them in a 2nd vector and do the reordering there and then print it
from there. Lets say for simplicity you dont need to update the original
vector to reflect the reodering.
What would be a simple ( less code but readable ) and elegant (using
std::algorithms & no explicit loops ) code to go about this common pattern ?
Lets assume that
- expensiveObject supports << for printing and
- sort() followed by rotate() is the only reordering needed.
My little experiments are not very satisfactory. So i am curious to see how
others are going about this.
|
I would use an index array whom elements (integer) are simply
the positions of the items in the vector. By this method the vector
does not need to be reorganised or reordered.
This method makes also sorting much faster because
the items aren't moved around; ie. the vector isn't changed at all.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Kim, Seungtai
Guest
|
| Posted: Tue Apr 26, 2005 9:01 am Post subject: Re: Messing with expensive objects in containers |
|
|
"Roshan Naik"
| Quote: | Problem: You are to work with a vector<expensiveObject>. It is expensive to
make copies of the expensiveObject objects. But you want to reorder
(sort/rotate/randomize/whatever) it and print the results .So you get some
sort of reference (pointers/reference/iterators) to each of its elements and
store them in a 2nd vector and do the reordering there and then print it
from there.
|
You cannot save the reference of somthing into the vector. Because it
cannot fullfill the some of the vector's requirements. Of course, the iterator
and the pointer can do it.
| Quote: | Lets say for simplicity you dont need to update the original
vector to reflect the reodering.
|
The vector uses the copies of the original inputs by the copy-semantics.
Since after creating instance of the vector, there can be more than
copy operations if you try to modify the vector. And I think that it might be
the point that you concerned about.
| Quote: | What would be a simple ( less code but readable ) and elegant (using
std::algorithms & no explicit loops ) code to go about this common pattern ?
Lets assume that
- expensiveObject supports << for printing and
- sort() followed by rotate() is the only reordering needed.
|
Why should do you use the second vector? I think that it's not needed and
even it is dangerous. Because the any of the invalidation can make
the second vector be invalid, easily. If you manage the whole invalidation,
it will make the code to be twisted. There is no general coding pattern.
Instead of doing, I suggest that you directly mange the copy operations
by overloading related operators for the expensiveObject, not pointer to.
If the expensiveObject's members consists of pointers, it can offer
reducing the copying area by simple ownership mangement. And it might
require the comparing operations for odering. It's more simple and safe.
Do you have any reasons you should use the second vector?
| Quote: | My little experiments are not very satisfactory. So i am curious to see how
others are going about this.
|
What sort of experiments you did?
What sort of the problems makes you unsatisfactory?
--
S Kim
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Carl Barron
Guest
|
| Posted: Tue Apr 26, 2005 4:48 pm Post subject: Re: Messing with expensive objects in containers |
|
|
In article <G73be.12857$An2.9797 (AT) newsread2 (DOT) news.pas.earthlink.net>,
Roshan Naik <someone (AT) somehwere (DOT) com> wrote:
| Quote: | Problem: You are to work with a vector<expensiveObject>. It is expensive to
make copies of the expensiveObject objects. But you want to reorder
(sort/rotate/randomize/whatever) it and print the results .So you get some
sort of reference (pointers/reference/iterators) to each of its elements and
store them in a 2nd vector and do the reordering there and then print it
from there. Lets say for simplicity you dont need to update the original
vector to reflect the reodering.
What would be a simple ( less code but readable ) and elegant (using
std::algorithms & no explicit loops ) code to go about this common pattern ?
Lets assume that
- expensiveObject supports << for printing and
- sort() followed by rotate() is the only reordering needed.
My little experiments are not very satisfactory. So i am curious to see how
others are going about this.
OOP purists dont like this: |
// work around ADL...
// short cut inheritance not an OOP hierarchy!!!
struct expensive_ptr:boost::shared_ptr
{
explicit expensive_ptr(expensiveObject *p)
:boost::shared_ptr<expensiveObject>(p){}
// other constructors are similiar if needed.
expensive_ptr(){}
};
struct expensive_less
{
bool operator () (const expensive_ptr &x,const expensive_ptr &y)
{ return *x < *y;}
};
inline
std::ostream & operator << (std::ostream &os,const expensive_ptr &x)
{
return os << *x;
};
std::vector
std::sort(data.begin(),data.end(),expensive_less()); // sort
std::rotate() is direct.
as is operator << ();
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Maciej Sobczak
Guest
|
| Posted: Tue Apr 26, 2005 4:57 pm Post subject: Re: Messing with expensive objects in containers |
|
|
Hi,
Roshan Naik wrote:
| Quote: | Problem: You are to work with a vector<expensiveObject>. It is expensive to
make copies of the expensiveObject objects. But you want to reorder
(sort/rotate/randomize/whatever) it and print the results
|
Please see the view template class which can be used to do this (see
example 4,5):
http://www.msobczak.com/prog/bin/view.zip
--
Maciej Sobczak : http://www.msobczak.com/
Programming : http://www.msobczak.com/prog/
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Alberto Barbati
Guest
|
| Posted: Tue Apr 26, 2005 5:06 pm Post subject: Re: Messing with expensive objects in containers |
|
|
Roshan Naik wrote:
| Quote: | Problem: You are to work with a vector<expensiveObject>. It is expensive to
make copies of the expensiveObject objects. But you want to reorder
(sort/rotate/randomize/whatever) it and print the results .So you get some
sort of reference (pointers/reference/iterators) to each of its elements and
store them in a 2nd vector and do the reordering there and then print it
from there. Lets say for simplicity you dont need to update the original
vector to reflect the reodering.
What would be a simple ( less code but readable ) and elegant (using
std::algorithms & no explicit loops ) code to go about this common pattern ?
Lets assume that
- expensiveObject supports << for printing and
- sort() followed by rotate() is the only reordering needed.
My little experiments are not very satisfactory. So i am curious to see how
others are going about this.
|
Of course, I assume that you have already considered (and possibly
discarded) the opportunity of using std::list instead of std::vector.
std::list provides a no-copy sort algorithm, and rotate() can easily and
very efficiently be implemented via splice().
If you use a vector of pointers to objects stored in some other
container, then you might consider using boost::indirect_iterator
([url]http://boost.org/libs/iterator/doc/indirect_iterator.html#example)[/url].
Just don't make the mistake to use a vector of custodial pointers to
new-allocated objects, because it has been discussed several times that
it's not a Good Thing(tm). In this case a possibility would be to use a
vector of boost::shared_ptr<>. Unfortunately, one of my favorite
solutions, namely boost::ptr_vector<>, is not suitable in your case.
Although boost::ptr_vector<> contains just pointers to new-allocated
objects, its peculiar iterators will make std::sort() perform copies of
the full objects.
HTH,
Alberto
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Roland Pibinger
Guest
|
| Posted: Wed Apr 27, 2005 8:22 am Post subject: Re: Messing with expensive objects in containers |
|
|
On 25 Apr 2005 19:08:54 -0400, "Roshan Naik" <someone (AT) somehwere (DOT) com>
wrote:
| Quote: | Problem: You are to work with a vector<expensiveObject>. It is expensive to
make copies of the expensiveObject objects. But you want to reorder
(sort/rotate/randomize/whatever) it and print the results .So you get some
sort of reference (pointers/reference/iterators) to each of its elements and
store them in a 2nd vector and do the reordering there and then print it
from there. Lets say for simplicity you dont need to update the original
vector to reflect the reodering.
What would be a simple ( less code but readable ) and elegant (using
std::algorithms & no explicit loops ) code to go about this common pattern ?
Lets assume that
- expensiveObject supports << for printing and
- sort() followed by rotate() is the only reordering needed.
My little experiments are not very satisfactory. So i am curious to see how
others are going about this.
|
You may use a special vector for pointers,
http://www.codeproject.com/vcpp/stl/ptr_vecto.asp , and write your
code similar to the following example:
void foo()
{
vector
// ...
ptr_vector<expensiveObject> pVec (vec.begin(), vec.end());
stdx::sort (pVec.begin(), pVec.end()); // note namespace stdx!
stdx::rotate (pVec.begin(), middle, pVec.end());
}
In the above example pointed-to objects are not copied by stdx::sort
and stdx::rotate. ptr_vector creates a 'dereference view' of the
contained pointers. It claims no ownership of the pointed-to objects
so you can create different 'dereference views' on the same underlying
data (actually that's one of the main use cases of ptr_vector).
Best wishes,
Roland Pibinger
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Allan W
Guest
|
| Posted: Wed Apr 27, 2005 8:31 am Post subject: Re: Messing with expensive objects in containers |
|
|
Roshan Naik wrote:
| Quote: | Problem: You are to work with a vector<expensiveObject>. It is
expensive to
make copies of the expensiveObject objects. But you want to reorder
(sort/rotate/randomize/whatever) it and print the results .So you get
some
sort of reference (pointers/reference/iterators) to each of its
elements and
store them in a 2nd vector and do the reordering there and then print
it
from there. Lets say for simplicity you dont need to update the
original
vector to reflect the reodering.
What would be a simple ( less code but readable ) and elegant (using
std::algorithms & no explicit loops ) code to go about this common
pattern ?
Lets assume that
- expensiveObject supports << for printing and
- sort() followed by rotate() is the only reordering needed.
|
1. Create a predicate functor:
// Predicate functor for tag sort
struct Pred {
std::vector
Pred(std::vector<ExpensiveObject>&ee) : e(ee) {}
bool operator()(int a, int b) { return e[a]<e[b]; }
};
2. Create an array of integers, and sort it using the predicate.
// Create an array with consecutive integers
std::vector
for (i=0; i<int(ExpensiveVector.size()); ++i)
intvec[i]=i;
// Now use it in a tag sort
sort(intvec.begin(), intvec.end(), Pred(ExpensiveVector));
3. Now you can access the array in sorted order by using intvec:
for (std::vector
std::cout << ExpensiveVector[*x];
This does comparisons, but no copies.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
stuart.allie@gmail.com
Guest
|
| Posted: Wed Apr 27, 2005 12:41 pm Post subject: Re: Messing with expensive objects in containers |
|
|
Alberto Barbati wrote:
| Quote: | Just don't make the mistake to use a vector of custodial pointers to
new-allocated objects, because it has been discussed several times
that
it's not a Good Thing(tm).
|
Just curious, why is this not a "Goodd Thing?"
Stuart
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Roshan Naik
Guest
|
| Posted: Thu Apr 28, 2005 1:09 am Post subject: Re: Messing with expensive objects in containers |
|
|
| Quote: | You cannot save the reference of somthing into the vector. Because it
cannot fullfill the some of the vector's requirements. Of course, the
iterator
and the pointer can do it.
|
Yup.. my mistake!
| Quote: |
Why should do you use the second vector? I think that it's not needed and
even it is dangerous. Because the any of the invalidation can make
the second vector be invalid, easily. If you manage the whole
invalidation,
it will make the code to be twisted. There is no general coding pattern.
Instead of doing, I suggest that you directly mange the copy operations
by overloading related operators for the expensiveObject, not pointer to.
If the expensiveObject's members consists of pointers, it can offer
reducing the copying area by simple ownership mangement. And it might
require the comparing operations for odering. It's more simple and safe.
Do you have any reasons you should use the second vector?
|
Cuz i dont want to mess with the original vector. It holds expensiveObjects
that are, well, expensive to copy around ...and i dont have access to modify
the internals of the class so that i rewrite its copy operations.
And most importantly, I dont want to get in the business of rewriting copy
operations for every such "expensiveObject" type that i encounter.
| Quote: |
My little experiments are not very satisfactory. So i am curious to see
how
others are going about this.
What sort of experiments you did?
|
The kind that Carl demonstates in his code.... then some custom iterators
and some other things that not worth mentioning.
| Quote: |
What sort of the problems makes you unsatisfactory?
|
Ended with too much code that was not very general purpose.
-Roshan
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Alberto Barbati
Guest
|
| Posted: Thu Apr 28, 2005 12:30 pm Post subject: Re: Messing with expensive objects in containers |
|
|
[email]stuart.allie (AT) gmail (DOT) com[/email] wrote:
| Quote: | Alberto Barbati wrote:
Just don't make the mistake to use a vector of custodial pointers to
new-allocated objects, because it has been discussed several times
that it's not a Good Thing(tm).
Just curious, why is this not a "Goodd Thing?"
|
The main reason is that as soon as you call delete on a pointer, the
pointer becomes invalid and accessing an such a pointer gives an
undefined behaviour. In particular, the pointer ceases to be
CopyConstructible and Assignable and having such stuff in a standard
container is a violation of the container requirements.
There are probably other reasons too, but I don't recall them now.
Alberto
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Carl Barron
Guest
|
| Posted: Fri Apr 29, 2005 8:40 am Post subject: Re: Messing with expensive objects in containers |
|
|
In article <9BNbe.87274$zZ1.2447044 (AT) twister1 (DOT) libero.it>, Alberto
Barbati <AlbertoBarbati (AT) libero (DOT) it> wrote:
| Quote: | stuart.allie (AT) gmail (DOT) com wrote:
Alberto Barbati wrote:
Just don't make the mistake to use a vector of custodial pointers to
new-allocated objects, because it has been discussed several times
that it's not a Good Thing(tm).
Just curious, why is this not a "Goodd Thing?"
The main reason is that as soon as you call delete on a pointer, the
pointer becomes invalid and accessing an such a pointer gives an
undefined behaviour. In particular, the pointer ceases to be
CopyConstructible and Assignable and having such stuff in a standard
container is a violation of the container requirements.
There are probably other reasons too, but I don't recall them now.
Also use of <algorithm> is likely to cause assignments of values in a |
sequence, for example remove, and unique come to mind, but there might
be others that do this.
foo *p = new foo;
foo *q = new foo;
p = q; // memory leak..
,,,
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Paul Rosen
Guest
|
| Posted: Sat Apr 30, 2005 11:26 am Post subject: Re: Messing with expensive objects in containers |
|
|
Carl Barron wrote:
| Quote: | In article <9BNbe.87274$zZ1.2447044 (AT) twister1 (DOT) libero.it>, Alberto
Barbati <AlbertoBarbati (AT) libero (DOT) it> wrote:
[email]stuart.allie (AT) gmail (DOT) com[/email] wrote:
Alberto Barbati wrote:
Just don't make the mistake to use a vector of custodial pointers to
new-allocated objects, because it has been discussed several times
that it's not a Good Thing(tm).
Just curious, why is this not a "Goodd Thing?"
The main reason is that as soon as you call delete on a pointer, the
pointer becomes invalid and accessing an such a pointer gives an
undefined behaviour. In particular, the pointer ceases to be
CopyConstructible and Assignable and having such stuff in a standard
container is a violation of the container requirements.
|
I want to make sure I understand what you are warning against. Are you
saying that the following construct should be avoided?
I also have expensive objects that need to be put in collections. I
create them and put them in a list that is private, and have one or more
collections (either vector or map) that contain iterators to items in
the list.
There is some extra work to delete, but in my case, I tend to initialize
at the beginning and not delete until I'm ready to clear the entire object.
The advantages of this is that I can have different sort orders in
different vectors and I never have to invalidate an iterator.
I don't think I've got a problem with dangling pointers because all of
the collections are private members in the same class, and I can control
access to them. The outside world only requests an object and receives
an iterator to it.
If an outside class wishes to hold onto an iterator it needs to be an
Observer and watch for a message that the collection is going away.
So, first, is this what has been "discussed many times" and dismissed?
If so, what is the other fast way to handle these objects?
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Alberto Barbati
Guest
|
| Posted: Sun May 01, 2005 10:57 am Post subject: Re: Messing with expensive objects in containers |
|
|
Paul Rosen wrote:
| Quote: | Barbati <AlbertoBarbati (AT) libero (DOT) it> wrote:
The main reason is that as soon as you call delete on a pointer, the
pointer becomes invalid and accessing an such a pointer gives an
undefined behaviour. In particular, the pointer ceases to be
CopyConstructible and Assignable and having such stuff in a standard
container is a violation of the container requirements.
I want to make sure I understand what you are warning against. Are you
saying that the following construct should be avoided?
I also have expensive objects that need to be put in collections. I
create them and put them in a list that is private, and have one or more
collections (either vector or map) that contain iterators to items in
the list.
|
I was talking specifically about *custodial pointers*, that is a pointer
you eventually call delete onto. As you seem to have collections of
iterators, that remark does not apply to you. Of course, you still need
to be careful about invalidating those iterators but that's a different
(albeit similar) issue.
For example, one possible reasonably safe approach is the following:
1) put all your heavy-weight objects in a std::list, or even a
std::deque if you always add/remove objects at the end of the sequence;
call this the "storage" container;
2) get iterators (in fact, in this case also pointers would be ok) to
the elements in the "storage" container and put them in whatever
container type you need.
Unless you call splice (for list) or insert/erase in the middle (for
deque), the only way of invalidating pointer/iterators is by removing
the controlled object. So you just need to be careful to empty/destroy
the iterators/pointers container *before* removing objects from the
"storage" container and you'll be ok.
[Note: In fact if you create all heavy-weight objects at startup and
destroy all of them at the end, so that no object is added/removed
during the "real" code, then the "storage" container could also be
std::vector. Calling std::reserve can be used to avoid reallocation
during the vector initial "filling".]
| Quote: | There is some extra work to delete, but in my case, I tend to initialize
at the beginning and not delete until I'm ready to clear the entire object.
|
What extra work exactly? I don't understand.
In the approach above the only extra work you need is to ensure that the
"storage" data member is declared *before* the "pointer" containers, so
that they will be destroyed in the correct order.
| Quote: | I don't think I've got a problem with dangling pointers because all of
the collections are private members in the same class, and I can control
access to them. The outside world only requests an object and receives
an iterator to it.
If an outside class wishes to hold onto an iterator it needs to be an
Observer and watch for a message that the collection is going away.
|
Data-hiding is not the issue here. The problem with custodial pointers
is that unless you're extra careful you can get undefined behaviour no
matter how well you hide you sensitive data.
| Quote: | So, first, is this what has been "discussed many times" and dismissed?
If so, what is the other fast way to handle these objects?
|
No, it's a slightly different issue, as I wrote above.
There are several ways to handle your case. One I already given above.
Another is to use smart pointers such as boost::shared_ptr. The "view"
approach suggested by Maciej Sobczak looks interesting too. I would
suggest him to post it on the Boost mailing list for review as it seems
different enough from boost::multi_index (which is even another option!).
HTH,
Alberto
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Maciej Sobczak
Guest
|
| Posted: Mon May 02, 2005 12:27 pm Post subject: Re: Messing with expensive objects in containers |
|
|
Hi,
Alberto Barbati wrote:
| Quote: | The "view"
approach suggested by Maciej Sobczak looks interesting too. I would
suggest him to post it on the Boost mailing list for review
|
I did some time ago, but there was no interest (maybe it's the time to
refresh it?).
Anyway, the "view" concept, as implemented here:
http://www.msobczak.com/prog/bin/view.zip (11kB)
appeared to be just a small fraction (but maybe therefore much easier to
use) of this:
http://www.zib.de/weiser/vtl/
| Quote: | as it seems
different enough from boost::multi_index
|
It is. The most important difference is that view is a technique that
you can use non-intrusively on *already existing* STL sequences.
--
Maciej Sobczak : http://www.msobczak.com/
Programming : http://www.msobczak.com/prog/
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
