flat_map

#include <flat_map/flat_map.hpp>

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

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 */;
using insert_return_type = struct /* unspecified */
{
    iterator  position;
    bool      inserted;
    node_type node;
};

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_map();

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

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

template <typename InputIterator>
flat_map(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_map(flat_map const& other);

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

Copy from other.

flat_map(flat_map&& other);

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

Move entire elements from other.

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

flat_map(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_map(range_order order, Container const& cont);
explicit flat_map(range_order order, Container const& cont, Compare const& comp, allocator_type const& alloc = allocator_type());
explicit flat_map(range_order order, Container const& cont, allocator_type const& alloc);
explicit flat_map(range_order order, Container&& cont);
explicit flat_map(range_order order, Container&& cont, Compare const& comp, allocator_type const& alloc = allocator_type());
explicit flat_map(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, and uniqued range O(1), otherwise O(E).

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_map& operator=(flat_map const& other);

Copy from other.

flat_map& operator=(flat_map&& 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_map& operator=(std::initializer_list<value_type> ilist);

Complexity

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

Element access

at

mapped_type const& at(key_type const& key) const;
mapped_type& at(key_type const& key);

Exceptions

Throws std::out_of_range only if key is not found.

Complexity

O(log(N)).

operator[]

mapped_type& operator[](key_type const& key);
mapped_type& operator[](key_type&& key);

Complexity

Amortized O(log(N)).

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();

This Available 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

std::pair<iterator, bool> insert(value_type const& value);

template <typename V>
std::pair<iterator, bool> insert(V&& value);

std::pair<iterator, bool> 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 or the element which has same key, bool denotes whether the insertion is succeeded.

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 or the element which has same key.

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.

insert_return_type 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 or the element which has same key.

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.

insert_or_assign

template <typename M>
std::pair<iterator, bool> insert_or_assign(key_type const& key, M&& obj);

template <typename M>
std::pair<iterator, bool> insert_or_assign(key_type&& key, M&& obj);

template <typename M>
iterator insert_or_assign(const_iterator hint, key_type const& key, M&& obj);

template <typename M>
iterator insert_or_assign(const_iterator hint, key_type&& key, M&& obj);

Same as insert() except replace with obj if key is always exists.

emplace

template <typename... Args>
std::pair<iterator, bool> 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)...)).

try_emplace

template <typename... Args>
std::pair<iterator, bool> try_emplace(key_type const& key, Args&&... args);

template <typename... Args>
std::pair<iterator, bool> try_emplace(key_type&& key, Args&&... args);

template <typename... Args>
iterator try_emplace(const_iterator hint, key_type const& key, Args&&... args);

template <typename... Args>
iterator try_emplace(const_iterator hint, key_type&& key, Args&&... args);

Equivalent to insert(value_type(key, std::forward<Args>(args)...)) in first and second form. Equivalent to insert(hint, value_type(key, std::forward<Args>(args)...)) in third and fourth form.

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_map& 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::map::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(M E) for insertion. O(N+E) for searching insertion point if source ordered in same order, otherwise O(E log(N)).

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_map<Key, T, Compare, Container> const& lhs, flat_map<Key, T, Compare, Container> const& rhs);

Complexity

O(N).

operator!=

template <typename Key, typename T, typename Compare, typename Container>
bool operator!=(flat_map<Key, T, Compare, Container> const& lhs, flat_map<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_map<Key, T, Compare, Container> const& lhs, flat_map<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_map<Key, T, Compare, Container> const& lhs, flat_map<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_map<Key, T, Compare, Container> const& lhs, flat_map<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_map<Key, T, Compare, Container> const& lhs, flat_map<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_map<Key, T, Compare, Container> const& lhs, flat_map<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_map<Key, T, Compare, Container>& lhs, flat_map<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_map<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_map(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
  -> flat_map<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_map(std::initializer_list<std::pair<Key, T>>, Compare = Compare(), Allocator = Allocator())
  -> flat_map<Key, T, Compare, std::vector<std::pair<Key, T>, Allocator>>;

template <typename InputIterator, typename Allocator>
flat_map(InputIterator, InputIterator, Allocator)
  -> flat_map<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_map(std::initializer_list<std::pair<Key, T>>, Allocator)
  -> flat_map<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.

Files

flat_map.md

Latest commit

History

flat_map.md

File metadata and controls

flat_map

Member types

Member classes

Constructor

Operator

Constructors

Assignments

Element access

at

operator[]

Iterators

begin

cbegin

end

cend

rbegin

crbegin

rend

crend

Capacity

empty

size

max_size

reserve

capacity

shrink_to_fit

Modifiers

clear

insert

insert_or_assign

emplace

emplace_hint

try_emplace

erase

swap

extract

merge

Lookup

count

find

contains

equal_range

lower_bound

upper_bound

Observers

Non member functions

operator==

operator!=

operator<

operator<=

operator>

operator>=

operator<=>

swap

erase_if

Deduction guides