Why won't set<string> iterator work?

[Steve Edwards]

Hi,

1)

I'm making a container for string pointers...

set<string*> strSet;

strSet.insert(...); // insert some strings
....
....


But when I come to iterate over them, I'm getting an error that there is
no operator= for iter:

set<string>::iterator iter;
for(iter = *strSet.begin(); iter != strSet.end(); iter++)

This is exactly what I did when I was learning about maps, and it worked
fine. Have I misunderstood, or should iterators work the same with all
containers?



2)
I could just as easily use a vector for these strings, and remove the
duplicates manually. However, when I tried this, nothing got removed,
even though I had no compiler errors:


vector<string> strVec;

strVec.push_back("test");
strVec.push_back("test");
strVec.push_back("test");

strVec[2].erase();

My text book states that vector is not ideal for random access removal,
but not that it is impossible. have I got this wrong?




Thanks

Steve

 

[Alf P. Steinbach]

* Steve Edwards:

1)

I'm making a container for string pointers...

set<string*> strSet;

strSet.insert(...); // insert some strings
...
...


But when I come to iterate over them, I'm getting an error that there is
no operator= for iter:

set<string>::iterator iter;
for(iter = *strSet.begin(); iter != strSet.end(); iter++)

This is exactly what I did when I was learning about maps, and it worked
fine. Have I misunderstood, or should iterators work the same with all
containers?

What's that '*' in there?

2)
I could just as easily use a vector for these strings, and remove the
duplicates manually. However, when I tried this, nothing got removed,
even though I had no compiler errors:


vector<string> strVec;

strVec.push_back("test");
strVec.push_back("test");
strVec.push_back("test");

strVec[2].erase();

My text book states that vector is not ideal for random access removal,
but not that it is impossible. have I got this wrong?

Both. I mean, both the textbook and you. Whether a vector is ideal for
random access removal depends on context and what's meant by removal.

However, the code you have shown calls 'erase' on one of the strings in
the vector, which changes that string but does not remove it from the
vector.

Calling 'erase' on the vector would effect a removal (in the most common
sense of the word), but in time linear in the size of the vector.

 

[Kai-Uwe Bux]

Hi,

1)

I'm making a container for string pointers...

set<string*> strSet;

If possible, work with set<string> not set<string*>. Note that std::set<>
keeps its elements in a sorted order and uses that order to determine if a
new element is already in the set. For string object the order is done by
lexicographic comparison, which is very likely what you want. For object of
type string*, however, the comparison is done by comparing the *pointers*
not the pointees.

strSet.insert(...); // insert some strings
...
...


But when I come to iterate over them, I'm getting an error that there is
no operator= for iter:

set<string>::iterator iter;

for(iter = *strSet.begin(); iter != strSet.end(); iter++)

Ask yourself what the expression *strSet.begin() will evaluate to.

This is exactly what I did when I was learning about maps, and it worked
fine.

No, either it is not what you did back then, or it did not work (or both).

Have I misunderstood, or should iterators work the same with all
containers?

2)
I could just as easily use a vector for these strings, and remove the
duplicates manually. However, when I tried this, nothing got removed,
even though I had no compiler errors:


vector<string> strVec;

strVec.push_back("test");
strVec.push_back("test");
strVec.push_back("test");

strVec[2].erase();

My text book states that vector is not ideal for random access removal,
but not that it is impossible. have I got this wrong?

This does not call the erase() method for the object strVec but for the
string object in strVec[2]. This is *not* what you say you intended doing.


Best

Kai-Uwe Bux

 

[Ivan Vecerina]

[ 1) already answered ]
: 2)
: I could just as easily use a vector for these strings, and remove the
: duplicates manually. However, when I tried this, nothing got removed,
: even though I had no compiler errors:
:
:
: vector<string> strVec;
:
: strVec.push_back("test");
: strVec.push_back("test");
: strVec.push_back("test");
:
: strVec[2].erase();
[again, Alf already pointed out your mistake]

: My text book states that vector is not ideal for random access removal,
: but not that it is impossible. have I got this wrong?

Removal of duplicate entries can be relatively efficient if
you do it all in one go ( using <algorithm> ):
std::sort( strVec.begin(), strVec.end() );
strVec.erase( std::unique( strVec.begin(), strVec.end() )
, strVec.end()
);

