want to efficiently overcome mismatch between key

Question

I'm creating a map (from string to string in this example) in shared memory using Boost.Interprocess. The compiler seems to want to force me, during retrieval from the map, to allocate memory in the managed segment just to (unnecessarily) contain the query term.

I'd like to be able to look up values in a shared map more efficiently, by matching the map's keys against instances that are already in non-shared memory, without performing this extra allocation. But it's refusing to compile if I try to use a std::string or const char * as the argument to the map's find method. (see compiler error messages at bottom).

Do I need to define some sort of comparator method between my shared-memory key type and its non-shared equivalent (std::string in this example)? If so, what should this look like and how should I make the map use it? If not, what should I do?

Here's the code, followed by the compiler errors. The problem is towards the bottom of main().

// shmap2.cpp

#include <boost/interprocess/managed_shared_memory.hpp>
#include <boost/interprocess/allocators/allocator.hpp>
#include <boost/interprocess/containers/map.hpp>
#include <boost/interprocess/containers/vector.hpp>
#include <boost/interprocess/containers/string.hpp>

//Typedefs of allocators and containers
namespace Shared
{
    typedef boost::interprocess::managed_shared_memory
        Segment;

    typedef boost::interprocess::managed_shared_memory::segment_manager
        SegmentManager;

    typedef boost::interprocess::allocator< void, SegmentManager >
        Allocator;

    typedef boost::interprocess::allocator< char, SegmentManager >
        CharAllocator;

    typedef boost::interprocess::basic_string< char, std::char_traits< char >, CharAllocator > 
        String;

    typedef std::less< String >
        StringComparator;

    // Definition of the shared map from String to String
    // (To avoid confusion, let's strictly use Python-like definitions of "key", "value" and "item")
    typedef std::pair< const String, String >
        MapItem;

    typedef boost::interprocess::allocator< MapItem, SegmentManager >
        MapItemAllocator;

    typedef boost::interprocess::map< String, String, StringComparator, MapItemAllocator >
        Map;
}

int main( void )
{
    struct shm_remove
    {
        shm_remove() { boost::interprocess::shared_memory_object::remove( "MySharedMemory" ); }
        ~shm_remove(){ boost::interprocess::shared_memory_object::remove( "MySharedMemory" ); }
    } remover;

    // Create shared memory
    Shared::Segment seg( boost::interprocess::create_only, "MySharedMemory", 65536 );

    // An allocator instance that can be converted to any allocator< T, Shared::SegmentManager > type
    Shared::Allocator alloc( seg.get_segment_manager() );

    // An instance of the string comparator, to construct the map
    Shared::StringComparator cmp;

    // Construct the shared memory map
    Shared::Map * myMapPtr = seg.construct< Shared::Map >( "myMap" )( cmp, alloc );

    // Here's the problem:

    // std::string key( "foo" );            // Compilation fails if you use this.
    // char key[] = "foo";                  // Compilation fails if you use this.
    Shared::String key( "foo", alloc );     // This the only version I can get to work.
                                            // But it forces you to create a copy of
                                            // the key you are searching for, in
                                            // the managed segment.

    // This is the point of the exercise:
    Shared::Map::iterator it = myMapPtr->find( key );

    return 0;
}

With a std::string as the key:

$ g++ -o shmap2 -D BOOST_ALL_NO_LIB  -I ../boost_1_57_0  shmap2.cpp
shmap2.cpp:79:40: error: no matching member function for call to 'find'
                Shared::Map::iterator it = myMapPtr->find( key );
                                           ~~~~~~~~~~^~~~
