static_unordered_flat_multimap.md

sfl::static_unordered_flat_multimap

Table of Contents

• Summary
• Template Parameters
• Public Member Types
• Public Member Classes
• Public Data Members
• Public Member Functions
  • (constructor)
  • (destructor)
  • operator=
  • key_eq
  • value_eq
  • begin, cbegin
  • end, cend
  • nth
  • index_of
  • empty
  • full
  • size
  • max_size
  • capacity
  • available
  • clear
  • emplace
  • emplace_hint
  • insert
  • erase
  • swap
  • find
  • count
  • contains
  • data
• Non-member Functions
  • operator==
  • operator!=
  • swap
  • erase_if

Summary

Defined in header sfl/static_unordered_flat_multimap.hpp:

namespace sfl
{
    template < typename Key,
               typename T,
               std::size_t N,
               typename KeyEqual = std::equal_to<Key> >
    class static_unordered_flat_multimap;
}

sfl::static_unordered_flat_multimap is an associative container similar to std::unordered_multimap, but the capacity is fixed and the underlying storage is implemented as an unsorted vector.

sfl::static_unordered_flat_multimap internally holds statically allocated array of size N and stores elements into this array, which avoids dynamic memory allocation and deallocation. This container never uses dynamic memory management.

The number of elements in static flat unordered multimap cannot be greater than N. Attempting to insert more than N elements into this container results in undefined behavior.

The complexity of insertion or removal of elements is O(1). The complexity of search is O(N).

The elements of sfl::static_unordered_flat_multimap are always stored contiguously in the memory.

Iterators to elements of sfl::static_unordered_flat_multimap are random access iterators and they meet the requirements of LegacyRandomAccessIterator.

sfl::static_unordered_flat_multimap meets the requirements of Container and ContiguousContainer. The requirements of UnorderedAssociativeContainer are partionally met.

This container is convenient for bare-metal embedded software development.

Template Parameters

1. typename Key
   

   Key type.

2. typename T
   

   Value type.

3. std::size_t N
   

   Size of the internal statically allocated array, i.e. the maximal number of elements that this container can contain.

4. typename KeyEqual
   

   Function for comparing keys.

Public Member Types

Member Type	Definition
key_type	Key
mapped_type	T
value_type	std::pair<Key, T>
size_type	std::size_t
difference_type	std::ptrdiff_t
key_equal	KeyEqual
reference	value_type&
const_reference	const value_type&
pointer	value_type*
const_pointer	const value_type*
iterator	LegacyRandomAccessIterator and LegacyContiguousIterator to value_type
const_iterator	LegacyRandomAccessIterator and LegacyContiguousIterator to const value_type

Public Member Classes

class value_equal
{
public:
    bool operator()(const value_type& x, const value_type& y) const;
};

Public Data Members

static constexpr size_type static_capacity = N;

Public Member Functions

(constructor)

1. static_unordered_flat_multimap() noexcept(std::is_nothrow_default_constructible<KeyEqual>::value)
   

2. explicit static_unordered_flat_multimap(const KeyEqual& equal) noexcept(std::is_nothrow_copy_constructible<KeyEqual>::value)
   

   Effects: Constructs an empty container.

   
   
   

3. template <typename InputIt>
   static_unordered_flat_multimap(InputIt first, InputIt last);
   

4. template <typename InputIt>
   static_unordered_flat_multimap(InputIt first, InputIt last, const KeyEqual& equal);
   

   Preconditions: std::distance(first, last) <= capacity()

   Effects: Constructs an empty container and inserts elements from the range [first, last).

   Note: This overload participates in overload resolution only if InputIt satisfies requirements of LegacyInputIterator.

   Complexity: Linear in std::distance(first, last).

   
   
   

5. static_unordered_flat_multimap(std::initializer_list<value_type> ilist);
   

6. static_unordered_flat_multimap(std::initializer_list<value_type> ilist, const KeyEqual& equal);
   

   Preconditions: ilist.size() <= capacity()

   Effects: Constructs an empty container and inserts elements from the initializer list ilist.

   Complexity: Linear in ilist.size().

   
   
   

7. static_unordered_flat_multimap(const static_unordered_flat_multimap& other);
   

   Effects: Copy constructor. Constructs the container with the copy of the contents of other.

   Complexity: Linear in size.

   
   
   

