API Documentation

We provide three user-facing implementations of ALEX:

AlexMap is a near drop-in replacement for std::map.
AlexMultiMap is a near drop-in replacement for std::multimap.
Alex is the internal implementation that supports both AlexMap and AlexMultimap. It exposes slightly more functionality.

ALEX has a few important differences compared to its standard library equivalents:

Keys and payloads (i.e., the mapped type) are stored separately, so dereferencing an iterator returns a copy of the key/payload pair, not return a reference. Our iterators have methods to directly return references to the key or payload individually.
The iterators are of type ForwardIterator, instead of BidirectionalIterator. Therefore, iterators do not support decrementing.
Currently, we only support numerical key types. We do not support arbitrary user-defined key types. As a result, you should not change the default comparison function in the class template.

AlexMap Documentation
AlexMultiMap Documentation
Alex Documentation

AlexMap Documentation

AlexMap is a near drop-in replacement for std::map.

// T is the key type, and P is the payload type (i.e., the mapped type).
template <class T, class P, class Compare = AlexCompare, class Alloc = std::allocator<std::pair<T,P>>>
class AlexMap;

Constructors and Copy

// Default constructor.
AlexMap();

// Initializes an empty ALEX with a special key comparison object or allocator.
AlexMap(const Compare& comp, const Alloc& alloc = Alloc());
AlexMap(const Alloc& alloc);

// Initializes with range [first, last). The range does not need to be
// sorted. This creates a temporary copy of the data. If possible, we
// recommend directly using bulk_load() instead.
template <class InputIterator>
AlexMap(InputIterator first, InputIterator last, const Compare& comp, const Alloc& alloc = Alloc());
template <class InputIterator>
AlexMap(InputIterator first, InputIterator last, const Alloc& alloc = Alloc());

// Copy constructor. The newly initialized ALEX will contain a copy of all key/payload pairs.
AlexMap(const AlexMap& other);

// Assignment operator. All the key/payload pairs are copied.
AlexMap& operator=(const AlexMap& other);

// Bulk loads a sorted array of key-payload pairs.
// The index must be empty when calling this method.
void bulk_load(const V values[], int num_keys);

Iterators

iterator begin();

iterator end();

const_iterator cbegin() const;

const_iterator cend() const;

reverse_iterator rbegin();

reverse_iterator rend();

const_reverse_iterator crbegin() const;

const_reverse_iterator crend() const;

Capacity

// Returns true if there are no elements in the container.
bool empty() const;

// Returns number of elements in the container.
size_t size() const;

Element access

// If the input key matches the key of an element in the container,
// the function returns a reference to its payload.
// If the input key does not match the key of any element in the container,
// the function inserts a new element with that key and returns a reference
// to its payload.
P& operator[] (const T& key);

// If the input key matches the key of an element in the container,
// the function returns a reference to its payload.
// If the input key does not match the key of any element in the container,
// the function throws an exception.
P& at(const T& key);
const P& at(const T& key) const;

Modifiers

// If the input key does not already exist in the container, this function inserts
// the value and returns an iterator to the inserted element and the boolean true.
// If the input key already exists in the container, no insert occurs and this
// function returns an iterator to the existing element with that key and the boolean
// false.
std::pair<iterator, bool> insert(const V& value);

// Same as above.
std::pair<iterator, bool> insert(const T& key, const P& payload);

// Inserts all elements in [first, last).
template <class InputIterator>
void insert(InputIterator first, InputIterator last);

// Erases all keys with a certain key value.
int erase(const T& key);

// Erases element pointed to by iterator.
void erase(iterator it);

// Swaps all content of this container with another.
void swap(const AlexMap& other);

// Removes all elements.
void clear();

Operations

// If the key exists, returns an iterator to its element.
// Otherwise, returns iterator to end.
iterator find(const T& key);
const_iterator find(const T& key) const;

// Returns number of elements with the input key.
size_t count(const T& key);

// Returns iterator to the first element whose key is not
// less than the input key.
iterator lower_bound(const T& key);
const_iterator lower_bound(const T& key) const;

// Returns iterator to the first element whose key is greater
// than the input key.
iterator upper_bound(const T& key);
const_iterator upper_bound(const T& key) const;

