[#BloombergLP-bslalg-RbTreeUtil-findInsertLocation-080]
= xref:BloombergLP.adoc[BloombergLP]::xref:BloombergLP/bslalg.adoc[bslalg]::xref:BloombergLP/bslalg/RbTreeUtil.adoc[RbTreeUtil]::findInsertLocation
:relfileprefix: ../../../
:mrdocs:

`findInsertLocation` overloads

== Synopses

Declared in `<bslalg_rbtreeutil.h>`

Return the address of the node that would be the parent a node holding the specified `value`, if it were to be inserted into the specified `tree` (organized according to the specified `comparator`), and load, into the specified `insertAsLeftChildFlag`, `true` if `value` would be held as the returned node's left child, and `false` if `value` would be held in its right child, unless `tree` is empty, in which case return `tree‐>sentinel()` and load `true` into `insertAsLeftChildFlag`. Optionally specify a `hint`, suggesting a node in `tree` that might be the immediate successor of a node holding `value` if it were to be inserted into `tree`. If the supplied `hint` is the successor, this operation will take amortized constant time; otherwise, it will take O(log(N)) operations, where N is the number of nodes in the tree. If a node holding `value` is inserted as suggested by this method, the resulting tree will be an ordered binary tree, but may require rebalancing (and re‐coloring) to again be a valid red‐black tree. `COMPARATOR` shall be a functor providing two methods that can be called as if they have the following signatures: ` bool operator()(const RbTreeNode&, const VALUE&) const; bool operator()(const VALUE&, const RbTreeNode&) const; ` The behavior is undefined unless `comparator` provides a strict weak ordering on objects of type `VALUE`, `tree` is well‐formed (see `isWellFormed`), and `hint`, if supplied, is a node in `tree`. Note that this operation is intended to be used in conjunction with the `insertAt` method.


[source,cpp,subs="verbatim,replacements,macros,-callouts"]
----
template<
    class NODE_VALUE_COMPARATOR,
    class VALUE>
static
xref:BloombergLP/bslalg/RbTreeNode.adoc[RbTreeNode]*
xref:BloombergLP/bslalg/RbTreeUtil/findInsertLocation-08e.adoc[findInsertLocation](
    bool* insertAsLeftChildFlag,
    xref:BloombergLP/bslalg/RbTreeAnchor.adoc[RbTreeAnchor]* tree,
    NODE_VALUE_COMPARATOR& comparator,
    VALUE const& value);
----

[.small]#xref:BloombergLP/bslalg/RbTreeUtil/findInsertLocation-08e.adoc[_» more..._]#

Return the address of the node before which the specified `value` should be inserted into the specified `tree`, using the specified `hint` to improve performance when it is the immediate successor.


[source,cpp,subs="verbatim,replacements,macros,-callouts"]
----
template<
    class NODE_VALUE_COMPARATOR,
    class VALUE>
static
xref:BloombergLP/bslalg/RbTreeNode.adoc[RbTreeNode]*
xref:BloombergLP/bslalg/RbTreeUtil/findInsertLocation-00.adoc[findInsertLocation](
    bool* insertAsLeftChildFlag,
    xref:BloombergLP/bslalg/RbTreeAnchor.adoc[RbTreeAnchor]* tree,
    NODE_VALUE_COMPARATOR& comparator,
    VALUE const& value,
    xref:BloombergLP/bslalg/RbTreeNode.adoc[RbTreeNode]* hint);
----

[.small]#xref:BloombergLP/bslalg/RbTreeUtil/findInsertLocation-00.adoc[_» more..._]#


[.small]#Created with https://www.mrdocs.com[MrDocs]#