50#include <initializer_list>
76 template<Type::SafeValue K, Type::SafeValue V,
class Compare = std::less<K>>
77 requires std::strict_weak_order<Compare, const K&, const K&>
115 explicit value_compare(Compare compare): m_compare(compare) {}
127 template<
bool IsConst>
129 using NodeType = std::conditional_t<IsConst, const Node, Node>;
136 using reference = std::conditional_t<IsConst, const value_type&, value_type&>;
137 using pointer = std::conditional_t<IsConst, const value_type*, value_type*>;
149 template<
bool OtherConst>
150 requires IsConst && (!OtherConst)
194 template<
bool OtherConst>
195 bool operator==(const
BasicIterator<OtherConst>& other) const noexcept {
return m_node == other.m_node; }
205 explicit BasicIterator(NodeType* node)
noexcept: m_node(node) {}
243 if (
this != &other) {
245 m_node = other.m_node;
246 other.m_node =
nullptr;
271 bool empty() const noexcept {
return m_node ==
nullptr; }
277 explicit operator bool() const noexcept {
return !
empty(); }
283 const K&
key()
const {
return m_node->Entry.first; }
289 V&
mapped() {
return m_node->Entry.second; }
295 const V&
mapped()
const {
return m_node->Entry.second; }
310 explicit node_type(Node* node)
noexcept: m_node(node) {}
315 void reset() noexcept {
316 if (m_node ==
nullptr)
318 m_node->Entry.~value_type();
323 Node* m_node =
nullptr;
346 explicit Map(
const Compare& compare);
368 for (
const auto& entry : other)
378 for (
auto& entry : other)
389 template<std::ranges::input_range R>
390 requires std::convertible_to<std::ranges::range_reference_t<R>, value_type>
400 Map(std::initializer_list<value_type> values);
429 Map replacement(other);
441 Map replacement(std::move(other));
464 value_compare
value_comp()
const {
return value_compare(m_compare); }
542 bool empty() const noexcept {
return m_size == 0; }
554 size_type max_size() const noexcept {
return std::numeric_limits<size_type>::max() /
sizeof(Node); }
619 template<class InputIt>
621 for (; first != last; ++first)
630 void insert(std::initializer_list<value_type> values);
638 template<std::ranges::input_range R>
639 requires std::convertible_to<std::ranges::range_reference_t<R>,
value_type>
641 for (
auto&& entry : range)
653 template<
class... Args>
664 template<
class... Args>
676 template<
class... Args>
688 template<
class... Args>
698 template<
class... Args>
709 template<
class... Args>
793 insert_return_type
insert(node_type&& handle);
822 template<
class OtherCompare>
954 const V&
at(
const K& key)
const;
975 bool operator<(
const Map& other)
const requires requires(
const K& a,
const K& b,
const V& c,
const V& d) { a < b; c < d; };
982 bool operator<=(
const Map& other)
const requires requires(
const K& a,
const K& b,
const V& c,
const V& d) { a < b; c < d; };
989 bool operator>(
const Map& other)
const requires requires(
const K& a,
const K& b,
const V& c,
const V& d) { a < b; c < d; };
996 bool operator>=(
const Map& other)
const requires requires(
const K& a,
const K& b,
const V& c,
const V& d) { a < b; c < d; };
1003 std::map<K, V, Compare> exported(m_compare);
1027 bool HintMatches(const_iterator hint,
const K& key)
const noexcept;
1033 void CreateHeader();
1038 void DestroyHeader() noexcept;
1047 template<class... Args>
1048 Node* MakeNode(Args&&... args);
1054 void DestroyNode(Node* node) noexcept;
1060 void DestroyTree(Node* node) noexcept;
1069 Node* Clone(const Node* source, Node* parent);
1076 Node* FindNode(const K& key) const noexcept;
1084 void InsertNode(Node* node, Node* parent,
bool left) noexcept;
1090 void Unlink(Node* node) noexcept;
1096 void EraseNode(Node* node) noexcept;
1102 Node* Leftmost() const noexcept;
1108 void RotateLeft(Node* node) noexcept;
1114 void RotateRight(Node* node) noexcept;
1116 key_compare m_compare;
1129 template<
Type::SafeValue K,
Type::SafeValue V, class Compare>
1130 inline
void swap(
Map<K, V, Compare>& left,
Map<K, V, Compare>& right) noexcept {
1146 template<SafeValue K, SafeValue V,
class Compare>
1147 requires IsSafe<K>::value && IsSafe<V>::value
1156 template<SafeValue K, SafeValue V,
class Compare>
1166 template<SafeValue K, SafeValue V,
class Compare>
Bidirectional cursor over Base-owned map nodes.
Definition map.hxx:128
Map::value_type value_type
Entry type.
Definition map.hxx:134
pointer operator->() const noexcept
Access the entry stored in the node.
Definition map.hxx:163
friend class BasicIterator
Definition map.hxx:199
std::bidirectional_iterator_tag iterator_concept
C++20 iterator concept.
Definition map.hxx:133
BasicIterator() noexcept
Construct a singular iterator.
Definition map.hxx:143
std::ptrdiff_t difference_type
Iterator distance type.
Definition map.hxx:135
BasicIterator & operator++() noexcept
Advance to the next ordered entry.
std::conditional_t< IsConst, const value_type &, value_type & > reference
Entry reference.
Definition map.hxx:136
void StormByteSafeCursor
Base cursor mark. Copying the cursor copies one node pointer.
Definition map.hxx:138
friend class Map
Definition map.hxx:198
reference operator*() const noexcept
Return the entry stored in the node.
Definition map.hxx:157
&&!OtherConst BasicIterator(const BasicIterator< OtherConst > &other) noexcept
Convert a mutable iterator to a const iterator.
Definition map.hxx:151
std::conditional_t< IsConst, const value_type *, value_type * > pointer
Entry pointer.
Definition map.hxx:137
std::bidirectional_iterator_tag iterator_category
Iterator category.
Definition map.hxx:132
Owning handle to one extracted Base node.
Definition map.hxx:224
node_type & operator=(node_type &&other) noexcept
Take the node.
Definition map.hxx:242
node_type(const node_type &)=delete
Copying a node handle is not supported.
~node_type()
Destroy the owned node, if any.
Definition map.hxx:265
const K & key() const
Return the owned key.
Definition map.hxx:283
node_type() noexcept=default
Construct an empty handle.
V & mapped()
Return the owned mapped value.
Definition map.hxx:289
node_type & operator=(const node_type &)=delete
Copying a node handle is not supported.
bool empty() const noexcept
Test whether the handle owns a node.
Definition map.hxx:271
const V & mapped() const
Return the owned mapped value.
Definition map.hxx:295
friend class Map
Definition map.hxx:304
void swap(node_type &other) noexcept
Exchange owned nodes.
Definition map.hxx:301
Orders entries by key, using the map comparator.
Definition map.hxx:96
bool operator()(const value_type &left, const value_type &right) const
Compare two entries by key.
Definition map.hxx:106
friend class Map
Definition map.hxx:97
Ordered unique-key map stored on Base's heap.
Definition map.hxx:78
V & operator[](const K &key)
Return the mapped value, inserting a value-initialized one if absent.
key_compare key_comp() const
Definition map.hxx:458
Map(const Map &other)
Copy every node into new Base blocks.
bool operator>=(const Map &other) const
Order maps lexicographically.
iterator insert_or_assign(const_iterator hint, const K &key, V &&value)
Insert or replace the mapped value, using hint when the neighbouring keys confirm it.
Pair< const_iterator, const_iterator > const_equal_range_result
Read-only lower and upper bound.
Definition map.hxx:216
iterator insert_or_assign(const_iterator hint, const K &key, const V &value)
Insert or replace the mapped value, using hint when the neighbouring keys confirm it.
STORMBYTE_FORCE_INLINE Map(const std::map< K, V, Compare > &other)
Copy a caller-owned STL map.
Definition map.hxx:367
insert_result emplace(Args &&... args)
Construct an entry from arguments forwarded to value_type.
insert_result try_emplace(K &&key, Args &&... args)
Construct an entry in a new node if the key is absent.
STORMBYTE_FORCE_INLINE Map(std::map< K, V, Compare > &&other)
Move elements from a caller-owned STL map and leave it empty.
Definition map.hxx:377
iterator erase(iterator position) noexcept
Erase the entry at an iterator.
const_equal_range_result equal_range(const K &key) const noexcept
Return the equal range of a key.
size_type count(const K &key) const noexcept
Return the number of entries with a key.
insert_result try_emplace(const K &key, Args &&... args)
Construct an entry in a new node if the key is absent.
STORMBYTE_FORCE_INLINE Map(std::from_range_t, R &&range)
Copy the entries of range.
Definition map.hxx:391
const_iterator upper_bound(const K &key) const noexcept
Return the first entry greater than a key.
bool operator>(const Map &other) const
Order maps lexicographically.
bool operator<=(const Map &other) const
Order maps lexicographically.
bool contains(const K &key) const noexcept
Test whether a key is present.
iterator insert_or_assign(const_iterator hint, K &&key, const V &value)
Insert or replace the mapped value, using hint when the neighbouring keys confirm it.
iterator erase(const_iterator position) noexcept
Erase the entry at a read-only iterator.
K key_type
Key type.
Definition map.hxx:83
insert_result insert_or_assign(K &&key, const V &value)
Insert or replace the mapped value.
iterator insert(const_iterator hint, node_type &&handle)
Insert an extracted node, using hint when the neighbouring keys confirm it.
insert_return_type insert(node_type &&handle)
Insert an extracted node if its key is absent.
STORMBYTE_FORCE_INLINE void insert_range(R &&range)
Definition map.hxx:640
Pair< iterator, bool > insert_result
Iterator to the entry and whether it was inserted.
Definition map.hxx:214
V & operator[](K &&key)
Return the mapped value, inserting a value-initialized one if absent.
Pair< const K, V > value_type
Entry type. The key is immutable.
Definition map.hxx:85
void merge(Map< K, V, OtherCompare > &source)
Move unique keys from source into this map.
Size size_type
Element count. Size, not std::size_t.
Definition map.hxx:87
const_iterator cbegin() const noexcept
STORMBYTE_FORCE_INLINE Map & operator=(std::map< K, V, Compare > &&other)
Move-assign elements from a caller-owned STL map and leave it empty.
Definition map.hxx:440
equal_range_result equal_range(const K &key) noexcept
Return the equal range of a key.
bool operator==(const Map &other) const
Compare entries in order.
Compare key_compare
Key ordering.
Definition map.hxx:86
reverse_iterator rend() noexcept
Return the reverse end iterator.
Definition map.hxx:512
insert_result insert_or_assign(const K &key, const V &value)
Insert or replace the mapped value.
Map(std::initializer_list< value_type > values)
Insert every entry of an initializer list.
iterator erase(const_iterator first, const_iterator last) noexcept
Erase a half-open range.
BasicIterator< true > const_iterator
Read-only iterator.
Definition map.hxx:211
iterator begin() noexcept
Return a mutable iterator to the first entry.
Pair< iterator, iterator > equal_range_result
Lower and upper bound.
Definition map.hxx:215
void swap(Map &other) noexcept
V & at(const K &key)
Return the mapped value.
bool operator<(const Map &other) const
Order maps lexicographically.
const_reverse_iterator crbegin() const noexcept
Return a read-only reverse iterator to the last entry.
Definition map.hxx:530
size_type size() const noexcept
Return the entry count.
Definition map.hxx:548
STORMBYTE_FORCE_INLINE std::strong_ordering operator<=>(const Map &other) const
Order maps lexicographically by key, then mapped value.
size_type max_size() const noexcept
Return the largest representable entry count.
Definition map.hxx:554
void insert(std::initializer_list< value_type > values)
Insert every entry of an initializer list.
const_reverse_iterator rend() const noexcept
Return the read-only reverse end iterator.
Definition map.hxx:524
std::reverse_iterator< const_iterator > const_reverse_iterator
Read-only reverse iterator.
Definition map.hxx:213
std::ptrdiff_t difference_type
Iterator distance type.
Definition map.hxx:88
iterator emplace_hint(const_iterator hint, Args &&... args)
Construct an entry from arguments, using hint when the neighbouring keys confirm it.
Map()
Construct an empty map.
const value_type & const_reference
Read-only entry reference.
Definition map.hxx:90
V mapped_type
Mapped type.
Definition map.hxx:84
value_compare value_comp() const
Return an entry comparator that uses the key ordering.
Definition map.hxx:464
const_reverse_iterator rbegin() const noexcept
Return a read-only reverse iterator to the last entry.
Definition map.hxx:518
reverse_iterator rbegin() noexcept
Definition map.hxx:506
const_iterator lower_bound(const K &key) const noexcept
Return the first entry not less than a key.
Map & operator=(std::initializer_list< value_type > values)
Replace the contents with an initializer list.
iterator lower_bound(const K &key) noexcept
Return the first entry not less than a key.
insert_result insert_or_assign(const K &key, V &&value)
Insert or replace the mapped value.
const_iterator find(const K &key) const noexcept
Find an entry.
iterator try_emplace(const_iterator hint, const K &key, Args &&... args)
Construct an entry if the key is absent, using hint when the neighbouring keys confirm it.
iterator find(const K &key) noexcept
Find an entry.
size_type erase(const K &key) noexcept
Erase the entry with a key.
bool empty() const noexcept
Test whether the map has no entries.
Definition map.hxx:542
const V & at(const K &key) const
Return the mapped value.
const_iterator cend() const noexcept
Map(const Compare &compare)
Construct an empty map with a comparator.
iterator try_emplace(const_iterator hint, K &&key, Args &&... args)
Construct an entry if the key is absent, using hint when the neighbouring keys confirm it.
void clear() noexcept
Destroy every node.
value_type & reference
Mutable entry reference.
Definition map.hxx:89
std::reverse_iterator< iterator > reverse_iterator
Mutable reverse iterator.
Definition map.hxx:212
iterator insert_or_assign(const_iterator hint, K &&key, V &&value)
Insert or replace the mapped value, using hint when the neighbouring keys confirm it.
node_type extract(const_iterator position)
Unlink the entry at position and return that node.
BasicIterator< false > iterator
Mutable iterator.
Definition map.hxx:210
iterator upper_bound(const K &key) noexcept
Return the first entry greater than a key.
Map(Map &&other)
Take the tree.
~Map() noexcept
Destroy every node through Base.
insert_result insert(const value_type &entry)
node_type extract(const K &key)
Unlink the entry with key and return that node.
const_reverse_iterator crend() const noexcept
Return the read-only reverse end iterator.
Definition map.hxx:536
insert_result insert_or_assign(K &&key, V &&value)
Insert or replace the mapped value.
std::pair whose members keep their own Safe storage.
Definition pair.hxx:73
Second second
Second value.
Definition pair.hxx:79
First first
First value.
Definition pair.hxx:78
Count of abstract units (uint64_t storage).
Definition size.hxx:107
Type whose == and != both yield something convertible to bool.
Definition comparison.hxx:81
Recognizes a conditional Safe component after stripping cv and references.
Definition safe.hxx:301
Private Base heap used by StormByte::Safe::Shared, StormByte::Safe::Unique and StormByte::Safe::Clona...
void Free(void *pointer) noexcept
Release a block obtained from Allocate.
Owned values that cross a DLL without the caller's CRT.
void swap(Binary &left, Binary &right) noexcept
Exchange two sequences.
Definition binary.hxx:760
Root namespace of the StormByte suite.
Octet count. Defined in byte_size.hxx. Forwarded so Type::Numeral can name it.
Host-width-stable count (uint64_t), implicit only to std::size_t.
Result of inserting an extracted node.
Definition map.hxx:329
iterator position
Entry, or end when the node was not inserted and is empty.
Definition map.hxx:330
bool inserted
Whether the node was linked.
Definition map.hxx:331
node_type node
Returned node when the key was already present.
Definition map.hxx:332
Recognizes types whose DLL-boundary safety depends on documented provider requirements.
Definition safe.hxx:262
Recognizes collection values with Base-controlled lifetime.
Definition safe.hxx:347
Recognizes Base Safe components, not universal ABI compatibility.
Definition safe.hxx:138
#define STORMBYTE_PUBLIC_TYPE
Definition visibility.h:57
#define STORMBYTE_PUBLIC
Definition visibility.h:52