bimap

bimap.hpp

#pragma once

#include <cassert>
#include <map>
#include <memory>
#include <utility>

template <class L, class R, class CompareLeft = std::less<L>, class CompareRight = std::less<R>,
          class AllocatorLeft = std::allocator<std::pair<const L, const R *>>,
          class AllocatorRight = std::allocator<std::pair<const R, const L *>>>
class bimap {
  public:
	using left_type = L;
	using right_type = R;

	using left_storage_type = std::map<L, const R *, CompareLeft, AllocatorLeft>;
	using left_iterator = typename left_storage_type::iterator;
	using left_const_iterator = const left_iterator;

	using right_storage_type = std::map<R, const L *, CompareRight, AllocatorRight>;
	using right_iterator = typename right_storage_type::iterator;
	using right_const_iterator = const right_iterator;

	void insert(const L &left, const R &right)
	{
		erase_from_left(left);
		erase_from_right(right);

		const auto left_iter = m_left.insert({left, nullptr}).first;
		const auto right_iter = m_right.insert({right, nullptr}).first;

		left_iter->second = &right_iter->first;
		right_iter->second = &left_iter->first;
	}

	const L *left(const R &right) const
	{
		const auto right_iter = m_right.find(right);
		if (right_iter == m_right.end()) {
			return nullptr;
		}
		return right_iter->second;
	}

	const R *right(const L &left) const
	{
		const auto left_iter = m_left.find(left);
		if (left_iter == m_left.end()) {
			return nullptr;
		}
		return left_iter->second;
	}

	void erase_from_left(const L &left)
	{
		const auto left_iter = m_left.find(left);
		if (left_iter != m_left.end()) {
			erase_from_left(left_iter);
		}
	}

	void erase_from_left(left_iterator left_iter)
	{
		const auto right_iter = m_right.find(*left_iter->second);
		assert(right_iter != m_right.end());

		m_left.erase(left_iter);
		m_right.erase(right_iter);
	}

	void erase_from_right(const R &right)
	{
		const auto right_iter = m_right.find(right);
		if (right_iter != m_right.end()) {
			erase_from_right(right_iter);
		}
	}

	void erase_from_right(right_iterator right_iter)
	{
		const auto left_iter = m_left.find(*right_iter->second);
		assert(left_iter != m_left.end());

		m_left.erase(left_iter);
		m_right.erase(right_iter);
	}

	void clear()
	{
		m_left.clear();
		m_right.clear();
	}

	bool empty() const { return m_left.empty(); }
	size_t size() const { return m_left.size(); }

	left_iterator begin() { return m_left.begin(); }
	left_iterator end() { return m_left.end(); }
	left_const_iterator begin() const { return m_left.begin(); }
	left_const_iterator end() const { return m_left.end(); }
	left_const_iterator cbegin() const { return m_left.cbegin(); }
	left_const_iterator cend() const { return m_left.cend(); }
	left_iterator rbegin() { return m_left.rbegin(); }
	left_iterator rend() { return m_left.rend(); }
	left_const_iterator rbegin() const { return m_left.rbegin(); }
	left_const_iterator rend() const { return m_left.rend(); }
	left_const_iterator crbegin() const { return m_left.crbegin(); }
	left_const_iterator crend() const { return m_left.crend(); }

	right_iterator right_begin() { return m_right.begin(); }
	right_iterator right_end() { return m_right.end(); }
	right_const_iterator right_begin() const { return m_right.begin(); }
	right_const_iterator right_end() const { return m_right.end(); }
	right_const_iterator right_cbegin() const { return m_right.cbegin(); }
	right_const_iterator right_cend() const { return m_right.cend(); }
	right_iterator right_rbegin() { return m_right.rbegin(); }
	right_iterator right_rend() { return m_right.rend(); }
	right_const_iterator right_rbegin() const { return m_right.rbegin(); }
	right_const_iterator right_rend() const { return m_right.rend(); }
	right_const_iterator right_crbegin() const { return m_right.crbegin(); }
	right_const_iterator right_crend() const { return m_right.crend(); }