8. static_unordered_flat_multimap(static_unordered_flat_multimap&& other);
   

   Effects: Move constructor. Constructs the container with the contents of other using move semantics.

   other is not guaranteed to be empty after the move.

   other is in a valid but unspecified state after the move.

   Complexity: Linear in size.

   
   
   

(destructor)

1. ~static_unordered_flat_multimap();
   

   Effects: Destructs the container. The destructors of the elements are called and the used storage is deallocated.

   Complexity: Linear in size.

   
   
   

operator=

1. static_unordered_flat_multimap& operator=(const static_unordered_flat_multimap& other);
   

   Effects: Copy assignment operator. Replaces the contents with a copy of the contents of other.

   Returns: *this().

   Complexity: Linear in size.

   
   
   

2. static_unordered_flat_multimap& operator=(static_unordered_flat_multimap&& other);
   

   Effects: Move assignment operator. Replaces the contents with those of other using move semantics.

   other is not guaranteed to be empty after the move.

   other is in a valid but unspecified state after the move.

   Returns: *this().

   Complexity: Linear in size.

   
   
   

3. static_unordered_flat_multimap& operator=(std::initializer_list<value_type> ilist);
   

   Preconditions: ilist.size() <= capacity()

   Effects: Replaces the contents with those identified by initializer list ilist.

   Returns: *this().

   Complexity: Linear in size.

   
   
   

key_eq

1. key_equal key_eq() const;
   

   Effects: Returns the function object that compares keys for equality, which is a copy of this container's constructor argument equal.

   Complexity: Constant.

   
   
   

value_eq

1. value_equal value_eq() const;
   

   Effects: Returns a function object that compares objects of type value_type.

   Complexity: Constant.

   
   
   

begin, cbegin

1. iterator begin() noexcept;
   

2. const_iterator begin() const noexcept;
   

3. const_iterator cbegin() const noexcept;
   

   Effects: Returns an iterator to the first element of the container. If the container is empty, the returned iterator will be equal to end().

   Complexity: Constant.

   
   
   

end, cend

1. iterator end() noexcept;
   

2. const_iterator end() const noexcept;
   

3. const_iterator cend() const noexcept;
   

   Effects: Returns an iterator to the element following the last element of the container. This element acts as a placeholder; attempting to access it results in undefined behavior.

   Complexity: Constant.

   
   
   

nth

1. iterator nth(size_type pos) noexcept;
   

2. const_iterator nth(size_type pos) const noexcept;
   

   Preconditions: pos <= size()

   Effects: Returns an iterator to the element at position pos.

   If pos == size(), the returned iterator is equal to end().

   Complexity: Constant.

   
   
   

index_of

1. size_type index_of(const_iterator pos) const noexcept;
   

   Preconditions: cbegin() <= pos && pos <= cend()

   Effects: Returns position of the element pointed by iterator pos, i.e. std::distance(begin(), pos).

   If pos == end(), the returned value is equal to size().

   Complexity: Constant.

   
   
   

empty

1. bool empty() const noexcept;
   

   Effects: Returns true if the container has no elements, i.e. whether begin() == end().

   Complexity: Constant.

   
   
   

full

1. bool full() const noexcept;
   

   Effects: Returns true if the container is full, i.e. whether size() == capacity().

   Complexity: Constant.

   
   
   

size

1. size_type size() const noexcept;
   

   Effects: Returns the number of elements in the container, i.e. std::distance(begin(), end()).

   Complexity: Constant.

   
   
   

max_size

1. static constexpr size_type max_size() const noexcept;
   

   Effects: Returns the maximum number of elements the container is able to hold, i.e. N.

   Complexity: Constant.

   
   
   

capacity

1. static constexpr size_type capacity() const noexcept;
   

   Effects: Returns the maximum number of elements the container is able to hold, i.e. N.

   Complexity: Constant.

   
   
   

available

1. size_type available() const noexcept;
   

   Effects: Returns the number of elements that can be inserted into the container, i.e. capacity() - size().

   Complexity: Constant.

   
   
   

clear

1. void clear() noexcept;
   

   Effects: Erases all elements from the container. After this call, size() returns zero and capacity() remains unchanged.

   Complexity: Linear in size().

   
   
   

