flat_multimap.md

flat_multimap

#include <flat_map/flat_multimap.hpp>

template <typename Key,
          typename T,
          typename Compare = std::less<Key>,
          typename Container = std::vector<std::pair<Key, T>>>
class flat_multimap;

Requirements

• Container should meet Container, AllocatorAwareContainer, SequenceContainer, and ReversibleContainer.

Complexity

• N denotes number of elements that stored in the container.
• M denotes number of elements that shifted by insert/erase.
• E denotes number of target elements that inserted or erased.

Member types

using key_type = Key;
using mapped_type = T;
using value_type = std::pair<Key, T>;
using size_type = std::size_t;
using difference_type = std::ptrdiff_t;
using key_compare = Compare;
using allocator_type = typename Container::allocator_type;
using reference = typename Container::reference;
using const_reference = typename Container::const_reference;
using pointer = typename Container::pointer;
using const_pointer = typename Container::const_pointer;
using iterator = typename Container::iterator;
using const_iterator = typename Container::const_iterator;
using reverse_iterator = typename Container::reverse_iterator;
using const_reverse_iterator = typename Container::const_reverse_iterator;
using node_type = /* unspecified */;

Member classes

struct value_compare;

Constructor

protected:
value_type(Compare c);

Operator

bool operator()(value_type const& lhs, value_type const& rhs);

Return value

comp(lhs.first, rhs.first)

Constructors

flat_multimap();

explicit flat_multimap(Compare const& comp, allocator_type const& alloc = allocator_type());

template <typename InputIterator>
flat_multimap(InputIterator first, InputIterator last, Compare const& comp = Compare(), allocator_type const& alloc = allocator_type());

template <typename InputIterator>
flat_multimap(InputIterator first, InputIterator last, allocator_type const& alloc);

Construct container from [first, last).

Pre requirements

InputIterator should meet InputIterator.

Complexity

O(E log(E)) if enough additional memory is available, otherwise O(E log^2(E)).

flat_multimap(flat_multimap const& other);

flat_multimap(flat_multimap const& other, allocator_type const& alloc);

Copy from other.

flat_multimap(flat_multimap&& other);

flat_multimap(flat_multimap&& other, allocator_type const& alloc);

Move entire elements from other.

flat_multimap(std::initializer_list<value_type> init, Compare const& comp = Compare(), allocator_type const& alloc = allocator_type());

flat_multimap(std::initializer_list<value_type> init, allocator_type const& alloc);

Construct from init.

Complexity

O(E log(E)) if enough additional memory is available, otherwise O(E log^2(E)).

explicit flat_multimap(range_order order, Container const& cont);
explicit flat_multimap(range_order order, Container const& cont, Compare const& comp, allocator_type const& alloc = allocator_type());
explicit flat_multimap(range_order order, Container const& cont, allocator_type const& alloc);
explicit flat_multimap(range_order order, Container&& cont);
explicit flat_multimap(range_order order, Container&& cont, Compare const& comp, allocator_type const& alloc = allocator_type());
explicit flat_multimap(range_order order, Container&& cont, allocator_type const& alloc);

Complexity

For non sorted range, amortized O(E log(E)) if enough additional memory is available, otherwise amortized O(E log^2(E)). For sorted range O(1).

Container& base() &;

Refer underlying container. The behavior is unspecified with any base container modifications except updating value (not key).

Container const& base() const&;

Refer underlying container.

Container base() &&;

Move every containing elements to returned sequence.

Postcondition

• size() == 0

Assignments

flat_multimap& operator=(flat_multimap const& other);

Copy from other.

flat_multimap& operator=(flat_multimap&& other) noexcept(/* see below */);

Move entire elements from other.

Exceptions

No exception only if it meets all of

• std::is_nothrow_move_assignable_v<Container> == true and
• std::is_nothrow_move_assignable_v<Compare> == true

flat_multimap& operator=(std::initializer_list<value_type> ilist);

Complexity

O(E log(E)) if enough additional memory is available, otherwise O(E log^2(E)).

Iterators

begin

iterator begin() noexcept;
const_iterator begin() const noexcept;

cbegin

const_iterator cbegin() const noexcept;

end

iterator end() noexcept;
const_iterator end() const noexcept;

