gmd::binary_tree_set

template <
	binary_tree_type Tree,
	typename Key,
	bool Threaded = false,
	typename Comparator = std::less<Key>,
	typename Allocator = std::allocator<Key>
> struct binary_tree_set;

gmd::binary_tree_set is a container that stores a sorted set of (unique) elements of type Key in a binary tree structure. The type of tree is defined by the template parameter Tree, while the sorting is done by using a key comparison function/object of type Comparator, which gets defaulted to std::less. The comparison mechanism follows the strict weak ordering formalization. The template parameter Allocator defines the type of allocator that will be used to allocate the elements in the container, and it is defaulted to std::allocator.

The Threaded parameter specifies whether the binary tree elements should have pointers to their in-order predecessors and successors. This allows for a faster iteration through the elements of the container (guaranteed O(1) time complexity), but it comes at the expense of additional memory and a slight time overhead whenever element insertion or removal is performed. This parameter gets defaulted to false, as in the STL/C++ Standard Library's std::set implementation.

Member type	Definition
`key_type`	`Key`
`value_type`	`Key`
`size_type`	`std::size_t`
`difference_type`	`std::ptrdiff_t`
`key_compare`	`Comparator`
`value_compare`	`Comparator`
`allocator_type`	`Allocator`
`reference`	`value_type &`
`const_reference`	`const value_type &`
`pointer`	`value_type *`
`const_pointer`	`const value_type *`
`iterator` `traversor` `reverse_iterator` `reverse_traversor`	Binary tree traversor
`const_iterator` `const_traversor` `const_reverse_iterator` `const_reverse_traversor`	Constant Binary tree traversor

Constructor

# binary_tree_set ([const key_compare &c, const allocator_type &a]) <>

Default constructor Constructs an empty container.

_{template <typename T1, typename T2>}
# binary_tree_set (const T1 &first, const T2 &last [, const key_compare &c, const allocator_type &a]) <>

Range constructor Constructs the container with the contents of the range [first, last). It is equivalent to call the default constructor followed by insert(first, last).

# binary_tree_set (const binary_tree_set &other [, const key_compare &c, const allocator_type &a]) <>

Copy constructor Constructs the container with the copy of the contents of other. If a comparator or an allocator are not provided, they are obtained by copy from the ones in other. In the case of the allocator, the following is used: std::allocator_traits<allocator_type>::select_on_container_copy_construction().

# binary_tree_set (binary_tree_set &&other [, const key_compare &c, const allocator_type &a]) <>

Move constructor Constructs the container with the contents of other, using move semantics. If a comparator or an allocator are not provided, they are obtained by move-construction from the ones in other.

# binary_tree_set (const std::initializer_list<value_type> &il [, const key_compare &c, const allocator_type &a]) <>

Initializer list constructor Constructs the container with the contents of the initializer list il. It is equivalent to call the default constructor followed by insert(il).

Example

int main (const int, const char **)
{
	// (1) Default constructor
	gmd::binary_tree_set<gmd::tree_avl, int> a;
	a.insert({1, 3, 5});
	std::cout << "a: "; for(int &x: a) std::cout << x << ' '; std::cout << '\n';

	// (2) Range constructor
	gmd::binary_tree_set<gmd::tree_avl, int> b(++a.begin(), a.end());
	std::cout << "b: "; for(int &x: b) std::cout << x << ' '; std::cout << '\n';

	// (3) Copy constructor
	gmd::binary_tree_set<gmd::tree_avl, int> c(a);
	c.insert(2);
	std::cout << "c: "; for(int &x: c) std::cout << x << ' '; std::cout << '\n';

	// (4) Move constructor
	gmd::binary_tree_set<gmd::tree_avl, int> d(std::move(b));
	std::cout << "b: "; for(int &x: b) std::cout << x << ' '; std::cout << '\n';
	std::cout << "d: "; for(int &x: d) std::cout << x << ' '; std::cout << '\n';

	// (5) Initializer list constructor
	gmd::binary_tree_set<gmd::tree_avl, int> e{4, 6, 5};
	std::cout << "e: "; for(int &x: e) std::cout << x << ' '; std::cout << '\n';
}

Output

a: 1 3 5
b: 3 5
c: 1 2 3 5
b:
d: 3 5
e: 4 5 6

Destructor

# ~binary_tree_set () <>

Destructs and deallocates the container and all its elements.

Assign operator

# binary_tree_set &operator= (const binary_tree &other) <>

Copy assignment Replaces the contents of the containers with a copy of the contents of other. The allocator is replaced only if std::allocator_traits<allocator_type>::propagate_on_container_copy_assignment::value is set to true.

