A C++ template library for embedded applications
MIT licensed
Designed and
maintained by
John Wellbelove
flat_map / flat_multimap

A fixed capacity map based on a sorted vector.
The container is an associative lookup table with O(N) insertion and erase, and O(log N) search.
This container is best used for tables that are occasionally updated and spend most of their time being searched.
The interface is most similar to std::map.
Uses std::less as the default key comparison method.

etl::flat_map<typename TKey, typename TMapped, size_t SIZE, TKeyCompare = etl::less>

Inherits from etl::iflat_map<TKey, TMapped, TKeyCompare>
etl::iflat_map may be used as a size independent pointer or reference type for any etl::flat_map instance.
____________________________________________________________________________________________________
Template deduction guides
C++17 and above

template <typename... TPairs>
etl::flat_map(TPairs...)

Example
etl::flat_map data{ etl::pair{0, 1}, etl::pair{2, 3}, etl::pair{4, 5}, etl::pair{6, 7} };
Defines data as an flat_map of int/int pairs, of length 4, containing the supplied data.
____________________________________________________________________________________________________
Make template
C++11 and above
template <typename TKey,
          typename TMapped,
          typename TKeyCompare = etl::less<TKey>,
          typename... TPairs>
constexpr auto make_flat_map(TValues&&... values)

Example
auto data = etl::make_flat_map<int, int>(etl::pair{0, 1}, etl::pair{2, 3},
                                         etl::pair{4, 5}, etl::pair{6, 7});
____________________________________________________________________________________________________
Member types

key_type                TKey
mapped_type             TMapped
value_type              pair<const key_type, mapped_type>
                        The type is either std::pair (default) or etl::pair (ETL_NO_STL)
size_type               std::size_t
difference_type         std::ptrdiff_t
reference               T&
const_reference         const T&
rvalue_reference        T&&
pointer                 T*
const_pointer           const T*
iterator                Random access iterator
const_iterator          Constant random access iterator
reverse_iterator        reverse_iterator<iterator>
const_reverse_iterator  reverse_iterator<const_iterator>

____________________________________________________________________________________________________
Static Constants

MAX_SIZE  The maximum size of the flat map.
____________________________________________________________________________________________________
Constructor

etl::flat_map<Tkey, TMapped, SIZE, TKeyCompare>();

etl::flat_map(const flat_map& other)
etl::flat_map(flat_map&& other)

template <typename TIterator>
etl::flat_map<Tkey, TMapped, SIZE, TKeyCompare>(TIterator begin, TIterator end);
____________________________________________________________________________________________________
Element access

TMapped& at(key_parameter_t key)
const TMapped& at(key_parameter_t key) const
Returns a reference or const reference to the indexed element.
Emits an etl::flat_map_out_of_range if the key is not in the table. If asserts or exceptions are not enabled then
undefined behaviour occurs.
____________________________________________________________________________________________________
TMapped& operator[](key_parameter_t key)
const TMapped& operator[](key_parameter_t key) const
Returns a reference or const reference to the indexed element.
If the key is not in the table then a new entry is created.
____________________________________________________________________________________________________
Iterators

iterator begin()
const_iterator begin() const
const_iterator cbegin() const
Returns an iterator to the beginning of the map.
____________________________________________________________________________________________________
iterator end()
const_iterator end() const
const_iterator cend() const
Returns an iterator to the end of the map.
____________________________________________________________________________________________________
iterator rbegin()
const_iterator rbegin() const
const_iterator crbegin() const
Returns a reverse iterator to the beginning of the map.
____________________________________________________________________________________________________
iterator rend()
const_iterator rend() const
const_iterator crend() const
Returns a reverse iterator to the end of the map.
____________________________________________________________________________________________________
Capacity

bool empty() const
Returns true if the size of the map is zero, otherwise false.
____________________________________________________________________________________________________
bool full() const
Returns true if the size of the lookup is SIZE, otherwise false.
____________________________________________________________________________________________________
size_t size() const
Returns the size of the lookup.
____________________________________________________________________________________________________
size_t max_size() const
Returns the maximum possible size of the map.
____________________________________________________________________________________________________
size_t available() const
Returns the remaining available capacity in the map.
____________________________________________________________________________________________________
Modifiers

flat_map& operator = (const flat_map& rhs)
flat_map& operator = (flat_map&& rhs)
Copies or moves the data from another flat map.
____________________________________________________________________________________________________
pair<iterator, bool> insert(const value_type& value)
pair<iterator, bool> insert(value_type&& value)
iterator insert(iterator position, const value_type& value)
iterator insert(iterator position, value_type&& value)

