Bloat Tests for Large Map

CMakeLists.txt

cmake_minimum_required(VERSION 2.8)

add_definitions(-std=c++14)
add_definitions(-Wall)
add_definitions(-Wextra)

include_directories("/usr/local/include")

add_executable(large_map_1
	large_map_1.cpp
  )
add_executable(large_map_2
	large_map_2.cpp
  )
add_executable(large_map_3
	large_map_3.cpp
  )

large_map_1.cpp

#include<boost/hana/map.hpp>
#include<boost/hana/range.hpp>
#include<vector>

namespace hana = boost::hana;

template <int i>
auto buildLargeMap() {
  return hana::unpack(hana::range_c<int, 0, i>, [](auto ...x) {
    return hana::make_map(hana::make_pair(x, std::vector<int>{})...);
  });
}

int main() {
  auto x = buildLargeMap<500>();
}

large_map_2.cpp

#include<boost/hana/map.hpp>
#include<boost/hana/range.hpp>
#include<vector>

namespace hana = boost::hana;

template <int i>
auto buildLargeMap() {
  return hana::unpack(hana::range_c<int, 0, i>, [](auto ...x) {
    return hana::make_tuple(hana::make_pair(x, std::vector<int>{})...);
  });
}

using LargeMap = decltype(buildLargeMap<500>());

int main() {
  auto x = hana::unpack(LargeMap{}, hana::make_map);  
}

large_map_3.cpp

#include "./map.hpp"
#include<boost/hana/range.hpp>
#include<vector>

namespace hana = boost::hana;

template <int i>
auto buildLargeMap() {
  return hana::unpack(hana::range_c<int, 0, i>, [](auto ...x) {
    return hana::make_map(hana::make_pair(x, std::vector<int>{})...);
  });
}

using LargeMap = decltype(buildLargeMap<500>());

int main() {
  auto x = LargeMap{};
}

map.hpp

//modified: added naive default constructor - Jason Rice
/*!
@file
Defines `boost::hana::map`.

@copyright Louis Dionne 2015
Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
 */

#ifndef BOOST_HANA_MAP_HPP
#define BOOST_HANA_MAP_HPP

#include <boost/hana/fwd/map.hpp>

#include <boost/hana/all_of.hpp>
#include <boost/hana/any_of.hpp>
#include <boost/hana/append.hpp>
#include <boost/hana/at.hpp>
#include <boost/hana/bool.hpp>
#include <boost/hana/concept/comparable.hpp>
#include <boost/hana/concept/constant.hpp>
#include <boost/hana/concept/product.hpp>
#include <boost/hana/contains.hpp>
#include <boost/hana/core/make.hpp>
#include <boost/hana/detail/decay.hpp>
#include <boost/hana/detail/fast_and.hpp>
#include <boost/hana/detail/index_if.hpp>
#include <boost/hana/detail/operators/adl.hpp>
#include <boost/hana/detail/operators/comparable.hpp>
#include <boost/hana/detail/operators/searchable.hpp>
#include <boost/hana/equal.hpp>
#include <boost/hana/find.hpp>
#include <boost/hana/find_if.hpp>
#include <boost/hana/first.hpp>
#include <boost/hana/fold_left.hpp>
#include <boost/hana/functional/compose.hpp>
#include <boost/hana/functional/demux.hpp>
#include <boost/hana/functional/partial.hpp>
#include <boost/hana/fwd/at_key.hpp>
#include <boost/hana/fwd/core/convert.hpp>
#include <boost/hana/insert.hpp>
#include <boost/hana/is_subset.hpp>
#include <boost/hana/keys.hpp>
#include <boost/hana/length.hpp>
#include <boost/hana/remove_if.hpp>
#include <boost/hana/second.hpp>
#include <boost/hana/transform.hpp>
#include <boost/hana/tuple.hpp>
#include <boost/hana/unpack.hpp>
#include <boost/hana/value.hpp>

#include <cstddef>
#include <type_traits>
#include <utility>


namespace boost { namespace hana {
    //////////////////////////////////////////////////////////////////////////
    // operators
    //////////////////////////////////////////////////////////////////////////
    namespace detail {
        template <>
        struct comparable_operators<map_tag> {
            static constexpr bool value = true;
        };
    }

