-
Notifications
You must be signed in to change notification settings - Fork 129
API Documentation
Jialin Ding edited this page Jun 14, 2020
·
9 revisions
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 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.
AlexMap Documentation
AlexMultiMap Documentation
Alex 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;// 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);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;// Returns true if there are no elements in the container.
bool empty() const;
// Returns number of elements in the container.
size_t size() const;// 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;// 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();// 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;Compare key_comp() const;
Alloc get_allocator() const;const struct Stats& get_stats() const;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;// 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);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;// Returns true if there are no elements in the container.
bool empty() const;
// Returns number of elements in the container.
size_t size() const;// 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();// 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;Compare key_comp() const;
Alloc get_allocator() const;const struct Stats& get_stats() const;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;// 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);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;// Returns true if there are no elements in the container.
bool empty() const;
// Returns number of elements in the container.
size_t size() const;// 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();// 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);Compare key_comp() const;
Alloc get_allocator() const;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();