In some circumstances, the performance characteristics of this
approach could compete with those of std::set.

Ivan

 

[Steve Edwards]

* Steve Edwards:

What's that '*' in there?

Ah... thanks. I was originally using pointers in my sets and got
confused.(They are subsets of a very large array of strings and I wanted
to avoid the memory overhead of having copies, but as Kai said the
sorting benefits are worth it.)

2)
I could just as easily use a vector for these strings, and remove the
duplicates manually. However, when I tried this, nothing got removed,
even though I had no compiler errors:


vector<string> strVec;

strVec.push_back("test");
strVec.push_back("test");
strVec.push_back("test");

strVec[2].erase();

My text book states that vector is not ideal for random access removal,
but not that it is impossible. have I got this wrong?

Both. I mean, both the textbook and you. Whether a vector is ideal for
random access removal depends on context and what's meant by removal.

However, the code you have shown calls 'erase' on one of the strings in
the vector, which changes that string but does not remove it from the
vector.

Calling 'erase' on the vector would effect a removal (in the most common
sense of the word), but in time linear in the size of the vector.

OK, I see what I was doing wrong, and from Ivan's example I can see how
to do it using <algorithm>. But is there a way to use erase() in the
trivial case where you want to remove a single known index? i.e.

vector<string> vec;

vec.push_back("zero");
vec.push_back("one");
vec.push_back("two");

vec.erase( [1] ); !!

 

[Steve Edwards]

[ 1) already answered ]
: 2)
: I could just as easily use a vector for these strings, and remove the
: duplicates manually. However, when I tried this, nothing got removed,
: even though I had no compiler errors:
:
:
: vector<string> strVec;
:
: strVec.push_back("test");
: strVec.push_back("test");
: strVec.push_back("test");
:
: strVec[2].erase();
[again, Alf already pointed out your mistake]

: My text book states that vector is not ideal for random access removal,
: but not that it is impossible. have I got this wrong?

Removal of duplicate entries can be relatively efficient if
you do it all in one go ( using <algorithm> ):
std::sort( strVec.begin(), strVec.end() );
strVec.erase( std::unique( strVec.begin(), strVec.end() )
, strVec.end()
);

In some circumstances, the performance characteristics of this
approach could compete with those of std::set.

Ivan

Thanks for the code which is specific for my application.
However, I am finding it difficult to find examples (in books or on the
web) of trivial cases of dealing with specific indexing. The above kind
of method would be overkill if you know you just want to remove
strVec[7].

 

[Kai-Uwe Bux]

Steve Edwards wrote:

[snip]

OK, I see what I was doing wrong, and from Ivan's example I can see how
to do it using <algorithm>. But is there a way to use erase() in the
trivial case where you want to remove a single known index? i.e.

vector<string> vec;

vec.push_back("zero");
vec.push_back("one");
vec.push_back("two");

vec.erase( [1] ); !!

From memory (not tested):

vec.erase( vec.begin() + 1 );


Best

Kai-Uwe Bux

 

[Steve Edwards]

Steve Edwards wrote:

[snip]

OK, I see what I was doing wrong, and from Ivan's example I can see how
to do it using <algorithm>. But is there a way to use erase() in the
trivial case where you want to remove a single known index? i.e.

vector<string> vec;

vec.push_back("zero");
vec.push_back("one");
vec.push_back("two");

vec.erase( [1] ); !!

From memory (not tested):

vec.erase( vec.begin() + 1 );


Best

Kai-Uwe Bux

Thanks, that appears to work as needed.

Steve

 

[Michiel.Salters]

std::sort( strVec.begin(), strVec.end() );
strVec.erase( std::unique( strVec.begin(), strVec.end() )
, strVec.end()
);

Thanks for the code which is specific for my application.
However, I am finding it difficult to find examples (in books or on the
web) of trivial cases of dealing with specific indexing. The above kind
of method would be overkill if you know you just want to remove
strVec[7].

Yep. In that case, a solution might be
std::swap(strVec[7], strVec.back());
strVec.pop_back();
which is O(1) but of course destroys the order.

HTH,
Michiel Salters