Re: memory efficient STL allocator alternatives? [ solved ]

From:

Alberto Ganesh Barbati <AlbertoBarbati@libero.it>

Newsgroups:

comp.lang.c++.moderated

Date:

Fri, 1 Aug 2008 18:19:37 CST

Message-ID:

<tJIkk.37763$Ca.16093@twister2.libero.it>

Eric Meijer ha scritto:

// 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;
    }

this might be optimized to:

       V w;
       w.reserve(v.size() - 1);
       w.assign(v.begin(), i);
       ++i;
       std::copy(i, v.end(), back_inserter(w));

this implementation avoids initializing the element of the vector.

    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++;

this might be optimized to:

       vector<T> w;
       w.reserve(v.size() + ShrinkThreshold);
       w.assign(v.begin(), i);
       w.push_back(t);
       std::copy(i, v.end(), back_inserter(w));

(notice how it looks like the previous one)

    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! ]