echomap::BidirectionalUnorderedMapping< Key, Value > Class Template Reference

Maintains a bidirectional mapping between a key and value, allowing fast lookup on both objects. More...

#include <BidirectionalUnorderedMapping.hpp>

Public Types
using	iterator = decltype(forward_map)::iterator
	The bidirectional container non-constant iterator.
using	const_iterator = decltype(forward_map)::const_iterator
	The bidirectional container constant iterator.

Public Member Functions
const_iterator	begin () const noexcept
const_iterator	cbegin () const noexcept
const_iterator	end () const noexcept
const_iterator	cend () const noexcept
bool	empty () const noexcept
std::size_t	size () const noexcept
void	clear () noexcept
	Removes all entries from the mapping.
template<typename KeyT, typename ValueT>
std::pair< const_iterator, bool >	emplace (KeyT &&key, ValueT &&value)
	Emplaces an entry to the mapping.
bool	erase_by_key (const Key &key)
	Removes an entry from the mapping by its key.
bool	erase_by_value (const Value &value)
	Removes an entry from the mapping by its value.
const_iterator	find_by_key (const Key &key) const
	Locates an entry in the mapping by its key.
const_iterator	find_by_value (const Value &value) const
	Locates an entry in the mapping by its value.

Private Attributes
std::unordered_map< Key, Value >	forward_map
	The "forward" map, mapping keys to values in the conventional way.
std::unordered_map< Value, Key >	reverse_map
	The "reverse" map, mapping values to keys.

Detailed Description

template<typename Key, typename Value>
class echomap::BidirectionalUnorderedMapping< Key, Value >

Maintains a bidirectional mapping between a key and value, allowing fast lookup on both objects.

Template Parameters

Key	The first key type
Value	The second key type, colloquially the "value".

The templated types should typically be small (such as a stable integral ID), since their values are duplicated internally across two STL unordered hashing containers.

To guarantee implementation invariants, the bidirectional mapping container does not expose mutable access to its members. Mutation of the iterators of the underlying storage containers can be done exclusively through the public interface.

Definition at line 33 of file BidirectionalUnorderedMapping.hpp.

Member Typedef Documentation

const_iterator

template<typename Key, typename Value>

using echomap::BidirectionalUnorderedMapping< Key, Value >::const_iterator = decltype(forward_map)::const_iterator

The bidirectional container constant iterator.

Definition at line 53 of file BidirectionalUnorderedMapping.hpp.

iterator

template<typename Key, typename Value>

using echomap::BidirectionalUnorderedMapping< Key, Value >::iterator = decltype(forward_map)::iterator

The bidirectional container non-constant iterator.

Definition at line 52 of file BidirectionalUnorderedMapping.hpp.

Member Function Documentation

begin()

template<typename Key, typename Value>

const_iterator echomap::BidirectionalUnorderedMapping< Key, Value >::begin ( ) const

inlinenodiscardnoexcept

Definition at line 55 of file BidirectionalUnorderedMapping.hpp.

    {
        return forward_map.begin();
    }

cbegin()

template<typename Key, typename Value>

const_iterator echomap::BidirectionalUnorderedMapping< Key, Value >::cbegin ( ) const

inlinenodiscardnoexcept

Definition at line 60 of file BidirectionalUnorderedMapping.hpp.

    {
        return forward_map.cbegin();
    }

cend()

template<typename Key, typename Value>

const_iterator echomap::BidirectionalUnorderedMapping< Key, Value >::cend ( ) const

inlinenodiscardnoexcept

Definition at line 70 of file BidirectionalUnorderedMapping.hpp.

    {
        return forward_map.cend();
    }

clear()

template<typename Key, typename Value>

void echomap::BidirectionalUnorderedMapping< Key, Value >::clear ( )

inlinenoexcept

Removes all entries from the mapping.

Postcondition

All internal containers are cleared.

Definition at line 90 of file BidirectionalUnorderedMapping.hpp.

    {
        forward_map.clear();
        reverse_map.clear();
 
        assert(forward_map.empty());
        assert(reverse_map.empty());
    }

emplace()

template<typename Key, typename Value>

template<typename KeyT, typename ValueT>

std::pair< const_iterator, bool > echomap::BidirectionalUnorderedMapping< Key, Value >::emplace ( KeyT && key, ValueT && value )

inline

Emplaces an entry to the mapping.

Template Parameters

KeyT	Type of the forward key
ValueT	Type of the forward value

Parameters

key	Key from the forward perspective
value	Value from the forward perspective

Returns

1. Constant iterator to the inserted element, or the end iterator if the insertion failed.
2. Did an insertion take place?

