-
Notifications
You must be signed in to change notification settings - Fork 111
API Documentation
Jialin Ding edited this page Feb 10, 2021
·
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 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 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. 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;// 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() const;
// Size in bytes of all the keys, payloads, and bitmaps stored in this index
long long data_size() const;