boost::mpl::map fails boost::mpl::equal?

Question

Boost MPL documentation states that boost::map::equal

"Returns a true-valued Integral Constant if the two sequences Seq1 and Seq2 are identical when compared _element_ by _element_ .

but it seems that the associative sequence map is not checked for equality element _wise_:

The following demo will show this: Map2 should equal Map3, which both increment the 'int_<1>' value_type at 'key'. Look at the typedef defining Map3. Size and the only element is dumped n the demo:

#include<iostream>
#include<boost/mpl/map.hpp>
#include<boost/mpl/at.hpp>
#include<boost/mpl/insert.hpp>
#include<boost/mpl/erase_key.hpp>
#include<boost/mpl/pair.hpp>
#include<boost/mpl/int.hpp>
#include<boost/mpl/plus.hpp>
#include<boost/mpl/equal.hpp>
#include<boost/mpl/size.hpp>
#include<boost/mpl/front.hpp>

namespace mpl = boost::mpl;
using mpl::int_;

using std::cout;
using std::endl;
using std::is_same;

int main(int argc, char *argv[])
{

    typedef int key;

    typedef typename mpl::map<mpl::pair<key, int_<1>>> Map;
    typedef typename mpl::map<mpl::pair<key, int_<2>>> Map2;

    typedef typename mpl::insert<
    typename mpl::erase_key<Map,
                            key>::type, 
        mpl::pair<key, 
                  typename mpl::plus<int_<1>, 
                                     typename mpl::at<Map, key>::type>::type
        >::type
    >::type Map3;

    cout << "equal? " << mpl::equal<Map2,Map3>::type::value << endl;
    cout << "size? " << mpl::size<Map3>::value << endl;
    cout << "key type at front? " << typeid(mpl::front<Map3>::type::first).name() << endl;
    cout << "value type at front? " << mpl::front<Map3>::type::second::value << endl;

    cout << "expected size? " << mpl::size<Map2>::value << endl;
    cout << "expected key type at front? " << typeid(mpl::front<Map2>::type::first).name() << endl;
    cout << "expected value type at front? " << mpl::front<Map2>::type::second::value << endl;

    return 0;
}

I am using gcc 4.8.1 with boost 1.51

Answer 1

The reason it does not work as expected is that mpl::plus<int_<1>, mpl::at<Map, key>::type is mpl::integral_constant<int, 2>, whereas mpl::int_<2> is a different type.

A working version:

typedef mpl::map<mpl::pair<key, mpl::integral_c<int, 1>>> Map;
typedef mpl::map<mpl::pair<key, mpl::integral_c<int, 2>>> Map2;

typedef mpl::insert<
    mpl::erase_key<Map, key>::type,
    mpl::pair<key, mpl::plus<mpl::integral_c<int, 1>, mpl::at<Map, key>::type>::type>
>::type Map3;

Answer 2

The result of inserting elements in a different order into a boost::mpl::map are different types -- even if the mapping is the same. To work around this problem, you could rebuild the sequence by sorting it every time you modify it. This adds strongly to the complexity the compiler has to deal with, especially if the number of entries are larger.