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 forstd::unique_ptr<T>
.SSVUT_EXPECT
is a test macro - the test fails unless the boolean expression inside returnstrue
.- The real values (pairs) are stored in
storage
, astd::vector
ofstd::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 thefirst
orsecond
member. This trick is used to access the members of the pairs from a pointer to theirfirst
orsecond
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.