# binary_tree_set &operator= (binary_tree &&other) <>

Move assignment Replaces the contents with those of other using move semantics. The allocator is replaced only if std::allocator_traits<allocator_type>::propagate_on_container_move_assignment::value is set to true. If not, and neither std::allocator_traits<allocator_type>::is_always_equal::value is set true nor the allocators compare equal, then the elements are copied instead.

# binary_tree_set &operator= (std::initializer_list<value_type> &il) <>

Initializer list assignment Replaces the contents with those of the initializer list il.

Note: All four variants of binary_tree (set, map, multiset, multimap) are accepted, as well as any template signature, as long as value_type is the same. When copying the elements, if the containers are conversion compatible, then the structure of other is replicated; otherwise, the elements are copied one by one. For more information, refer to type conversion.

Example

int main (const int, const char **)
{
	// (1) Copy assignment
	gmd::binary_tree_set<gmd::tree_avl, int> a{3, 5, 2};
	std::cout << "a: "; for(int &x: a) std::cout << x << ' '; std::cout << '\n';
	gmd::binary_tree_set<gmd::tree_avl, int> b; b = a;
	std::cout << "b: "; for(int &x: b) std::cout << x << ' '; std::cout << '\n';

	// (2) Move assignment
	gmd::binary_tree_multiset<gmd::tree_avl, int> c{1, 6, 1};
	std::cout << "c: "; for(int &x: c) std::cout << x << ' '; std::cout << '\n';
	gmd::binary_tree_set<gmd::tree_rb, int> d; d = std::move(c);
	std::cout << "c: "; for(int &x: c) std::cout << x << ' '; std::cout << '\n';
	std::cout << "d: "; for(int &x: d) std::cout << x << ' '; std::cout << '\n';

	// (3) Initializer list assignment
	a = {7, 4};
	std::cout << "a: "; for(int &x: a) std::cout << x << ' '; std::cout << '\n';
}

Output

a: 2 3 5
b: 2 3 5
c: 1 1 6
c:
d: 1 6
a: 4 7

Comparison operators

# bool operator== (binary_tree &other) <>
# bool operator== (const binary_tree &other) const <>
# bool operator!= (binary_tree &other) <>
# bool operator!= (const binary_tree &other) const <>
# bool operator< (binary_tree &other) <>
# bool operator< (const binary_tree &other) const <>
# bool operator> (binary_tree &other) <>
# bool operator> (const binary_tree &other) const <>
# bool operator<= (binary_tree &other) <>
# bool operator<= (const binary_tree &other) const <>
# bool operator>= (binary_tree &other) <>
# bool operator>= (const binary_tree &other) const <>
# int spaceship (binary_tree &other) <>
# int spaceship (const binary_tree &other) const <>

Compares the contents of *this and other lexicographically. The spaceship function returns -1 if the contents of the *this are lexicographically lesser than the contents of other; 0 if equal; 1 if greater.

Note: All four variants of binary_tree (set, map, multiset, multimap) are accepted, as well as any template signature, as long as either key_type is the same or key_compare::is_transparent is valid.

Example

int main (const int, const char **)
{
	gmd::binary_tree_set<gmd::tree_avl, int> a{1, 3, 4};
	gmd::binary_tree_set<gmd::tree_rb, int> b{1, 3, 4, 5};
	gmd::binary_tree_set<gmd::tree_avl, int> c{2, 3, 4};

	std::cout << "a: "; for(int &x: a) std::cout << x << ' '; std::cout << '\n';
	std::cout << "b: "; for(int &x: b) std::cout << x << ' '; std::cout << '\n';
	std::cout << "c: "; for(int &x: c) std::cout << x << ' '; std::cout << '\n';
	std::cout << "a == b: " << (a == b ? "true" : "false") << '\n';
	std::cout << "b != c: " << (b != c ? "true" : "false") << '\n';
	std::cout << "a < b: " << (a < b ? "true" : "false") << '\n';
	std::cout << "b > c: " << (b > c ? "true" : "false") << '\n';
	std::cout << "a <=> c: " << a.spaceship(c) << '\n';
}

Output

a: 1 3 4
b: 1 3 4 5
c: 2 3 4
a == b: false
b != c: true
a < b: true
b > c: false
a <=> c: -1

Observers

# key_compare key_comp () const <>

Returns a copy of the function object used to compare the keys.

# value_compare value_comp () const <>

Returns a copy of the function object that compares the values.

# key_compare & get_comparator () <>
# const key_compare & get_comparator () const <>

Returns the comparator associated with the container.

