using map, list etc. in const methods

[Christof Krueger]

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!

 

[Donovan Rebbechi]

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?

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

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 (?).

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 ?

Do you know a good webpage or tutorial about
this topic? I would like to learn how to do it the right way.

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.

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.

Two good books about the C++ standard library:

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

Cheers,

 

[red floyd]

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!

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:air<string,CNode*>,
void >
{
private:
mutable int count;
public:
my_counter() : count(0) { }
void operator()(const std:air<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();
}

 

[Rob Williscroft]

Christof Krueger wrote in
[snip]

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?

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.

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 (?).

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

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.

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

Rob.

 

[Christof Krueger]

map<string,CNode*>::const_iterator

thanks, that makes sense

btw, you can do this using

count_if(themap.begin(),themap.end(),isWhite); // isWhite returns true if the piece is white

very handy. I'll use it.

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 ?

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!

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.




Two good books about the C++ standard library:

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

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.

 

[Christof Krueger]

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

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?

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

e.g.:

class my_counter : public std::unary_function<
std:air<string,CNode*>,
void >
{
private:
mutable int count;
public:
my_counter() : count(0) { }
void operator()(const std:air<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();
}

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

 

[Donovan Rebbechi]

Donovan Rebbechi wrote:
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!

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

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,

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]

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. "red_floyd" is either a troll, or knows
just enough to be really dangerous.

Cheers,

 

[Andrew Taylor]

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

Why not just use a std::auto_ptr?

 

[Donovan Rebbechi]

Why not just use a std::auto_ptr?

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,

 

[Artie Gold]

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]

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

Many thanks,
-ag

 

[Donovan Rebbechi]

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]

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

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,

 

[Artie Gold]

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]

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

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

Tremendous!

--ag