Failure to compile with std::set, compiles OK with std::vector, why?

  • Thread starter Joost Kraaijeveld
  • Start date
J

Joost Kraaijeveld

Hi,

The code below does not compile if I use the std::set, but it compiles
OK if I use the std::vector. Can anyone tell me why this is?

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <functional>

struct Integer
{
Integer(int anInt) : integer(anInt)
{}
bool operator<( const Integer& anInteger) const
{ return integer < anInteger.integer;}
void print()
{std::cout << integer << std::endl;}
int integer;
};

int main(int argc, char* argv[])
{
// std::vector<Integer> collection(5,2);
std::set<Integer> collection(5,2);

std::for_each(collection.begin(),
collection.end(),
std::mem_fun_ref(&Integer::print));
return 0;
}

TIA

Joost
 
J

jason.cipriani

The code below does not compile if I use the std::set, but it compiles
OK if I use the std::vector. Can anyone tell me why this is?

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <functional>

struct Integer
{
  Integer(int anInt) : integer(anInt)
  {}
  bool operator<( const Integer& anInteger) const
  { return integer < anInteger.integer;}
  void print()
  {std::cout << integer << std::endl;}
  int integer;

};

int main(int argc, char* argv[])
{
//  std::vector<Integer> collection(5,2);
  std::set<Integer> collection(5,2);


There is no set<Integer> constructor that takes two integers as
parameters. See:

http://www.sgi.com/tech/stl/set.html

For more information.
  std::for_each(collection.begin(),
                collection.end(),
                std::mem_fun_ref(&Integer::print));

Unrelated, consider declaring Integer::print as const up in the class
declaration, if Integer::print() modifies the Integer, it can break
order invariants in the set. I may be misunderstanding something, but
it seems like some information about const is lost in mem_fun_ref /
for_each somewhere, I'd expect a warning to be generated.
  return 0;

}


Jason
 
J

Joost Kraaijeveld

Hi Jason,

Thanks for the answer.

There is no set<Integer> constructor that takes two integers as
parameters. See:

http://www.sgi.com/tech/stl/set.html
You are right. The code should have been:

int main(int argc, char* argv[])
{
// std::vector<Integer> collection(5,2);
std::set<Integer> collection;
collection.insert(0);

std::for_each(collection.begin(),
collection.end(),
std::mem_fun_ref(&Integer::print));
return 0;
}


But that is not the error I am referring to. I am referring to this error:

c++ -O0 -g3 -Wall -c -fmessage-length=0 -MMD -MP -MF"Main.d" -MT"Main.d"
-o"Main.o" "../Main.cpp"
/usr/include/c++/4.3/bits/stl_algo.h: In function ‘_Funct
std::for_each(_IIter, _IIter, _Funct) [with _IIter =
std::_Rb_tree_const_iterator<Integer>, _Funct = std::mem_fun_ref_t<void,
Integer>]’:
.../Main.cpp:27: instantiated from here
/usr/include/c++/4.3/bits/stl_algo.h:3791: error: no match for call to
‘(std::mem_fun_ref_t<void, Integer>) (const Integer&)’
/usr/include/c++/4.3/bits/stl_function.h:560: note: candidates are: _Ret
Unrelated, consider declaring Integer::print as const up in the class
declaration, if Integer::print() modifies the Integer, it can break
order invariants in the set. I may be misunderstanding something, but
it seems like some information about const is lost in mem_fun_ref /
for_each somewhere, I'd expect a warning to be generated.
Actually, an error is issued (see above). And indeed, changing the print
function to "void print() const" makes it compile both with the vector
and the set.

I still do not understand why there is a difference between the vector
and the set version. As far as I know, std::for_each allows for mutating
(non-const) operations and there is nothing in either
collection.begin()/end() or std::mem_fun_ref that suggests const-ness
somewhere.

Joost
 
A

alfps

* Joost Kraaijeveld:
I still do not understand why there is a difference between the vector
and the set version. As far as I know, std::for_each allows for mutating
(non-const) operations and there is nothing in either
collection.begin()/end() or std::mem_fun_ref that suggests const-ness
somewhere.