# allocator_type get_allocator () const <>

Returns a copy of the allocator associated with the container.

Example

struct Info {
	int v[2];
	Info(int w) : v{w, w+1} {}
	bool operator< (const Info &i) const {
		return v[0] < i.v[0];
	}
};

int main(const int, const char **)
{
	using btset_a = gmd::binary_tree_set<gmd::tree_avl, int>;
	using btset_b = gmd::binary_tree_set<gmd::tree_avl, int, false, std::greater<int>>;
	using btset_c = gmd::binary_tree_set<gmd::tree_avl, Info>;
	btset_a a;
	btset_b b;
	btset_c c;

	btset_a::key_compare x = a.key_comp();
	btset_b::value_compare y = b.value_comp();
	std::cout << "a (1 < 2): " << (x(1, 2) ? "true" : "false") << '\n';
	std::cout << "b (1 > 2): " << (y(1, 2) ? "true" : "false") << '\n';
	std::cout << "b (1 <= 2): " << (!y(1, 2) ? "true" : "false") << '\n';

	btset_c::allocator_type z = c.get_allocator();
	Info *i = std::allocator_traits<btset_c::allocator_type>::allocate(z, 2);
	new(&i[0]) Info(1);
	new(&i[1]) Info(3);
	std::cout << "i[0]: v = {" << i[0].v[0] << ", " << i[0].v[1] << "}\n";
	std::cout << "i[1]: v = {" << i[1].v[0] << ", " << i[1].v[1] << "}\n";
	i[0].~Info();
	i[1].~Info();
	std::allocator_traits<btset_c::allocator_type>::deallocate(z, i, 2);
}

Output

a (1 < 2): true
b (1 > 2): false
b (1 <= 2): true
i[0]: v = {1, 2}
i[1]: v = {3, 4}

Traversors

# traversor root () <>
# const_traversor root () const <>
# const_traversor croot () const <>

Returns a traversor to the root element of the container. If the container is empty, the returned traversor will be empty (invalid) and cannot be dereferenced.

# reverse_traversor rroot () <>
# const_reverse_traversor rroot () const <>
# const_reverse_traversor crroot () const <>

Returns a reverse traversor to the root element of the container. If the container is empty, the returned traversor will be empty (invalid) and cannot be dereferenced.

# traversor begin () <>
# const_traversor begin () const <>
# const_traversor cbegin () const <>

Returns a traversor to the first element of the container. If the container is empty, the returned traversor will be equivalent to end().

# reverse_traversor rbegin () <>
# const_reverse_traversor rbegin () const <>
# const_reverse_traversor crbegin () const <>

Returns a reverse traversor to the first element of the container. If the container is empty, the returned traversor will be equivalent to rend().

# traversor end () <>
# const_traversor end () const <>
# const_traversor cend () const <>

Returns a traversor to the element following the last element of the container (past-the-end). As such, it cannot be dereferenced.

# reverse_traversor rend () <>
# const_reverse_traversor rend () const <>
# const_reverse_traversor crend () const <>

Returns a reverse traversor to the element following the last element of the container (past-the-end). As such, it cannot be dereferenced.

Example

int main(const int, const char **)
{
	using btset = gmd::binary_tree_set<gmd::tree_avl, int>;
	btset a{1, 8, 4, 3, 7};

	std::cout << "a: ";
	for(btset::traversor x = a.begin(); x != a.end(); ++x)
		std::cout << *x << " ";
	std::cout << "\n";

	btset::traversor x = a.root();
	std::cout << "root: " << *x << "\n";
	if(x.right()())
		std::cout << "right: " << *x.right() << "\n";

	std::cout << "reverse from root: ";
	for(btset::const_reverse_traversor y = x.reverse(); y != a.crend(); ++y)
		std::cout << *y << " ";
	std::cout << "\n";
}

Output

a: 1 3 4 7 8
root: 4
right: 8
reverse from root: 4 3 1

Capacity

# bool empty () const <>

Returns true if the container is empty; false otherwise.

# size_type size () const <>

Returns the number of elements in the container.

# size_type max_size () const <>

Returns the maximum number of elements the container is able to hold due to system or library implementation limitations. However, the size of the container may be limited to a smaller value at runtime.

Example

int main(const int, const char **)
{
	gmd::binary_tree_set<gmd::tree_avl, int> a;

	std::cout << "empty: " << (a.empty() ? "true" : "false") << "\n";
	std::cout << "size: " << a.size() << "\n";
	a.insert({3, 1, 2});
	std::cout << "a: "; for(int &x: a) std::cout << x << ' '; std::cout << '\n';
	std::cout << "empty: " << (a.empty() ? "true" : "false") << "\n";
	std::cout << "size: " << a.size() << "\n";

	std::cout << "max_size: " << a.max_size() << "\n";
}

