using map, list etc. in const methods

Hello,

I'm quite new to C++ so maybe there's something I miss.
I write a simple board game. It has a board class. This class has a
method that returns the count of pieces a player has on the board. Since
this function does not change anything in the class I declared it as
const. To count all pieces of a given color the functions iterates
through a "map" of CNode-pointers. "CNode" is another class that is
irrelevant to the problem.

Here comes the function: (EColor is an enum of colors, not important here)

int
CBoard::countPieces(EColor color) const
{
// "nodes" is a private class member
// with type map<string,CNode*>
int count = 0;
for (map<string,CNode*>::iterator i=nodes.begin();
i != nodes.end();
i++)
{
// do something with (*i)
// ...
}
return count;
}

The compiler refuses to compile the code, because I violate the
constness of the function in the line where I declare the iterator.
Is there a proper way (or workaround) to leave the function const?

Another point: I've heard, that it is not good to store pointers to
objects in stl-containers like map, list, vector etc. because of
ownership problems (?). Do you know a good webpage or tutorial about
this topic? I would like to learn how to do it the right way.
There are a lot of classes in the STL and I would like to know how to
use their whole power. At the moment I'm just using lists, vectors and
maps in lack of a good book or online tutorial discussing the STL in detail.

Thanks in advance!

--
Regards,
Christof Krueger

Remove "donotspam" if you want to email me.

re: using map, list etc. in const methods

In article <burrlk$j5g$07$1@news.t-online.com>, Christof Krueger wrote:[color=blue]
> Hello,
>
> I'm quite new to C++ so maybe there's something I miss.
> I write a simple board game. It has a board class. This class has a
> method that returns the count of pieces a player has on the board. Since
> this function does not change anything in the class I declared it as
> const. To count all pieces of a given color the functions iterates
> through a "map" of CNode-pointers. "CNode" is another class that is
> irrelevant to the problem.
>
> Here comes the function: (EColor is an enum of colors, not important here)
>
> int
> CBoard::countPieces(EColor color) const
> {
> // "nodes" is a private class member
> // with type map<string,CNode*>
> int count = 0;
> for (map<string,CNode*>::iterator i=nodes.begin();
> i != nodes.end();
> i++)
> {
> // do something with (*i)
> // ...
> }
> return count;
> }
>
> The compiler refuses to compile the code, because I violate the
> constness of the function in the line where I declare the iterator.
> Is there a proper way (or workaround) to leave the function const?[/color]

map<string,CNode*>::const_iterator

btw, you can do this using

count_if(themap.begin(),themap.end(),isWhite); // isWhite returns true if the piece is white
[color=blue]
> Another point: I've heard, that it is not good to store pointers to
> objects in stl-containers like map, list, vector etc. because of
> ownership problems (?).[/color]

It's not necessarily a bad thing. But you need to make sure that you understand
who "owns" a given pointer, and you need to make sure that the map doesn't hold
on to "dead pointers".

Here's my question: how are your pointers allocated and deleted ? Who owns them ?
[color=blue]
> Do you know a good webpage or tutorial about
> this topic? I would like to learn how to do it the right way.[/color]

This topic is too complicated to be discussed exhaustively in "a webpage". You
need to read a couple of good books that deal with memory management issues.
[color=blue]
> There are a lot of classes in the STL and I would like to know how to
> use their whole power. At the moment I'm just using lists, vectors and
> maps in lack of a good book or online tutorial discussing the STL in detail.[/color]

Two good books about the C++ standard library:

"Accelerated C++" Koenig and Moo
"The Standard C++ Library A Tutorial and a Reference" Josuttis

Cheers,
--
Donovan Rebbechi
http://pegasus.rutgers.edu/~elflord/

re: using map, list etc. in const methods

