class btree

template <typename Params>

class btree

Defined at line 1317 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

Public Methods

void btree<Params> (const key_compare & comp, const allocator_type & alloc)

Defined at line 1401 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

void btree<Params> (const btree<Params> & other)

Defined at line 1404 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

void btree<Params> (const btree<Params> & other, const allocator_type & alloc)

Defined at line 1405 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

void btree<Params> (btree<Params> && other)

Defined at line 1409 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

void btree<Params> (btree<Params> && other, const allocator_type & alloc)

Defined at line 1415 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

void ~btree<Params> ()

Defined at line 1425 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

iterator begin ()

Defined at line 1436 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

const_iterator begin ()

Defined at line 1437 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

iterator end ()

Defined at line 1438 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

const_iterator end ()

Defined at line 1439 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

reverse_iterator rbegin ()

Defined at line 1442 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

const_reverse_iterator rbegin ()

Defined at line 1443 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

reverse_iterator rend ()

Defined at line 1446 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

const_reverse_iterator rend ()

Defined at line 1447 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

template <typename K>
iterator lower_bound (const K & key)

Finds the first element whose key is not less than `key`.

Defined at line 1453 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

template <typename K>
const_iterator lower_bound (const K & key)

Defined at line 1457 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

template <typename K>
iterator upper_bound (const K & key)

Finds the first element whose key is greater than `key`.

Defined at line 1468 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

template <typename K>
const_iterator upper_bound (const K & key)

Defined at line 1472 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

template <typename K>
std::pair<const_iterator, const_iterator> equal_range (const K & key)

Defined at line 1482 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

template <typename ValueType>
iterator insert_multi (ValueType && v)

Inserts a value into the btree.

Defined at line 1522 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

template <typename K>
iterator find (const K & key)

Finds an element with key equivalent to `key` or returns `end()` if `key`

is not present.

Defined at line 1551 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

template <typename K>
const_iterator find (const K & key)

Defined at line 1555 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

const key_compare & key_comp ()

Defined at line 1565 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

template <typename K1, typename K2>
bool compare_keys (const K1 & a, const K2 & b)

Defined at line 1569 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

value_compare value_comp ()

Defined at line 1573 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

size_type size ()

Size routines.

Defined at line 1581 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

size_type max_size ()

Defined at line 1582 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

bool empty ()

Defined at line 1583 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

size_type height ()

The height of the btree. An empty tree will have height 0.

Defined at line 1586 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

size_type leaf_nodes ()

The number of internal, leaf and total nodes used by the btree.

Defined at line 1603 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

size_type internal_nodes ()

Defined at line 1604 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

size_type nodes ()

Defined at line 1607 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

size_type bytes_used ()

The total number of bytes used by the btree.

TODO(b/169338300): update to support node_btree_*.

Defined at line 1614 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

double average_bytes_per_value ()

The average number of bytes used per value stored in the btree assuming

random insertion order.

Defined at line 1626 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

double fullness ()

The fullness of the btree. Computed as the number of elements in the btree

divided by the maximum number of elements a tree with the current number

of nodes could hold. A value of 1 indicates perfect space

utilization. Smaller values indicate space wastage.

Returns 0 for empty trees.

Defined at line 1638 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

double overhead ()

The overhead of the btree structure in bytes per node. Computed as the

total number of bytes used by the btree minus the number of bytes used for

storing elements divided by the number of elements.

Returns 0 for empty trees.

Defined at line 1646 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

allocator_type get_allocator ()

The allocator used by the btree.

Defined at line 1653 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

btree<Params> & operator= (const btree<Params> & other)

Assign the contents of other to *this.

Defined at line 2390 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

btree<Params> & operator= (btree<Params> && other)

Defined at line 2406 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

template <typename K>
std::pair<iterator, bool> lower_bound_equal (const K & key)

Finds the first element whose key is not less than `key` and also returns

whether that element is equal to `key`.

Defined at line 2233 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

template <typename K>
std::pair<iterator, iterator> equal_range (const K & key)

Finds the range of values which compare equal to key. The first member of

the returned pair is equal to lower_bound(key). The second member of the

pair is equal to upper_bound(key).

Defined at line 2246 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

template <typename K, typename... Args>
std::pair<iterator, bool> insert_unique (const K & key, Args &&... args)

Inserts a value into the btree only if it does not already exist. The

boolean return value indicates whether insertion succeeded or failed.

Requirement: if `key` already exists in the btree, does not consume `args`.

Requirement: `key` is never referenced after consuming `args`.

Defined at line 2275 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

template <typename K, typename... Args>
std::pair<iterator, bool> insert_hint_unique (iterator position, const K & key, Args &&... args)

Inserts with hint. Checks to see if the value should be placed immediately

before `position` in the tree. If so, then the insertion will take

amortized constant time. If not, the insertion will take amortized

logarithmic time as if a call to insert_unique() were made.

Requirement: if `key` already exists in the btree, does not consume `args`.

Requirement: `key` is never referenced after consuming `args`.

Defined at line 2301 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

template <typename InputIterator, typename = decltype(std::declval<const key_compare &>()(
                                    params_type::key(*std::declval<InputIterator>()),
                                    std::declval<const key_type &>()))>
void insert_iterator_unique (InputIterator b, InputIterator e, int )

Insert a range of values into the btree.

Note: the first overload avoids constructing a value_type if the key

already exists in the btree.

Defined at line 2326 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

template <typename InputIterator>
void insert_iterator_unique (InputIterator b, InputIterator e, char )

We need the second overload for cases in which we need to construct a

value_type in order to compare it with the keys already in the btree.

Defined at line 2334 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

template <typename ValueType>
iterator insert_multi (const key_type & key, ValueType && v)

Inserts a value into the btree.

Defined at line 2346 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

template <typename ValueType>
iterator insert_hint_multi (iterator position, ValueType && v)

Insert with hint. Check to see if the value should be placed immediately

before position in the tree. If it does, then the insertion will take

amortized constant time. If not, the insertion will take amortized

logarithmic time as if a call to insert_multi(v) were made.

Defined at line 2360 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

template <typename InputIterator>
void insert_iterator_multi (InputIterator b, InputIterator e)

Insert a range of values into the btree.

Defined at line 2382 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

iterator erase (iterator iter)

Erase the specified iterator from the btree. The iterator must be valid

(i.e. not equal to end()). Return an iterator pointing to the node after

the one that was erased (or end() if none exists).

Requirement: does not read the value at `*iter`.

Defined at line 2438 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

std::pair<size_type, iterator> erase_range (iterator begin, iterator end)

Erases range. Returns the number of keys erased and an iterator pointing

to the element after the last erased element.

Defined at line 2531 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

void clear ()

Clear the btree, deleting all of the values it contains.

Defined at line 2576 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

void swap (btree<Params> & other)

Swaps the contents of `this` and `other`.

Defined at line 2585 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

void verify ()

Verifies the structure of the btree.

Defined at line 2602 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h

Friends

template <typename Params>
class btree_access