cend

const_iterator cend() const noexcept;

rbegin

reverse_iterator rbegin() noexcept;
const_reverse_iterator rbegin() const noexcept;

crbegin

const_reference crbegin() const noexcept;

rend

reverse_iterator rend() noexcept;
const_reverse_iterator rend() const noexcept;

crend

const_reference crend() const noexcept;

Capacity

empty

bool empty() const noexcept;

size

size_type size() const noexcept;

max_size

size_type max_size() const noexcept;

reserve

void reserve(size_type new_cap);

Available only if Container::reserve() is provided.

Postcondition

• capacity() == new_cap

capacity

size_type capacity() const noexcept;

Available only if Container::capacity() is provided.

shrink_to_fit

void shrink_to_fit();

Available only if Container::shrink_to_fit() is provided.

Postcondition

• capacity() == size()

Complexity

O(N).

Modifiers

clear

void clear();

Clear container.

Postcondition

• size() == 0

Invalidation

Invalidates every interators and references.

insert

iterator insert(value_type const& value);

template <typename V>
iterator insert(V&& value);

iterator insert(value_type&& value);

Insert a value.

The second form only participants in overload resolution if std::is_constructible_v<value_type, V&&> == true.

Return value

An iterator to inserted value.

Complexity

Amortized O(M) for insertion, O(log(N)) for searching insertion point.

Invalidation

Same as Container::insert.

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

template <typename V>
iterator insert(const_iterator hint, V&& value);

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

Insert a value. The hint is used for looking up insertion point.

The second form only participants in overload resolution if std::is_constructible_v<value_type, V&&> == true.

Return value

An iterator to inserted value.

Complexity

Amortized O(M) for insertion, O(1) for searching insertion point with valid hint otherwise O(log(N)).

Invalidation

Same as Container::insert.

template <typename InputIterator>
void insert(InputIterator first, InputIterator last);

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

Range insertion. Same effect as insert(range_order::no_ordered, first, last) and insert(range_order::no_ordered, ilist) respectively.

Pre requirements

InputIterator should meet InputIterator.

iterator insert(node_type&& node)

iterator insert(const_iterator hint, node_type&& node)

Insert node. The hint is used in same way as other insert().

Return value

An iterator to inserted value.

Complexity

Amortized O(M) for insertion, O(log(N)) for searching insertion point.

Invalidation

Same as Container::insert.

template <typename InputIterator>
void insert(range_order order, InputIterator first, InputIterator last);

void insert(range_order order, std::initializer_list<value_type> ilist);

Range insertion with ordered or non-ordered range.

Pre requirements

InputIterator should meet InputIterator. If the order is range_order::sorted or range_order::unique_sorted, the ranges should be sorted in Compare order, otherwise the behaviour is undefined.

Complexity

For non sorted range, amortized O((N+E) log(N+E)) if enough additional memory is available, otherwise amortized O((N+E) log^2(N+E)). For sorted range, amortized O(N+E) if enough additional memory is available, otherwise amortized O((N+E) log(N+E)).

Invalidation

Same as Container::insert.

emplace

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

Equivalent to insert(value_type(std::forward<Args>(args)...)).

emplace_hint

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

Equivalent to insert(hint, value_type(std::forward<Args>(args)...)).

erase

iterator erase(iterator pos);

iterator erase(const_iterator pos);

iterator erase(const_iterator first, const_iterator last);

size_type erase(key_type const& key)

Return value

An iterator that next to erased elements.

Complexity

O(M)in first and second form. O(M) for erasing, O(log(N)) for searching target element in third form.

Invalidation

Same as Container::erase.

swap

void swap(flat_multimap& other) noexcept(/* see below */);

Swap elements, allocator, and comparator.

Exceptions

No exception only if it meets all of

• std::allocator_traits<allocator_type>::is_always_equal::value and
• std::is_nothrow_swappable<Compare>::value

extract

node_type extract(const_iterator position);

node_type extract(key_type const& key);

Extract an element and returns it. Unlike std::multimap::extract, move element.

Pre requirements

position should be valid dereferenceable iterator in first form.

Return value

Extracted node handle.

Complexity

O(M) in first form. O(M) for extraction, O(log(N)) for searching target element in second form.

