API Documentation

API Documentation

We provide three user-facing implementations of ALEX:

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

ALEX has a few important differences 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.
• The internal comparison object (passed as Compare in the class template) must support comparisons between arbitrary numerical types, instead of just the key type. This is because our models output double-precision floating point numbers, so we must compare the key type against doubles.

Table of Contents

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

// Constructor initializing 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

bool empty() const;

size_t size() const;

size_t max_size() const;

Element access

P& operator[] (const T& key);

P& at(const T& key);

Modifiers

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

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

std::pair<iterator, bool> insert(const T& key, const P& payload);

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

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

void swap(const AlexMap& other);

// Removes all elements
void clear();

Operations

iterator find(const T& key);

size_t count(const T& key);

iterator lower_bound(const T& key);

iterator upper_bound(const T& key);

std::pair<iterator, iterator> equal_range(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;

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

// Constructor initializing 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

bool empty() const;

size_t size() const;

size_t max_size() const;

Modifiers

iterator insert(const V& value);

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

iterator insert(const T& key, const P& payload);

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

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

void swap(const AlexMap& other);

// Removes all elements
void clear();

Operations

iterator find(const T& key);

size_t count(const T& key);

iterator lower_bound(const T& key);

iterator upper_bound(const T& key);

std::pair<iterator, iterator> equal_range(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;

Alex Documentation

Alex is the internal implementation that supports both AlexMap and AlexMultimap. It exposes slightly more functionality.

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

// Constructor initializing 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

bool empty() const;

size_t size() const;

size_t max_size() const;

Modifiers

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

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

std::pair<iterator, bool> insert(const T& key, const P& payload);

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

void swap(const AlexMap& other);

// Removes all elements
void clear();

Operations

iterator find(const T& key);

size_t count(const T& key);

iterator lower_bound(const T& key);

iterator upper_bound(const T& key);

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

// 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)

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

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