Output

empty: true
size: 0
a: 1 2 3
empty: false
size: 3
max_size: 576460752303423487

Modifiers

Clear

# void clear () <>

Removes all elements from the container.

Example

int main(const int, const char **)
{
	gmd::binary_tree_set<gmd::tree_avl, int> a{4, 2, 3, 1};
	std::cout << "a: "; for(int &x: a) std::cout << x << ' '; std::cout << '\n';

	a.clear();
	std::cout << "a: "; for(int &x: a) std::cout << x << ' '; std::cout << '\n';
	std::cout << "size: " << a.size() << "\n";
}

Output

a: 1 2 3 4
a:
size: 0

Insert

_{template <bool Replace = false>}
# std::pair<traversor, bool> insert (const value_type &info) <>
_{template <bool Replace = false>}
# std::pair<traversor, bool> insert (value_type &&info) <>

Inserts info in the container. Returns a pair consisting of a traversor to the inserted element (or to the element that prevented the insertion) and a boolean value set to true if the insertion took place.

_{template <bool Replace = false, typename T1, typename T2>}
# size_type insert (const T1 &first, const T2 &last) <>

Inserts elements from range [first, last). Returns the number of elements inserted. Even though first and last can be of different types, last must be reachable from first and T1 needs to satisfy EqualityComparable towards T2.

_{template <bool Replace = false>}
# size_type insert (std::initializer_list<value_type> &il) <>

Inserts elements from the initializer list il. Returns the number of elements inserted.

_{template <bool Replace = false, typename T>}
# std::pair<traversor, bool> insert_hint (const T &hint, const value_type &info) <>
_{template <bool Replace = false, typename T>}
# std::pair<traversor, bool> insert_hint (const T &hint, value_type &&info) <>

Inserts info in the container, taking hint as a possible location for the new element. Returns a pair consisting of a traversor to the inserted element (or to the element that prevented the insertion) and a boolean value set to true if the insertion took place. hint must be a non const traversor. This function can also be called as insert(hint, info).

Note: If Replace is set to true and an element that compares equivalent already exists in the container, its value_type value is replaced. Also, the return values (bool and size_type) are set to true and +1 only if the elements were inserted without need for replacement.

Example

struct Info {
	Info (int a, int b) : v{a, b} {}
	int v[2];
	bool operator< (const Info &i) const { return v[0] < i.v[0]; }
};

int main(const int, const char **)
{
	gmd::binary_tree_set<gmd::tree_avl, Info> a;
	gmd::binary_tree_set<gmd::tree_rb, Info> b;

	auto y = a.insert(Info(2,0));
	std::cout << "inserted: " << (y.second ? "true" : "false") << "\n";
	std::cout << "element: " << (*y.first).v[0] << ' ' << y.first->v[1] << "\n";
	std::cout << "a: ";
	for(Info &x: a) std::cout << '[' << x.v[0] << ',' << x.v[1] << '] ';
	std::cout << '\n';

	size_t z = a.insert({Info(1,0), Info(2,1), Info(3,0), Info(4,0)});
	std::cout << "# inserted: " << z << "\n";
	std::cout << "a: "; for(Info &x: a) std::cout << x.v[0] << ',' << x.v[1] << ' '; std::cout << '\n';

	y = a.insert<true>(Info(2,1));
	std::cout << "inserted: " << (y.second ? "true" : "false") << "\n";
	std::cout << "a: "; for(Info &x: a) std::cout << x.v[0] << ',' << x.v[1] << ' '; std::cout << '\n';

	b.insert(a.root(), a.cend());
	std::cout << "b: "; for(Info &x: b) std::cout << x.v[0] << ',' << x.v[1] << ' '; std::cout << '\n';

	b.insert_hint(b.end(), Info(5,0));
	std::cout << "b: "; for(Info &x: b) std::cout << x.v[0] << ',' << x.v[1] << ' '; std::cout << '\n';
}

Output

inserted: true
element: 2,0
a: 2,0
# inserted: 3
a: 1,0 2,0 3,0 4,0
inserted: false
a: 1,0 2,1 3,0 4,0
b: 2,1 3,0 4,0
b: 2,1 3,0 4,0 5,0

Emplace

_{template <bool Replace = false, typename... Args>}
# std::pair<traversor, bool> emplace (Args&&... info) <>

Inserts a new element in the container constructed in-place with info. Returns a pair consisting of a traversor to the inserted element (or to the element that prevented the insertion) and a boolean value set to true if the insertion took place.

