Bidirectional map based on memory manipulation

Question

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 <iostream>
#include <set>
#include <utility>
#include <cstddef>
#include <SSVUtils/SSVUtils.hpp>
namespace Internal
{
 template<typename T> struct PtrComparator
 {
 inline bool operator()(const T* mA, const T* mB) const noexcept { return *mA < *mB; }
 };
} 
template<typename T1, typename T2> class SneakyBimap
{
 public:
 using BMPair = std::pair<T1, T2>;
 using Storage = std::vector<ssvu::Uptr<BMPair>>;
 template<typename T> using PtrSet = std::set<const T*, Internal::PtrComparator<T>>;
 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<T1> set1;
 PtrSet<T2> set2;
 template<typename T> inline BMPair* getPairImpl(const T* mPtr) const noexcept
 {
 return const_cast<BMPair*>(reinterpret_cast<const BMPair*>(mPtr));
 }
 inline const char* getPairBasePtr(const T2* mItem) const noexcept
 {
 static_assert(std::is_standard_layout<BMPair>::value, "BMPair must have standard layout");
 return reinterpret_cast<const char*>(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<typename TA1, typename TA2> inline void emplace(TA1&& mArg1, TA2&& mArg2)
 {
 assert(!this->has(mArg1) && !this->has(mArg2));
 auto pair(std::make_unique<std::pair<T1, T2>>(std::forward<TA1>(mArg1), std::forward<TA2>(mArg2)));
 set1.emplace(&(pair->first));
 set2.emplace(&(pair->second));
 storage.emplace_back(std::move(pair));
 }
 inline void insert(const BMPair& mPair)
 {
 this->emplace(mPair.first, mPair.second);
 }
 template<typename T> inline void erase(const T& mKey) 
 {
 assert(this->has(mKey)); 
 const auto& pairPtr(getPairPtr(&mKey));
 set1.erase(&(pairPtr->first));
 set2.erase(&(pairPtr->second));
 ssvu::eraseRemoveIf(storage, [&pairPtr](const ssvu::Uptr<std::pair<T1, T2>>& mI){ return mI.get() == pairPtr; });
 assert(!this->has(mKey)); 
 }
 inline const T2& at(const T1& mKey) const noexcept
 {
 const auto& itr(set1.find(&mKey));
 if(itr == std::end(set1)) throw std::out_of_range{"mKey was not found in set1"};
 return getImpl(*itr);
 }
 inline const T1& at(const T2& mKey) const noexcept
 {
 const auto& itr(set2.find(&mKey));
 if(itr == std::end(set2)) throw std::out_of_range{"mKey was not found in set2"};
 return getImpl(*itr);
 }
 inline T2& operator[](const T1& mKey) noexcept { assert(this->has(mKey)); return getImpl(*set1.find(&mKey)); }
 inline T1& operator[](const T2& mKey) noexcept { assert(this->has(mKey)); return getImpl(*set2.find(&mKey)); }
 inline const T2& operator[](const T1& mKey) const noexcept { assert(this->has(mKey)); return getImpl(*set1.find(&mKey)); }
 inline const T1& operator[](const T2& mKey) const noexcept { assert(this->has(mKey)); return getImpl(*set2.find(&mKey)); }
 inline void clear() noexcept { storage.clear(); set1.clear(); set2.clear(); }
 inline bool empty() const noexcept { return storage.empty(); }
 inline auto size() const noexcept -> decltype(storage.size()) { return storage.size(); }
 inline auto count(const T1& mKey) const noexcept -> decltype(set1.count(&mKey)) { return set1.count(&mKey); } 
 inline auto count(const T2& mKey) const noexcept -> decltype(set2.count(&mKey)) { return set2.count(&mKey); }
 inline auto find(const T1& mKey) const noexcept -> decltype(set1.find(&mKey)) { return set1.find(&mKey); } 
 inline auto find(const T2& mKey) const noexcept -> decltype(set2.find(&mKey)) { return set2.find(&mKey); }
 inline bool has(const T1& mKey) const noexcept { return this->find(mKey) != std::end(set1); }
 inline bool has(const T2& mKey) const noexcept { return this->find(mKey) != std::end(set2); }
 inline auto begin() noexcept -> decltype(storage.begin()) { return storage.begin(); }
 inline auto end() noexcept -> decltype(storage.end()) { return storage.end(); }
 inline auto begin() const noexcept -> decltype(storage.begin()) { return storage.begin(); }
 inline auto end() const noexcept -> decltype(storage.end()) { return storage.end(); }
 inline auto cbegin() const noexcept -> decltype(storage.cbegin()) { return storage.cbegin(); }
 inline auto cend() const noexcept -> decltype(storage.cend()) { return storage.cend(); }
 inline auto rbegin() noexcept -> decltype(storage.rbegin()) { return storage.rbegin(); }
 inline auto rend() noexcept -> decltype(storage.rend()) { return storage.rend(); }
 inline auto crbegin() const noexcept -> decltype(storage.crbegin()) { return storage.crbegin(); }
 inline auto crend() const noexcept -> decltype(storage.crend()) { return storage.crend(); }
};
SSVU_TEST(SneakyBimapTests)
{
 SneakyBimap<int, std::string> sb;
 SSVUT_EXPECT(sb.empty());
 SSVUT_EXPECT(!sb.has(10));
 SSVUT_EXPECT(!sb.has("banana"));
 SSVUT_EXPECT(sb.count(10) == 0);
 SSVUT_EXPECT(sb.count("banana") == 0);
 sb.emplace(10, "banana");
 SSVUT_EXPECT(!sb.empty());
 SSVUT_EXPECT(sb.size() == 1);
 SSVUT_EXPECT(sb.has(10));
 SSVUT_EXPECT(sb.has("banana"));
 SSVUT_EXPECT(sb.count(10) == 1);
 SSVUT_EXPECT(sb.count("banana") == 1);
 SSVUT_EXPECT(sb.at(10) == "banana");
 SSVUT_EXPECT(sb[10] == "banana");
 SSVUT_EXPECT(sb.at("banana") == 10);
 SSVUT_EXPECT(sb["banana"] == 10);
 sb["banana"] = 25;
 SSVUT_EXPECT(!sb.empty());
 SSVUT_EXPECT(sb.size() == 1);
 SSVUT_EXPECT(!sb.has(10));
 SSVUT_EXPECT(sb.has(25));
 SSVUT_EXPECT(sb.has("banana"));
 SSVUT_EXPECT(sb.count(10) == 0);
 SSVUT_EXPECT(sb.count(25) == 1);
 SSVUT_EXPECT(sb.count("banana") == 1);
 SSVUT_EXPECT(sb.at(25) == "banana");
 SSVUT_EXPECT(sb[25] == "banana");
 SSVUT_EXPECT(sb.at("banana") == 25);
 SSVUT_EXPECT(sb["banana"] == 25);
 sb["banana"] = 15;
 sb[15] = "melon";
 sb.emplace(10, "cucumber");
 SSVUT_EXPECT(!sb.empty());
 SSVUT_EXPECT(sb.size() == 2);
 SSVUT_EXPECT(sb.has(10));
 SSVUT_EXPECT(sb.has(15));
 SSVUT_EXPECT(!sb.has(25));
 SSVUT_EXPECT(sb.has("melon"));
 SSVUT_EXPECT(sb.has("cucumber"));
 SSVUT_EXPECT(!sb.has("banana"));
 SSVUT_EXPECT(sb.count(10) == 1);
 SSVUT_EXPECT(sb.count(15) == 1);
 SSVUT_EXPECT(sb.count(25) == 0);
 SSVUT_EXPECT(sb.count("melon") == 1);
 SSVUT_EXPECT(sb.count("cucumber") == 1);
 SSVUT_EXPECT(sb.count("banana") == 0);
 SSVUT_EXPECT(sb.at(10) == "cucumber");
 SSVUT_EXPECT(sb[10] == "cucumber");
 SSVUT_EXPECT(sb.at("cucumber") == 10);
 SSVUT_EXPECT(sb["cucumber"] == 10);
 SSVUT_EXPECT(sb.at(15) == "melon");
 SSVUT_EXPECT(sb[15] == "melon");
 SSVUT_EXPECT(sb.at("melon") == 15);
 SSVUT_EXPECT(sb["melon"] == 15);
 sb.clear();
 SSVUT_EXPECT(sb.empty());
 SSVUT_EXPECT(sb.size() == 0);
 SSVUT_EXPECT(!sb.has(10));
 SSVUT_EXPECT(!sb.has(15));
 SSVUT_EXPECT(!sb.has(25));
 SSVUT_EXPECT(!sb.has("melon"));
 SSVUT_EXPECT(!sb.has("cucumber"));
 SSVUT_EXPECT(!sb.has("banana"));
}
SSVU_TEST_END();
int main()
{
 SSVU_TEST_RUN_ALL();
 return 0;
}

Notes:

• ssvu::eraseRemoveIf performs the erase-remove idiom on a container, with a predicate.
• ssvu::Uptr<T> is just an alias for std::unique_ptr<T>.
• SSVUT_EXPECT is a test macro - the test fails unless the boolean expression inside returns true.
• The real values (pairs) are stored in storage, a std::vector of std::unique_ptr<std::pair<T1, T2>>.
• By performing pointer arithmetic and reinterpret_cast / const_cast magic, is it possible to obtain the base address of the pair from the first or second member. This trick is used to access the members of the pairs from a pointer to their first or second member. Is there anything dangerous about this?
• Is there a way to avoid using std::unique_ptr, and improving the performance?
• If you want to compile the code yourself, SSVUtils is available here on my GitHub page.

---

Tested on g++ 4.8 and clang++ SVN, both with -O3 and -O0 options. All tests passed.

• einpoklum: Can you please separate the test and non-test code into different segments (with separate include's), for easier copy-and-paste? Also, do you have a version of this on GitHub?

Answer 1

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<BMPair>::value, "BMPair must have standard layout");
 return reinterpret_cast<const char*>(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<typename T> inline BMPair* getPairImpl(const T* mPtr) const noexcept
 {
 return const_cast<BMPair*>(reinterpret_cast<const BMPair*>(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<int,int>::BMPair data(1,2);
 SneakyBimap<int,int> 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<typename TA1, typename TA2>
inline void emplace(TA1&& mArg1, TA2&& mArg2)

The first thing you do is create a BMPair.

auto pair(std::make_unique<std::pair<T1, T2>>(std::forward<TA1>(mArg1), std::forward<TA2>(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<ssvu::Uptr<BMPair>>;

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<BMPair*>;
// 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::pair<T1, T2>>(std::forward<TA1>(mArg1), std::forward<TA2>(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.

Answer 2

I'm very confused by the fact that your class allows you to modify the keys stored inside an std::set by const_casting the pointer into said std::set.

I don't use STL so my knowledge is shallow at best, but this SO thread seems to agree that you must always erase and re-insert the key if you want to modify it.

My guess is that this code

sb["banana"] = 25;
// ...
sb["banana"] = 15;
sb[15] = "melon";
// ...
SSVUT_EXPECT(!sb.has("banana"));

only works because at this point of your test the sets contain just one item, so the red/black trees inside of them have no opportunity to get corrupted.