  private:
	left_storage_type m_left;
	right_storage_type m_right;
};

bimap_simple.hpp

#pragma once

#include <memory>
#include <utility>
#include <vector>

template <class L, class R, class Allocator = std::allocator<std::pair<L, R>>>
class bimap {
  public:
	using left_type = L;
	using right_type = R;

	using storage_type = std::vector<std::pair<L, R>, Allocator>;
	using allocator_type = Allocator;

	using iterator = typename storage_type::iterator;
	using const_iterator = const iterator;

	void insert(const L &left, const R &right)
	{
		erase_from_left(left);
		erase_from_right(right);
		m_elements.push_back({left, right});
	}

	L *left(const R &right)
	{
		for (auto &[l, r] : m_elements) {
			if (r == right) {
				return &l;
			}
		}
		return nullptr;
	}
	const L *left(const R &right) const { return const_cast<bimap<L, R> *>(this)->left(right); }

	R *right(const L &left)
	{
		for (auto &[l, r] : m_elements) {
			if (l == left) {
				return &r;
			}
		}
		return nullptr;
	}
	const R *right(const L &left) const { return const_cast<bimap<L, R> *>(this)->right(left); }

	void erase_from_left(const L &left)
	{
		for (auto it = m_elements.begin(); it != m_elements.end(); ++it) {
			if (it->first == left) {
				m_elements.erase(it);
				return;
			}
		}
	}

	void erase_from_right(const R &right)
	{
		for (auto it = m_elements.begin(); it != m_elements.end(); ++it) {
			if (it->second == right) {
				m_elements.erase(it);
				return;
			}
		}
	}

	void clear() { m_elements.clear(); }

	void reserve(size_t capacity) { return m_elements.reserve(capacity); }
	void shrink_to_fit() { return m_elements.shrink_to_fit(); }

	bool empty() const { return m_elements.empty(); }
	size_t size() const { return m_elements.size(); }

	iterator begin() { return m_elements.begin(); }
	iterator end() { return m_elements.end(); }
	const_iterator begin() const { return m_elements.begin(); }
	const_iterator end() const { return m_elements.end(); }
	const_iterator cbegin() const { return m_elements.cbegin(); }
	const_iterator cend() const { return m_elements.cend(); }
	iterator rbegin() { return m_elements.rbegin(); }
	iterator rend() { return m_elements.rend(); }
	const_iterator rbegin() const { return m_elements.rbegin(); }
	const_iterator rend() const { return m_elements.rend(); }
	const_iterator crbegin() const { return m_elements.crbegin(); }
	const_iterator crend() const { return m_elements.crend(); }

  private:
	storage_type m_elements;
};

main.cpp

#include "bimap.hpp"

#include <iostream>
#include <string>

int main()
{
	bimap<std::string, int> m;
	const auto &cm = m;

	m.insert("one", 1);
	m.insert("two", 2);
	m.insert("three", 3);

	for (const auto &[left, right] : m) {
		std::cout << left << ": " << *right << "\n";
	}

	std::cout << "----\n";

	std::cout << "one: " << *m.right("one") << "\n";
	std::cout << "one: " << *cm.right("one") << "\n";

	std::cout << "2: " << *m.left(2) << "\n";
	std::cout << "2: " << *cm.left(2) << "\n";

	std::cout << "----\n";

	m.erase_from_left("one");
	m.erase_from_right(3);

	for (const auto &[left, right] : m) {
		std::cout << left << ": " << *right << "\n";
	}

	std::cout << "----\n";

	m.insert("three", 1);
	m.insert("three", 3); // kicks out {"three", 1}

	m.insert("one", 3); // kicks out {"three", 3}
	m.insert("one", 1);

	for (const auto &[left, right] : m) {
		std::cout << left << ": " << *right << "\n";
	}
}