[boost] [ptr_container] How to shift part of a ptr_vector ?

From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2007-12-29 10:38:38

Dear Experts,

I have some code which currently uses a std::vector of pointers, and 
I'm investigating whether I can make it more concise, exception-safe, 
or otherwise better using a ptr_vector.  But I can't see a good way to 
replace the following code, which shifts part of the vector by one 
place, deleting one pointee and creating a new one at the other end:

struct LargeThing { .... };
std::vector<LargeThing*> v;

void shift(int start, int end) {
   delete v[start];
   for (int i=start; i<end; ++i) {  // or use a std::algorithm
     v[i]=v[i+1];
   }
   v[end] = new LargeThing;
}

With a ptr_vector, I think that I could do something like

struct LargeThing { .... };
boost::ptr_vector<LargeThing> v;

void shift(int start, int end) {
   v.release(v.begin()+start);  // or should that be erase() ?
   v.insert(v.begin()+end-1, new LargeThing);
}

But this has complexity O(v.length()), because v.release() has to move 
all elements beyond start, while my current code has complexity 
O(end-start), because it doesn't touch the elements beyond end.

Is there some better way to accomplish this?  Maybe transfer() can be 
used?  Or something involving swap()?

Thanks for any suggestions.

Phil.