growing a large vector iteratively
er
in the code below, i compare two options i) and ii). i have a feeling
we should use i) if A's size is a smaller than some threshold ii)
otherwise
1-is this correct?
2-what would that threshold be?
3-more precisely, in defining "A's size" i'm not sure if both member
functions and member variables affect the memory needed to store/copy
an object or only the member variables).
i)
vector<A> v;
while(has_not_converged()){
//some code that generates a temporary A a;
v.push_back(a); //a has to be copied//every--time v.capacity() is
reached, reallocation is necessary.
};//typically converges after up to a large, but unknown, number of
loops, such as say 100, 1000
ii)
vector<A*> v;
while(has_not_converged()){
//some code that generates A* a = new A();
vector<A*> v.push_back(a);
};//typically converges after up to a large number, but unknown number
of loops, for example 100, 1000
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std...@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]
Jim Langston
news:1186940634.1...@b79g2000hse.googlegroups.com...
> hi,
>
> in the code below, i compare two options i) and ii). i have a feeling
> we should use i) if A's size is a smaller than some threshold ii)
> otherwise
> 1-is this correct?
> 2-what would that threshold be?
> 3-more precisely, in defining "A's size" i'm not sure if both member
> functions and member variables affect the memory needed to store/copy
> an object or only the member variables).
>
> i)
> vector<A> v;
> while(has_not_converged()){
> //some code that generates a temporary A a;
> v.push_back(a); //a has to be copied//every--time v.capacity() is
> reached, reallocation is necessary.
> };//typically converges after up to a large, but unknown, number of
> loops, such as say 100, 1000
>
> ii)
> vector<A*> v;
> while(has_not_converged()){
> //some code that generates A* a = new A();
> vector<A*> v.push_back(a);
> };//typically converges after up to a large number, but unknown number
> of loops, for example 100, 1000
If you pre-estimate the size of the vector and .reserve() that many elements
or more, then there wouldn't be an issue with having to recopy the elements
each time.
Since typically when a container has to grab more memory it will double the
amount of memory needed, even if your estimate is off, there should only be
one copy necessary as the memory amount is effectively doubled.
If you are going to go with ii it is better to use some form of smart
pointer. I personally use ii in some maps std::map<int, someclass*> only
becuase someclass is not copyable. I should really use a smart pointer,
however.
Martin Bonner
> hi,
>
> in the code below, i compare two options i) and ii). i have a feeling
> we should use i) if A's size is a smaller than some threshold ii)
> otherwise
> 1-is this correct?
> 2-what would that threshold be?
> 3-more precisely, in defining "A's size" i'm not sure if both member
> functions and member variables affect the memory needed to store/copy
> an object or only the member variables).
Member functions are irrelevent. The real question is how much work
is involved in performing the copy construction? If A has a member
which is a large vector, then copying that could get very expensive
(even though sizeof(vector<>) is typically three pointers.)
You NEED to profile!
> i)
> vector<A> v;
> while(has_not_converged()){
> //some code that generates a temporary A a;
> v.push_back(a);
Note that this ALWAYS invokes one copy constructor for A. On average,
it will invoke one more copy constructor for the resize (assuming
doubling. If the vector capacity grows by 50%, I think that rises to
about 2.25).
Your optimization is worthwhile once the cost of a few copies of A
becomes large compared to the cost of generating the temporary.
> };
> //typically converges after up to a large, but unknown, number of
> loops, such as say 100, 1000
>
> ii)
> vector<A*> v;
> while(has_not_converged()){
> //some code that generates A* a = new A();
> v.push_back(a);
> };
er
> [ --- Please see the FAQ before posting. --- ]
> [ FAQ:http://www.comeaucomputing.com/csc/faq.html ]
thank you both for these very clear answers.
Alberto Ganesh Barbati
> hi,
>
> in the code below, i compare two options i) and ii). i have a feeling
> we should use i) if A's size is a smaller than some threshold ii)
> otherwise
> 1-is this correct?
> 2-what would that threshold be?
> 3-more precisely, in defining "A's size" i'm not sure if both member
> functions and member variables affect the memory needed to store/copy
> an object or only the member variables).
>
In addition to the answers you've already got, you can also consider
using a deque instead of a vector. A deque provides reasonably fast
random access but never requires reallocation.
Anyway: you need to profile ;-)
Ganesh
jams.lee
===================================== MODERATOR'S COMMENT:
Please trim moderation footers when replying to posts.
===================================== END OF MODERATOR'S COMMENT
er 写道:
I find this is very userful to me, thanks!