    //////////////////////////////////////////////////////////////////////////
    // map
    //////////////////////////////////////////////////////////////////////////
    //! @cond
    template <typename ...Pairs>
    struct map
        : detail::searchable_operators<map<Pairs...>>
        , detail::operators::adl<map<Pairs...>>
    {
        tuple<Pairs...> storage;
        using hana_tag = map_tag;
        static constexpr std::size_t size = sizeof...(Pairs);

        //here is my naive default constructor
        constexpr map()
            : storage(tuple<Pairs...>{})
        { }

        explicit constexpr map(tuple<Pairs...> const& ps)
            : storage(ps)
        { }

        explicit constexpr map(tuple<Pairs...>&& ps)
            : storage(static_cast<tuple<Pairs...>&&>(ps))
        { }
    };
    //! @endcond

    //////////////////////////////////////////////////////////////////////////
    // make<map_tag>
    //////////////////////////////////////////////////////////////////////////
    template <>
    struct make_impl<map_tag> {
        template <typename ...Pairs>
        static constexpr auto apply(Pairs&& ...pairs) {
        #ifndef BOOST_HANA_CONFIG_DISABLE_CONCEPT_CHECKS
            static_assert(detail::fast_and<Product<Pairs>::value...>::value,
            "hana::make_map(pairs...) requires all the 'pairs' to be Products");

            static_assert(detail::fast_and<
                Comparable<decltype(hana::first(pairs))>::value...
            >::value,
            "hana::make_map(pairs...) requires all the keys to be Comparable");

            static_assert(detail::fast_and<
                Constant<
                    decltype(hana::equal(hana::first(pairs), hana::first(pairs)))
                >::value...
            >::value,
            "hana::make_map(pairs...) requires all the keys to be "
            "Comparable at compile-time");
        #endif

            return map<typename detail::decay<Pairs>::type...>{
                hana::make_tuple(static_cast<Pairs&&>(pairs)...)
            };
        }
    };

    //////////////////////////////////////////////////////////////////////////
    // keys
    //////////////////////////////////////////////////////////////////////////
    template <>
    struct keys_impl<map_tag> {
        template <typename Map>
        static constexpr decltype(auto) apply(Map&& map) {
            return hana::transform(static_cast<Map&&>(map).storage, hana::first);
        }
    };

    //////////////////////////////////////////////////////////////////////////
    // values
    //////////////////////////////////////////////////////////////////////////
    //! @cond
    template <typename Map>
    constexpr decltype(auto) values_t::operator()(Map&& map) const {
        return hana::transform(static_cast<Map&&>(map).storage, hana::second);
    }
    //! @endcond

    //////////////////////////////////////////////////////////////////////////
    // insert
    //////////////////////////////////////////////////////////////////////////
    template <>
    struct insert_impl<map_tag> {
        template <typename Xs, typename Pair, typename Indices>
        static constexpr auto
        insert_helper(Xs&& xs, Pair&&, hana::true_, Indices) {
            return static_cast<Xs&&>(xs);
        }

        template <typename Xs, typename Pair, std::size_t ...n>
        static constexpr auto
        insert_helper(Xs&& xs, Pair&& pair, hana::false_, std::index_sequence<n...>) {
            return hana::make_map(
                hana::at_c<n>(static_cast<Xs&&>(xs).storage)..., static_cast<Pair&&>(pair)
            );
        }

        template <typename Xs, typename Pair>
        static constexpr auto apply(Xs&& xs, Pair&& pair) {
            constexpr bool contains = hana::value<decltype(
                hana::contains(xs, hana::first(pair))
            )>();
            constexpr std::size_t size = std::remove_reference<Xs>::type::size;
            return insert_helper(static_cast<Xs&&>(xs), static_cast<Pair&&>(pair),
                                 hana::bool_c<contains>, std::make_index_sequence<size>{});
        }
    };

