ext::linear_map

An adaptor map with lookup complexity O(N) based on sequence (contiguous structure by default). More...

#include <linear_map.h>

Public Types

	Name
using Key	key_type <br>Public typedefs.
using Value	mapped_type
using std::pair< key_type, mapped_type >	value_type
using Sequence< value_type >	container_type
using typename container_type::pointer	pointer <br>Iterator-related typedefs redeclared from the underlying container type.
using typename container_type::const_pointer	const_pointer
using typename container_type::reference	reference
using typename container_type::const_reference	const_reference
using typename container_type::iterator	iterator
using typename container_type::const_iterator	const_iterator
using typename container_type::reverse_iterator	reverse_iterator
using typename container_type::const_reverse_iterator	const_reverse_iterator
using typename container_type::size_type	size_type
using typename container_type::difference_type	difference_type

Public Functions

	Name
	linear_map() =default<br>Standard constructors (copy and move are implicit).
	linear_map(std::initializer_list< value_type > init_list)
template <typename Iterator > <br>	linear_map(Iterator first1, Iterator last1)
const_iterator	find(const key_type & key) const<br>Finds an entry in the map.
iterator	find(const key_type & key)
mapped_type &	operator[](const key_type & key)<br>Accesses an existing or default constructed entry.
mapped_type &	operator[](key_type && key)
const mapped_type &	at(const key_type & key) const<br>Accesses the value of the entry.
mapped_type &	at(const key_type & key)
std::pair< iterator, bool >	insert(const value_type & p)<br>Inserts a key-value pair into the map if the pair is not in the map.
std::pair< iterator, bool >	insert(value_type && p)
iterator	erase(const_iterator pos)<br>Erases the entry pointed by an iterator.
iterator	erase(iterator pos)
container_type &	data()
const container_type &	data() const
const_iterator	cbegin() const
const_iterator	begin() const
const_iterator	cend() const
const_iterator	end() const
reverse_iterator	rbegin()<br>Corresponding reverse iterators.
reverse_iterator	rend()
const_reverse_iterator	crbegin() const
const_reverse_iterator	rbegin() const
const_reverse_iterator	crend() const
const_reverse_iterator	rend() const
size_type	count(const key_type & key) const<br>Determines if an entry with the given key in the map.
template <typename Iterator > <br>void	insert(Iterator first1, Iterator last1)<br>Inserts a range of elements.
template <typename... Ts> <br>std::pair< iterator, bool >	emplace(Ts &&... args)<br>Attempts to build and insert an entry.
size_type	erase(const key_type & key)<br>Erases the entry with a key.
void	swap(linear_map & other)<br>Swaps data with another linear map.
size_type	size() const
bool	empty() const
void	clear()<br>Erases all entries in the map.
void	reserve(size_type n)<br>Prepares the linear map for a specified number of entries.
size_type	capacity() const
iterator	begin()
iterator	end()

Friends

	Name
bool	operator==(const linear_map & lhs, const linear_map & rhs) <br>Non-member equality test operators.
bool	operator!=(const linear_map & lhs, const linear_map & rhs)
void	swap(linear_map & lhs, linear_map & rhs) <br>Friend swap definition for convenience sake.

Detailed Description

cpp

template <typename Key ,
typename Value ,
class ErasePolicy  =DefaultEraser,
template< typename... > class Sequence =std::vector>
class ext::linear_map;

An adaptor map with lookup complexity O(N) based on sequence (contiguous structure by default).

Template Parameters:

Key The type of the unique keys.
Value The type of the values associated with the keys.
ErasePolicy The policy class that provides erase(it, *container) static member function to control the element erasure from the container.
Sequence The underlying container type.

This map is designed for a small number of elements and for small <Key, Value> size pairs. Consider this class a convenient wrapper around std::vector<std::pair<Key, Value>>.

Since this map is based on the vector by default, the order of insertions is preserved, and it provides random access iterators.

The major differences from the standard library maps:

The entry is std::pair<Key, Value> instead of std::pair<const Key, Value>, which means that the key can be modified as long as it stays unique.
Iterators, references, pointers can be invalidated by modifier functions (insert, erase, reserve, etc.). This is the inherited behavior from std::vector.
Some API may be extra or missing.

The performance of the map critically depends on the number of entries, the size of the key-value pair, and the cost of comparing keys for equality. The advantage of the linear_map comes from cache-friendliness, and fewer CPU front-end and back-end stalls.

From crude experimental results with random entries comparing with std::map, std::unordered_map, boost::flat_map:

For Key=int, Value=Object, sizeof(Object)=24, the linear_map outperforms up to 50 entries.
For Key=std::string(20 char), Value=Object, sizeof(Object)=24, the linear_map performs equally well up to 10 entries.

Public Types Documentation

using key_type

cpp

using ext::linear_map< Key, Value, ErasePolicy, Sequence >::key_type =  Key;

Public typedefs.

using mapped_type

cpp

using ext::linear_map< Key, Value, ErasePolicy, Sequence >::mapped_type =  Value;

using value_type

cpp

using ext::linear_map< Key, Value, ErasePolicy, Sequence >::value_type =  std::pair<key_type, mapped_type>;

using container_type

cpp

using ext::linear_map< Key, Value, ErasePolicy, Sequence >::container_type =  Sequence<value_type>;

using pointer

cpp

using ext::linear_map< Key, Value, ErasePolicy, Sequence >::pointer =  typename container_type::pointer;

Iterator-related typedefs redeclared from the underlying container type.

using const_pointer

cpp

using ext::linear_map< Key, Value, ErasePolicy, Sequence >::const_pointer =  typename container_type::const_pointer;

using reference

cpp

using ext::linear_map< Key, Value, ErasePolicy, Sequence >::reference =  typename container_type::reference;

using const_reference

cpp

using ext::linear_map< Key, Value, ErasePolicy, Sequence >::const_reference =  typename container_type::const_reference;

using iterator

cpp

using ext::linear_map< Key, Value, ErasePolicy, Sequence >::iterator =  typename container_type::iterator;

using const_iterator

cpp

using ext::linear_map< Key, Value, ErasePolicy, Sequence >::const_iterator =  typename container_type::const_iterator;

using reverse_iterator

cpp

using ext::linear_map< Key, Value, ErasePolicy, Sequence >::reverse_iterator =  typename container_type::reverse_iterator;

using const_reverse_iterator

cpp

using ext::linear_map< Key, Value, ErasePolicy, Sequence >::const_reverse_iterator =  typename container_type::const_reverse_iterator;

using size_type

cpp

using ext::linear_map< Key, Value, ErasePolicy, Sequence >::size_type =  typename container_type::size_type;

using difference_type

cpp

using ext::linear_map< Key, Value, ErasePolicy, Sequence >::difference_type =  typename container_type::difference_type;

Public Functions Documentation

function linear_map

cpp

linear_map() =default

Standard constructors (copy and move are implicit).

function linear_map

cpp

inline linear_map(
    std::initializer_list< value_type > init_list
)

function linear_map

cpp

template <typename Iterator >
inline linear_map(
    Iterator first1,
    Iterator last1
)

function find

cpp

inline const_iterator find(
    const key_type & key
) const

Finds an entry in the map.

Parameters:

key The key of the entry.

Return: Iterator pointing to the entry, or end() if not found.

function find

cpp

inline iterator find(
    const key_type & key
)

function operator[]

cpp

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

Accesses an existing or default constructed entry.

Parameters:

key The key of the entry.

Return: A reference to the value of the entry.

function operator[]

cpp

inline mapped_type & operator[](
    key_type && key
)

function at

cpp

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

Accesses the value of the entry.

Parameters:

key The key of the entry.

Exceptions:

std::out_of_range The entry is not in the map.

Return: The reference to the value.

function at

cpp

inline mapped_type & at(
    const key_type & key
)

function insert

cpp

inline std::pair< iterator, bool > insert(
    const value_type & p
)

Inserts a key-value pair into the map if the pair is not in the map.

Parameters:

p The entry.

Return: A pair of an iterator and insertion flag. The iterator points to possibly inserted entry, and the flag indicates whether the entry is actually inserted.

function insert

cpp

inline std::pair< iterator, bool > insert(
    value_type && p
)

function erase

cpp

inline iterator erase(
    const_iterator pos
)

Erases the entry pointed by an iterator.

Parameters:

pos An iterator pointing to the entry.

Return: An iterator pointing after the entry.

function erase

cpp

inline iterator erase(
    iterator pos
)

function data

cpp

inline container_type & data()

Return: The underlying data container. The container elements are ordered exactly as inserted.

function data

cpp

inline const container_type & data() const

function cbegin

cpp

inline const_iterator cbegin() const

Return: A read-only iterator pointing to the first entry.

function begin

cpp

inline const_iterator begin() const

function cend

cpp

inline const_iterator cend() const

Return: A read-only iterator pointing one past the last entry.

function end

cpp

inline const_iterator end() const

function rbegin

cpp

inline reverse_iterator rbegin()

Corresponding reverse iterators.

function rend

cpp

inline reverse_iterator rend()