merge

template <typename Comp, typename Allocator>
void merge(std::map<key_type, mapped_type, Comp, Allocator>& source);

template <typename Comp, typename Allocator>
void merge(std::map<key_type, mapped_type, Comp, Allocator>&& source);

template <typename Comp, typename Allocator>
void merge(std::multimap<key_type, mapped_type, Comp, Allocator>& source);

template <typename Comp, typename Allocator>
void merge(std::multimap<key_type, mapped_type, Comp, Allocator>&& source);

template <typename Comp, typename Cont>
void merge(flat_map<key_type, mapped_type, Comp, Cont>& source);

template <typename Comp, typename Cont>
void merge(flat_map<key_type, mapped_type, Comp, Cont>&& source);

template <typename Comp, typename Cont>
void merge(flat_multimap<key_type, mapped_type, Comp, Cont>& source);

template <typename Comp, typename Cont>
void merge(flat_multimap<key_type, mapped_type, Comp, Cont>&& source);

Merge source container into self.

Complexity

Amortized O((N+E) log^2(N+E)).

Lookup

count

size_type count(key_type const& key) const;

template <typename K>
size_type count(K const& key) const;

Count number of elements.

The second form is only participants in overload resolution if the Compare::is_transparent is valid.

Complexity

O(log(N)).

find

iterator find(key_type const& key)

const_iterator find(key_type const& key) const;

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

template <typename K>
const_iterator find(K const& key) const;

Find an element.

The third and fourth form are only participants in overload resolution if the Compare::is_transparent is valid.

Complexity

O(log(N)).

contains

bool contains(key_type const& key) const;

template <typename K>
bool contains(K const& key) const;

The second form are only participants in overload resolution if the Compare::is_transparent is valid.

Complexity

O(log(N)).

equal_range

std::pair<iterator, iterator> equal_range(key_type const& key);

std::pair<const_iterator, const_iterator> equal_range(key_type const& key) const;

template <typename K>
std::pair<iterator, iterator> equal_range(K const& key);

template <typename K>
std::pair<const_iterator, const_iterator> equal_range(K const& key) const;

Returns a range that contains elements with specified key.

The third and fourth form are only participants in overload resolution if the Compare::is_transparent is valid.

Complexity

O(log(N)).

lower_bound

iterator lower_bound(key_type const& key);

const_iterator lower_bound(key_type const& key) const;

template <typename K>
iterator lower_bound(K const& key);

template <typename K>
const_iterator lower_bound(K const& key) const;

Returns an iterator that points to first element which is not less than specified kye.

The third and fourth form are only participants in overload resolution if the Compare::is_transparent is valid.

Complexity

O(log(N)).

upper_bound

iterator upper_bound(key_type const& key);

const_iterator upper_bound(key_type const& key) const;

template <typename K>
iterator upper_bound(K const& key);

template <typename K>
const_iterator upper_bound(K const& key) const;

Returns an iterator that points to first element which is greater than specified kye.

The third and fourth form are only participants in overload resolution if the Compare::is_transparent is valid.

Complexity

O(log(N)).

Observers

key_compare key_comp() const;

value_compare value_comp() const;

Non member functions

operator==

template <typename Key, typename T, typename Compare, typename Container>
bool operator==(flat_multimap<Key, T, Compare, Container> const& lhs, flat_multimap<Key, T, Compare, Container> const& rhs);

Complexity

O(N).

operator!=

template <typename Key, typename T, typename Compare, typename Container>
bool operator!=(flat_multimap<Key, T, Compare, Container> const& lhs, flat_multimap<Key, T, Compare, Container> const& rhs);

Complexity

O(N).

Standard

This function is removed if

• __cpp_impl_three_way_comparison is defined, and
• __cpp_lib_three_way_comparison is defined.

operator<

template <typename Key, typename T, typename Compare, typename Container>
bool operator<(flat_multimap<Key, T, Compare, Container> const& lhs, flat_multimap<Key, T, Compare, Container> const& rhs);

Complexity

O(N).

Standard

This function is removed if

• __cpp_impl_three_way_comparison is defined, and
• __cpp_lib_three_way_comparison is defined.

operator<=

