CODEWITHSUNDEEP
stliteratorcopy
idealistikz
idealistikz

Reputation: 1267

STL copy implementation

The following is the definition of copy, according to http://www.sgi.com/tech/stl/copy.html. 

template<class InputIterator, class OutputIterator>
  OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result)
{
   while (first != last) *result++ = *first++;
   return result;
}

I wrote the following code.

vector<int> v;
set<int> s;

s.insert(7);
s.insert(11);
s.insert(27);

//copy elements from the set into the vector
copy(s.begin(), s.end(), v.begin());

Why does the call to copy above generate a runtime error but not a compile error? I'm assuming it has to do with the fact that the vector is empty, v.begin() == v.end(). But why?

Also, I fixed the code by changing it to the following. 

copy(s.begin(), s.end(), back_inserter(v));

Function back_inserter returns an iterator of type back_insert_iterator>. Why does this work? What is it doing?

Upvotes: 1

Views: 480

Answers (2)

zneak
zneak

Reputation: 138031

It fails because you're not respecting the third precondition listed on this same site:

There is enough space to hold all of the elements being copied. More formally, the requirement is that [result, result + (last - first)) is a valid range. [1]

An empty vector is smaller than a set of 3 elements, so you cannot perform the copy operation (which really should be called an "overwrite" operation). This information is not known at compile-time and therefore there is no compile-time failure. Keep in mind that while vectors and most other C++ STL collections are expandable at runtime, they cannot be expanded through their regular iterators operations (which mostly serve the purpose of enumerating items and specifying ranges).

The back_inserter function returns a special iterator that will insert elements to end of the collection. This iterator is an output iterator, and has very little to do with the iterators you can obtain through the begin() and end() methods of the vector. You cannot read from an output iterator.

Upvotes: 2

Jon Hanna
Jon Hanna

Reputation: 113232

Think of the simple case of arrays - with pointers for their iterators. Now, imagine s and v were arrays. If s had 3 elements and v 0 and you tried to copy s into v it wouldn't work. If however v had 3 elements, then the copy would work, over-writing the current contents.

The iterator model in the STL is a generalisation of this. Indeed, pointers can be used as iterators, but so can other objects (you can call copy with a pointer to the first element of an array and one to just past the end and it works). It therefore doesn't work for precisely the same reason.

back_inserter is an iterator which is intended for just this case; rather than move through the collection overwriting its current position, it increases the size of the collection (which must of course therefore be a collection that can grow, such as vector) and writes to the new position.

Upvotes: 0

Related Questions