Re: [C++] Vector - guaranteed to be contiguous?
From: Martijn Lievaart (m_at_remove.this.part.rtij.nl)
Date: 01/16/04
- Next message: Jerry Coffin: "Re: Problem writing to a file"
- Previous message: Jerry Coffin: "Re: Is This How It's SUPPOSED to Work?"
- In reply to: André Pönitz: "Re: [C++] Vector - guaranteed to be contiguous?"
- Next in thread: David White: "Re: [C++] Vector - guaranteed to be contiguous?"
- Reply: David White: "Re: [C++] Vector - guaranteed to be contiguous?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Fri, 16 Jan 2004 16:50:42 +0100
On Fri, 16 Jan 2004 14:38:48 +0000, André Pönitz wrote:
> Martijn Lievaart <m@remove.this.part.rtij.nl> wrote:
>> To clarify why it works, have a lookk at a hypothetical std::copy
>>
>> template<typename OUTITER, typename INITER, typename INITERT>
>> void some_algorithm(OUTITER out, INITER begin, INITER end)
>> {
>> for (INITER i=begin; i!=end; ++i)
>> *out++ = do_something(*i);
>> }
>>
>> It doesn't matter what types the iterators are, a long as the above gives
>> something which compiles. The same holds for std::vector::insert, that
>> member is templated on the input iterators as well.
>
> It should be really stressed that this works because it's an template
> and both iterator and pointers fulfill certain requirements.
>
> The reason is _not_ that iterators and pointers can be used
> interchangably.
>
> I know you know this but I think the discussion so far could still be
> mis-interpreted.
Yes, good addition.
For those that are still scratching their heads, I'll start simple and
work up from there. Lets undress the example to make it even simpler:
template<typename OUTITER, typename INITER, typename INITERT>
void copy(OUTITER out, INITER begin, INITER end)
{
for (INITER i=begin; i!=end; ++i)
*out++ = *i;
}
This copies from `begin', up to but not including `end' to whatever `out'
points to. We don't know yet what begin, end and out exactly are, but we
don't care here.
Now if we use this as follows:
const size_t N = 100;
char a[N], b[N];
// fill a here somehow
copy(b, a, a+N);
What happens is that the compiler sees copy and thinks, "Hey, I know copy.
But it is a template, let me try to deduce those types.
So after some pondering, the compiler decides that INITER must be a char*
and OUTITER must also be a char*. The compiler now generates the following:
// This is produced by the compiler, not by the programmer!
void copy<char*,char*>(char *out, char *begin, char *end)
{
for (char* i=begin; i!=end; ++i)
*out++ = *i;
}
No coding required by you, except the template. The template tells the
compiler how to create the function copy<char*,char*>.
Now we expand this a bit:
int c[N];
copy(c, a, a+N);
Now the compiler sees that OUTITER must be an int* and generates:
// This is produced by the compiler, not by the programmer!
void copy<int*,char*>(int *out, char *begin, char *end)
{
for (char* i=begin; i!=end; ++i)
*out++ = *i;
}
As an int can be assigned from a char, this works. But if we do:
struct mystruct {};
mystruct d[N];
copy(d, a, a+N);
what happens now?
Well, exactly the same happens. The compiler generates:
// This is produced by the compiler, not by the programmer!
void copy<mystruct*,char*>(mystruct *out, char *begin, char *end)
{
for (char* i=begin; i!=end; ++i)
*out++ = *i;
}
but when the compiler tries to compile it, it will complain about the
assignment "*out++ = *i;". That line now tries to assign a char to a
mystruct and because that is not possible, we get a compiler error.
The important point about the last example is that code generation from a
template and compiling that generated code are two completely seperate
things. In this last example the code generation went fine, but the
generated code did not compile.
Let's get back to pointers and iterators now. You should by now be able to
fill in iterators in the previous examples. Iterators have operator*,
operator++ and operator != defined, so the above code will compile fine if
INITER or OUTITER is an iterator instead of a pointer.
vector<int> v;
v.resize(N); // make room!
copy(v.begin(), a, a+N);
This works fine, as we can use a vector::iterator for `out' in copy. The
code the compiler generates is:
// This is produced by the compiler, not by the programmer!
void copy<vector::iterator,char*>(vector::iterator out, char *begin, char
*end) {
for (char* i=begin; i!=end; ++i)
*out++ = *i;
}
Similarly, INITER can be an iterator as well. A template is just a little
code generator, if whatever it generates is valid C++, it is OK. The
template couldn't care less about what types you pass it, it just applies
them and spits out code with the types filled in.
Now for one last twist. So how come we can pass a float* to
vector::insert? Remember this was the original question. Insert is also
templated, but it is a templated member function:
namespace std {
...
template<typename T>
class vector
{
...
struct iterator { ... };
...
template<class InIt>
void insert(iterator where, InIt first, InIt last);
...
};
...
}
So we create vectors with a certain type T, but can insert into that
vector with an iterator of unspecified type InIt. What can we use for
InIt? Well roughly speaking everything for which the following holds true:
If it is of type InIt
1) T t(*it); must compile (there must be a conversion from *it to a T)
2) ++it; must compile.
In reality, the standard places some more requirements on iterators, but
these are the most important. Clearly a pointer to a T (a T*) satisfies
these two requirements given:
T *p;
T t(*p); // 1) OK
++p; // 2) OK
Therefore, it is possible to:
vector<float> vf;
float array[SIZE] = { ... };
vf.resize(SIZE);
vf.insert(vf.begin(), array, array+SIZE);
Actually we can even say:
vector<float> vf;
int array[SIZE] = { ... };
vf.resize(SIZE);
vf.insert(vf.begin(), array, array+SIZE);
As an int can be assigned to a float (requirement 1), this will work! The
magic of templates!
OK, I hope I helped someone with this, otherwise I'll never write these
lengthy articles again! :-)
M4
P.S. If you want to insert into a vector, have a look at back_inserter. It
automatically resize the vector for you. Very handy.
- Next message: Jerry Coffin: "Re: Problem writing to a file"
- Previous message: Jerry Coffin: "Re: Is This How It's SUPPOSED to Work?"
- In reply to: André Pönitz: "Re: [C++] Vector - guaranteed to be contiguous?"
- Next in thread: David White: "Re: [C++] Vector - guaranteed to be contiguous?"
- Reply: David White: "Re: [C++] Vector - guaranteed to be contiguous?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