emplace

1. template <typename... Args>
   iterator emplace(Args&&... args);
   

   Preconditions: !full()

   Effects: Inserts a new element into the container.

   New element is constructed as value_type(std::forward<Args>(args)...).

   Note: The behavior is undefined if preconditions are not satisfied.

   Returns: Iterator to the inserted element.

   
   
   

emplace_hint

1. template <typename... Args>
   iterator emplace_hint(const_iterator hint, Args&&... args);
   

   Preconditions:

   1. !full()
   2. cbegin() <= hint && hint <= cend()

   Effects: Inserts a new element into the container.

   New element is constructed as value_type(std::forward<Args>(args)...).

   Iterator hint is used as a suggestion where to start to search insert position.

   Iterator hint is ignored due to container's underlying storage implementation. This overload exists just to have this container compatible with standard C++ containers as much as possible.

   Returns: Iterator to the inserted element.

   
   
   

insert

1. iterator insert(const value_type& value);
   

   Preconditions: !full()

   Effects: Inserts copy of value.

   Returns: Iterator to the inserted element.

   
   
   

2. iterator insert(value_type&& value);
   

   Preconditions: !full()

   Effects: Inserts value using move semantics.

   Returns: Iterator to the inserted element.

   
   
   

3. template <typename P>
   iterator insert(P&& value);
   

   Preconditions: !full()

   Effects: Inserts a new element into the container.

   New element is constructed as value_type(std::forward<P>(value)).

   Note: This overload participates in overload resolution only if std::is_constructible<value_type, P&&>::value is true.

   Returns: Iterator to the inserted element.

   
   
   

4. iterator insert(const_iterator hint, const value_type& value);
   

   Preconditions:

   1. !full()
   2. cbegin() <= hint && hint <= cend()

   Effects: Inserts copy of value.

   Iterator hint is used as a suggestion where to start to search insert position.

   Iterator hint is ignored due to container's underlying storage implementation. This overload exists just to have this container compatible with standard C++ containers as much as possible.

   Returns: Iterator to the inserted element.

   
   
   

5. iterator insert(const_iterator hint, value_type&& value);
   

   Preconditions:

   1. !full()
   2. cbegin() <= hint && hint <= cend()

   Effects: Inserts value using move semantics.

   Iterator hint is used as a suggestion where to start to search insert position.

   Iterator hint is ignored due to container's underlying storage implementation. This overload exists just to have this container compatible with standard C++ containers as much as possible.

   Returns: Iterator to the inserted element.

   
   
   

6. template <typename P>
   iterator insert(const_iterator hint, P&& value);
   

   Preconditions:

   1. !full()
   2. cbegin() <= hint && hint <= cend()

   Effects: Inserts a new element into the container.

   New element is constructed as value_type(std::forward<P>(value)).

   Iterator hint is used as a suggestion where to start to search insert position.

   Iterator hint is ignored due to container's underlying storage implementation. This overload exists just to have this container compatible with standard C++ containers as much as possible.

   Note: This overload participates in overload resolution only if std::is_constructible<value_type, P&&>::value is true.

   Returns: Iterator to the inserted element.

   
   
   

7. template <typename InputIt>
   void insert(InputIt first, InputIt last);
   

   Preconditions: std::distance(first, last) <= available()

   Effects: Inserts elements from range [first, last).

   The call to this function is equivalent to:

   while (first != last)
   {
       insert(*first);
       ++first;
   }
   

   Note: This overload participates in overload resolution only if InputIt satisfies requirements of LegacyInputIterator.

   
   
   

8. void insert(std::initializer_list<value_type> ilist);
   

   Preconditions: ilist.size() <= available()

   Effects: Inserts elements from initializer list ilist.

   The call to this function is equivalent to insert(ilist.begin(), ilist.end()).

   
   
   

erase

1. iterator erase(iterator pos);
   

2. iterator erase(const_iterator pos);
   

   Preconditions: cbegin() <= pos && pos < cend()

   Effects: Removes the element at pos.

   Returns: Iterator following the last removed element.

   
   
   