function crbegin

cpp

inline const_reverse_iterator crbegin() const

function rbegin

cpp

inline const_reverse_iterator rbegin() const

function crend

cpp

inline const_reverse_iterator crend() const

function rend

cpp

inline const_reverse_iterator rend() const

function count

cpp

inline size_type count(
    const key_type & key
) const

Determines if an entry with the given key in the map.

Parameters:

key The key of the entry.

Return: 1 if there's an entry, 0 otherwise.

function insert

cpp

template <typename Iterator >
inline void insert(
    Iterator first1,
    Iterator last1
)

Inserts a range of elements.

Parameters:

first1 The beginning of the range.
last1 The end of the range.

Template Parameters:

Iterator Iterator to the container with key-value pairs.

The range is not assumed to be unique.

function emplace

cpp

template <typename... Ts>
inline std::pair< iterator, bool > emplace(
    Ts &&... args
)

Attempts to build and insert an entry.

Parameters:

args Arguments for the construction of the entry.

Return: An iterator pointing to the entry, and a flag indicating if the insertion actually happened.

function erase

cpp

inline size_type erase(
    const key_type & key
)

Erases the entry with a key.

Parameters:

key The key of the entry.

Return: 1 if the existing entry has been removed, 0 if there's no entry with the given key.

function swap

cpp

inline void swap(
    linear_map & other
)

Swaps data with another linear map.

Parameters:

other Another linear map.

function size

cpp

inline size_type size() const

Return: The number of entries in the map.

function empty

cpp

inline bool empty() const

Return: true if there are no entries.

function clear

cpp

inline void clear()

Erases all entries in the map.

function reserve

cpp

inline void reserve(
    size_type n
)

Prepares the linear map for a specified number of entries.

Parameters:

n The number of expected entries.

function capacity

cpp

inline size_type capacity() const

Return: The capacity of the underlying container.

function begin

cpp

inline iterator begin()

Return: A read/write iterator pointing to the first entry.

function end

cpp

inline iterator end()

Return: A read/write iterator pointing one past the last entry.

Friends

friend operator==

cpp

friend bool operator==(
    const linear_map & lhs,

    const linear_map & rhs
);

Non-member equality test operators.

Parameters:

lhs First map.
rhs Second map.

Note: The order of elements is not relevant. If the order matters for equality, compare the underlying data containers directly.

The complexity is O(N^2).

friend operator!=

cpp

friend bool operator!=(
    const linear_map & lhs,

    const linear_map & rhs
);

friend swap

cpp

friend void swap(
    linear_map & lhs,

    linear_map & rhs
);

Friend swap definition for convenience sake.

Updated on 2026-01-09 at 21:59:12 +0000

ext::linear_map ​

Public Types ​

Public Functions ​

Friends ​

Detailed Description ​

Public Types Documentation ​

using key_type ​

using mapped_type ​

using value_type ​

using container_type ​

using pointer ​

using const_pointer ​

using reference ​

using const_reference ​

using iterator ​

using const_iterator ​

using reverse_iterator ​

using const_reverse_iterator ​

using size_type ​

using difference_type ​

Public Functions Documentation ​

function linear_map ​

function linear_map ​

function linear_map ​

function find ​

function find ​

function operator[] ​

function operator[] ​

function at ​

function at ​

function insert ​

function insert ​

function erase ​

function erase ​

function data ​

function data ​

function cbegin ​

function begin ​

function cend ​

function end ​

function rbegin ​

function rend ​

function crbegin ​

function rbegin ​

function crend ​

function rend ​

function count ​

function insert ​

function emplace ​

function erase ​

function swap ​

function size ​

function empty ​

function clear ​

function reserve ​

function capacity ​

function begin ​

function end ​

Friends ​

friend operator== ​

friend operator!= ​

friend swap ​

ext::linear_map

Public Types

Public Functions

Friends

Detailed Description

Public Types Documentation

using key_type

using mapped_type

using value_type

using container_type

using pointer

using const_pointer

using reference

using const_reference

using iterator

using const_iterator

using reverse_iterator

using const_reverse_iterator

using size_type

using difference_type

Public Functions Documentation

function linear_map

function linear_map

function linear_map

function find

function find

function operator[]

function operator[]

function at

function at

function insert

function insert

function erase

function erase

function data

function data

function cbegin

function begin

function cend

function end

function rbegin

function rend

function crbegin

function rbegin

function crend

function rend

function count

function insert

function emplace

function erase

function swap

function size

function empty

function clear

function reserve

function capacity

function begin

function end

Friends

friend operator==

friend operator!=

friend swap