const element type in standard library containers

[subramanian100in]

Program 1:
---------------
#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;

int main()
{
vector<const int> c2;

return EXIT_SUCCESS;
}

This program gives compilation error for the vector instantiation.

Now consider the following program 2:
-------------------------------------------------------
#include <cstdlib>
#include <iostream>
#include <set>
#include <utility>

using namespace std;

int main()
{
typedef pair<const int, const int> p_type;

multiset<p_type> c1;

c1.insert(make_pair(0, 2));

return EXIT_SUCCESS;
}

But this second program also has 'const int' as part of the element
type; but it compiles fine.

Why doesn't the first program compile and why does the second program
compile fine ?

Kindly clarify.

Thanks
V.Subramanian

 

[subramanian100in]

Consider the program z.cpp:

#include <cstdlib>
#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <map>
#include <utility>

using namespace std;

int main()
{
typedef pair<const int, const int> p_type;

vector<p_type> v;
//v.insert(v.begin(), make_pair(0, 2));

list<p_type> l;
l.insert(l.begin(), make_pair(0, 2));

deque<p_type> d;
//d.insert(d.begin(), make_pair(0, 2));

map<const int, const int> s;
s.insert(make_pair(0, 2));

return EXIT_SUCCESS;
}

I am using
g++ -std=c++98 -pedantic -Wall -Wextra z.cpp

Here if I remove the two comments(one each on vector insert and deque
insert), I get compilation error. But for list, there is no
compilation error for a similar insert. Why does compilation error
occur, only for vector and deque and not for list and map ?

Kindly clarify.

Thanks
V.Subramanian

 

[Bo Persson]

Consider the program z.cpp:

#include <cstdlib>
#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <map>
#include <utility>

using namespace std;

int main()
{
typedef pair<const int, const int> p_type;

vector<p_type> v;
//v.insert(v.begin(), make_pair(0, 2));

list<p_type> l;
l.insert(l.begin(), make_pair(0, 2));

deque<p_type> d;
//d.insert(d.begin(), make_pair(0, 2));

map<const int, const int> s;
s.insert(make_pair(0, 2));

return EXIT_SUCCESS;
}

I am using
g++ -std=c++98 -pedantic -Wall -Wextra z.cpp

Here if I remove the two comments(one each on vector insert and
deque insert), I get compilation error. But for list, there is no
compilation error for a similar insert. Why does compilation error
occur, only for vector and deque and not for list and map ?

Standard containers require that the value type is assignable. When
the pair members are const, it is not.

With list and map, you just get away with this violation when the
assignment operator isn't used by the implementation.


Bo Persson

 

[subramanian100in]

Standard containers require that the value type is assignable. When
the pair members are const, it is not.

With list and map, you just get away with this violation when the
assignment operator isn't used by the implementation.

Bo Persson

Does this mean that the CopyConstructible and Assignable requirements
are not mandatory for list, map ? Rather, are they implementation-
dependent ?

Kindly clarify.

Thanks
V.Subramanian

 

[Ian Collins]

Does this mean that the CopyConstructible and Assignable requirements
are not mandatory for list, map ? Rather, are they implementation-
dependent ?

No, you get away with it because the insert operation isn't doing an
assignment.

 

[James Kanze]

No, you get away with it because the insert operation isn't
doing an assignment.

You don't get away with anything. Violating the requirements is
undefined behavior. An implementation is not required to
diagnose it, but it isn't required to document what happens if
there is no diagnostic. The code is wrong, and should be
corrected, even if your tests today don't show any problems.

 

[Ian Collins]

You don't get away with anything. Violating the requirements is
undefined behavior. An implementation is not required to
diagnose it, but it isn't required to document what happens if
there is no diagnostic. The code is wrong, and should be
corrected, even if your tests today don't show any problems.

I think that's what I said.....

 

[James Kanze]

I think that's what I said.....

You said that even if the tests show that the code works...

Seriously, I think that's what you meant. But the way you
expressed it could easily be misunderstood by someone whose
native language wasn't English; it depended on a certain reading
between the lines. And I've had enough experience with
non-native English speakers to know that it helps to put the
dots on the i's (which I'm not sure that non-native speakers
will understand either).

 

[Ian Collins]

You said that even if the tests show that the code works...

Ah but I would have added a test for insert of an immutable object!

 

[James Kanze]

Ah but I would have added a test for insert of an immutable
object!

Which might pass, even though the code is wrong. Undefined
behavior means that tests are meaningless, and IMHO, the problem
*isn't* with the concept of testing.

The "meaningless" is obviously hyperbole. But the presence of
undefined behavior in C++ does make reliable software
significantly more difficult, since it reduces the significence
of tests: you can never be sure that the test didn't pass just
because some undefined behavior happened to work this time.

 