Christof Krueger wrote:[color=blue]
> Hello,
>
> I'm quite new to C++ so maybe there's something I miss.
> I write a simple board game. It has a board class. This class has a
> method that returns the count of pieces a player has on the board. Since
> this function does not change anything in the class I declared it as
> const. To count all pieces of a given color the functions iterates
> through a "map" of CNode-pointers. "CNode" is another class that is
> irrelevant to the problem.
>
> Here comes the function: (EColor is an enum of colors, not important here)
>
> int
> CBoard::countPieces(EColor color) const
> {
> // "nodes" is a private class member
> // with type map<string,CNode*>
> int count = 0;
> for (map<string,CNode*>::iterator i=nodes.begin();
> i != nodes.end();
> i++)
> {
> // do something with (*i)
> // ...
> }
> return count;
> }
>
> The compiler refuses to compile the code, because I violate the
> constness of the function in the line where I declare the iterator.
> Is there a proper way (or workaround) to leave the function const?
>
> Another point: I've heard, that it is not good to store pointers to
> objects in stl-containers like map, list, vector etc. because of
> ownership problems (?). Do you know a good webpage or tutorial about
> this topic? I would like to learn how to do it the right way.
> There are a lot of classes in the STL and I would like to know how to
> use their whole power. At the moment I'm just using lists, vectors and
> maps in lack of a good book or online tutorial discussing the STL in
> detail.
>
> Thanks in advance!
>[/color]

use const_iterator.

