Pointers as iterators; vector<string> representation...

[barcaroller]

1. If I pass pointers (char*) as iterators to an STL algorithm and the
return value is an iterator, can I convert that iterator to a pointer? If
yes, how?


2. What is the internal representation of vector<string>? Will the vector
contain the string objects or will it contain pointers/references to the
string objects? The reason I ask is that it is not clear to me how the
v.reserve() and &v[0] operations would work for a vector<string>.

 

[Jim Langston]

For most of the standard algorithms, the return value type is the same as
the one you pass. It's already a pointer, no need to convert. Test it,
you'll see.

Just an added note, the way to convert an iterator to a pointer is to take
the address of the dereferenced iterator. I.E.

&(*it) would be a pointer to the item if it is an iterator or a pointer.

2. What is the internal representation of vector<string>?
Implementation-defined.

Will the vector
contain the string objects or will it contain pointers/references to the
string objects? The reason I ask is that it is not clear to me how the
v.reserve() and &v[0] operations would work for a vector<string>.

The vector will contain a dynamic array of 'string' objects. The
'reserve' operation allocates the array capable of containing future
'string' objects (which will be constructed using 'placement new', most
likely). Taking the address of v[0] (which returns the reference to the
very first object in the inner array) will give you the starting address
of the inner array. What's there to [not] understand? Now, you probably
need to understand how 'string' works, as well. Do you?

As an added note you can find your implementation of std::string on your
system. Try opening up your string. file and taking a look. It can get
pretty esoteric but if you can understand that code you will be well on your
way to understanding C++.

 

[barcaroller]

The vector will contain a dynamic array of 'string' objects. The
'reserve' operation allocates the array capable of containing future
'string' objects (which will be constructed using 'placement new', most
likely). Taking the address of v[0] (which returns the reference to the
very first object in the inner array) will give you the starting address
of the inner array. What's there to [not] understand? Now, you probably
need to understand how 'string' works, as well. Do you?

If the vector "contains" the strings, then reserving ahead of time is not
useful for optimization because the vector would still not know what the
size of the strings are until they are actually inserted.

If, however, the vector contains only pointers/references to the strings,
reserve() would still not be useful.

 

[Andrey Tarasevich]

If the vector "contains" the strings, then reserving ahead of time is not
useful for optimization because the vector would still not know what the
size of the strings are until they are actually inserted.

Yes, we always do know the "size of the strings" in advance. The
'std::vector' object in this case contains 'std::string' objects. And
the size of the latter is always pre-determined and known at compile
time. This is the only size 'std::vector' needs to know about.

In general case it is the 'std::string' object itself that contains the
pointer to the controlled sequence (the actual "string"). The length of
the sequence can vary (it is allocated independently), but the size of
the 'std::string' object itself is always fixed and does not depend in
any way on the current length of the controlled sequence.

In other words, the actual "strings" (character sequences) are stored in
'std::vector<std::string>' by pointers, but it has absolutely nothing to
to with the 'std::vector' itself. This is an internal issue of
'std::string'. 'std::vector' doesn't know about it and doesn't care
about it.

Reserving 'std::vector<std::string>' ahead of time is, of course, useful
- it prevents unnecessary reallocations of 'std::vector' when adding
extra 'std::string' objects to the 'std::vector'.

If, however, the vector contains only pointers/references to the strings,
reserve() would still not be useful.

You seem to be caught in a terminological mix-up with regards to what is
a "string" and what the word "stores" means in this case.

But in any case, 'reserve()' is still useful (as described above).
Unless, again, you give the word "useful" some meaning that is not
immediately clear to me.

 

[Andrey Tarasevich]

1. If I pass pointers (char*) as iterators to an STL algorithm and the
return value is an iterator, can I convert that iterator to a pointer? If
yes, how?

Can you illustrate what you are talking about with an example? Normally
the return value is an iterator of the same kind as the one (the ones)
that was passed in. If you pass 'char*'s, you get back a 'char*'. No
need to convert anything.

 

[James Kanze]

news:[email protected]...

The vector will contain a dynamic array of 'string' objects.
 The 'reserve' operation allocates the array capable of
containing future 'string' objects (which will be
constructed using 'placement new', most likely).  Taking the
address of v[0] (which returns the reference to the very
first object in the inner array) will give you the starting
address of the inner array.  What's there to [not]
understand?  Now, you probably need to understand how
'string' works, as well.  Do you?

If the vector "contains" the strings, then reserving ahead of
time is not useful for optimization because the vector would
still not know what the size of the strings are until they are
actually inserted.

That depends on the implementation of std::string. The sizeof
(as opposed to the size of) an object is a compile time
constant; std::string needs an additional indirection to handle
variable length, but this is hidden in std::string; std::vector
doesn't no beans about it. And depending on the implementation,
it may not always have to do a deep copy, or it may not need the
extra indirection if the strings are short enough.

If, however, the vector contains only pointers/references to
the strings, reserve() would still not be useful.

Oh yes it is. Perhaps even more so. Increasing the capacity of
a vector means copying member objects. If std::string is
systematically doing a deep copy (most do, at least if the
strings are longer than a certain length), then copying will
mean allocating a new string, copying the data, then deleting
the old one. (It's things like this that motivated the entire
movable business in the next version of the standard.)

The most frequent reason for reserve(), however, is to ensure
the validity of iterators.

 

[barcaroller]

Thanks for the clarification. I hadn't realized that the size of the object
and object.size() were unrelated.

 

[barcaroller]

Can you illustrate what you are talking about with an example? Normally
the return value is an iterator of the same kind as the one (the ones)
that was passed in. If you pass 'char*'s, you get back a 'char*'. No need
to convert anything.

char* foo(char* a, char* b, char* c, char* d)
{
iterator i = search(a,b,c,d);

return ???
}

If I understand you correctly, I can say:

return i;