Consider the definition of a (simple) set: any possible element X is
either in the set, or not.

If you have a set S that contains X, then for efficiency this must be
represented by information derived from X.

And there is no way to cause that information (e.g. placement in a
tree or list structure) to be automatically updated when you change
the value of X.

Hence for a std::set you can't (at least not without sneaking in
through some back door).

Hence, you can't (without forcing your way) call a non-const member
function on X when X is provided by the set.


Cheers & hth.,

- Alf
 
J

jason.cipriani

Actually, an error is issued (see above). And indeed, changing the print
function to "void print() const" makes it compile both with the vector
and the set.

Ah, so I guess it wasn't unrelated after all. The constructor
parameters were a bit of a red herring. The reason I thought it was
unrelated is I was using MSVC, which seems to incorrectly compile the
code without complaining at all (see below). I turned to the C++03
standard to see what it had to say about it:
As far as I know, std::for_each allows for mutating
(non-const) operations and there is nothing in either
collection.begin()/end() or std::mem_fun_ref that suggests const-ness
somewhere.

Well, actually, for_each never allows for non-const operations, even
for vectors. C++03 defines for_each in section [25.1.1], under the
heading "non-modifying sequence operations". While the standard,
AFAICT, does not seem to precisely define what that means, its meaning
seems implied and it is separate from the "mutating sequence
operations" category.

Additionally, http://www.sgi.com/tech/stl/for_each.html (also under
the category "non-mutating algorithms" in the TOC) states:

"UnaryFunction does not apply any non-constant operation through its
argument."