_{template <bool Replace = false, typename T, typename... Args>}
# std::pair<traversor, bool> emplace_hint (const T &hint, Args&&... info) <>

Inserts a new element in the container constructed in-place with info, taking hint as a possible location for the new element. Returns a pair consisting of a traversor to the inserted element (or to the element that prevented the insertion) and a boolean value set to true if the insertion took place. hint must be a non const traversor.

Note: If Replace is set to true and an element the compares equivalent already exists in the container, its value_type value is replaced. Also, the return value (bool) is set to true only if the element was inserted without need for replacement.

Example

struct Info {
	Info (int a, int b) : v{a, b} {}
	int v[2];
	bool operator< (const Info &i) const { return v[0] < i.v[0]; }
};

int main(const int, const char **)
{
	gmd::binary_tree_set<gmd::tree_avl, Info> a;

	auto y = a.emplace(2, 0);
	std::cout << "emplaced: " << (y.second ? "true" : "false") << "\n";
	std::cout << "element: " << (*y.first).v[0] << ',' << y.first->v[1] << "\n";
	std::cout << "a: "; for(Info &x: a) std::cout << x.v[0] << ',' << x.v[1] << ' '; std::cout << '\n';

	y = a.emplace<true>(2, 1);
	std::cout << "emplaced: " << (y.second ? "true" : "false") << "\n";
	std::cout << "a: "; for(Info &x: a) std::cout << x.v[0] << ',' << x.v[1] << ' '; std::cout << '\n';

	a.emplace_hint(a.begin(), 1, 0);
	std::cout << "a: "; for(Info &x: a) std::cout << x.v[0] << ',' << x.v[1] << ' '; std::cout << '\n';
}

Output

emplaced: true
element: 2,0
a: 2,0
emplaced: false
a: 2,1
a: 1,0 2,1

Erase

# bool erase (const key_type &key) <>

Removes the element that compares equivalent to key, if existent. Returns true if an element is found and removed; false otherwise.

_{template <typename T>}
# void erase (const T &tr) <>

Removes the element referenced by tr, which must be a non const traversor.

_{template <typename T1, typename T2>}
# void erase (const T1 &first, const T2 &last) <>

Removes the elements in the range [first, last), which must be valid within the container. Both first and last must be non const traversors.

# size_type erase (const std::initializer_list<key_type> &il) <>

Removes the elements that compare equivalent to the keys in the initializer list il. Returns the amount of elements removed.

Example

int main(const int, const char **)
{
	gmd::binary_tree_set<gmd::tree_avl, int> a{1, 2, 3, 4, 5};
	std::cout << "a: "; for(int &x: a) std::cout << x << ' '; std::cout << '\n';

	a.erase(4);
	std::cout << "a: "; for(int &x: a) std::cout << x << ' '; std::cout << '\n';

	a.erase(a.root().next(), a.end());
	std::cout << "a: "; for(int &x: a) std::cout << x << ' '; std::cout << '\n';

	a.erase({1, 3});
	std::cout << "a: "; for(int &x: a) std::cout << x << ' '; std::cout << '\n';
}

Output

a: 1 2 3 4 5
a: 1 2 3 5
a: 1 2
a: 2

Transfer

_{template<bool Replace = false, typename T>}
# std::pair<traversor, bool> transfer (binary_tree &other, const T &tr) <>

Transfers an element from other into the container, if it does not exist. Returns a pair consisting of a traversor to the transferred element (or to the element that prevented the transferral) and a boolean value set to true if the transferral took place. tr must be a non const traversor in other.

Note: If Replace is set to true and an element that compares equivalent already exists in the container, its value_type value is replaced. Also, the return value (bool) is set to true only if the element was transferred without need for replacement. All four variants of binary_tree (set, map, multiset, multimap) are accepted, as well as any template signature, as long as value_type is the same.

Example

struct Info {
	Info (int a, int b) : v{a, b} {}
	int v[2];
	bool operator< (const Info &i) const { return v[0] < i.v[0]; }
};

