Quick question about std::vector.erase()

[Andreas5]

Hello again, i just finished excersise 11-6 in Accelerated C++.

Through this chapter the book emulates a simplified vector class, and as a excersise i have written an erase() member function.

My solution allocates new memory, with the size of the original minus the size of what i erase. Then i copy everything but the part i wish to erase into the new storage. Finally i destroy and deallocate the old storage.

Is this the fastest way to erase?

The code has typedefs and functions but here it is anyway:

template <class T> void Vec<T>::erase(iterator& begin, iterator& end) {

	if(begin) {
	
		// New size = old size - (end - begin)
		size_type new_size = (limit-data) - (end-begin);
		
		// new storage 
		iterator new_data = alloc.allocate(new_size);

		// copy first part into new storage
		iterator temp = std::uninitialized_copy(data, begin-1, new_data);

		// copy second part
		iterator new_avail = std::uninitialized_copy(end+1, avail, temp);

		// return the old space
		uncreate();

		// reset pointers to point to the newly allocated space
		data = new_data;
		avail = new_avail;
		limit = new_data + new_size;
	}
}

[arkoenig]

Your code has an interesting strategy, but it has a few problems.

First, the C++ standard defines erase to work by copying elements from the part of the vector after the erasure on top of the elements being erased, then destroying the elements at the end of the original vector. It does this for several reasons.

One reason is that this strategy makes it unnecessary to have enough memory to contain two copies of the entire vector, which would otherwise be necessary if you were erasing, say, a single element. It also makes it unnecessary to copy the elements before the point of the erasure, which might be important if you are erasing only a few elements near the end of the vector.

Still, your strategy is an interesting one, and it has the advantage that if you are erasing a large part of the vector, you wind up using less memory after the smoke has cleared. So let's look at the code and see if there are any problems.

My first observation is that the parameters begin and end should be type iterator or const iterator& , not iterator& . As your code is written, it insists on accepting lvalues as arguments, and implicitly states its intention to modify those arguments--which you have no reason to want to do.

The next problem is on line 12, where the second argument to uninitialized_copy , begin-1 , should be begin . It is easy to see that this code is wrong, because if begin should happen to be equal to data , then computing begin-1 would be trying to compute an iterator that corresponds to a point before the beginning of the vector's data, and this computation yields an invalid result. The correct value of the parameter, begin comes about because the iterator that describes the end of a range is always one element past the end of the range.

For an analogous reason, the first argument to uninitialized_copy in line 15, end+1 , should be end .

I don't see any other problems, but I have not tested the code.

Hope this helps.

[Andreas5]

Thank you for quick and helpful reply!

The method you mention was my first strategy but i couldnt make it work, im glad i asked anyway, really annoying that they have not provided answers with the book.

Takes a lot of work to get good with pointers!

[arkoenig]

The book does not have answers provided because I have found that when books have answers, too many readers look at the answers and think they've understood the problems.

So if you could not make your first strategy work, perhaps you should try harder. The main point to realize is that you should use copy rather than uninitialized_copy to copy the elements that are to fill the erasure; then destroy the elements at the end separately.

[Andreas5]

Oooh its you! Hehe i didnt expect answer from such an expert!

The book does not have answers provided because I have found that when books have answers, too many readers look at the answers and think they've understood the problems.

Yea i understand now that you mention it, i would probably have read the answers too early myself.

[Andreas5]

And thank you for this GREAT book!

[Andreas5]

Adding my last solution in case someone searches for it in the future:

template <class T> void Vec<T>::erase(const iterator& begin, const iterator& end) {

	if(begin) {

		std::copy(end, avail, begin);

		iterator new_avail = avail - (end-begin);

		while(avail != new_avail)
			alloc.destroy(--avail);

		avail = new_avail;
	}
}

[arkoenig]

I cannot resist pointing out that line 12 is unnecessary in this example, because the only way control can reach line 12 is if avail is found to be equal to new_avail in line 9.

I willl also point out that lines 5 and 8 can be collapsed into

iterator new_avail = std::copy(end, avail, begin);

because std::copy returns an iterator that refers to the position after the last element copied.

Finally, the test

if(begin)

in line 3 doesn't seem to do anything useful, because there is no general rule for what it means to use an iterator as a condition.

As before, I have not tested the code that corresponds to these comments, but hope you find them useful anyway.

[Andreas5]

Ah, thank you again.

I found 11-6 and 11-8 very hard, but i often only see solutions that are right infront of my nose :)