Bidirectional map based on memory manipulation

This is a bidirectional map implementation that stores the values as pairs on the heap, and uses pointer arithmetic for efficient lookup.

codepad link, may be easier to read

```
#include
#include
#include
#include
#include

namespace Internal
{
template struct PtrComparator
{
inline bool operator()(const T mA, const T mB) const noexcept { return *mA class SneakyBimap
{
public:
using BMPair = std::pair;
using Storage = std::vector>;
template using PtrSet = std::set>;

using iterator = typename Storage::iterator;
using const_iterator = typename Storage::const_iterator;
using reverse_iterator = typename Storage::reverse_iterator;
using const_reverse_iterator = typename Storage::const_reverse_iterator;

private:
Storage storage;
PtrSet set1;
PtrSet set2;

template inline BMPair getPairImpl(const T mPtr) const noexcept
{
return const_cast(reinterpret_cast(mPtr));
}

inline const char getPairBasePtr(const T2 mItem) const noexcept
{
static_assert(std::is_standard_layout::value, "BMPair must have standard layout");
return reinterpret_cast(mItem) - offsetof(BMPair, second);
}

inline BMPair getPairPtr(const T1 mItem) const noexcept { return getPairImpl(mItem); }
inline BMPair getPairPtr(const T2 mItem) const noexcept { return getPairImpl(getPairBasePtr(mItem)); }

inline T2& getImpl(const T1* mItem) noexcept { return getPairPtr(mItem)->second; }
inline T1& getImpl(const T2* mItem) noexcept { return getPairPtr(mItem)->first; }

inline const T2& getImpl(const T1* mItem) const noexcept { return getPairPtr(mItem)->second; }
inline const T1& getImpl(const T2* mItem) const noexcept { return getPairPtr(mItem)->first; }

public:
template inline void emplace(TA1&& mArg1, TA2&&

Here you assert that the type is standard layout (for use of offsetof)

inline const char* getPairBasePtr(const T2* mItem) const noexcept
    {
        static_assert(std::is_standard_layout::value, "BMPair must have standard layout");
        return reinterpret_cast(mItem) - offsetof(BMPair, second);            
    }

For symmetry and to make sure that the first element aligns to the beginning f the class you should probably do the same here.

template inline BMPair* getPairImpl(const T* mPtr) const noexcept
    {
        return const_cast(reinterpret_cast(mPtr));
    }

Don't need the new syntax here:

inline auto begin()     noexcept        -> decltype(storage.begin())    { return storage.begin(); }

The types of the iterators is well defined:

iterator begin() noexcept { return storage.begin(); }

Also don't specify inline unless you have too. Members declared inside the class are automatically inline so no need to add the keyword. PS. I assume you are not doing it to force inlining because the compiler will completely ignore you.

If you insert the same value you don't reuse a slot in storage:

typename SneakyBimap::BMPair   data(1,2);
 SneakyBimap                    store;
 store.insert(data);
 store.insert(data);
 store.insert(data);
 store.insert(data);
 store.insert(data);
 store.insert(data);
 store.insert(data);
 store.insert(data);
 store.insert(data);
 store.insert(data);
 store.insert(data);  // lots of storage used.

Not sure I would templatize this method:

template
inline void emplace(TA1&& mArg1, TA2&& mArg2)

The first thing you do is create a BMPair.

auto pair(std::make_unique>(std::forward(mArg1), std::forward(mArg2)))

And though you are forwarding the arguments to the constructor they will still need to convert the parameters as the object is constructed TA1 => T1 and TA2 => T2 so I don't think you gain any flexibility.

OK. Worked it out. By doing this you only have to convert the parameters once as you create the object. Rather than once at the call site (which happens if you don't templatize the parameters) followed by a copy during construction. Nice but ugly.

I would not use a vector of unique ptr.

using Storage = std::vector>;

As a user any dynamically allocated memory should be managed be either a smart pointer or a container. Since you are writing the container it is worth looking at writing the memory management to go with it.

using Storage = std::vector;

// OK just tried to re-write 
// void emplace(TA1&& mArg1, TA2&& mArg2)
// using only pointers.
// 
// It is possible but definitely non trivial
// to do in an exception safe manner as you have to insert data
// into three different containers all of which could throw during
// insertion.
// 
// Worth having a look at **BUT** now I think I would stick with
// std::unique_ptr until my container showed signs that it was
// causing efficiency problems having a good bash at it.

Now that I thought about it. You emplace does not provide the strong exception guarantee.

auto pair(std::make_unique>(std::forward(mArg1), std::forward(mArg2)));

        // Assume this works.
        set1.emplace(&(pair->first));

        // Assume this fails.
        // And throws an exception.
        set2.emplace(&(pair->second));

        // This is never done.
        // So `pair` still holds the value.
        storage.emplace_back(std::move(pair));

        // As `pair goes out of scope it deletes the object.
        // This means that `set1` holds a pointer to an invalid
        // memory location.

So now that I see that the same problems exist for both unique_ptr and pointer versions. I would go back to my original position of not using unique_ptr here. But it is non trivial and you should think about it.

StackExchange Code Review Q#42427, answer score: 3