int main(const int, const char **)
{
	gmd::binary_tree_set<gmd::tree_avl, Info> a{Info(1,0), Info(2,0), Info(3,0)}, b{Info(2,1)};
	gmd::binary_tree_set<gmd::tree_rb, Info> c;
	std::cout << "a: "; for(Info &x: a) std::cout << x.v[0] << ',' << x.v[1] << ' '; std::cout << '\n';
	std::cout << "b: "; for(Info &x: b) std::cout << x.v[0] << ',' << x.v[1] << ' '; std::cout << '\n';

	auto y = b.transfer<true>(a, a.root());
	std::cout << "transferred: " << (y.second ? "true" : "false") << "\n";
	std::cout << "a: "; for(Info &x: a) std::cout << x.v[0] << ',' << x.v[1] << ' '; std::cout << '\n';
	std::cout << "b: "; for(Info &x: b) std::cout << x.v[0] << ',' << x.v[1] << ' '; std::cout << '\n';

	c.transfer(a, a.begin());
	std::cout << "a: "; for(Info &x: a) std::cout << x.v[0] << ',' << x.v[1] << ' '; std::cout << '\n';
	std::cout << "c: "; for(Info &x: c) std::cout << x.v[0] << ',' << x.v[1] << ' '; std::cout << '\n';
}

Output

a: 1,0 2,0 3,0
b: 2,1
transferred: false
a: 1,0 3,0
b: 2,0
a: 3,0
c: 1,0

Merge

_{template<bool Replace = false>}
# size_type merge (binary_tree &other) <>

Merges the values of both containers into *this. This is achieved by attempting to transfer the elements of other one by one using transfer. Returns the number of elements merged from other into *this.

Note: If Replace is set to true and an element that compares equivalent already exists in the container, its value_type value is replaced. All four variants of binary_tree (set, map, multiset, multimap) are accepted, as well as any template signature, as long as value_type is the same. If the container is empty and the containers are conversion compatible, then the structure of other is replicated; otherwise, the elements are copied one by one. For more information, refer to type conversion.

Example

struct Info {
	Info (int a, int b) : v{a, b} {}
	int v[2];
	bool operator< (const Info &i) const { return v[0] < i.v[0]; }
};

int main(const int, const char **)
{
	gmd::binary_tree_multiset<gmd::tree_avl, Info> a{Info(1,0), Info(1,1), Info(2,0), Info(3,0)};
	gmd::binary_tree_set<gmd::tree_avl, Info> b{Info(2,1)};
	gmd::binary_tree_set<gmd::tree_rb, Info> c{Info(2,2)};
	std::cout << "a: "; for(Info &x: a) std::cout << x.v[0] << ',' << x.v[1] << ' '; std::cout << '\n';
	std::cout << "b: "; for(Info &x: b) std::cout << x.v[0] << ',' << x.v[1] << ' '; std::cout << '\n';
	std::cout << "c: "; for(Info &x: c) std::cout << x.v[0] << ',' << x.v[1] << ' '; std::cout << '\n';

	b.merge(a);
	std::cout << "a: "; for(Info &x: a) std::cout << x.v[0] << ',' << x.v[1] << ' '; std::cout << '\n';
	std::cout << "b: "; for(Info &x: b) std::cout << x.v[0] << ',' << x.v[1] << ' '; std::cout << '\n';

	c.merge<true>(a);
	std::cout << "a: "; for(Info &x: a) std::cout << x.v[0] << ',' << x.v[1] << ' '; std::cout << '\n';
	std::cout << "c: "; for(Info &x: c) std::cout << x.v[0] << ',' << x.v[1] << ' '; std::cout << '\n';
}

Output

a: 1,0 1,1 2,0 3,0
b: 2,1
c: 2,2
a: 1,1 2,0
b: 1,0 2,1 3,0
a:
c: 1,1 2,0

Swap

# void swap (binary_tree &other) <>

Exchanges the contents of the container with those of other.

Note: All four variants of binary_tree (set, map, multiset, multimap) are accepted, as well as any template signature, as long as value_type is the same. When copying the elements, if the containers are conversion compatible, then the structure of other is replicated, and vice-versa; otherwise, the elements are copied one by one. For more information, refer to type conversion.

Example

using intpair = std::pair<int, int>;

struct Comp {
	bool operator() (const intpair &a, const intpair &b) const {
		return a.first < b.first; }
};

int main(const int, const char **)
{
	gmd::binary_tree_set<gmd::tree_avl, intpair, false, Comp> a{{1,0}, {3,0}, {4,0}, {5,0}};
	gmd::binary_tree_multimap<gmd::tree_rb, int, int, true, std::greater<int>> b{{2,0}, {2,1}, {3,0}};
	std::cout << "a: "; for(intpair &x: a) std::cout << x.first << ',' << x.second << ' '; std::cout << '\n';
	std::cout << "b: "; for(intpair &x: b) std::cout << x.first << ',' << x.second << ' '; std::cout << '\n';

	a.swap(b);
	std::cout << "a: "; for(intpair &x: a) std::cout << x.first << ',' << x.second << ' '; std::cout << '\n';
	std::cout << "b: "; for(intpair &x: b) std::cout << x.first << ',' << x.second << ' '; std::cout << '\n';
}