3. iterator erase(const_iterator first, const_iterator last);
   

   Preconditions: cbegin() <= first && first <= last && last <= cend()

   Effects: Removes the elements in the range [first, last).

   Returns: Iterator following the last removed element.

   
   
   

4. size_type erase(const Key& key);
   

5. template <typename K>
   size_type erase(K&& x);
   

   Effects: Removes all elements with the key equivalent to key or x.

   Note: Overload (5) participates in overload resolution only if KeyEqual::is_transparent exists and is a valid type. It allows calling this function without constructing an instance of Key.

   Returns: Number of elements removed.

   
   
   

swap

1. void swap(static_unordered_flat_multimap& other);
   

   Effects: Exchanges the contents of the container with those of other.

   Complexity: Linear in size.

   
   
   

find

1. iterator find(const Key& key);
   

2. const_iterator find(const Key& key) const;
   

3. template <typename K>
   iterator find(const K& x);
   

4. template <typename K>
   const_iterator find(const K& x) const;
   

   Effects: Returns an iterator pointing to the element with key equivalent to key or x. Returns end() if no such element is found. If there are several elements with key in the container, any of them may be returned.

   Note: Overloads (3) and (4) participate in overload resolution only if KeyEqual::is_transparent exists and is a valid type. It allows calling these functions without constructing an instance of Key.

   Complexity: Constant in the best case. Linear in size() in the worst case.

   
   
   

count

1. size_type count(const Key& key) const;
   

2. template <typename K>
   size_type count(const K& x) const;
   

   Effects: Returns the number of elements with key equivalent to key or x.

   Note: Overload (2) participates in overload resolution only if KeyEqual::is_transparent exists and is a valid type. It allows calling this function without constructing an instance of Key.

   Complexity: Linear in size().

   
   
   

contains

1. bool contains(const Key& key) const;
   

2. template <typename K>
   bool contains(const K& x) const;
   

   Effects: Returns true if the container contains an element with key equivalent to key or x, otherwise returns false.

   Note: Overload (2) participates in overload resolution only if KeyEqual::is_transparent exists and is a valid type. It allows calling this function without constructing an instance of Key.

   Complexity: Constant in the best case. Linear in size() in the worst case.

   
   
   

data

1. value_type* data() noexcept;
   

2. const value_type* data() const noexcept;
   

   Effects: Returns pointer to the underlying array serving as element storage. The pointer is such that range [data(), data() + size()) is always a valid range, even if the container is empty. data() is not dereferenceable if the container is empty.

   Complexity: Constant.

   
   
   

Non-member Functions

operator==

1. template <typename K, typename T, std::size_t N, typename E>
   bool operator==
   (
       const static_unordered_flat_multimap<K, T, N, E>& x,
       const static_unordered_flat_multimap<K, T, N, E>& y
   );
   

   Effects: Checks if the contents of x and y are equal.

   The contents of x and y are equal if the following conditions hold:

   • x.size() == y.size()
   • For each element in x there is equal element in y.

   The comparison is performed by std::is_permutation. This comparison ignores the container's KeyEqual function.

   Returns: true if the contents of the x and y are equal, false otherwise.

   
   
   

operator!=

1. template <typename K, typename T, std::size_t N, typename E>
   bool operator!=
   (
       const static_unordered_flat_multimap<K, T, N, E>& x,
       const static_unordered_flat_multimap<K, T, N, E>& y
   );
   

   Effects: Checks if the contents of x and y are equal.

   For details see operator==.

   Returns: true if the contents of the x and y are not equal, false otherwise.

   
   
   

swap

1. template <typename K, typename T, std::size_t N, typename E>
   void swap
   (
       static_unordered_flat_multimap<K, T, N, E>& x,
       static_unordered_flat_multimap<K, T, N, E>& y
   );
   

   Effects: Swaps the contents of x and y. Calls x.swap(y).

   
   
   

erase_if

1. template <typename K, typename T, std::size_t N, typename E, typename Predicate>
   typename static_unordered_flat_multimap<K, T, N, E>::size_type
       erase_if(static_unordered_flat_multimap<K, T, N, E>& c, Predicate pred);
   

   Effects: Erases all elements that satisfy the predicate pred from the container.

   pred is unary predicate which returns true if the element should be removed.

   Returns: The number of erased elements.

   Complexity: Linear.

   
   
   

End of document.