template <typename Key, typename T, typename Compare, typename Container>
bool operator<=(flat_multimap<Key, T, Compare, Container> const& lhs, flat_multimap<Key, T, Compare, Container> const& rhs);

Complexity

O(N).

Standard

This function is removed if

• __cpp_impl_three_way_comparison is defined, and
• __cpp_lib_three_way_comparison is defined.

operator>

template <typename Key, typename T, typename Compare, typename Container>
bool operator>(flat_multimap<Key, T, Compare, Container> const& lhs, flat_multimap<Key, T, Compare, Container> const& rhs);

Complexity

O(N).

Standard

This function is removed if

• __cpp_impl_three_way_comparison is defined, and
• __cpp_lib_three_way_comparison is defined.

operator>=

template <typename Key, typename T, typename Compare, typename Container>
bool operator>=(flat_multimap<Key, T, Compare, Container> const& lhs, flat_multimap<Key, T, Compare, Container> const& rhs);

Complexity

O(N).

Standard

This function is removed if

• __cpp_impl_three_way_comparison is defined, and
• __cpp_lib_three_way_comparison is defined.

operator<=>

template <typename Key, typename T, typename Compare, typename Container>
/* see below */ operator<=>(flat_multimap<Key, T, Compare, Container> const& lhs, flat_multimap<Key, T, Compare, Container> const& rhs);

Return value

std::lexicographical_compare_three_way(lhs.begin(), lhs.end(), rhs.begin(), rhs.end())

Complexity

O(N).

Standard

This function is defined only if

• __cpp_impl_three_way_comparison is defined, and
• __cpp_lib_three_way_comparison is defined.

swap

template <typename Key, typename T, typename Compare, typename Container>
void swap(flat_multimap<Key, T, Compare, Container>& lhs, flat_multimap<Key, T, Compare, Container>& rhs) noexcept(/* see below */);

Exceptions

No exception only if noexcept(lhs.swap(rhs)) is true.

erase_if

template <typename Key, typename T, typename Compare, typename Container, typename Pred>
std::size_t erase_if(flat_multimap<Key, T, Compare, Container>& c, Pred pred);

Erase every elements which pred returned true.

Return value

Number of erased elements.

Complexity

O(N).

Deduction guides

template <typename InputIterator,
          typename Compare = std::less<iter_key_t<InputIterator>>,
          typename Allocator = iter_to_alloc_t<InputIterator>>
flat_multimap(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
  -> flat_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Compare, iter_to_container_t<InputIterator, Allocator>>;

template <typename Key, typename T,
          typename Compare = std::less<Key>,
          typename Allocator = typename std::vector<std::pair<Key, T>>::allocator_type>
flat_multimap(std::initializer_list<std::pair<Key, T>>, Compare = Compare(), Allocator = Allocator())
  -> flat_multimap<Key, T, Compare, std::vector<std::pair<Key, T>, Allocator>>;

template <typename InputIterator, typename Allocator>
flat_multimap(InputIterator, InputIterator, Allocator)
  -> flat_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, std::less<iter_key_t<InputIterator>>, iter_to_container_t<InputIterator, Allocator>>;

template <typename Key, typename T, typename Allocator>
flat_multimap(std::initializer_list<std::pair<Key, T>>, Allocator)
  -> flat_multimap<Key, T, std::less<Key>, std::vector<std::pair<Key, T>, Allocator>>;

First and second form are participants in overload resolution only if Compare doesn't satisfy Allocator, and Allocator satisfies Allocator. Third and fourth form are participants in overload resolution only if Allocator satisfies Allocator.

Where the exposition only type aliases are defined as

template <typename InputIterator>
using iter_key_t = std::remove_const_t<typename std::iterator_traits<InputIterator>::value_type::first_type>;

template <typename InputIterator>
using iter_val_t = typename std::iterator_traits<InputIterator>::value_type::second_type;

template <typename InputIterator>
using iter_to_alloc_t = std::allocator<iter_key_t<InputIterator>, iter_val_t<InputIterator>>;

template <typename InputIterator, typename Allocator>
using iter_to_container_t = std::vector<std::pair<iter_key_t<InputIterator>, iter_val_t<InputIterator>>, Allocator>;

Pre requirements

InputIterator should meet InputIterator.