A compiler should actually reject your code on the basis of passing a
non-const function to for_each (I think; although it may be a QoI
issue as I can't find a requirement for diagnostics in the standard
anywhere, somebody point me to the right section me if I'm wrong). It
is rejected by both Comeau and GCC (at least 3.4.5). Do you happen to
be using Visual Studio? MSVC seems to incorrectly accept the code.

If you want to apply non-const operations to the items in a container
you can use std::transform (which also can not be applied to an
std::set):

http://www.sgi.com/tech/stl/transform.html


Example (the only compiler I've found that accepts this is MSVC):

#include <algorithm>
#include <iostream>
#include <iterator>
#include <set>
using namespace std;

void negative (int &n) {
n = -n;
}

int main () {

set<int> s;

s.insert(2);
s.insert(4);
s.insert(6);
for_each(s.begin(), s.end(), negative);
s.insert(-4);

copy(s.begin(), s.end(), ostream_iterator<int>(cout, "\n"));
cin.get();

}


With MSVC 2008's implementation, the output of this program is:

-2
-4
-6
-4

The std::set has been broken, and both the ordering and uniqueness
invariants have been violated. Again, though, it's not a valid program
and is rejected by at least 2 other compilers.

Jason
 
T

Triple-DES

As far as I know, std::for_each allows for mutating
(non-const) operations and there is nothing in either
collection.begin()/end() or std::mem_fun_ref that suggests const-ness
somewhere.

Well, actually, for_each never allows for non-const operations, even
for vectors. C++03 defines for_each in section [25.1.1], under the
heading "non-modifying sequence operations". While the standard,
AFAICT, does not seem to precisely define what that means, its meaning
seems implied and it is separate from the "mutating sequence
operations" category.

It might be misleading, but the fact that for_each is a non-modifying
sequence operation does not imply that the function object f may not
modify its argument. Note also that for other operations like find,
there is an explicit requirement that the function object pred does
not modify the argument.
Additionally,http://www.sgi.com/tech/stl/for_each.html(also under
the category "non-mutating algorithms" in the TOC) states:

  "UnaryFunction does not apply any non-constant operation through its
argument."

This may be true for the SGi STL for_each (and possibly the original
STL for_each), but not for the C++ standard library for_each.
A compiler should actually reject your code on the basis of passing a
non-const function to for_each (I think; although it may be a QoI
issue as I can't find a requirement for diagnostics in the standard
anywhere, somebody point me to the right section me if I'm wrong). It
is rejected by both Comeau and GCC (at least 3.4.5). Do you happen to
be using Visual Studio? MSVC seems to incorrectly accept the code.

So long as the iterators are mutable (for containers this implies non-
const_iterators), I don't see a problem using for_each like this with
the sequence containers.
 
J

jason.cipriani

Well, actually, for_each never allows for non-const operations, even
for vectors. C++03 defines for_each in section [25.1.1], under the
heading "non-modifying sequence operations". While the standard,
AFAICT, does not seem to precisely define what that means, its meaning
seems implied and it is separate from the "mutating sequence
operations" category.

It might be misleading, but the fact that for_each is a non-modifying
sequence operation does not imply that the function object f may not
modify its argument. Note also that for other operations like find,
there is an explicit requirement that the function object pred does
not modify the argument.

What does being a "non-modifying sequence operation" imply if not
that? In any case, for_each can not modify it's argument if the
container is, say, a std::set. It breaks the set. If it could, then
the for_each implementation would have to remove and reinsert every
element it iterated over (and could very well reduce the size of the
set as a consequence of this).
Additionally,http://www.sgi.com/tech/stl/for_each.html(alsounder
the category "non-mutating algorithms" in the TOC) states:
  "UnaryFunction does not apply any non-constant operation through its
argument."

This may be true for the SGi STL for_each (and possibly the original
STL for_each), but not for the C++ standard library for_each.
[snip]
So long as the iterators are mutable (for containers this implies non-
const_iterators), I don't see a problem using for_each like this with
the sequence containers.

Fair enough; I'll buy that. Comeau does reject the following code:

#include <algorithm>
#include <set>

void modify (int &n) {
++ n;
}

int main () {
std::set<int> v;
std::for_each(v.begin(), v.end(), modify);
}

With the error:

"stl_algo.h", line 155: error: qualifiers dropped in binding
reference of
type "int &" to initializer of type "const int"

However, it does accept the code if a vector is used. That agrees with
what you say.

MSVC incorrectly allows for_each to be applied to a set, and that's
wrong; that much I'm certain of. Do you think, then, it's more
accurate to say that the *real* problem with MSVC is that it treats a
set's iterators as non-const when they should be const?

Comeau rejects this:

#include <set>
int main () {
std::set<int> v;
(*(v.begin())) ++;
}

Stating that the "expression must be a modifiable lvalue". However,
MSVC accepts it, which seems to lend evidence to that as the root
cause of MSVC's issue.


Jason
 
T

Triple-DES

What does being a "non-modifying sequence operation" imply if not
that? In any case, for_each can not modify it's argument if the
container is, say, a std::set. It breaks the set. If it could, then
the for_each implementation would have to remove and reinsert every
element it iterated over (and could very well reduce the size of the
set as a consequence of this).

That's harder to say since it is never defined. Perhaps that the
operation(algorithm) in itself inherently does not modify the
sequence, but a user-supplied function may modify the sequence. Except
that a predicate can't call a non-const function on an element.

The way I read it even a predicate may modify the sequence so long as
it respects the previous requirement (by e.g calling clear() on the
container). Of course that would still produce undefined behaviour
because of iterator invalidation.
MSVC incorrectly allows for_each to be applied to a set, and that's
wrong; that much I'm certain of. Do you think, then, it's more
accurate to say that the *real* problem with MSVC is that it treats a
set's iterators as non-const when they should be const?

Comeau rejects this:

#include <set>
int main () {
  std::set<int> v;
  (*(v.begin())) ++;

}

Stating that the "expression must be a modifiable lvalue". However,
MSVC accepts it, which seems to lend evidence to that as the root
cause of MSVC's issue.

In a way. Per the C++98 standard, and even the '03 standard,
set<T>::iterator is required to point to T, not const T. The latest
draft standard clarifies this, per http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-defects.html#103
which is in fact a very old defect.

Still, MS' implementation is conforming to C++03. On the other hand,
implementing the change would break code that modifies an object
without changing its relative ordering in the set.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top