[Ian Collins]

Which might pass, even though the code is wrong. Undefined
behavior means that tests are meaningless, and IMHO, the problem
*isn't* with the concept of testing.

I meant a test in the standard library container test suite.

The "meaningless" is obviously hyperbole. But the presence of
undefined behavior in C++ does make reliable software
significantly more difficult, since it reduces the significence
of tests: you can never be sure that the test didn't pass just
because some undefined behavior happened to work this time.

One of the purposes of tests is to remove undefined behaviour. But the
whole thing goes pear shaped when you rely on a library which has its
own undefined behaviour.

 

[James Kanze]

James Kanze wrote:

[...]

One of the purposes of tests is to remove undefined behaviour.
But the whole thing goes pear shaped when you rely on a
library which has its own undefined behaviour.

The problem is that formally speaking, you can't test for
undefined behavior, since whatever happens is undefined---it
could work in all your tests and still fail. Practically, of
course, regardless of what the standard says, the behavior is
always never totally undefined; the behavior of something like
i++ + i++ may be undefined, but once the compiler has generated
code for the statement, that code will always do the same thing.
It's still a situation which leaves much to be desired; ideally:
-- we'd like any test using such code to fail, or
-- failing that, we'd like to have the guarantee that if such
code passed our tests, it would pass then the next time we
compile as well (possibly with a different level of
optimization, or a more recent version of the compiler).
The first is, I think, practically unattainable, but reducing a
lot of the unnecessary undefined behavior in C++ would certainly
go a long way to reaching the second.

 

[Ian Collins]

James Kanze wrote:
[...]

The "meaningless" is obviously hyperbole. But the presence of
undefined behavior in C++ does make reliable software
significantly more difficult, since it reduces the significence
of tests: you can never be sure that the test didn't pass just
because some undefined behavior happened to work this time.

One of the purposes of tests is to remove undefined behaviour.
But the whole thing goes pear shaped when you rely on a
library which has its own undefined behaviour.

The problem is that formally speaking, you can't test for
undefined behavior, since whatever happens is undefined---it
could work in all your tests and still fail.

That goes without saying, but don't forget where we started, insertion
of an immutable object into a standard container. It would be possible
to assert this in the library code.

 

[James Kanze]

James Kanze wrote:

[...]

The "meaningless" is obviously hyperbole. But the
presence of undefined behavior in C++ does make reliable
software significantly more difficult, since it reduces
the significence of tests: you can never be sure that the
test didn't pass just because some undefined behavior
happened to work this time.
One of the purposes of tests is to remove undefined
behaviour. But the whole thing goes pear shaped when you
rely on a library which has its own undefined behaviour.

The problem is that formally speaking, you can't test for
undefined behavior, since whatever happens is undefined---it
could work in all your tests and still fail.

That goes without saying, but don't forget where we started,
insertion of an immutable object into a standard container.
It would be possible to assert this in the library code.

It would be possible for a library implementation to define most
or all of the undefined behavior, and check for it. (The better
ones do, or at least attempt to.) It would also be possible
(and desirable) that the a library which did so test it. But if
for whatever reasons (usually performance), the library decides
to leave it as "undefined behavior", how can the library
implementors test that it really is undefined? Or for that
matter, does such a test make sense? Isn't specifying something
as "undefined behavior" just another way of saying "we don't
have to test it"?

(But I think we largely agree here. Testing is important, and
anything that makes testing more difficult and less reliable is
a bad thing.)

 

[Ian Collins]

James Kanze wrote:
[...]
The "meaningless" is obviously hyperbole. But the
presence of undefined behavior in C++ does make reliable
software significantly more difficult, since it reduces
the significence of tests: you can never be sure that the
test didn't pass just because some undefined behavior
happened to work this time.
One of the purposes of tests is to remove undefined
behaviour. But the whole thing goes pear shaped when you
rely on a library which has its own undefined behaviour.
The problem is that formally speaking, you can't test for
undefined behavior, since whatever happens is undefined---it
could work in all your tests and still fail.

That goes without saying, but don't forget where we started,
insertion of an immutable object into a standard container.
It would be possible to assert this in the library code.

It would be possible for a library implementation to define most
or all of the undefined behavior, and check for it.

That depends if the library has undefined behaviour. If the type of
objects stored in a container is required to be copy constructable and
assignable, that can be tested. The test might have to be done at the
build level, a verification that compilation fails if this requirement
is violated.

I was thinking along the lines of:

#include <utility>
#include <list>

template < typename T >
struct CheckTypeIsAssignable : std::list<T>
{
CheckTypeIsAssignable()
{
T t;
t = T();
}
};

