Namespaces
Variants
Views
Actions

Difference between revisions of "cpp/container/node handle"

From cppreference.com
< cpp‎ | container
(to be linked to by map/set/etc::extract and ::insert)
 
m (+#Data members, fmt.)
 
(31 intermediate revisions by 13 users not shown)
Line 1: Line 1:
−
{{cpp/title|Node handle{{mark c++17}}}}
+
{{title|Node handle {{mark c++17}}}}
−
{{cpp/container/set/navbar}}
+
{{cpp/container/navbar}}
  
−
{{dcl begin }}
+
{{dcl begin}}
−
{{dcl | since=c++17 |
+
{{dcla|anchor=no|since=c++17|expos=yes|
−
template</*unspecified*/>
+
template</* unspecified */>
−
class /*unspecified*/
+
class /*node-handle*/;
 
}}  
 
}}  
 
{{dcl end}}
 
{{dcl end}}
Line 11: Line 11:
 
Associative containers {{lc|std::set}}, {{lc|std::map}}, {{lc|std::multiset}}, {{lc|std::multimap}}, {{lc|std::unordered_set}}, {{lc|std::unordered_map}}, {{lc|std::unordered_multiset}}, {{lc|std::unordered_multimap}} are node-based data structures, and their nodes can be extracted as an object of unspecified type known as ''node handle''.
 
Associative containers {{lc|std::set}}, {{lc|std::map}}, {{lc|std::multiset}}, {{lc|std::multimap}}, {{lc|std::unordered_set}}, {{lc|std::unordered_map}}, {{lc|std::unordered_multiset}}, {{lc|std::unordered_multimap}} are node-based data structures, and their nodes can be extracted as an object of unspecified type known as ''node handle''.
  
−
Node handle is a move-only type that owns and provides access to the element (the
+
Node handle is a move-only type that owns and provides access to the element (the {{tt|value_type}}) stored in the node, and provides non-const access to the key part of the element (the {{tt|key_type}}) and the mapped part of the element (the {{tt|mapped_type}}). If the node handle destructs while holding the node, the node is properly destructed using the appropriate allocator for the container. The node handle contains a copy of the container’s allocator. This is necessary so that the node handle can outlive the container.
−
{{tt|value_type}}) stored in the node, and provides non-const access to the key part of the element (the {{tt|key_type}}) and the mapped part of the element (the {{tt|mapped_type}}). If the node handle is allowed to destruct while holding the node, the node is properly destructed using the appropriate allocator for the container. The node handle contains a copy of the container’s allocator. This is necessary so that the node handle can outlive the container.
+
  
−
The exact type of node handle is unspecified, but each container exposes its node handle type as the member {{tt|node_type}}.
+
The exact type of node handle (shown here as {{c/core|/*node-handle*/}}) is unspecified, but each container exposes its node handle type as the member {{tt|node_type}}.
  
 
Node handles can be used to transfer ownership of an element between two associative containers with the same key, value, and allocator type (ignoring comparison or hash/equality), without invoking any copy/move operations on the container element (this kind of operation is known as "splicing"). Transfer between unique and non-unique containers is also permitted: a node handle from a {{lc|std::map}} can be inserted into an {{lc|std::multimap}}, but not into {{lc|std::unordered_map}} or {{lc|std::set}}.
 
Node handles can be used to transfer ownership of an element between two associative containers with the same key, value, and allocator type (ignoring comparison or hash/equality), without invoking any copy/move operations on the container element (this kind of operation is known as "splicing"). Transfer between unique and non-unique containers is also permitted: a node handle from a {{lc|std::map}} can be inserted into an {{lc|std::multimap}}, but not into {{lc|std::unordered_map}} or {{lc|std::set}}.
  
 
A node handle may be empty, in which case it holds no element and no allocator. The default-constructed and moved-from node handle is empty. In addition, an empty node handle can be produced by a failed call to container member function {{tt|extract}}.
 
A node handle may be empty, in which case it holds no element and no allocator. The default-constructed and moved-from node handle is empty. In addition, an empty node handle can be produced by a failed call to container member function {{tt|extract}}.
 +
 +
Pointers and references to an element that are obtained while it is owned by a node handle are invalidated if the element is successfully inserted into a container.
 +
 +
For all map containers ({{lc|std::map}}, {{lc|std::multimap}}, {{lc|std::unordered_map}}, and {{lc|std::unordered_multimap}}) whose {{tt|key_type}} is {{tt|K}} and {{tt|mapped_type}} is {{tt|T}}, the behavior of operations involving node handles is undefined if a user-defined specialization of {{lc|std::pair}} exists for {{c/core|std::pair<K, T>}} or {{c/core|std::pair<const K, T>}}.
  
 
===Member types===
 
===Member types===
 
{{dsc begin}}
 
{{dsc begin}}
−
{{dsc hitem | Member type | Definition}}
+
{{dsc hitem|Type|Definition}}
−
{{dsc inc | cpp/container/dsc key_type | node_handle}}
+
{{dsc inc|cpp/container/dsc key_type|node_handle}}
−
{{dsc inc | cpp/container/dsc value_type | node_handle}}
+
{{dsc inc|cpp/container/dsc mapped_type|node_handle}}
−
{{dsc inc | cpp/container/dsc mapped_type | node_handle}}
+
{{dsc inc|cpp/container/dsc value_type|node_handle}}
−
{{dsc inc | cpp/container/dsc allocator_type | node_handle}}
+
{{dsc inc|cpp/container/dsc allocator_type|node_handle}}
 +
{{dsc expos mem type|container_node_type|private=yes|a container node, the type is unspecified}}
 +
{{dsc expos mem type|ator_traits|id=ator_traits|private=yes|allocator traits of type {{c/core|std::allocator_traits<allocator_type>}}}}
 
{{dsc end}}
 
{{dsc end}}
  
−
===Member functions===
+
===Data members===
 +
{{dsc begin}}
 +
{{dsc hitem|Member|Definition}}
 +
{{dsc expos mem obj|ptr_|id=ptr|maybe=yes|spec={{cc multi
 +
|typename ator_traits::template
 +
|    rebind_traits<container_node_type>::pointer}}|TODO}}
 +
{{dsc expos mem obj|alloc_|id=alloc|maybe=yes|spec={{c/core|std::optional<allocator_type>}}|TODO}}
 +
{{dsc end}}
  
−
{{member | {{small|node handle::}}node-handle| 2=
+
===Member functions===
 +
{{member|constructors|2=
 
{{dcl begin}}
 
{{dcl begin}}
−
{{dcl|num=1|notes={{mark|node-handle is implementation-defined}}|
+
{{dcl|num=1|
−
constexpr node-handle()
+
constexpr /*node-handle*/() noexcept;
 
}}
 
}}
−
{{dcl |num=2|notes={{mark|node-handle is implementation-defined}}|
+
{{dcl|num=2|
−
node-handle(node-handle&& nh)
+
/*node-handle*/(/*node-handle*/&& nh) noexcept;
 
}}
 
}}
 
{{dcl end}}
 
{{dcl end}}
 
@1@ The default constructor initializes the node handle to the empty state.
 
@1@ The default constructor initializes the node handle to the empty state.
−
@2@ The move constructor takes ownership of the container element from {{tt|nh}}, move-constructs the member allocator, and leaves {{tt|nh}} in the empty state.
+
@2@ The move constructor takes ownership of the container element from {{c|nh}}, move-constructs the member allocator, and leaves {{c|nh}} in the empty state.
  
 
===Parameters===
 
===Parameters===
 
{{par begin}}
 
{{par begin}}
−
{{par | nh | a node handle with the same type (not necessarily the same container)}}
+
{{par|nh|a node handle with the same type (not necessarily the same container)}}
 
{{par end}}
 
{{par end}}
−
 
−
===Exceptions===
 
−
@1@ {{noexcept}}
 
−
@2@ {{noexcept}}
 
  
 
===Notes===
 
===Notes===
Line 56: Line 65:
 
}}
 
}}
  
−
{{member | {{small|node handle::}}operator{{=}}| 2=
+
{{member|operator{{=}}|2=
−
{{dcl begin}}
+
{{ddcl|1=
−
{{dcl|notes={{mark|node-handle is implementation-defined}}|1=
+
/*node-handle*/& operator=(/*node-handle*/&& nh);
−
node-handle& operator=(node-handle&& nh);
+
 
}}
 
}}
−
{{dcl end}}
 
 
* If the node handle is not empty,  
 
* If the node handle is not empty,  
−
:* destroys the {{tt|value_type}} subobject in the container element object managed by this node handle by calling {{tt|std::allocator_traits<allocator_type>::destroy}}
+
:* destroys the {{tt|value_type}} subobject in the container element object managed by this node handle by calling {{tt|ator_traits::destroy}};
−
:* deallocates the container element by calling {{tt|allocator_traits<allocator_type>::rebind_traits<container-node-type>::deallocate}}
+
:* deallocates the container element by calling {{c/core|ator_traits::rebind_traits</*container-node-type*/>::deallocate}};
−
* Acquires ownership of the container element from {{tt|nh}}
+
* Acquires ownership of the container element from {{c|nh}};
−
* If node handle was empty (and so did not contain an allocator) or if {{tt|allocator_traits<allocator_type>::propagate_on_container_move_assignment}} is {{tt|true}}, move-assigns the allocator from {{tt|nh}}
+
* If node handle was empty (and so did not contain an allocator) or if {{c/core|ator_traits::propagate_on_container_move_assignment}} is {{c|true}}, move-assigns the allocator from {{c|nh}};
−
* sets {{tt|nh}} to the empty state
+
* sets {{c|nh}} to the empty state.
  
−
The behavior is undefined if the node is not empty and {{tt|allocator_traits<allocator_type>::propagate_on_container_move_assignment}} is {{tt|false}} and the allocators do not compare equal.
+
The behavior is undefined if the node is not empty and {{c/core|ator_traits::propagate_on_container_move_assignment}} is {{c|false}} and the allocators do not compare equal.
  
 
===Parameters===
 
===Parameters===
 
{{par begin}}
 
{{par begin}}
−
{{par | nh | a node handle with the same type (not necessarily the same container)}}
+
{{par|nh| node handle with the same type (not necessarily the same container)}}
 
{{par end}}
 
{{par end}}
 +
 
===Return===
 
===Return===
 +
{{c|*this}}
 +
 
===Exceptions===
 
===Exceptions===
−
(none)
+
Throws nothing.
  
 
===Notes===
 
===Notes===
Line 83: Line 93:
 
}}
 
}}
  
−
{{member | {{small|node handle::}}~node-handle | 2=
+
{{member|destructor|2=
−
{{dcl begin}}
+
{{ddcl|
−
{{dcl |
+
~/*node-handle*/();
−
~node-handle();
+
 
}}
 
}}
−
{{dcl end}}
 
  
 
* If the node handle is not empty,  
 
* If the node handle is not empty,  
−
:* destroys the {{tt|value_type}} subobject in the container element object managed by this node handle by calling {{tt|std::allocator_traits<allocator_type>::destroy}}
+
:* destroys the {{tt|value_type}} subobject in the container element object managed by this node handle by calling {{c/core|ator_traits::destroy}};
−
:* deallocates the container element by calling {{tt|allocator_traits<allocator_type>::rebind_traits<container-node-type>::deallocate}}
+
:* deallocates the container element by calling {{c/core|ator_traits::rebind_traits</*container-node-type*/>::deallocate}}.
−
 
+
−
===Exceptions===
+
−
(none)
+
 
}}
 
}}
  
−
{{member | {{small|node handle::}}empty| 2=
+
{{member|empty|2=
−
{{dcl begin}}
+
{{ddcl|
−
{{dcl |
+
bool empty() const noexcept;
−
bool empty() const;
+
 
}}
 
}}
−
{{dcl end}}
 
−
Returns {{tt|true}} if the node handle is empty, {{tt|false}} otherwise.
 
  
−
===Exceptions===
+
Returns {{c|true}} if the node handle is empty, {{c|false}} otherwise.
−
{{noexcept}}
+
 
}}
 
}}
  
−
{{member | {{small|node handle::}}operator bool| 2=
+
{{member|operator bool|2=
−
{{dcl begin}}
+
{{ddcl|
−
{{dcl |
+
explicit operator bool() const noexcept;
−
explicit operator bool() const;
+
 
}}
 
}}
−
{{dcl end}}
 
−
Converts to {{tt|false}} if the node handle is empty, {{tt|true}} otherwise.
 
  
−
===Exceptions===
+
Converts to {{c|false}} if the node handle is empty, {{c|true}} otherwise.
−
{{noexcept}}
+
 
}}
 
}}
  
−
 
+
{{member|get_allocator|2=
−
{{member | {{small|node handle::}}get_allocator| 2=
+
{{ddcl|
−
{{dcl begin}}
+
−
{{dcl |
+
 
allocator_type get_allocator() const;
 
allocator_type get_allocator() const;
 
}}
 
}}
−
{{dcl end}}
 
  
 
Returns a copy of the stored allocator (which is a copy of the allocator of the source container). The behavior is undefined if the node handle is empty.
 
Returns a copy of the stored allocator (which is a copy of the allocator of the source container). The behavior is undefined if the node handle is empty.
  
 
===Exceptions===
 
===Exceptions===
−
(none)
+
Throws nothing.
 
}}
 
}}
  
−
{{member | {{small|node handle::}}value | 2=
+
{{member|value|2=
−
{{dcl begin}}
+
{{ddcl|notes={{mark|set containers only}}|
−
{{dcl |notes={{mark|set containers only}}|
+
 
value_type& value() const;
 
value_type& value() const;
 
}}
 
}}
−
{{dcl end}}
 
  
 
Returns a reference to the {{tt|value_type}} subobject in the container element object managed by this node handle. The behavior is undefined if the node handle is empty.
 
Returns a reference to the {{tt|value_type}} subobject in the container element object managed by this node handle. The behavior is undefined if the node handle is empty.
  
 
===Exceptions===
 
===Exceptions===
−
(none)
+
Throws nothing.
 
}}
 
}}
  
−
{{member | {{small|node handle::}}key | 2=
+
{{member|key|2=
−
{{dcl begin}}
+
{{ddcl|notes={{mark|map containers only}}|
−
{{dcl |notes={{mark|map containers only}}|
+
 
key_type& key() const;
 
key_type& key() const;
 
}}
 
}}
−
{{dcl end}}
 
  
 
Returns a non-const reference to the {{tt|key_type}} member of the {{tt|value_type}} subobject in the container element object managed by this node handle. The behavior is undefined if the node handle is empty.
 
Returns a non-const reference to the {{tt|key_type}} member of the {{tt|value_type}} subobject in the container element object managed by this node handle. The behavior is undefined if the node handle is empty.
  
 
===Exceptions===
 
===Exceptions===
−
(none)
+
Throws nothing.
  
 
===Notes===
 
===Notes===
Line 165: Line 155:
 
}}
 
}}
  
−
{{member | {{small|node handle::}}mapped | 2=
+
{{member|mapped|2=
−
{{dcl begin}}
+
{{ddcl|notes={{mark|map containers only}}|
−
{{dcl |notes={{mark|map containers only}}|
+
 
mapped_type& mapped() const;
 
mapped_type& mapped() const;
 
}}
 
}}
−
{{dcl end}}
 
  
 
Returns a reference to the {{tt|mapped_type}} member of the {{tt|value_type}} subobject in the container element object managed by this node handle. The behavior is undefined if the node handle is empty.
 
Returns a reference to the {{tt|mapped_type}} member of the {{tt|value_type}} subobject in the container element object managed by this node handle. The behavior is undefined if the node handle is empty.
  
 
===Exceptions===
 
===Exceptions===
−
(none)
+
Throws nothing.
 
}}
 
}}
  
−
{{member | {{small|node handle::}}swap | 2=
+
{{member|swap|2=
−
{{dcl begin}}
+
{{ddcl|
−
{{dcl |
+
void swap(/*node-handle*/& nh) noexcept(/* see below */);
−
void swap(node-handle& nh)
+
 
}}
 
}}
−
{{dcl end}}
 
  
−
* swaps ownership of container nodes
+
* swaps ownership of container nodes;
−
* if one node is empty or if both nodes are non-empety and {{tt|std::allocator_traits<alloocator_type>::propagate_on_container_swap}} is {{tt|true}}, swaps the allocators as well
+
* if one node is empty or if both nodes are non-empty and {{c/core|ator_traits::propagate_on_container_swap}} is {{c|true}}, swaps the allocators as well.
  
−
The behavior is undefined if both nodes are not empty and {{tt|allocator_traits<allocator_type>::propagate_on_container_swap}} is {{tt|false}} and the allocators do not compare equal.
+
The behavior is undefined if both nodes are not empty and {{c/core|ator_traits::propagate_on_container_swap}} is {{c|false}} and the allocators do not compare equal.
  
 
===Exceptions===
 
===Exceptions===
−
{{noexcept(std::allocator_traits<allocator_type>::propagate_on_container_swap::value {{!!}}
+
{{noexcept|ator_traits::propagate_on_container_swap::value {{!!}}
−
std::allocator_traits<allocator_type>::is_always_equal::value)}}
+
        ator_traits::is_always_equal::value}}
 
}}
 
}}
  
 
===Non-member functions===
 
===Non-member functions===
−
{{member | swap | 2=
+
{{member|swap|2=
−
{{dcl begin}}
+
{{ddcl|
−
{{dcl |
+
friend void swap(/*node-handle*/& x, /*node-handle*/& y) noexcept(noexcept(x.swap(y)));
−
friend void swap(node-handle& x, node-handle& y)  
+
}}
−
{{dcl end}}
+
  
−
Effectively executes {[c|x.swap(y)}}
+
Effectively executes {{c|x.swap(y)}}.
  
−
===Exceptions===
+
{{cpp/hidden friend|{{tti|node-handle}}}}
−
{{noexcept|noexcept(x.swap(y))}}
+
 
}}
 
}}
 +
 +
{{langlinks|es|ja|zh}}

Latest revision as of 11:45, 3 October 2024

 
C++
 
Containers library
 
template</* unspecified */>
class /*node-handle*/;
 (since C++17)
(exposition only*)

Associative containers std::set, std::map, std::multiset, std::multimap, std::unordered_set, std::unordered_map, std::unordered_multiset, std::unordered_multimap are node-based data structures, and their nodes can be extracted as an object of unspecified type known as node handle.

Node handle is a move-only type that owns and provides access to the element (the value_type) stored in the node, and provides non-const access to the key part of the element (the key_type) and the mapped part of the element (the mapped_type). If the node handle destructs while holding the node, the node is properly destructed using the appropriate allocator for the container. The node handle contains a copy of the container’s allocator. This is necessary so that the node handle can outlive the container.

The exact type of node handle (shown here as /*node-handle*/) is unspecified, but each container exposes its node handle type as the member node_type.

Node handles can be used to transfer ownership of an element between two associative containers with the same key, value, and allocator type (ignoring comparison or hash/equality), without invoking any copy/move operations on the container element (this kind of operation is known as "splicing"). Transfer between unique and non-unique containers is also permitted: a node handle from a std::map can be inserted into an std::multimap, but not into std::unordered_map or std::set.

A node handle may be empty, in which case it holds no element and no allocator. The default-constructed and moved-from node handle is empty. In addition, an empty node handle can be produced by a failed call to container member function extract.

Pointers and references to an element that are obtained while it is owned by a node handle are invalidated if the element is successfully inserted into a container.

For all map containers (std::map, std::multimap, std::unordered_map, and std::unordered_multimap) whose key_type is K and mapped_type is T, the behavior of operations involving node handles is undefined if a user-defined specialization of std::pair exists for std::pair<K, T> or std::pair<const K, T>.

Contents

[edit] Member types

Type Definition
key_type (map containers only) the key stored in the node[edit]
mapped_type (map containers only) the mapped part of the element stored in the node[edit]
value_type (set containers only) the element stored in the node[edit]
allocator_type the allocator to be used when destroying the element[edit]
container_node_type (private) a container node, the type is unspecified
(exposition-only member type*)
ator_traits (private) allocator traits of type std::allocator_traits<allocator_type>
(exposition-only member type*)

[edit] Data members

Member Definition
typename ator_traits::template
    rebind_traits<container_node_type>::pointer ptr_
(conditionally present) 		TODO
(exposition-only member object*)
std::optional<allocator_type> alloc_
(conditionally present) 		TODO
(exposition-only member object*)

[edit] Member functions

constructors

constexpr /*node-handle*/() noexcept;
 (1)
/*node-handle*/(/*node-handle*/&& nh) noexcept;
 (2)
1) The default constructor initializes the node handle to the empty state.
2) The move constructor takes ownership of the container element from nh, move-constructs the member allocator, and leaves nh in the empty state.

Parameters

nh - a node handle with the same type (not necessarily the same container)

Notes

Node handles are move-only, the copy constructor is not defined.

operator=

/*node-handle*/& operator=(/*node-handle*/&& nh);
  • If the node handle is not empty,
  • destroys the value_type subobject in the container element object managed by this node handle by calling ator_traits::destroy;
  • deallocates the container element by calling ator_traits::rebind_traits</*container-node-type*/>::deallocate;
  • Acquires ownership of the container element from nh;
  • If node handle was empty (and so did not contain an allocator) or if ator_traits::propagate_on_container_move_assignment is true, move-assigns the allocator from nh;
  • sets nh to the empty state.

The behavior is undefined if the node is not empty and ator_traits::propagate_on_container_move_assignment is false and the allocators do not compare equal.

Parameters

nh - node handle with the same type (not necessarily the same container)

Return

*this

Exceptions

Throws nothing.

Notes

Node handles are move-only, the copy assignment is not defined.

destructor

~/*node-handle*/();
  • If the node handle is not empty,
  • destroys the value_type subobject in the container element object managed by this node handle by calling ator_traits::destroy;
  • deallocates the container element by calling ator_traits::rebind_traits</*container-node-type*/>::deallocate.

empty

bool empty() const noexcept;

Returns true if the node handle is empty, false otherwise.

operator bool

explicit operator bool() const noexcept;

Converts to false if the node handle is empty, true otherwise.

get_allocator

allocator_type get_allocator() const;

Returns a copy of the stored allocator (which is a copy of the allocator of the source container). The behavior is undefined if the node handle is empty.

Exceptions

Throws nothing.

value

value_type& value() const;
 (set containers only)

Returns a reference to the value_type subobject in the container element object managed by this node handle. The behavior is undefined if the node handle is empty.

Exceptions

Throws nothing.

key

key_type& key() const;
 (map containers only)

Returns a non-const reference to the key_type member of the value_type subobject in the container element object managed by this node handle. The behavior is undefined if the node handle is empty.

Exceptions

Throws nothing.

Notes

This function makes it possible to modify the key of a node extracted from a map, and then re-insert it into the map, without ever copying or moving the element.

mapped

mapped_type& mapped() const;
 (map containers only)

Returns a reference to the mapped_type member of the value_type subobject in the container element object managed by this node handle. The behavior is undefined if the node handle is empty.

Exceptions

Throws nothing.

swap

void swap(/*node-handle*/& nh) noexcept(/* see below */);
  • swaps ownership of container nodes;
  • if one node is empty or if both nodes are non-empty and ator_traits::propagate_on_container_swap is true, swaps the allocators as well.

The behavior is undefined if both nodes are not empty and ator_traits::propagate_on_container_swap is false and the allocators do not compare equal.

Exceptions

noexcept specification:  
noexcept(ator_traits::propagate_on_container_swap::value ||
         ator_traits::is_always_equal::value)

[edit] Non-member functions

swap

friend void swap(/*node-handle*/& x, /*node-handle*/& y) noexcept(noexcept(x.swap(y)));

Effectively executes x.swap(y).

This function is not visible to ordinary unqualified or qualified lookup, and can only be found by argument-dependent lookup when node-handle is an associated class of the arguments.

Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/container/node_handle&oldid=176688"