Definition at line 118 of file BidirectionalUnorderedMapping.hpp.

    {
        auto forward_insertion = forward_map.emplace(std::forward<KeyT>(key), std::forward<ValueT>(value));
        if (!forward_insertion.second)
            return {forward_insertion.first, false};
 
        try {
            const auto& inserted_key = forward_insertion.first->first;
            // ReSharper disable once CppTooWideScopeInitStatement - Intentionally wide for readability.
            const auto& inserted_value = forward_insertion.first->second;
 
            if (!reverse_map.emplace(inserted_value, inserted_key).second) {
                forward_map.erase(forward_insertion.first);
                return {forward_map.end(), false};
            }
        } catch (...) {
            forward_map.erase(forward_insertion.first);
            throw;
        }
 
        assert(forward_map.size() == reverse_map.size());
        return {forward_insertion.first, true};
    }

empty()

template<typename Key, typename Value>

bool echomap::BidirectionalUnorderedMapping< Key, Value >::empty ( ) const

inlinenodiscardnoexcept

Definition at line 75 of file BidirectionalUnorderedMapping.hpp.

    {
        return forward_map.empty();
    }

end()

template<typename Key, typename Value>

const_iterator echomap::BidirectionalUnorderedMapping< Key, Value >::end ( ) const

inlinenodiscardnoexcept

Definition at line 65 of file BidirectionalUnorderedMapping.hpp.

    {
        return forward_map.end();
    }

erase_by_key()

template<typename Key, typename Value>

bool echomap::BidirectionalUnorderedMapping< Key, Value >::erase_by_key ( const Key & key )

inline

Removes an entry from the mapping by its key.

Parameters

key	The key of the entry to remove.

Returns

Was an element removed?

Postcondition

All internal containers meet the size invariant.

Definition at line 152 of file BidirectionalUnorderedMapping.hpp.

    {
        const auto itr = forward_map.find(key);
        if (itr == forward_map.end())
            return false;
 
        reverse_map.erase(itr->second);
        forward_map.erase(itr);
 
        assert(forward_map.size() == reverse_map.size());
 
        return true;
    }

erase_by_value()

template<typename Key, typename Value>

bool echomap::BidirectionalUnorderedMapping< Key, Value >::erase_by_value ( const Value & value )

inline

Removes an entry from the mapping by its value.

Parameters

value

The value of the entry to remove.

Returns

Was an element removed?

Postcondition

All internal containers meet the size invariant.

Definition at line 175 of file BidirectionalUnorderedMapping.hpp.

    {
        const auto itr = reverse_map.find(value);
        if (itr == reverse_map.end())
            return false;
 
        forward_map.erase(itr->second);
        reverse_map.erase(itr);
 
        assert(forward_map.size() == reverse_map.size());
 
        return true;
    }

find_by_key()

template<typename Key, typename Value>

const_iterator echomap::BidirectionalUnorderedMapping< Key, Value >::find_by_key ( const Key & key ) const

inline

Locates an entry in the mapping by its key.

Parameters

key	The key of the entry to locate.

Returns

A constant iterator to the located element, or the end iterator of the container if no element was found.

Definition at line 197 of file BidirectionalUnorderedMapping.hpp.

    {
        return forward_map.find(key);
    }

find_by_value()

template<typename Key, typename Value>

const_iterator echomap::BidirectionalUnorderedMapping< Key, Value >::find_by_value ( const Value & value ) const

inline

Locates an entry in the mapping by its value.

Parameters

value

The value of the entry to locate.

Returns

A constant iterator to the located element, or the end iterator of the container if no element was found.

Definition at line 210 of file BidirectionalUnorderedMapping.hpp.

    {
        const auto reverse_map_it = reverse_map.find(value);
        if (reverse_map_it == reverse_map.end())
            return forward_map.end();
 
        const auto forward_map_it = forward_map.find(reverse_map_it->second);
        assert(forward_map_it != forward_map.end()); // Verify class invariant.
 
        return forward_map_it;
    }

size()

template<typename Key, typename Value>

std::size_t echomap::BidirectionalUnorderedMapping< Key, Value >::size ( ) const

inlinenodiscardnoexcept

Definition at line 80 of file BidirectionalUnorderedMapping.hpp.

    {
        return forward_map.size();
    }

Member Data Documentation

forward_map

template<typename Key, typename Value>

std::unordered_map<Key, Value> echomap::BidirectionalUnorderedMapping< Key, Value >::forward_map

private

The "forward" map, mapping keys to values in the conventional way.

Invariant

Every K-V entry in the forward map relates to a corresponding V-K entry in the reverse map.

The forward map contains no excess elements than those in the reverse map.

Definition at line 41 of file BidirectionalUnorderedMapping.hpp.

reverse_map

template<typename Key, typename Value>

std::unordered_map<Value, Key> echomap::BidirectionalUnorderedMapping< Key, Value >::reverse_map

private

The "reverse" map, mapping values to keys.

Invariant

Every V-K entry in the reverse map relates to a corresponding K-V entry in the forward map.

The reverse map contains no excess elements than those in the forward map.

Definition at line 49 of file BidirectionalUnorderedMapping.hpp.

---

The documentation for this class was generated from the following file:

• src/objects/BidirectionalUnorderedMapping.hpp