Re: memory efficient STL allocator alternatives? [ solved ]
In article <4892fb59$0$49588$e4fe514c@news.xs4all.nl>,
Eric Meijer <eric_no1spam1@xs4all.nl> wrote:
---- 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);
}
}
You may wish to avoid default constructing the elements in w, since they
are just going to be overwritten by the copy. One such way to write
this is:
template<typename V>
void LeanErase(V& v, typename V::iterator i)
{
if (v.capacity() >= v.size() + threshold)
{
V w;
w.reserve(v.size() - 1);
std::copy(v.begin(), i, std::back_inserter(w));
std::copy(++i, v.end(), std::back_inserter(w));
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);
}
}
Both to avoid the default construction and to use the same template
parameters as LeanErase, I'd write it as:
template<typename V>
void LeanInsert(V& v, typename V::iterator i, typename V::value_type
const& t)
{
if (v.capacity() < v.size() + 1)
{
V w;
w.reserve(v.size() + threshold);
std::copy(v.begin(), i, std::back_inserter(w));
w.push_back(t);
if (i != v.end())
{
std::copy(++i, v.end(), std::back_inserter(w));
}
w.swap(v);
}
else
{
v.insert(i, t);
}
}
--
Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> 773 961-1620
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]