int main()
{
CheckTypeIsAssignable<std:air<const int, const int> > c1;

return 0;
}

int main()
{
CheckTypeIsAssignable<std:air<const int, const int> > c1;

return 0;
}

(But I think we largely agree here. Testing is important, and
anything that makes testing more difficult and less reliable is
a bad thing.)

Can't argue with that!

 

[James Kanze]

James Kanze wrote:
James Kanze wrote:
[...]
The "meaningless" is obviously hyperbole. But the
presence of undefined behavior in C++ does make reliable
software significantly more difficult, since it reduces
the significence of tests: you can never be sure that the
test didn't pass just because some undefined behavior
happened to work this time.
One of the purposes of tests is to remove undefined
behaviour. But the whole thing goes pear shaped when you
rely on a library which has its own undefined behaviour.
The problem is that formally speaking, you can't test for
undefined behavior, since whatever happens is undefined---it
could work in all your tests and still fail.
That goes without saying, but don't forget where we started,
insertion of an immutable object into a standard container.
It would be possible to assert this in the library code.

It would be possible for a library implementation to define
most or all of the undefined behavior, and check for it.

That depends if the library has undefined behaviour. If the
type of objects stored in a container is required to be copy
constructable and assignable, that can be tested.

I'm not sure we're on the same wave length. There are two
issues, and I'm not really sure which one we're talking about.

The first: in specific cases (library or not), C++ has undefined
behavior. You cannot reliably test whether your code falls into
one of those cases or not unless the implementation has defined
the behavior in some specific way you can test for. Two good
examples: instantiating an std::list over a type which doesn't
support assignment (which will never in fact fail with some
implementations of std::list), and something like i++ + ++i (in
which case I know of no implementation where it will "fail", but
it won't always give the same results). In my opinion, such
undefined behavior seriously reduces the confidence we can have
in our tests, and C++ really should try to close as many of
these holes as possible.

The second is the case of library implementors themselves. The
standard says that in certain cases (e.g. std::string(NULL)),
the library has undefined behavior. If, as an implementor, you
define this behavior (e.g. by guaranteeing an assertion
failure), you can and should test for it. But if you decide not
to do so, what does it even mean to test it? Does it have any
meaning to test to ensure that you haven't accidentally defined
any behavior, and if so, how do you test it? Again, in general,
my opinion is that you shouldn't define such cases; that as a
library implementor, you should define the behavior regardless
of what the client code does. But performance considerations
can intervene; checking for null in std::string(char const*)
isn't that expensive, but tracking iterators to verify their
validity can definitely have a measurable impact on performance.

The test might have to be done at the build level, a
verification that compilation fails if this requirement is
violated.

Concept checking, in sum. Some standard library implementations
(g++, and maybe also Dinkumware) implement concept checking
already. The next version of the standard will introduce
language support for this, and require the library to use it (I
think). A lot less undefined behavior, and a major step
forward.

I was thinking along the lines of:

#include <utility>
#include <list>

template < typename T >
struct CheckTypeIsAssignable : std::list<T>
{
CheckTypeIsAssignable()
{
T t;
t = T();
}
};

int main()
{
CheckTypeIsAssignable<std:air<const int, const int> > c1;

return 0;
}

int main()
{
CheckTypeIsAssignable<std:air<const int, const int> > c1;

return 0;
}

I'm not quite sure what you're trying to show in this example.
It doesn't test the library in anyway (at least that I can see),
and it doesn't test your code (i.e. verifying that you haven't
instantiated std::list over a type which isn't assignable).
Such concept checks have to be part of the library to be useful.
(Thus, g++ does do something like this when you instantiate an

Can't argue with that!

So you'd agree with me that C++ should eliminate undefined
behavior as far as possible.

 

[Ian Collins]

Concept checking, in sum. Some standard library implementations
(g++, and maybe also Dinkumware) implement concept checking
already. The next version of the standard will introduce
language support for this, and require the library to use it (I
think). A lot less undefined behavior, and a major step
forward.

Yes and long overdue!

I'm not quite sure what you're trying to show in this example.
It doesn't test the library in anyway (at least that I can see),
and it doesn't test your code (i.e. verifying that you haven't
instantiated std::list over a type which isn't assignable).

The idea was for a test case that should fail to compile. As you say,
the over simplified example I posted doesn't do a great deal. I
originally had a private member,

void checkTypeIsAssignable()
{
T t;
t = T();
};

to be called from the container constructors thus:

if(0) checkTypeIsAssignable();

The call should be optimised away by an optimiser while still causing a
compilation error for immutable types.

So you'd agree with me that C++ should eliminate undefined
behavior as far as possible.

Yes.