// Returns the bounds of a range that includes all the elements
// which have a key equivalent to the input key.
std::pair<iterator, iterator> equal_range(const T& key);
std::pair<const_iterator, const_iterator> equal_range(const T& key) const;

Observers and allocator

Compare key_comp() const;

Alloc get_allocator() const;

Custom methods with no STL equivalents

const struct Stats& get_stats() const;

AlexMultiMap Documentation

AlexMultimap is a near drop-in replacement for std::multimap.

// T is the key type, and P is the payload type (i.e., the mapped type).
template <class T, class P, class Compare = AlexCompare, class Alloc = std::allocator<std::pair<T,P>>>
class AlexMultimap;

Constructors and Copy

// Default constructor.
AlexMultimap();

// Initializes an empty ALEX with a special key comparison object or allocator.
AlexMultimap(const Compare& comp, const Alloc& alloc = Alloc());
AlexMultimap(const Alloc& alloc);

// Initializes with range [first, last). The range does not need to be
// sorted. This creates a temporary copy of the data. If possible, we
// recommend directly using bulk_load() instead.
template <class InputIterator>
AlexMultimap(InputIterator first, InputIterator last, const Compare& comp, const Alloc& alloc = Alloc());
template <class InputIterator>
AlexMultimap(InputIterator first, InputIterator last, const Alloc& alloc = Alloc());

// Copy constructor. The newly initialized ALEX will contain a copy of all key/payload pairs.
AlexMultimap(const AlexMap& other);

// Assignment operator. All the key/payload pairs are copied.
AlexMultimap& operator=(const AlexMap& other);

// Bulk loads a sorted array of key-payload pairs.
// The index must be empty when calling this method.
void bulk_load(const V values[], int num_keys);

Iterators

iterator begin();

iterator end();

const_iterator cbegin() const;

const_iterator cend() const;

reverse_iterator rbegin();

reverse_iterator rend();

const_reverse_iterator crbegin() const;

const_reverse_iterator crend() const;

Capacity

// Returns true if there are no elements in the container.
bool empty() const;

// Returns number of elements in the container.
size_t size() const;

Modifiers

// Inserts the value and returns an iterator to it.
iterator insert(const V& value);

// Same as above.
iterator insert(const T& key, const P& payload);

// Inserts all elements in [first, last).
template <class InputIterator>
void insert(InputIterator first, InputIterator last);

// Erases all keys with a certain key value.
int erase(const T& key);

// Erases element pointed to by iterator.
void erase(iterator it);

// Swaps all content of this container with another.
void swap(const AlexMap& other);

// Removes all elements.
void clear();

Operations

// If the key exists, returns an iterator to its element.
// Otherwise, returns iterator to end.
iterator find(const T& key);
const_iterator find(const T& key) const;

// Returns number of elements with the input key.
size_t count(const T& key);

// Returns iterator to the first element whose key is not
// less than the input key.
iterator lower_bound(const T& key);
const_iterator lower_bound(const T& key) const;

// Returns iterator to the first element whose key is greater
// than the input key.
iterator upper_bound(const T& key);
const_iterator upper_bound(const T& key) const;

// Returns the bounds of a range that includes all the elements
// which have a key equivalent to the input key.
std::pair<iterator, iterator> equal_range(const T& key);
std::pair<const_iterator, const_iterator> equal_range(const T& key) const;

Observers and allocator

Compare key_comp() const;

Alloc get_allocator() const;

Custom methods with no STL equivalents

const struct Stats& get_stats() const;

Alex Documentation

Alex is the internal implementation that supports both AlexMap and AlexMultimap. It exposes slightly more functionality. In particular, the Alex class allows you to access the payload of a key directly using get_payload(), without the overhead of constructing an iterator.

// T is the key type, and P is the payload type (i.e., the mapped type).
template <class T, class P, class Compare = AlexCompare, class Alloc = std::allocator<std::pair<T,P>>, bool allow_duplicates = true>
class Alex;

Constructors and Copy

// Default constructor.
Alex();