../boost_1_57_0/boost/container/detail/tree.hpp:1089:13: note: candidate function not
      viable: no known conversion from 'std::string' (aka 'basic_string<char,
      char_traits<char>, allocator<char> >') to 'const key_type' (aka 'const
      boost::container::basic_string<char, std::__1::char_traits<char>,
      boost::interprocess::allocator<char, boost::interprocess::segment_manager<char,
      boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family,
      boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index> >
      >') for 1st argument
   iterator find(const key_type& k)
            ^
../boost_1_57_0/boost/container/detail/tree.hpp:1092:19: note: candidate function not
      viable: no known conversion from 'std::string' (aka 'basic_string<char,
      char_traits<char>, allocator<char> >') to 'const key_type' (aka 'const
      boost::container::basic_string<char, std::__1::char_traits<char>,
      boost::interprocess::allocator<char, boost::interprocess::segment_manager<char,
      boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family,
      boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index> >
      >') for 1st argument
   const_iterator find(const key_type& k) const
                  ^
1 error generated.

With const char * as the key:

$ g++ -o shmap2 -D BOOST_ALL_NO_LIB  -I ../boost_1_57_0  shmap2.cpp
In file included from shmap2.cpp:17:
In file included from ../boost_1_57_0/boost/interprocess/containers/string.hpp:19:
../boost_1_57_0/boost/container/string.hpp:676:59: error: no matching constructor for
      initialization of 'allocator_type' (aka 'boost::interprocess::allocator<char,
      boost::interprocess::segment_manager<char,
      boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family,
      boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index> >')
   basic_string(const CharT* s, const allocator_type& a = allocator_type())
                                                          ^
shmap2.cpp:79:46: note: in instantiation of default function argument expression for
      'basic_string<char, std::__1::char_traits<char>, boost::interprocess::allocator<char,
      boost::interprocess::segment_manager<char,
      boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family,
      boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index> > >'
      required here
                Shared::Map::iterator it = myMapPtr->find( key );
                                                           ^
../boost_1_57_0/boost/interprocess/allocators/allocator.hpp:140:4: note: candidate
      constructor template not viable: requires single argument 'other', but no
      arguments were provided
   allocator(const allocator<T2, SegmentManager> &other)
   ^
../boost_1_57_0/boost/interprocess/allocators/allocator.hpp:129:4: note: candidate
     constructor not viable: requires single argument 'segment_mngr', but no arguments
     were provided
   allocator(segment_manager *segment_mngr)
   ^
../boost_1_57_0/boost/interprocess/allocators/allocator.hpp:134:4: note: candidate
     constructor not viable: requires single argument 'other', but no arguments were
     provided
   allocator(const allocator &other)
   ^
1 error generated.

UPDATE: following the suggestion of sehe, below, I tried replacing

typedef std::less< String >
    StringComparator;

with

typedef struct
{
    template< typename T, typename U >
    bool operator()( const T & t, const U & u )
        const { return t < u; }
} StringComparator;

but got the same two compiler errors.

Answer 1

You can use a custom comparator

   struct MyLess {
        template <typename T, typename U>
            bool operator()(const T&t, const U&u) const
        {
            return t<u;
        }
    };

In your code you can just typedef it as StringComparator

UPDATE To the comments

---

Multi Index To The Rescue

If you want to replace the std::map/boost::container::map with a Boost Multi Index container (which supports lookup by CompatibleKey), here's a demo of how to do it:

I've borrowed some of the idea's from the documentation section Emulating standard containers with multi_index_container.

Note that std::string as the lookup key still won't work, but you can easily use .c_strio() in that event.

Live On Coliru

#include <boost/interprocess/managed_shared_memory.hpp>
#include <boost/interprocess/allocators/allocator.hpp>
#include <boost/interprocess/containers/map.hpp>
#include <boost/interprocess/containers/vector.hpp>
#include <boost/interprocess/containers/string.hpp>

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/member.hpp>

namespace emulation {
    template <typename T1,typename T2,typename Alloc>
        struct mutable_pair
        {
            typedef T1 first_type;
            typedef T2 second_type;

            mutable_pair(Alloc alloc):first(T1(alloc)),second(T2(alloc)){}
            mutable_pair(const T1& f,const T2& s):first(f),second(s){}
            mutable_pair(const std::pair<T1,T2>& p):first(p.first),second(p.second){}

            T1         first;
            mutable T2 second;
        };

    using namespace boost::multi_index;

    template <typename Key, typename T, typename Compare, typename Allocator, typename Element = mutable_pair<Key, T, Allocator> >
        using map = multi_index_container<
            Element,
            indexed_by<
                ordered_unique<member<Element,Key,&Element::first>,Compare>
            >,
            typename Allocator::template rebind<Element>::other
        >;

  template <typename Key, typename T, typename Compare, typename Allocator, typename Element = mutable_pair<Key, T, Allocator> >
    using multimap = multi_index_container<
        Element,
        indexed_by<
            ordered_non_unique<member<Element,Key,&Element::first>,Compare>
        >,
        typename Allocator::template rebind<Element>::other
    >;

  template <typename Key, typename T, typename Compare, typename Allocator> 
      struct wrap_map : map<Key, T, Compare, Allocator> {
          typedef map<Key, T, Compare, Allocator> base_type;
          typedef typename base_type::template nth_index<0>::type index_type;

          wrap_map(Allocator alloc) : base_type({}, alloc)
          {
          }

          wrap_map(Compare cmp, Allocator alloc) : base_type(
                  typename base_type::ctor_args_list{
                    typename index_type::ctor_args { typename index_type::key_from_value {}, cmp }
                  },
                  alloc)
          {
          }
      };
}

// Typedefs of allocators and containers
namespace Shared {
    typedef boost::interprocess::managed_shared_memory Segment;
    typedef boost::interprocess::managed_shared_memory::segment_manager SegmentManager;
    typedef boost::interprocess::allocator<void, SegmentManager> Allocator;
    typedef boost::interprocess::allocator<char, SegmentManager> CharAllocator;
    typedef boost::interprocess::basic_string<char, std::char_traits<char>, CharAllocator> String;

    struct MyLess {
        template <typename T, typename U> bool operator()(const T &t, const U &u) const { return t < u; }
    };
    typedef MyLess StringComparator;


    typedef boost::interprocess::allocator<char, SegmentManager> StringAlloc;
    typedef emulation::mutable_pair<const String, String, StringAlloc> MapItem;
    typedef boost::interprocess::allocator<MapItem, SegmentManager> MapItemAllocator;
    typedef emulation::wrap_map<String, String, StringComparator, MapItemAllocator> Map;
}

int main(void) {
    struct shm_remove {
        shm_remove() { boost::interprocess::shared_memory_object::remove("MySharedMemory"); }
        ~shm_remove() { boost::interprocess::shared_memory_object::remove("MySharedMemory"); }
    } remover;

    // Create shared memory
    Shared::Segment seg(boost::interprocess::create_only, "MySharedMemory", 65536);
    Shared::Allocator alloc(seg.get_segment_manager());

    // An instance of the string comparator, to construct the map
    Shared::StringComparator cmp;

    // Construct the shared memory map
    Shared::Map *myMapPtr = seg.construct<Shared::Map>("myMap")(cmp, alloc);

    myMapPtr->emplace(Shared::String("foo", alloc), Shared::String("bar", alloc));
    myMapPtr->emplace(Shared::String("goo", alloc), Shared::String("car", alloc));
    myMapPtr->emplace(Shared::String("hoo", alloc), Shared::String("dar", alloc));

    Shared::String key("foo", alloc);

    // This is the point of the exercise:
    auto it = myMapPtr->find(key);

    if (it!=myMapPtr->end())
        std::cout << "Found: '" << it->first << "' -> '" << it->second << "'\n";

    // this is now okay too
    char szkey[] = "foo";
    it = myMapPtr->find(szkey);
    if (it!=myMapPtr->end())
        std::cout << "Found: '" << it->first << "' -> '" << it->second << "'\n";

    // this is now okay too
    std::string skey("foo");
    it = myMapPtr->find(skey.c_str());
    if (it!=myMapPtr->end())
        std::cout << "Found: '" << it->first << "' -> '" << it->second << "'\n";

    return 0;
}

Prints:

Found: 'foo' -> 'bar'
Found: 'foo' -> 'bar'
Found: 'foo' -> 'bar'

---

Scoped Allocators For Extra Awesomesauce?

Now, interestingly, Boost Container supports Scoped Allocators, so you could do away with the repeated passing of the allocators, however, Boost Multi Index sadly doesn't support it fully. Here's a halfway approach that's about as far as I could get it (still somewhat user friendlier):

Live On Coliru

#include <boost/interprocess/managed_shared_memory.hpp>
#include <boost/interprocess/allocators/allocator.hpp>
#include <boost/interprocess/containers/map.hpp>
#include <boost/interprocess/containers/vector.hpp>
#include <boost/interprocess/containers/string.hpp>

#include <boost/container/scoped_allocator.hpp>

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/member.hpp>

namespace emulation {
    template <typename T1,typename T2,typename Alloc>
        struct mutable_pair
        {
            typedef Alloc allocator_type;
            typedef T1 first_type;
            typedef T2 second_type;

            mutable_pair(Alloc alloc):first(T1(alloc)),second(T2(alloc)){}
            mutable_pair(const T1& f,const T2& s):first(f),second(s){}
            mutable_pair(const std::pair<T1,T2>& p):first(p.first),second(p.second){}

            template <typename U, typename V, typename Alloc2>
            mutable_pair(const U& f,const V& s, Alloc2 alloc):first(f, alloc),second(s, alloc){}

            T1         first;
            mutable T2 second;
        };

    using namespace boost::multi_index;

    template <typename Key, typename T, typename Compare, typename Allocator, typename Element = mutable_pair<Key, T, Allocator> >
        using map = multi_index_container<
            Element,
            indexed_by<
                ordered_unique<member<Element,Key,&Element::first>,Compare>
            >,
            typename Allocator::template rebind<Element>::other
        >;

  template <typename Key, typename T, typename Compare, typename Allocator, typename Element = mutable_pair<Key, T, Allocator> >
    using multimap = multi_index_container<
        Element,
        indexed_by<
            ordered_non_unique<member<Element,Key,&Element::first>,Compare>
        >,
        typename Allocator::template rebind<Element>::other
    >;

  template <typename Key, typename T, typename Compare, typename Allocator> 
      struct wrap_map : map<Key, T, Compare, Allocator> {
          typedef map<Key, T, Compare, Allocator> base_type;
          typedef typename base_type::template nth_index<0>::type index_type;

          wrap_map(Allocator alloc) : base_type({}, alloc)
          { 
          }

          wrap_map(Compare cmp, Allocator alloc) : base_type(
                  typename base_type::ctor_args_list{
                    typename index_type::ctor_args { typename index_type::key_from_value {}, cmp }
                  },
                  alloc)
          { 
          }
      };
}


// Typedefs of allocators and containers
namespace Shared {
    typedef boost::interprocess::managed_shared_memory Segment;
    typedef Segment::segment_manager SegmentManager;
    typedef boost::container::scoped_allocator_adaptor<boost::interprocess::allocator<void, SegmentManager> > Allocator;

    typedef Allocator::rebind<char>::other CharAllocator;
    typedef boost::interprocess::basic_string<char, std::char_traits<char>, CharAllocator> String;

    struct MyLess {
        template <typename T, typename U> bool operator()(const T &t, const U &u) const { return t < u; }
    };
    typedef MyLess StringComparator;

    typedef emulation::mutable_pair<String, String, CharAllocator> MapItem;
    typedef Allocator::rebind<MapItem>::other MapItemAllocator;
    typedef emulation::wrap_map<String, String, StringComparator, MapItemAllocator> Map;
}

int main(void) {
    struct shm_remove {
        shm_remove() { boost::interprocess::shared_memory_object::remove("MySharedMemory"); }
        ~shm_remove() { boost::interprocess::shared_memory_object::remove("MySharedMemory"); }
    } remover;

    // Create shared memory
    Shared::Segment seg(boost::interprocess::create_only, "MySharedMemory", 65536);
    Shared::Allocator alloc(seg.get_segment_manager());

    // An instance of the string comparator, to construct the map
    Shared::StringComparator cmp;

    // Construct the shared memory map
    Shared::Map *myMapPtr = seg.construct<Shared::Map>("myMap")(cmp, alloc);

    myMapPtr->emplace("foo", "bar", alloc);
    myMapPtr->emplace("goo", "car", alloc);
    myMapPtr->emplace("hoo", "dar", alloc);

    // This the only version I can get to work.  But it forces you to create a
    // copy of the key you are searching for, in the managed segment.
    Shared::String key("foo", alloc);     

    // This is the point of the exercise:
    auto it = myMapPtr->find(key);

    if (it!=myMapPtr->end())
        std::cout << "Found: '" << it->first << "' -> '" << it->second << "'\n";

    // this is now okay too
    char szkey[] = "foo";
    it = myMapPtr->find(szkey);
    if (it!=myMapPtr->end())
        std::cout << "Found: '" << it->first << "' -> '" << it->second << "'\n";

    // this is now okay too
    std::string skey("foo");
    it = myMapPtr->find(skey.c_str());
    if (it!=myMapPtr->end())
        std::cout << "Found: '" << it->first << "' -> '" << it->second << "'\n";

    return 0;
}

Also printing

Found: 'foo' -> 'bar'
Found: 'foo' -> 'bar'
Found: 'foo' -> 'bar'

Answer 2

The following is adapted from the C++03-compatible code linked from @sehe's comment on vis own answer. Although I don't really know what I'm doing, I've generalized it in the way that seemed fitting for maps whose keys are not of the same type as their mapped values, by adding a second allocator type to the mutable_pair and map_gen definitions. I've made it clear which namespace everything comes from and removed the multimap_gen definition for brevity. It compiles to allow map< string vector<int> >-type objects in shared memory to be queried with const char *.

The one thing I wasn't sure of was whether ValueType needs to make an appearance in the rebind line, but it seems to compile and work as is so far...

#include <boost/interprocess/managed_shared_memory.hpp>
#include <boost/interprocess/allocators/allocator.hpp>
#include <boost/interprocess/containers/map.hpp>
#include <boost/interprocess/containers/vector.hpp>
#include <boost/interprocess/containers/string.hpp>

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/member.hpp>

namespace sehe
{
    template < typename T1, typename T2, typename Alloc1, typename Alloc2 >
        struct mutable_pair
        {
            typedef T1 first_type;
            typedef T2 second_type;

            mutable_pair( Alloc1 alloc1, Alloc2 alloc2 ) : first( T1( alloc1 ) ), second( T2( alloc2 ) ) {}
            mutable_pair( const T1 & f, const T2 & s ) : first( f ), second( s ) {}
            mutable_pair( const std::pair< T1, T2 > & p ) : first( p.first ), second( p.second ) {}

            T1         first;
            mutable T2 second;
        };


    template <typename KeyType, typename ValueType, typename Compare, typename KeyAllocator, typename ValueAllocator, typename Element = mutable_pair< KeyType, ValueType, KeyAllocator, ValueAllocator > >
        struct map_gen
        {
            typedef boost::multi_index::multi_index_container
            <
                Element,
                boost::multi_index::indexed_by
                <
                    boost::multi_index::ordered_unique< boost::multi_index::member< Element, KeyType, &Element::first >, Compare >
                >,
                typename KeyAllocator::template rebind<Element>::other
            > type;
        };

    typedef struct {
        template <typename T, typename U> bool operator()(const T &t, const U &u) const { return t < u; }
    } Comparator;

}

// Typedefs of allocators and containers
namespace Shared
{
    typedef boost::interprocess::managed_shared_memory Segment;
    typedef boost::interprocess::managed_shared_memory::segment_manager SegmentManager;
    typedef boost::interprocess::allocator<void, SegmentManager> Allocator;


    typedef boost::interprocess::allocator<char, SegmentManager> CharAlloc;
    typedef boost::interprocess::basic_string<char, std::char_traits<char>, CharAlloc> String;
    typedef boost::interprocess::allocator< String, SegmentManager > StringAlloc;

    typedef boost::interprocess::allocator< int, SegmentManager > IntAlloc;
    typedef boost::interprocess::vector< int, IntAlloc > IntVector;
    typedef boost::interprocess::allocator< IntVector, SegmentManager > IntVectorAlloc;

    typedef sehe::map_gen< String, String,    sehe::Comparator, StringAlloc, StringAlloc >::type StringStringMap;
    typedef sehe::map_gen< String, IntVector, sehe::Comparator, StringAlloc, IntVectorAlloc >::type StringIntVectorMap;
}