for (map<string,CNode*>::const_iterator i = nodes.begin(); ...

Also, you should use ++i instead of i++, for reasons of style and
efficiency (no need to copy the "old" state of the iterator).

You might also want to look into using std::for_each()

e.g.:

class my_counter : public std::unary_function<
std::pair<string,CNode*>,
void >
{
private:
mutable int count;
public:
my_counter() : count(0) { }
void operator()(const std::pair<string,CNode*>& val) const
{
// do something here that manipulates count
}
int get_count() const { return count; }
};



int CBoard::countPieces(EColor color)
{
return std::for_each(nodes.begin(),
nodes.end(),
my_counter()).get_count();
}

re: using map, list etc. in const methods

Christof Krueger wrote in news:burrlk$j5g$07$1@news.t-online.com:

[snip]
[color=blue]
>
> int
> CBoard::countPieces(EColor color) const
> {
> // "nodes" is a private class member
> // with type map<string,CNode*>
> int count = 0;
> for (map<string,CNode*>::iterator i=nodes.begin();[/color]

for ( map<string,CNode*>::const_iterator i=nodes.begin();
[color=blue]
> i != nodes.end();
> i++)
> {
> // do something with (*i)
> // ...
> }
> return count;
> }
>
> The compiler refuses to compile the code, because I violate the
> constness of the function in the line where I declare the iterator.
> Is there a proper way (or workaround) to leave the function const?[/color]

Your problem is that when you call nodes.begin() your calling
the const version that returns a const_iterator. a const_iterator
like a pointer to a const doesn't allow you to modify the item
that its iterating (pointing) to.
[color=blue]
>
> Another point: I've heard, that it is not good to store pointers to
> objects in stl-containers like map, list, vector etc. because of
> ownership problems (?).[/color]

Look into smart pointers, in particular boost::shared_ptr:
http://www.boost.org/libs/smart_ptr/shared_ptr.htm

[color=blue]
> Do you know a good webpage or tutorial about
> this topic? I would like to learn how to do it the right way.
> There are a lot of classes in the STL and I would like to know how to
> use their whole power. At the moment I'm just using lists, vectors and
> maps in lack of a good book or online tutorial discussing the STL in
> detail.
>[/color]

No, mostly people around hear recomend geting a good book.
Accelerated C++ (Koenig & moo) is most recomended book for this.

Rob.
--
http://www.victim-prime.dsl.pipex.com/

re: using map, list etc. in const methods

Donovan Rebbechi wrote:
[color=blue]
> In article <burrlk$j5g$07$1@news.t-online.com>, Christof Krueger wrote:
>[color=green]
>>Hello,
>>
>>I'm quite new to C++ so maybe there's something I miss.
>>I write a simple board game. It has a board class. This class has a
>>method that returns the count of pieces a player has on the board. Since
>>this function does not change anything in the class I declared it as
>>const. To count all pieces of a given color the functions iterates
>>through a "map" of CNode-pointers. "CNode" is another class that is
>>irrelevant to the problem.
>>
>>Here comes the function: (EColor is an enum of colors, not important here)
>>
>>int
>>CBoard::countPieces(EColor color) const
>>{
>> // "nodes" is a private class member
>> // with type map<string,CNode*>
>> int count = 0;
>> for (map<string,CNode*>::iterator i=nodes.begin();
>> i != nodes.end();
>> i++)
>> {
>> // do something with (*i)
>> // ...
>> }
>> return count;
>>}
>>
>>The compiler refuses to compile the code, because I violate the
>>constness of the function in the line where I declare the iterator.
>>Is there a proper way (or workaround) to leave the function const?[/color]
>
>
> map<string,CNode*>::const_iterator[/color]
thanks, that makes sense :)
[color=blue]
> btw, you can do this using
>
> count_if(themap.begin(),themap.end(),isWhite); // isWhite returns true if the piece is white[/color]
very handy. I'll use it.
[color=blue]
>[color=green]
>>Another point: I've heard, that it is not good to store pointers to
>>objects in stl-containers like map, list, vector etc. because of
>>ownership problems (?).[/color]
>
>
> It's not necessarily a bad thing. But you need to make sure that you understand
> who "owns" a given pointer, and you need to make sure that the map doesn't hold
> on to "dead pointers".
>
> Here's my question: how are your pointers allocated and deleted ? Who owns them ?[/color]
In this case the board creates the nodes, stores them in the map and
deletes them in it's destructor. I see that ownership is a question of
design. Thanks!

[color=blue][color=green]
>>Do you know a good webpage or tutorial about
>>this topic? I would like to learn how to do it the right way.[/color]
>
>
> This topic is too complicated to be discussed exhaustively in "a webpage". You
> need to read a couple of good books that deal with memory management issues.
>
>[color=green]
>>There are a lot of classes in the STL and I would like to know how to
>>use their whole power. At the moment I'm just using lists, vectors and
>>maps in lack of a good book or online tutorial discussing the STL in detail.[/color]
>
>
> Two good books about the C++ standard library:
>
> "Accelerated C++" Koenig and Moo
> "The Standard C++ Library A Tutorial and a Reference" Josuttis[/color]
I'll take a look on Josuttis book.


Another question:
If I had a public method getNodeMap() that should return my nodes-map to
the caller, is there a possibility to make this method const and to
return a const version of the map, so that the caller may not change the
returned map? I tried that once, but failed because of a lot of compiler
errors.

--
Regards,
Christof Krueger

Remove "donotspam" if you want to email me.

re: using map, list etc. in const methods

red floyd wrote:
[color=blue]
> Christof Krueger wrote:
>[color=green]
>> Hello,
>>
>> I'm quite new to C++ so maybe there's something I miss.
>> I write a simple board game. It has a board class. This class has a
>> method that returns the count of pieces a player has on the board.
>> Since this function does not change anything in the class I declared
>> it as const. To count all pieces of a given color the functions
>> iterates through a "map" of CNode-pointers. "CNode" is another class
>> that is irrelevant to the problem.
>>
>> Here comes the function: (EColor is an enum of colors, not important
>> here)
>>
>> int
>> CBoard::countPieces(EColor color) const
>> {
>> // "nodes" is a private class member
>> // with type map<string,CNode*>
>> int count = 0;
>> for (map<string,CNode*>::iterator i=nodes.begin();
>> i != nodes.end();
>> i++)
>> {
>> // do something with (*i)
>> // ...
>> }
>> return count;
>> }
>>
>> The compiler refuses to compile the code, because I violate the
>> constness of the function in the line where I declare the iterator.
>> Is there a proper way (or workaround) to leave the function const?
>>
>> Another point: I've heard, that it is not good to store pointers to
>> objects in stl-containers like map, list, vector etc. because of
>> ownership problems (?). Do you know a good webpage or tutorial about
>> this topic? I would like to learn how to do it the right way.
>> There are a lot of classes in the STL and I would like to know how to
>> use their whole power. At the moment I'm just using lists, vectors and
>> maps in lack of a good book or online tutorial discussing the STL in
>> detail.
>>
>> Thanks in advance!
>>[/color]
>
> use const_iterator.
>
> for (map<string,CNode*>::const_iterator i = nodes.begin(); ...
>
> Also, you should use ++i instead of i++, for reasons of style and
> efficiency (no need to copy the "old" state of the iterator).[/color]
I always thought that i++ is equivalent to ++i in a for loop. Could you
give more detail what the difference is since I do not understand what
you mean by saying "no need to copy the "old" state of the iterator".
Are there cases where it would be nessecary to use i++ though?
[color=blue]
>
> You might also want to look into using std::for_each()
>
> e.g.:
>
> class my_counter : public std::unary_function<
> std::pair<string,CNode*>,
> void >
> {
> private:
> mutable int count;
> public:
> my_counter() : count(0) { }
> void operator()(const std::pair<string,CNode*>& val) const
> {
> // do something here that manipulates count
> }
> int get_count() const { return count; }
> };
>
>
>
> int CBoard::countPieces(EColor color)
> {
> return std::for_each(nodes.begin(),
> nodes.end(),
> my_counter()).get_count();
> }[/color]
I don't understand why std::for_each(...) returns a my_counter object in
this case. Could you explain it to me pleas (or just give me a hint so I
can look it up myself)?


--
Regards,
Christof Krueger

Remove "donotspam" if you want to email me.

re: using map, list etc. in const methods

In article <burtuq$hld$01$1@news.t-online.com>, Christof Krueger wrote:[color=blue]
> Donovan Rebbechi wrote:[/color]
[color=blue][color=green]
>> It's not necessarily a bad thing. But you need to make sure that you understand
>> who "owns" a given pointer, and you need to make sure that the map doesn't hold
>> on to "dead pointers".
>>
>> Here's my question: how are your pointers allocated and deleted ? Who owns them ?[/color]
> In this case the board creates the nodes, stores them in the map and
> deletes them in it's destructor. I see that ownership is a question of
> design. Thanks![/color]

I see.

But why not instead store the node in an automatic structure:

class Handle
{
Node* impl;
public:
Handle(Node* x):impl(x) {}
/*
how you "handle" these is up to you ...
Handle (const Handle& );
Handle& operator= (const Handle&);
*/
~Handle() { delete impl; }
Node& operator*() { return *impl; }
const Node& operator*() const { return *impl; }
Node* operator->(){ return impl; }
const Node* operator->() const { return impl; }
};
[color=blue]
> Another question:
> If I had a public method getNodeMap() that should return my nodes-map to
> the caller, is there a possibility to make this method const and to
> return a const version of the map,[/color]

You could make the function return a const reference to the map. But that's
a bad idea because it reveals implementation details.

A better approach would be to have begin() and end() methods that return
const_iterators and use a typedef to make it looks as though the map iterators
"belong" to the board class.

e.g.
class Board
{
std::map<foo,bar> m;
public:
typedef std::map< foo, bar>::const_iterator const_iterator;

const_iterator begin() const { return m.begin(); }
const_iterator end() const { return m.end(); }


Cheers,
--
Donovan Rebbechi
http://pegasus.rutgers.edu/~elflord/

re: using map, list etc. in const methods

In article <buru8p$s2n$02$1@news.t-online.com>, Christof Krueger wrote:[color=blue]
> I don't understand why std::for_each(...) returns a my_counter object in
> this case.[/color]

It does in case you want to do a post-mortem on the state of the object, as
he shows.

However, storing state in function objects like this is a hideous abomination
which can cause all kinds of subtle errors [ see Herb Sutter: More Exceptional C++).
I'd recommend steering clear of this. "red_floyd" is either a troll, or knows
just enough to be really dangerous.

Cheers,
--
Donovan Rebbechi
http://pegasus.rutgers.edu/~elflord/

re: using map, list etc. in const methods

Donovan Rebbechi wrote:
[color=blue]
> But why not instead store the node in an automatic structure:
>
> class Handle
> {
> Node* impl;
> public:
> Handle(Node* x):impl(x) {}
> /*
> how you "handle" these is up to you ...
> Handle (const Handle& );
> Handle& operator= (const Handle&);
> */
> ~Handle() { delete impl; }
> Node& operator*() { return *impl; }
> const Node& operator*() const { return *impl; }
> Node* operator->(){ return impl; }
> const Node* operator->() const { return impl; }
> };[/color]

Why not just use a std::auto_ptr?

--
Andrew

re: using map, list etc. in const methods

In article <CijQb.241071$JQ1.135987@pd7tw1no>, Andrew Taylor wrote:[color=blue]
> Donovan Rebbechi wrote:
>[color=green]
>> But why not instead store the node in an automatic structure:
>>
>> class Handle
>> {
>> Node* impl;
>> public:
>> Handle(Node* x):impl(x) {}
>> /*
>> how you "handle" these is up to you ...
>> Handle (const Handle& );
>> Handle& operator= (const Handle&);
>> */
>> ~Handle() { delete impl; }
>> Node& operator*() { return *impl; }
>> const Node& operator*() const { return *impl; }
>> Node* operator->(){ return impl; }
>> const Node* operator->() const { return impl; }
>> };[/color]
>
> Why not just use a std::auto_ptr?[/color]

Because he's storing it in a std::map. auto_ptr doesn't play nice with
standard containers because copy construct and copy-assign modify their
arguments.

For example, this doesn't compile:

std::map<int, std::auto_ptr<int> > m;
std::map<int, std::auto_ptr<int> > n(m);

To "play nice" with containers, you'd a smart pointer that had non-modifying
copy operations (like a reference counted pointer, or a deep-copy pointer)

Cheers,
--
Donovan Rebbechi
http://pegasus.rutgers.edu/~elflord/

re: using map, list etc. in const methods

Donovan Rebbechi wrote:[color=blue]
> In article <buru8p$s2n$02$1@news.t-online.com>, Christof Krueger wrote:
>[color=green]
>>I don't understand why std::for_each(...) returns a my_counter object in
>>this case.[/color]
>
>
> It does in case you want to do a post-mortem on the state of the object, as
> he shows.
>
> However, storing state in function objects like this is a hideous abomination
> which can cause all kinds of subtle errors [ see Herb Sutter: More Exceptional C++).
> I'd recommend steering clear of this. [snip][/color]

Not having said source at hand, might you elaborate (or at least sketch)?

Many thanks,
-ag


--
Artie Gold -- Austin, Texas

re: using map, list etc. in const methods

In article <busn64$ljsoh$1@ID-219787.news.uni-berlin.de>, Artie Gold wrote:[color=blue]
> Donovan Rebbechi wrote:[color=green]
>> In article <buru8p$s2n$02$1@news.t-online.com>, Christof Krueger wrote:
>>[color=darkred]
>>>I don't understand why std::for_each(...) returns a my_counter object in
>>>this case.[/color]
>>
>>
>> It does in case you want to do a post-mortem on the state of the object, as
>> he shows.
>>
>> However, storing state in function objects like this is a hideous abomination
>> which can cause all kinds of subtle errors [ see Herb Sutter: More Exceptional C++).
>> I'd recommend steering clear of this. [snip][/color]
>
> Not having said source at hand, might you elaborate (or at least sketch)?[/color]

Many algorithms copy their predicates. The order of application is often
specified.

I'm going to offer a sketch that's relevant to this example.

for_each "should" behave sensibly, one would hope, from reading the standard:

Effects: Applies f to the result of dereferencing every iterator in the
range [first, last) starting from first and proceeding to last - 1
Returns: f
Complexity: applies f exactly last - first times.

Great! So what does this code do ?

template <typename T>
struct counter
{
int val;
counter () : val(0){}
void operator()(T& x) { ++val; }
};


int main()
{
std::vector<int> v;
v.resize(20);
counter<int> a;
std::cout << std::for_each(v.begin(),v.end(),counter<int>() ).val
<< std::endl;
std::cout << a.val << std::endl; // surely this is the same, right ?
}

The problem is that for_each takes a value parameter, so it operates on a
copy of 'a', not on 'a' itself. This is why for_each returns the predicate.

So there's nothing strictly "incorrect" about "red_floyd's" code, though
count_if is really much simpler. Philosophically, however, it's problematic
because it forces you to depend on side effects, which in turn forces you to
worry about the details of the loop mechanics -- which is precisely the sort
of thing that functional programming is supposed to abstract away.

BTW, in circumstances where some sort of "running total" is required, one can
use the accumulate algorithm (it's quite easy to write a counter function
object that you can use with accumulate in this example) It's a cleaner
solution in that it doesn't burden your function object with state information.

struct counter2
{
template <typename T>
int operator() (int x, const T&) { return x+1; }
};

accumulate(x.begin(),x.end(),0,counter2());

Cheers,
--
Donovan Rebbechi
http://pegasus.rutgers.edu/~elflord/

re: using map, list etc. in const methods

Donovan Rebbechi wrote:[color=blue]
> In article <busn64$ljsoh$1@ID-219787.news.uni-berlin.de>, Artie Gold wrote:
>[color=green]
>>Donovan Rebbechi wrote:
>>[color=darkred]
>>>In article <buru8p$s2n$02$1@news.t-online.com>, Christof Krueger wrote:
>>>
>>>
>>>>I don't understand why std::for_each(...) returns a my_counter object in
>>>>this case.
>>>
>>>
>>>It does in case you want to do a post-mortem on the state of the object, as
>>>he shows.
>>>
>>>However, storing state in function objects like this is a hideous abomination
>>>which can cause all kinds of subtle errors [ see Herb Sutter: More Exceptional C++).
>>>I'd recommend steering clear of this. [snip][/color]
>>
>>Not having said source at hand, might you elaborate (or at least sketch)?[/color]
>
>
> Many algorithms copy their predicates. The order of application is often
> specified.
>
> I'm going to offer a sketch that's relevant to this example.
>
> for_each "should" behave sensibly, one would hope, from reading the standard:
>
> Effects: Applies f to the result of dereferencing every iterator in the
> range [first, last) starting from first and proceeding to last - 1
> Returns: f
> Complexity: applies f exactly last - first times.
>
> Great! So what does this code do ?
>
> template <typename T>
> struct counter
> {
> int val;
> counter () : val(0){}
> void operator()(T& x) { ++val; }
> };
>
>
> int main()
> {
> std::vector<int> v;
> v.resize(20);
> counter<int> a;
> std::cout << std::for_each(v.begin(),v.end(),counter<int>() ).val
> << std::endl;
> std::cout << a.val << std::endl; // surely this is the same, right ?
> }
>
> The problem is that for_each takes a value parameter, so it operates on a
> copy of 'a', not on 'a' itself. This is why for_each returns the predicate.
>
> So there's nothing strictly "incorrect" about "red_floyd's" code, though
> count_if is really much simpler. Philosophically, however, it's problematic
> because it forces you to depend on side effects, which in turn forces you to
> worry about the details of the loop mechanics -- which is precisely the sort
> of thing that functional programming is supposed to abstract away.
>
> BTW, in circumstances where some sort of "running total" is required, one can
> use the accumulate algorithm (it's quite easy to write a counter function
> object that you can use with accumulate in this example) It's a cleaner
> solution in that it doesn't burden your function object with state information.
>
> struct counter2
> {
> template <typename T>
> int operator() (int x, const T&) { return x+1; }
> };
>
> accumulate(x.begin(),x.end(),0,counter2());
>[/color]
Tremendous!

--ag

--
Artie Gold -- Austin, Texas