Output

a: 1,0 3,0 4,0 5,0
b: 3,0 2,0 2,1
a: 2,0 3,0
b: 5,0 4,0 3,0 1,0

Lookup

Count

_{template <typename Key>}
# size_type count (const Key &key) <>
_{template <typename Key>}
# size_type count (const Key &key) const <>

Returns the number of elements with a key that compares equivalent to key. Because this container does not allow duplicates, the return value is either 0 or 1.

Note: The function is valid only if either Key and key_type are the same or key_compare::is_transparent is valid.

Example

int main(const int, const char **)
{
	gmd::binary_tree_set<gmd::tree_avl, int> a{1, 3, 4};
	std::cout << "a: "; for(int &x: a) std::cout << x << ' '; std::cout << '\n';

	std::cout << "count 1: " << a.count(1) << "\n";
	std::cout << "count 2: " << a.count(2) << "\n";
}

Output

a: 1 3 4
count 1: 1
count 2: 0

Contains

_{template <typename Key>}
# bool contains (const Key &key) <>
_{template <typename Key>}
# bool contains (const Key &key) const <>

Checks if there exists an element with a key that compares equivalent to key. Returns true if such element exists; false otherwise.

It is equivalent to count(key) or find(key) != end().

Note: The function is valid only if either Key and key_type are the same or key_compare::is_transparent is valid.

Example

int main(const int, const char **)
{
	gmd::binary_tree_set<gmd::tree_avl, int> a{1, 3, 4};
	std::cout << "a: "; for(int &x: a) std::cout << x << ' '; std::cout << '\n';

	std::cout << "contains 3: " << (a.contains(3) ? "true" : "false") << "\n";
	std::cout << "contains 2: " << (a.contains(2) ? "true" : "false") << "\n";
}

Output

a: 1 3 4
contains 3: true
contains 2: false

Find

_{template <typename Key>}
# traversor find (const Key &key) <>
_{template <typename Key>}
# const_traversor find (const Key &key) const <>

_{template <typename Key>}
# traversor find_short (const Key &key) <>
_{template <typename Key>}
# const_traversor find_short (const Key &key) const <>

Returns a traversor of an element with a key equivalent to key. If no such element exists, a past-the-end traversor (e.g. end()) is returned. The function find_short() is more efficient than find() when the element to be found is more likely to be close to the root, such as in a Splay-like tree.

Note: The function is valid only if either Key and key_type are the same or key_compare::is_transparent is valid.

Example

struct Comp {
	using is_transparent = void;
	bool operator() (const int &i1, const int &i2) const { return i1 < i2; }
	bool operator() (const double &d, const int &i) const { return d < i; }
	bool operator() (const int &i, const double &d) const { return i < d; }
};

int main(const int, const char **)
{
	using btset = gmd::binary_tree_set<gmd::tree_avl, int, false, Comp>;
	btset a{1, 3, 4};
	std::cout << "a: "; for(int &x: a) std::cout << x << ' '; std::cout << '\n';

	std::cout << "find 2.0: ";
	btset::reverse_traversor y = a.find(2.0);
	if(y != a.rend()) std::cout << "true - " << *y << "\n";
	else              std::cout << "false\n";

	std::cout << "find 4: ";
	btset::const_traversor z = a.find_short(4);
	if(z != a.cend()) std::cout << "true - " << *z << "\n";
	else              std::cout << "false\n";
}

Output

a: 1 3 4
find 2.0: false
find 4: true - 4

Lower bound

_{template <typename Key>}
# traversor lower_bound (const Key &key) <>
_{template <typename Key>}
# const_traversor lower_bound (const Key &key) const <>

Returns a traversor to the first element that is not lesser than key. If no such element exists, a past-the-end traversor (e.g. end()) is returned.

Note: The function is valid only if either Key and key_type are the same or key_compare::is_transparent is valid.

Example

int main(const int, const char **)
{
	gmd::binary_tree_set<gmd::tree_avl, int> a{1, 3, 4};
	std::cout << "a: "; for(int &x: a) std::cout << x << ' '; std::cout << '\n';

	std::cout << "lower_bound 2: ";
	auto y = a.lower_bound(2);
	if(y != a.end()) std::cout << *y;
	std::cout << "\n";

	a.insert(2);
	std::cout << "a: "; for(int &x: a) std::cout << x << ' '; std::cout << '\n';

	std::cout << "lower_bound 2: ";
	y = a.lower_bound(2);
	if(y != a.end()) std::cout << *y;
	std::cout << "\n";
}

