Skip to main content
gamedev.net
🔒 Locked

Problems with std::set

Started by LonelyStar Jun 24, 2007 at 5:17 PM 6 replies 1k views
Original Post
LonelyStar
LonelyStar
Hello, I have my problems with standard set. I have a set with a class as parameter over wich I want to iterate like this: 

class A
{
  void func();
};

int main()
{
  std::set set;
  ...
  std::set::iterator i;
  for(i=set.begin();i!=set.end();++i)
  {
    (*i).func(); //Offending line
  }
  ...
}
On the line marked with "Offending line" I get the following compile error: "passing const A as 'this' argument of 'void A::func()' discards qualifiers" The problem is solved if I declare "func" as const: 

class A
{
  void func() const;
}
...
But I want to make changes to A from within "func" :( What can I do? thanks! Nathan
rip-off
rip-off
As noted here (approx 3rd paragraph), std::set and other associative containers cannot have mutable iterators. Think about what would happen if you had a set of std::string objects and you modified the strings during iteration, how would the std::set know to re-order them?
blog | twitter
taby
taby
As mentioned by rip-off, order is not maintained. It is possible however in MSVC++ 2005 Express Edition:

#include <set>using std::set;#include <iostream>using std::cout;using std::endl;#include <cstdlib>#include <ctime>class A{public:	A(const long unsigned int src_x)	{		x = src_x;	}	void func(void)	{		x += rand();	}	const bool operator<(const A &rhs) const	{		if(x < rhs.x)			return true;		return false;	}	long unsigned int x;};int main(void){//	srand(time(0));	set s;	s.insert(A(2));	s.insert(A(1));	s.insert(A(4));	// Print out original value, then alter it.	for(set::iterator i = s.begin(); i != s.end(); i++)	{		cout << i->x << endl;		i->func();	}	// Print out new value.	for(set::iterator i = s.begin(); i != s.end(); i++)	{		cout << i->x << endl;	}	return 0;}
the_edd
the_edd
taby: that code has exactly the problem that the LonelyStar is trying to avoid. The elements of a set are effectively const and you're trying to call a non-const member function on one of its elements.

If you want to modify an element of a set you have a few options:

1. Copy the element out, modify it and re-insert it (you may need to remove the original from the set too if the revised element isn't equivalent).
2. Make the appropriate members mutable (a bit dangerous).
3. Make the appropriate internal object that needs modifying a (smart) pointer (equally dangerous). This works because you can modify what the pointer refers to without changing the value of the pointer.
4. Extract the portion of your element type that decides the ordering and use an std::map<> instead.

2 and 3 are dangerous because they might affect the element's position in the ordering defined by the less<> predicate for your type.

Edd
LonelyStar
LonelyStar
Hello,

Well, since the members I want to change do not effect the order of the elements, I will just make them mutable.
Thanks for your help!
Nathan
iMalc
iMalc
Quote:
Original post by LonelyStar
Hello,

Well, since the members I want to change do not effect the order of the elements, I will just make them mutable.
Thanks for your help!
Nathan
Yeah that's fine then, though it does suggest a map may be more appropriate.

taby: What on earth is with that "const long unsigned int"? Are you going for a most-unnecessary-keywords-in-a-row award?
Zahlman
Zahlman
Quote:
Original post by iMalc
Yeah that's fine then, though it does suggest a map may be more appropriate.


To go into more detail: Separate the object into the const, order-determining part (which will become a 'key') and the mutable, non-order-determining part (the 'value'). Create a std::map mapping keys to values. Typedef std::pair (the type which is stored in nodes of the map), and rework the old class interface into a set of free functions that operate on such pairs (or perhaps just on keys or just on values). You can, for example, replace the old lookup (if you need to be really strict) by a lookup on key, followed by a check that the values match.
taby
taby
"As mentioned by rip-off, order is not maintained". Which is useful if you do not require order to be maintained after transformation. If this is not useful, the OP LonelyStar could probably figure out on their own that they would just have to iterate over the unordered set and manually insert into a new set to regain order. If this method does not compile due to non-standard behaviour, then a nimble vector can be used to hold the data during/after the transformation pass (std::sort).

Either way, it turned out that sort order wasn't even an issue to begin with. The point being that you should have considered that scenario. Instead, everyone goes all bonkers over std::map.

It is a style called "const correctness", and it helps one not to alter what should be constant. Less mistakes are made due to lack of concentration. It is also a sign to the reader of the source that the author knows the algorithm well.

OP LonelyStar is probably not an automaton incapable of deciding for themselves. If you want to be critical, be nice (your behaviour affects everyone).

[Edited by - taby on June 25, 2007 5:46:25 AM]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.