template <typename TIterator>
void insert(TIterator first, TIterator last)
Inserts values in to the map.
If the map is full then emits an etl::flat_map_full. If asserts or exceptions are not enabled then undefined
behaviour occurs.
The return type is either std::pair (default) or etl::pair (ETL_NO_STL)
____________________________________________________________________________________________________
pair<iterator, bool> emplace((const value_type& value))
pair<iterator, bool> emplace(const key_type& key, const mapped_type& value)
Inserts key/value pairs into the map by constructing directly into storage.
The return type is either std::pair (default) or etl::pair (ETL_NO_STL)
____________________________________________________________________________________________________
Inserts key/value pairs into the map by constructing directly into storage. The value is constructed from the set of 'value'
parameters.

C++03
template <typename T1>
pair<iterator, bool> emplace(const key_type& key, const T1& value1)

template <typename T1, typename T2>
pair<iterator, bool> emplace(const key_type& key, const T1& value1, const T2& value2)

template <typename T1, typename T2, typename T3>
pair<iterator, bool> emplace(const key_type& key, const T1& value1, const T2& value2, const T3& value3)

template <typename T1, typename T2, typename T3, typename T4>
pair<iterator, bool> emplace(const key_type& key, const T1& value1, const T2& value2, const T3& value3,
const T4& value4)
The emplace functions differ from that of std::map in that, due to C++03 not supporting 'perfect forwarding', the
values for constructing mapped types must be listed as parameters and not nested in a 'mapped' value parameter.
The return type is either std::pair (default) or etl::pair (ETL_NO_STL)

C++11
template <typename ... Args>
pair<iterator, bool> emplace(const key_type& key, Args&& ... args)
____________________________________________________________________________________________________
size_t erase(key_value_parameter_t key)
void erase(iterator i_element)
void erase(iterator first, iterator last)

20.20.0
iterator erase(const_iterator i_element)
iterator erase(const_iteratorfirst, const_iteratorlast)

20.21.0
template <typename K>
size_t erase(K&& key)

Erases values in the map.
Returns an iterator to the next element in the map.
Iterator parameters are not checked for validity.
____________________________________________________________________________________________________
void clear();
Clears the lookup to a size of zero.
____________________________________________________________________________________________________
Search

iterator find(key_value_parameter_t key)
const_iterator find(key_value_parameter_t key) const

iterator lower_bound(key_value_parameter_t key)
const_iterator lower_bound(key_value_parameter_t key) const

iterator upper_bound(key_value_parameter_t key)
const_iterator upper_bound(key_value_parameter_t key) const

pair<iterator, iterator> equal_range(key_value_parameter_t key)
pair<const_iterator, const_iterator> equal_range(key_value_parameter_t key) const
The return type is either std::pair (default) or etl::pair (ETL_NO_STL)
____________________________________________________________________________________________________
20.21.0
C++11 or above
For comparators that define is_transparent.

template <typename K>
iterator find(const K& key)

template <typename K>
const_iterator find(const K& key) const
____________________________________________________________________________________________________
20.21.0
C++11 or above
template <typename K>
iterator lower_bound(const K& key)

template <typename K>
const_iterator lower_bound(const K& key) const
____________________________________________________________________________________________________
20.21.0
C++11 or above
template <typename K>
iterator upper_bound(const K& key)

template <typename K>
const_iterator upper_bound(const K& key) const
____________________________________________________________________________________________________
20.21.0
C++11 or above
template <typename K>
pair<iterator, iterator> equal_range(const K& key)

template <typename K>
pair<const_iterator, const_iterator> equal_range(const K& key) const
____________________________________________________________________________________________________
20.21.0
bool contains(key_value_parameter_t key) const
Check if the container contains the key.

20.21.0
C++11 or above
For comparators that define is_transparent.
template <typename K>
bool contains(const K& k) const
Check if the container contains the key.
____________________________________________________________________________________________________
Non-member functions

Lexicographically comparisons
==  true if the contents of the maps are equal, otherwise false.
!=  true if the contents of the maps are not equal, otherwise false.
___________________________________________________________________________________________________
Technical stuff

Flat maps are usually implemented internally as a sorted vector of key/value pairs. Whilst this makes searching fast, it
can have a detrimental effect when items are inserted into a container that stores complex, non-trivial keys or values.
As inserting requires that all of the items above the insert position must be shifted, this can become an expensive
operation for larger containers.

To improve insertion performance ETL flat maps are implemented as vectors of pointers to key/value pairs, sorted by
key value. An insertion will involve a copy of a range of pointers; an operation that can be made very fast.

The downside is that access to an item via an iterator will involve one indirection and the overhead of the container will
be one pointer per item. A normal flat map implementation does not have this overhead.
_________________________________________________________________________________________________________
_______________________________________________________________________________________________
flat_map.h / flat_multimap.h