[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.c++

Pointers as iterators; vector representation...

barcaroller

11/7/2008 11:05:00 PM


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>.


9 Answers

Victor Bazarov

11/7/2008 11:38:00 PM

0

barcaroller wrote:
> 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?

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.

> 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?

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

Jim Langston

11/7/2008 11:55:00 PM

0


"Victor Bazarov" <v.Abazarov@comAcast.net> wrote in message
news:gf2jh4$5cm$1@news.datemas.de...
> barcaroller wrote:
>> 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?
>
> 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

11/8/2008 12:43:00 AM

0


"Victor Bazarov" <v.Abazarov@comAcast.net> wrote in message
news:gf2jh4$5cm$1@news.datemas.de...

> 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

11/8/2008 3:23:00 AM

0

barcaroller wrote:
> 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.

--
Best regards,
Andrey Tarasevich

Andrey Tarasevich

11/8/2008 3:25:00 AM

0

barcaroller wrote:
> 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.

--
Best regards,
Andrey Tarasevich

James Kanze

11/8/2008 9:26:00 AM

0

On Nov 8, 1:42 am, "barcaroller" <barcarol...@music.net> wrote:
> "Victor Bazarov" <v.Abaza...@comAcast.net> wrote in message

> news:gf2jh4$5cm$1@news.datemas.de...

> > 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.

--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

barcaroller

11/8/2008 3:33:00 PM

0


"Andrey Tarasevich" <andreytarasevich@hotmail.com> wrote in message
news:gf30m1$v90$1@aioe.org...

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

barcaroller

11/8/2008 3:33:00 PM

0


"Andrey Tarasevich" <andreytarasevich@hotmail.com> wrote in message
news:gf30qm$v90$2@aioe.org...

> 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;

Hendrik Schober

11/9/2008 12:28:00 AM

0

barcaroller wrote:
> "Andrey Tarasevich" <andreytarasevich@hotmail.com> wrote in message
> news:gf30qm$v90$2@aioe.org...
>
>> 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;

That depends on what type 'iterator' is in your code.

Schobi