Output

a: 1 3 4
lower_bound 2: 3
a: 1 2 3 4
lower_bound 2: 2

Upper bound

_{template <typename Key>}
# traversor upper_bound (const Key &key) <>
_{template <typename Key>}
# const_traversor upper_bound (const Key &key) const <>

Returns a traversor to the first element that is greater than key. If no such element exists, a past-the-end traversor (e.g. end()) is returned.

Note: The function is valid only if either Key and key_type are the same or key_compare::is_transparent is valid.

Example

int main(const int, const char **)
{
	gmd::binary_tree_set<gmd::tree_avl, int> a{1, 3, 4};
	std::cout << "a: "; for(int &x: a) std::cout << x << ' '; std::cout << '\n';

	std::cout << "upper_bound 2: ";
	auto y = a.upper_bound(2);
	if(y != a.end()) std::cout << *y;
	std::cout << "\n";
}

Output

a: 1 3 4
upper_bound 2: 3

Equal range

_{template <typename Key>}
# std::pair<traversor, traversor> equal_range (const Key &key) <>
_{template <typename Key>}
# std::pair<const_traversor, const_traversor> equal_range (const Key &key) const <>

Returns a range containing all the elements with a key equivalent to key. Because this container does not allow duplicates, the range will have at most size 1. Alternatively, the first traversor may be obtained with lower_bound(key), and the second with upper_bound(key).

Note: The function is valid only if either Key and key_type are the same or key_compare::is_transparent is valid.

Example

int main(const int, const char **)
{
	gmd::binary_tree_set<gmd::tree_avl, int> a{1, 3, 4};
	std::cout << "a: "; for(int &x: a) std::cout << x << ' '; std::cout << '\n';

	std::cout << "equal_range 2: ";
	auto y = a.equal_range(2);
	if(y.first == y.second) std::cout << "no element found\n";
	else                    std::cout << "element found\n";

	std::cout << "equal_range 3: ";
	y = a.equal_range(3);
	for(auto z = y.first; z != y.second; ++z)
		std::cout << *z << ' ';
	std::cout << "\n";
}

Output

a: 1 3 4
equal_range 2: no element found
equal_range 3: 3

Print

_{template <bool Verbose = false, typename Printer>}
# void print (Printer &printer) const <>
_{template <bool Verbose = false, typename Printer>}
# void print ([const Printer &printer]) const <>
_{template <bool Verbose = false, typename Printer, typename T>}
# void print (const T &tr, Printer &printer) const <>
_{template <bool Verbose = false, typename Printer, typename T>}
# void print (const T &tr [, const Printer &printer]) const <>

Prints the tree or subtree to the stdout. If Verbose is set to true, aditional internal tree information is also displayed.

Note: Printer should print an element to the stdout without the new line character.

Example

struct Print {
	void operator() (const int &i) const {
		std::cout << i ;
	}
};

int main(const int, const char **)
{
	gmd::binary_tree_set<gmd::tree_avl, int> a{1, 3, 4, 6};
	gmd::binary_tree_set<gmd::tree_rb, int> b{2, 3, 5, 6, 7};
	std::cout << "a: "; for(int &x: a) std::cout << x << ' '; std::cout << '\n';
	std::cout << "b: "; for(int &x: b) std::cout << x << ' '; std::cout << '\n';

	std::cout << "\n"; a.print<true>(Print());
	std::cout << "\n"; b.print<true, Print>();
	std::cout << "\n"; b.print(b.root().right(), [](const int &i){ std::cout << i; });
}

Output

a: 1 3 4 6
b: 2 3 5 6 7

      ┌──╴• 6
  ┌──╴+ 4
─╴+ 3
  └──╴• 1

      ┌──╴R 7
  ┌──╴B 6
  │   └──╴R 5
─╴B 3
  └──╴B 2

  ┌──╴7
┄╴6
  └──╴5

Files

set.md

Latest commit

History

set.md

File metadata and controls

gmd::binary_tree_set

Constructor

Example

Output

Destructor

Assign operator

Example

Output

Comparison operators

Example

Output

Observers

Example

Output

Traversors

Example

Output

Capacity

Example

Output

Modifiers

Clear

Example

Output

Insert

Example

Output

Emplace

Example

Output

Erase

Example

Output

Transfer

Example

Output

Merge

Example

Output

Swap

Example

Output

Lookup

Count

Example

Output

Contains

Example

Output

Find

Example

Output

Lower bound

Example

Output

Upper bound

Example

Output

Equal range

Example

Output

Print

Example

Output