    //////////////////////////////////////////////////////////////////////////
    // erase_key
    //////////////////////////////////////////////////////////////////////////
    template <>
    struct erase_key_impl<map_tag> {
        template <typename M, typename Key>
        static constexpr decltype(auto) apply(M&& map, Key&& key) {
            return hana::unpack(
                hana::remove_if(
                    static_cast<M&&>(map).storage,
                    hana::compose(
                        hana::equal.to(static_cast<Key&&>(key)),
                        hana::first
                    )
                ),
                hana::make_map
            );
        }
    };

    //////////////////////////////////////////////////////////////////////////
    // Comparable
    //////////////////////////////////////////////////////////////////////////
    template <>
    struct equal_impl<map_tag, map_tag> {
        template <typename M1, typename M2>
        static constexpr auto equal_helper(M1 const&, M2 const&, hana::false_) {
            return hana::false_c;
        }

        template <typename M1, typename M2>
        static constexpr auto equal_helper(M1 const& m1, M2 const& m2, hana::true_) {
            return hana::all_of(hana::keys(m1), hana::demux(equal)(
                hana::partial(hana::find, m1),
                hana::partial(hana::find, m2)
            ));
        }

        template <typename M1, typename M2>
        static constexpr auto apply(M1 const& m1, M2 const& m2) {
            return equal_impl::equal_helper(m1, m2, hana::bool_c<
                decltype(hana::length(m1.storage))::value ==
                decltype(hana::length(m2.storage))::value
            >);
        }
    };

    //////////////////////////////////////////////////////////////////////////
    // Searchable
    //////////////////////////////////////////////////////////////////////////
    template <>
    struct find_if_impl<map_tag> {
        template <typename M, typename Pred>
        static constexpr auto apply(M&& map, Pred&& pred) {
            return hana::transform(
                hana::find_if(static_cast<M&&>(map).storage,
                    hana::compose(static_cast<Pred&&>(pred), hana::first)),
                hana::second
            );
        }
    };

    template <>
    struct any_of_impl<map_tag> {
        template <typename M, typename Pred>
        static constexpr auto apply(M const& map, Pred const& pred)
        { return hana::any_of(hana::keys(map), pred); }
    };

    template <>
    struct is_subset_impl<map_tag, map_tag> {
        template <typename Ys>
        struct all_contained {
            Ys const& ys;
            template <typename ...X>
            constexpr auto operator()(X const& ...x) const {
                return hana::bool_c<detail::fast_and<
                    hana::value<decltype(hana::contains(ys, x))>()...
                >::value>;
            }
        };

        template <typename Xs, typename Ys>
        static constexpr auto apply(Xs const& xs, Ys const& ys) {
            auto ys_keys = hana::keys(ys);
            return hana::unpack(hana::keys(xs), all_contained<decltype(ys_keys)>{ys_keys});
        }
    };

    template <>
    struct at_key_impl<map_tag> {
        template <typename Xs, typename Key>
        static constexpr decltype(auto) apply(Xs&& xs, Key const& key) {
            using Pack = typename detail::make_pack<Xs>::type;
            using Pred = decltype(hana::compose(hana::equal.to(key), hana::first));
            constexpr std::size_t index = detail::index_if<Pred, Pack>::value;
            return hana::second(hana::at_c<index>(static_cast<Xs&&>(xs).storage));
        }
    };

    //////////////////////////////////////////////////////////////////////////
    // Foldable
    //////////////////////////////////////////////////////////////////////////
    template <>
    struct unpack_impl<map_tag> {
        template <typename M, typename F>
        static constexpr decltype(auto) apply(M&& map, F&& f) {
            return hana::unpack(static_cast<M&&>(map).storage,
                                static_cast<F&&>(f));
        }
    };

    //////////////////////////////////////////////////////////////////////////
    // Construction from a Foldable
    //////////////////////////////////////////////////////////////////////////
    template <typename F>
    struct to_impl<map_tag, F, when<Foldable<F>::value>> {
        template <typename Xs>
        static constexpr decltype(auto) apply(Xs&& xs) {
            return hana::fold_left(
                static_cast<Xs&&>(xs), hana::make_map(), hana::insert
            );
        }
    };
}} // end namespace boost::hana

#endif // !BOOST_HANA_MAP_HPP