// Initializes an empty ALEX with a special key comparison object or allocator.
Alex(const Compare& comp, const Alloc& alloc = Alloc());
Alex(const Alloc& alloc);

// Initializes with range [first, last). The range does not need to be
// sorted. This creates a temporary copy of the data. If possible, we
// recommend directly using bulk_load() instead.
template <class InputIterator>
Alex(InputIterator first, InputIterator last, const Compare& comp, const Alloc& alloc = Alloc());
template <class InputIterator>
Alex(InputIterator first, InputIterator last, const Alloc& alloc = Alloc());

// Copy constructor. The newly initialized ALEX will contain a copy of all key/payload pairs.
Alex(const AlexMap& other);

// Assignment operator. All the key/payload pairs are copied.
Alex& operator=(const AlexMap& other);

// Bulk loads a sorted array of key-payload pairs.
// The index must be empty when calling this method.
void bulk_load(const V values[], int num_keys);

Iterators

iterator begin();

iterator end();

const_iterator cbegin() const;

const_iterator cend() const;

reverse_iterator rbegin();

reverse_iterator rend();

const_reverse_iterator crbegin() const;

const_reverse_iterator crend() const;

Capacity

// Returns true if there are no elements in the container.
bool empty() const;

// Returns number of elements in the container.
size_t size() const;

Modifiers

// If allow_duplicates is true, then this function follows the behavior
// of AlexMultimap::insert and always sets the second element of the
// returned pair to true.
// If allow_duplicates is false, then this function follows the behavior
// of AlexMap::insert.
std::pair<iterator, bool> insert(const V& value);

// Same as above.
std::pair<iterator, bool> insert(const T& key, const P& payload);

// Inserts all elements in [first, last).
template <class InputIterator>
void insert(InputIterator first, InputIterator last);

// Erases all keys with a certain key value.
int erase(const T& key);

// Erases the left-most key with the given key value.
int erase_one(const T& key);

// Erases element pointed to by iterator.
void erase(iterator it);

// Swaps all content of this container with another.
void swap(const AlexMap& other);

// Removes all elements.
void clear();

Operations

// If the key exists, returns an iterator to its element.
// Otherwise, returns iterator to end.
iterator find(const T& key);
const_iterator find(const T& key) const;

// Returns number of elements with the input key.
size_t count(const T& key);

// Returns iterator to the first element whose key is not
// less than the input key.
iterator lower_bound(const T& key);
const_iterator lower_bound(const T& key) const;

// Returns iterator to the first element whose key is greater
// than the input key.
iterator upper_bound(const T& key);
const_iterator upper_bound(const T& key) const;

// Returns the bounds of a range that includes all the elements
// which have a key equivalent to the input key.
std::pair<iterator, iterator> equal_range(const T& key);
std::pair<const_iterator, const_iterator> equal_range(const T& key) const;

// Directly returns a pointer to the payload found through find(key)
// This avoids the overhead of creating an iterator
// Returns null pointer if there is no exact match of the key
P* get_payload(const T& key) const;

// Looks for the last key no greater than the input value
// Conceptually, this is equal to the last key before upper_bound()
iterator find_last_no_greater_than(const T& key);

// Directly returns a pointer to the payload found through
// find_last_no_greater_than(key)
// This avoids the overhead of creating an iterator
P* get_payload_last_no_greater_than(const T& key);

Observers and allocator

Compare key_comp() const;

Alloc get_allocator() const;

Custom methods with no STL equivalents

const struct Stats& get_stats() const;

// Size in bytes of all the model nodes (including pointers) and metadata in data nodes
long long model_size() const;

// Size in bytes of all the keys, payloads, and bitmaps stored in this index
long long data_size() const;

API Documentation

Table of Contents

AlexMap Documentation

Constructors and Copy

Iterators

Capacity

Element access

Modifiers

Operations

Observers and allocator

Custom methods with no STL equivalents

AlexMultiMap Documentation

Constructors and Copy

Iterators

Capacity

Modifiers

Operations

Observers and allocator

Custom methods with no STL equivalents

Alex Documentation

Constructors and Copy

Iterators

Capacity

Modifiers

Operations

Observers and allocator

Custom methods with no STL equivalents