Issue with key of std::map

Question

Consider the following code. A tuple consisting of integer and vector of integer is defined as the key of a map. However, I was surprised that the compiler does not throw any error when inserting or looking for a tuple consisting of integer and integer as the key. How can this be, since the second element of the tuple should be of the type vector of integer?

std::map <boost::tuple<int, vector<int > >, int> test;
std::map <boost::tuple<int, vector<int > >, int>::iterator test_it;

vector <int> t;
t.push_back(4);

test.insert(make_pair(boost::make_tuple(3, t), 4));

test.insert(make_pair(boost::make_tuple(3, 6), 4));

test_it = test.find(boost::make_tuple(3, 7)); 
if(test_it != test.end()) 
throw " test is passed";  

Answer 1

Seems like a bug in Boost and many C++ standard library implementations. The problem is shared by both pair and tuple. The simplest code to demonstrate it is:

#include <vector>
#include <utility>
using namespace std;
int main() {
    //compiles
    pair<int,vector<int>> bug1( pair<int,int>(5,6) );

    //compiles
    pair<int,vector<int>> bug2;
    bug2 = pair<int,int>(5,6);
}

Clang 4.0 with libc++ and the other one accepts this, Comeau Online accepts it too. GCC 4.7.1 gives an error.

It must not compile, according to:

20.3.2/12

template<class U, class V> pair(const pair<U, V>& p);

Remark: This constructor shall not participate in overload resolution unless const U& is implicitly convertible to first_type and const V& is implicitly convertible to second_type.

20.3.2/23

template<class U, class V> pair& operator=(const pair<U, V>& p);

Requires: is_assignable<first_type&, const U&>::value is true and is_assignable<second_type&, const V&>::value is true.

Answer 2

The issue is the implicit conversion. It's not from int to std::vector<int>; that wouldn't work, because the constructor involved there is declared explicit, and so cannot be used for implicit conversions. The implicit conversion is from std::pair<int, int> to std::pair<int, std::vector<int> >. This uses the constructor derived from the template: template <typename U1, typename U2> std::pair( std::pair<U1, U2> const& ), which is not implicit. And the definition of this constructor is:

template <typename T1, typename T2>
template <typename U1, typename U2>
std::pair<T1, T2>::std::pair( std::pair<U1, U2> const& other )
    : first( other.first )
    , second( other.second )
{
}

(This is not exactly how the standard specifies it. But the specification in C++03 doesn't allow much else. In C++11, there's a lot of extra baggage so that things can be move constructed when possible, but I think the final effect comes out the the same.)

Note that in this constructor, there is an explicit invocation of the constructor, rather than an implicit conversion. So for the implicit conversion of pair to work, it is sufficient that the two types be explicitly convertible.

Personally, I doubt that this was the original intent. I suspect, in fact, that most of the language surrounding std::pair was frozen before explicit was added to the language, so there wasn't an issue. Later, no one thought to revisit the issue. And in C++11, revisiting it would have broken backwards compatibility. So you get some unexpected conversions.

Note that this isn't the only situation where forwarding causes an explicit conversion to become implicit. Consider:

std::vector<std::vector<int> > v2D( 5, 10 );

Obviously, 10 is not a std::vector<int> (which is what the second argument should be). But... in C++03, this matches the constructor template:

template<typename ForwardIterator, typename ForwardIterator>
std::vector( ForwardIterator begin, ForwardIterator end );

And the standard has some special language for this:

— the constructor

template <class InputIterator>
X(InputIterator f, InputIterator l, const Allocator& a = Allocator())

shall have the same effect as:

X(static_cast<typename X::size_type>(f),
static_cast<typename X::value_type>(l), a)

if InputIterator is an integral type.

And the implicit conversion has become explicit.

(Note that without this special language,

std::vector<int> v(10, 42);

fails to compile: the intantiation of the template constructor, above, is an exact match, which is better than std::vector<int>( size_t, int ). The committee felt that requiring an explicit cast of the first integer, above, to size_t was perhaps asking too much of the users.)

C++11 has changed the wording here significantly, and:

std::vector<int, std::vector<int>> v2D( 10, 42 );

is no longer legal.

No such changes, at laest that I can see, were applied to the constructor of std::pair.