Re: memory efficient STL allocator alternatives? [ solved ]
JoshuaMaurice@gmail.com wrote:
[ ... ]
In case you overlooked it, might I again suggest what
lhyatt@princeton.edu recommended. It's the common idiom that if you
want to shrink the vector's capacity to its current size, then you do:
On Jul 31, 7:19 am, "lhy...@princeton.edu" <lhy...@gmail.com> wrote:
template<typename Vector>
void shrink_vector(Vector& v) {
Vector(v.begin(), v.end()).swap(v);
}
Or, more commonly,
vector<int>(x).swap(x);
If you build each vector one at a time, then at the end of working
with each vector, you can shrink its capacity to its size, and proceed
to the next one. You will gain your desired space savings with a small
amount of time overhead.
If you're building all the vectors at once, and you don't know when
you're done with some vector, then there is no "end point" when you're
done working with some vector. Thus the only way to save space is to
shrink it after every remove and insert, or some sort of heuristic to
determine when to shrink. This problem would be more interesting, and
we don't have enough information on your exact problem to solve it.
This is indeed the case, the whole set of vectors is updated in a
chaotic pattern (it _is_ a fractal (http://www.elmweb.nl/)), and I don't
know when a particular vector is "ready". I took the shrink_vector
function as inspiration to implement alternatives for the insert() and
erase() methods for vectors (see code fragment below). The advantage
above the shrink_vector function is that it prevents an extra copy of
the elements of the vector. The "ShrinkThreshold" allows a trade-off
between cpu and memory resources. This tackles the problem.
What I don't like about it is that to my taste the solution contains too
much "inside knowledge" about the memory allocation strategies of
vector. I also don't know to what degree this is standard required
behaviour, common usage, or even GNU libstdc++ specific (I guess not).
Would there be a "market" for a lean_vector<T> class that behaves along
the lines of the code below, or can this behaviour be factored out of
vector somehow?
Thanks everyone for the suggestions.
Eric
---- code fragment ----
// threshold for shrinking intervals vector
const size_t ShrinkThreshold = 4;
// "lean" erase that never lets the capacity grow
// beyond size + ShrinkThreshold
template<typename V>
void LeanErase(V& v, typename V::iterator i)
{
if(v.capacity() >= v.size() + ShrinkThreshold) {
V w(v.size() - 1);
typename V::iterator wi = w.begin();
for(typename V::iterator vi = v.begin(); vi != v.end(); ++vi) {
if(vi == i) continue;
*wi++ = *vi;
}
w.swap(v);
}
else {
v.erase(i);
}
}
// lean insert that grows the vector capacity only by ShrinkThreshold
template<typename T>
void LeanInsert(vector<T>& v, typename vector<T>::iterator i,
const T& t)
{
if(v.capacity() < v.size() + 1) {
vector<T> w;
w.reserve(v.size() + ShrinkThreshold);
w.resize(v.size() + 1);
typename vector<T>::iterator vi(v.begin());
typename vector<T>::iterator wi = w.begin();
while(vi != i) *wi++ = *vi++;
*wi++ = t;
while(vi != v.end()) *wi++ = *vi++;
w.swap(v);
}
else {
v.insert(i, t);
}
}
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]