[#BloombergLP-bdlcc-SkipList-0a]
= xref:BloombergLP.adoc[BloombergLP]::xref:BloombergLP/bdlcc.adoc[bdlcc]::SkipList
:relfileprefix: ../../
:mrdocs:

This class provides a generic thread‐safe Skip List (an ordered associative container). It supports an almost complete set of _value_ _semantic_ operations, including copy construction, assignment, equality comparison, and `ostream` printing (but not BDEX serialization).

== Synopsis

Declared in `<bdlcc_skiplist.h>`

[source,cpp,subs="verbatim,replacements,macros,-callouts"]
----
template<
    class KEY,
    class DATA>
class SkipList;
----

== Type Aliases

[cols="1,4"]
|===
| Name| Description
| xref:BloombergLP/bdlcc/SkipList-0a/Pair.adoc[`Pair`] 
| Unmanaged reference to a key/data pair in this list.
| xref:BloombergLP/bdlcc/SkipList-0a/PairHandle.adoc[`PairHandle`] 
| Managed handle to a key/data pair in this list.
|===


== Enums

[cols="1,4"]
|===
| Name| Description
| xref:BloombergLP/bdlcc/SkipList-0a/_04enum.adoc[`Unnamed enum`] 
| Status codes returned by skip‐list operations.
|===


== Member Functions

[cols="1,4"]
|===
| Name| Description
| xref:BloombergLP/bdlcc/SkipList-0a/2constructor-0a.adoc[`SkipList`]         [.small]#[constructor]#
| Constructors
| xref:BloombergLP/bdlcc/SkipList-0a/2destructor.adoc[`~SkipList`] [.small]#[destructor]#
| Destroy this Skip List. The behavior is undefined if references are outstanding to any pairs in the list.
| xref:BloombergLP/bdlcc/SkipList-0a/operator_assign.adoc[`operator=`] 
| Assign to this Skip List the value of the specified `rhs` list and return a reference to the modifiable list.
| xref:BloombergLP/bdlcc/SkipList-0a/add-09d.adoc[`add`] 
| `add` overloads
| xref:BloombergLP/bdlcc/SkipList-0a/addAtLevelRaw.adoc[`addAtLevelRaw`] 
| Add the specified `key` / `data` pair to this list at the specified `level`, and load into the specified `result` a reference to the pair in the list. The `result` reference must be released (using `releaseReferenceRaw`) when it is no longer needed. Load into the the optionally specified `newFrontFlag` a `true` value if the pair is at the front of the list, and a `false` value otherwise. The behavior is undefined if `level` is greater than the implementation‐defined maximum level of this class, or if `level` is negative. Note that this method is provided for testing purposes.
| xref:BloombergLP/bdlcc/SkipList-0a/addAtLevelRawR.adoc[`addAtLevelRawR`] 
| Add the specified `key` / `data` pair to this list at the specified `level`, and load into the specified `result` a reference to the pair in the list. Search for the correct position for `key` from the back of the list (in descending order by key value). The `result` reference must be released (using `releaseReferenceRaw`) when it is no longer needed. Load into the optionally specified `newFrontFlag` a `true` value if the pair is at the front of the list, and a `false` value otherwise. The behavior is undefined if `level` is greater than the implementation‐defined maximum level of this class, or if `level` is negative. Note that this method is provided for testing purposes.
| xref:BloombergLP/bdlcc/SkipList-0a/addAtLevelUniqueRaw.adoc[`addAtLevelUniqueRaw`] 
| Add the specified `key` / `data` pair to this list at the specified `level`, and load into the specified `result` a reference to the pair in the list. The `result` reference must be released (using `releaseReferenceRaw`) when it is no longer needed. Load into the the optionally specified `newFrontFlag` a `true` value if the pair is at the front of the list, and a `false` value otherwise. The behavior is undefined if `level` is greater than the implementation‐defined maximum level of this class, or if `level` is negative. Return 0 on success, and a non‐zero value (with no effect on the list) if `key` is already in the list. Note that this method is provided for testing purposes.
| xref:BloombergLP/bdlcc/SkipList-0a/addAtLevelUniqueRawR.adoc[`addAtLevelUniqueRawR`] 
| Add the specified `key` / `data` pair to this list at the specified `level`, and load into the specified `result` a reference to the pair in the list. Search for the correct position for `key` from the back of the list (in descending order by key value). The `result` reference must be released (using `releaseReferenceRaw`) when it is no longer needed. Load into the optionally specified `newFrontFlag` a `true` value if the pair is at the front of the list, and a `false` value otherwise. The behavior is undefined if `level` is greater than the implementation‐defined maximum level of this class, or if `level` is negative. Return 0 on success, and a non‐zero value (with no effect on the list) if `key` is already in the list. Note that this method is provided for testing purposes.
| xref:BloombergLP/bdlcc/SkipList-0a/addPairReferenceRaw.adoc[`addPairReferenceRaw`] 
| Increment the reference count for the list element referred to by the specified `reference`. There must be a corresponding call to `releaseReferenceRaw` when the reference is no longer needed. The behavior is undefined `item` has already been released. Return `reference`.
| xref:BloombergLP/bdlcc/SkipList-0a/addR-0f.adoc[`addR`] 
| `addR` overloads
| xref:BloombergLP/bdlcc/SkipList-0a/addRaw.adoc[`addRaw`] 
| Add the specified `key` / `data` pair to this list, and load into the specified `result` a reference to the pair in the list. The `result` reference must be released (using `releaseReferenceRaw`) when it is no longer needed. Load into the optionally specified `newFrontFlag` a `true` value if the pair is at the front of the list, and a `false` value otherwise.
| xref:BloombergLP/bdlcc/SkipList-0a/addRawR.adoc[`addRawR`] 
| Add the specified `key` / `data` pair to this list, and load into the specified `result` a reference to the pair in the list. Search for the correct position for `key` from the back of the list (in descending order by key value). The `result` reference must be released (using `releaseReferenceRaw`) when it is no longer needed. Load into the optionally specified `newFrontFlag` a `true` value if the pair is at the front of the list, and a `false` value otherwise.
| xref:BloombergLP/bdlcc/SkipList-0a/addUnique-03.adoc[`addUnique`] 
| `addUnique` overloads
| xref:BloombergLP/bdlcc/SkipList-0a/addUniqueR-09.adoc[`addUniqueR`] 
| `addUniqueR` overloads
| xref:BloombergLP/bdlcc/SkipList-0a/addUniqueRaw.adoc[`addUniqueRaw`] 
| Add the specified `key` / `data` pair to this list, and load into the specified `result` a reference to the pair in the list. The `result` reference must be released (using `releaseReferenceRaw`) when it is no longer needed. Load into the optionally specified `newFrontFlag` a `true` value if the pair is at the front of the list, and a `false` value otherwise. Return 0 on success, and a non‐zero value (with no effect on the list) if `key` is already in the list.
| xref:BloombergLP/bdlcc/SkipList-0a/addUniqueRawR.adoc[`addUniqueRawR`] 
| Add the specified `key` / `data` pair to this list, and load into the specified `result` a reference to the pair in the list. Search for the correct position for `key` from the back of the list (in descending order by key value). The `result` reference must be released (using `releaseReferenceRaw`) when it is no longer needed. Load into the optionally specified `newFrontFlag` a `true` value if the pair is at the front of the list, and a `false` value otherwise. Return 0 on success, and a non‐zero value (with no effect on the list) if `key` is already in the list.
| xref:BloombergLP/bdlcc/SkipList-0a/allocator.adoc[`allocator`] 
| Return the allocator used by this object to supply memory.
| xref:BloombergLP/bdlcc/SkipList-0a/back.adoc[`back`] 
| Load into the specified `back` a reference to the last item in the list. Return 0 on success, and a non‐zero value (with no effect on `back`) if the list is empty.
| xref:BloombergLP/bdlcc/SkipList-0a/backRaw.adoc[`backRaw`] 
| Load into the specified `back` a reference to the last item in the list. The `back` reference must be released (using `releaseReferenceRaw`) when it is no longer needed. Return 0 on success, and a non‐zero value if the list is empty. Note that if the list is empty, the value of `*back` is undefined.
| xref:BloombergLP/bdlcc/SkipList-0a/data.adoc[`data`] 
| Load into the specified `value` the "data" value of the pair identified by the `reference`.
| xref:BloombergLP/bdlcc/SkipList-0a/exists.adoc[`exists`] 
| Return `true` if there is a pair in the list with the specified `key`, and `false` otherwise.
| xref:BloombergLP/bdlcc/SkipList-0a/find.adoc[`find`] 
| Load into the specified `item` a reference to the element in this list with the specified `key` found by searching the list from the front (in ascending order of key value). If multiple elements having `key` are in the container, load `item` with the _first_ matching element. Return 0 on success, and a non‐zero value (with no effect on `item`) if no such element exists. If there are multiple elements in the list with the `key`, it is undefined which one is returned.
| xref:BloombergLP/bdlcc/SkipList-0a/findLowerBound.adoc[`findLowerBound`] 
| Load into the specified `item` a reference to the first element in this list whose key value is not less than the specified `key` found by searching the list from the front (in ascending order of key value). Return 0 on success, and a non‐zero value (with no effect on `item`) if no such element exists.
| xref:BloombergLP/bdlcc/SkipList-0a/findLowerBoundR.adoc[`findLowerBoundR`] 
| Load into the specified `item` a reference to the first element in this list whose key value is not less than the specified `key` found by searching the list from the back (in descending order of key value). Return 0 on success, and a non‐zero value (with no effect on `item`) if no such element exists.
| xref:BloombergLP/bdlcc/SkipList-0a/findLowerBoundRRaw.adoc[`findLowerBoundRRaw`] 
| Load into the specified `item` a reference to the first element in this list whose key value is not less than the specified `key` found by searching the list from the back (in descending order of key value). Return 0 on success, and a non‐zero value (with no effect on `item`) if no such element exists. The `item` reference must be released (using `releaseReferenceRaw`) when it is no longer needed.
| xref:BloombergLP/bdlcc/SkipList-0a/findLowerBoundRaw.adoc[`findLowerBoundRaw`] 
| Load into the specified `item` a reference to the first element in this list whose key value is not less than the specified `key` found by searching the list from the front (in ascending order of key value). Return 0 on success, and a non‐zero value (with no effect on `item`) if no such element exists. The `item` reference must be released (using `releaseReferenceRaw`) when it is no longer needed.
| xref:BloombergLP/bdlcc/SkipList-0a/findR.adoc[`findR`] 
| Load into the specified `item` a reference to the element in this list with the specified `key` found by searching the list from the back (in descending order of key value). If multiple elements having `key` are in the container, load `item` with the _last_ matching element. `key` are present, find the last one. Return 0 on success, and a non‐zero value (with no effect on `item`) if no such element exists. If there are multiple elements in the list with the `key`, it is undefined which one is returned.
| xref:BloombergLP/bdlcc/SkipList-0a/findRRaw.adoc[`findRRaw`] 
| Load into the specified `item` a reference to the element in this list with the specified `key` found by searching the list from the back (in descending order of key value). Return 0 on success, and a non‐zero value (with no effect on `item`) if no such element exists. If there are multiple elements in the list with the `key`, it is undefined which one is returned. The `item` reference must be released (using `releaseReferenceRaw`) when it is no longer needed.
| xref:BloombergLP/bdlcc/SkipList-0a/findRaw.adoc[`findRaw`] 
| Load into the specified `item` a reference to the element in this list with the specified `key` found by searching the list from the front (in ascending order of key value). Return 0 on success, and a non‐zero value (with no effect on `item`) if no such element exists. If there are multiple elements in the list with the `key`, it is undefined which one is returned. The `item` reference must be released (using `releaseReferenceRaw`) when it is no longer needed.
| xref:BloombergLP/bdlcc/SkipList-0a/findUpperBound.adoc[`findUpperBound`] 
| Load into the specified `item` a reference to the first element in this list whose key value is greater than the specified `key` found by searching the list from the front (in ascending order of key value). Return 0 on success, and a non‐zero value (with no effect on `item`) if no such element exists.
| xref:BloombergLP/bdlcc/SkipList-0a/findUpperBoundR.adoc[`findUpperBoundR`] 
| Load into the specified `item` a reference to the first element in this list whose key value is greater than the specified `key` found by searching the list from the back (in descending order of key value). Return 0 on success, and a non‐zero value (with no effect on `item`) if no such element exists.
| xref:BloombergLP/bdlcc/SkipList-0a/findUpperBoundRRaw.adoc[`findUpperBoundRRaw`] 
| Load into the specified `item` a reference to the first element in this list whose key value is greater than the specified `key` found by searching the list from the back (in descending order of key value). Return 0 on success, and a non‐zero value (with no effect on `item`) if no such element exists. The `item` reference must be released (using `releaseReferenceRaw`) when it is no longer needed.
| xref:BloombergLP/bdlcc/SkipList-0a/findUpperBoundRaw.adoc[`findUpperBoundRaw`] 
| Load into the specified `item` a reference to the first element in this list whose key value is greater than the specified `key` found by searching the list from the front (in ascending order of key value). Return 0 on success, and a non‐zero value (with no effect on `item`) if no such element exists. The `item` reference must be released (using `releaseReferenceRaw`) when it is no longer needed.
| xref:BloombergLP/bdlcc/SkipList-0a/front.adoc[`front`] 
| Load into the specified `front` a reference to the first item in the list. Return 0 on success, and a non‐zero value (with no effect on `front`) if the list is empty.
| xref:BloombergLP/bdlcc/SkipList-0a/frontRaw.adoc[`frontRaw`] 
| Load into the specified `front` a reference to the first item in the list. The `front` reference must be released (using `releaseReferenceRaw`) when it is no longer needed. Return 0 on success, and a non‐zero value if the list is empty.
| xref:BloombergLP/bdlcc/SkipList-0a/isEmpty.adoc[`isEmpty`] 
| Return `true` if this list is empty, and `false` otherwise.
| xref:BloombergLP/bdlcc/SkipList-0a/key.adoc[`key`] 
| Load into the specified `value` the "key" value of the pair identified by the `reference`.
| xref:BloombergLP/bdlcc/SkipList-0a/length.adoc[`length`] 
| Return the number of items in this list.
| xref:BloombergLP/bdlcc/SkipList-0a/next.adoc[`next`] 
| Load into the specified `next` a reference to the item that appears in the list after the item identified by the specified `reference`. Return 0 on success, or a non‐zero value if `reference` refers to the back of the list.
| xref:BloombergLP/bdlcc/SkipList-0a/nextRaw.adoc[`nextRaw`] 
| Load into the specified `next` a reference to the item that appears in the list after the item identified by the specified `reference`. The `next` reference must be released (using `releaseReferenceRaw`) when it is no longer needed. Return 0 on success, or a non‐zero value if `reference` refers to the back of the list.
| xref:BloombergLP/bdlcc/SkipList-0a/popFront.adoc[`popFront`] 
| Remove the first item from the list and load a reference to it into the optionally specified `item`. Return 0 on success, and a non‐zero value if the list is empty.
| xref:BloombergLP/bdlcc/SkipList-0a/popFrontRaw.adoc[`popFrontRaw`] 
| Remove the first item from the list and load a reference to it into the specified `item`. This reference must be released (using `releaseReferenceRaw`) when it is no longer needed. Return 0 on success, and a non‐zero value if the list is empty.
| xref:BloombergLP/bdlcc/SkipList-0a/previous.adoc[`previous`] 
| Load into the specified `prevPair` a reference to the pair that appears in the list before the pair identified by the specified `reference`. Return 0 on success, or a non‐zero value if `reference` refers to the front of the list.
| xref:BloombergLP/bdlcc/SkipList-0a/previousRaw.adoc[`previousRaw`] 
| Load into the specified `prevPair` a reference to the pair that appears in the list before the pair identified by the specified `reference`. The `prevPair` reference must be released (using `releaseReferenceRaw`) when it is no longer needed. Return 0 on success, or a non‐zero value if `reference` refers to the front of the list.
| xref:BloombergLP/bdlcc/SkipList-0a/print.adoc[`print`] 
| Format this list object to the specified output `stream` at the (absolute value of) the optionally specified indentation `level` and return a reference to `stream`. If `level` is specified, optionally specify `spacesPerLevel`, the number of spaces per indentation level for this and all of its nested objects. If `level` is negative, suppress indentation of the first line. If `spacesPerLevel` is negative, suppress all indentation AND format the entire output on one line. If `stream` is not valid on entry, this operation has no effect.
| xref:BloombergLP/bdlcc/SkipList-0a/releaseReferenceRaw.adoc[`releaseReferenceRaw`] 
| Release the specified `reference`. After calling this method, the value of `reference` must not be used or released again.
| xref:BloombergLP/bdlcc/SkipList-0a/remove.adoc[`remove`] 
| Remove the item identified by the specified `reference` from the list. Return 0 on success, and a non‐zero value if the pair has already been removed from the list.
| xref:BloombergLP/bdlcc/SkipList-0a/removeAll-0e.adoc[`removeAll`] 
| `removeAll` overloads
| xref:BloombergLP/bdlcc/SkipList-0a/removeAllRaw-08.adoc[`removeAllRaw`] 
| `removeAllRaw` overloads
| xref:BloombergLP/bdlcc/SkipList-0a/skipBackward.adoc[`skipBackward`] 
| If the item identified by the specified `item` is not at the front of the list, load a reference to the previous item in the list into `item`; otherwise reset the value of `item`. Return 0 on success, and `e_NOT_FOUND` (with no effect on the value of `item`) if `item` is no longer in the list.
| xref:BloombergLP/bdlcc/SkipList-0a/skipBackwardRaw.adoc[`skipBackwardRaw`] 
| If the item identified by the specified `item` is not at the front of the list, load a reference to the previous item in the list into `item`; otherwise reset the value of `item`. Return 0 on success, and `e_NOT_FOUND` (with no effect on the value of `item`) if `item` is no longer in the list.
| xref:BloombergLP/bdlcc/SkipList-0a/skipForward.adoc[`skipForward`] 
| If the item identified by the specified `item` is not at the end of the list, load a reference to the next item in the list into `item`; otherwise reset the value of `item`. Return 0 on success, and `e_NOT_FOUND` (with no effect on the value of `item`) if `item` is no longer in the list.
| xref:BloombergLP/bdlcc/SkipList-0a/skipForwardRaw.adoc[`skipForwardRaw`] 
| If the item identified by the specified `item` is not at the end of the list, load a reference to the next item in the list into `item`; otherwise reset the value of `item`. Return 0 on success, and `e_NOT_FOUND` (with no effect on the value of `item`) if `item` is no longer in the list.
| xref:BloombergLP/bdlcc/SkipList-0a/update.adoc[`update`] 
| Assign the specified `newKey` value to the pair identified by the specified `reference`, moving the pair within the list as necessary. Load into the optionally specified `newFrontFlag` a `true` value if the new location of the pair is the front of the list. Return 0 on success, `e_NOT_FOUND` if the pair referred to by `reference` is no longer in the list, or `e_DUPLICATE` if the optionally specified `allowDuplicates` is `false` and `newKey` already appears in the list.
| xref:BloombergLP/bdlcc/SkipList-0a/updateR.adoc[`updateR`] 
| Assign the specified `newKey` value to the pair identified by the specified `reference`, moving the pair within the list as necessary. Search for the new position from the back of the list (in descending order by key value). Load into the optionally specified `newFrontFlag` a `true` value if the new location of the pair is the front of the list. Return 0 on success, `e_NOT_FOUND` if the pair referred to by `reference` is no longer in the list, or `e_DUPLICATE` if the optionally specified `allowDuplicates` is `false` and `newKey` already appears in the list.
| xref:BloombergLP/bdlcc/SkipList-0a/2conversion.adoc[`operator BloombergLP::bslmf::NestedTraitDeclaration<SkipList, UsesBslmaAllocator>`] 
| Declare that this type uses a `bslma` allocator.
|===


== Static Member Functions

[cols="1,4"]
|===
| Name| Description
| xref:BloombergLP/bdlcc/SkipList-0a/level.adoc[`level`] 
| Return the level of the pair identified by the specified `reference`. This method is provided for testing.
|===


== Specializations

[cols="1,4"]
|===
| Name| Description
| xref:BloombergLP/bdlcc/SkipList-0b.adoc[`SkipList<long long, EventData>`] 
| This class provides a generic thread‐safe Skip List (an ordered associative container). It supports an almost complete set of _value_ _semantic_ operations, including copy construction, assignment, equality comparison, and `ostream` printing (but not BDEX serialization).
| xref:BloombergLP/bdlcc/SkipList-0d.adoc[`SkipList<long long, RecurringEventData>`] 
| This class provides a generic thread‐safe Skip List (an ordered associative container). It supports an almost complete set of _value_ _semantic_ operations, including copy construction, assignment, equality comparison, and `ostream` printing (but not BDEX serialization).
|===


== Friends

[cols="1,4"]
|===
| Name| Description
| `xref:BloombergLP/bdlcc/operator_not_eq-03.adoc[BloombergLP::bdlcc::operator!=]`
| Return `true` if the specified lists have different values.
| `xref:BloombergLP/bdlcc/operator_eq-0e.adoc[BloombergLP::bdlcc::operator==]`
| Return `true` if the specified lists have the same value.
| `xref:BloombergLP/bdlcc/SkipListPairHandle.adoc[BloombergLP::bdlcc::SkipListPairHandle]`
| Objects of this class refer to an association (pair) in a `SkipList`. A `bdlcc::SkipListPairHandle` is implicitly convertible to a `const Pair*` and thus may be used anywhere in the `SkipList` API that a `const Pair*` is expected.
| `xref:BloombergLP/bdlcc/SkipListPair.adoc[BloombergLP::bdlcc::SkipListPair]`
| Pointers to objects of this class are used in the "raw" API of `SkipList`; however, objects of the class are never constructed as the class serves only to provide type‐safe pointers.
|===

== Non-Member Functions

[cols="1,4"]
|===
| Name| Description
| xref:BloombergLP/bdlcc/operator_not_eq-0e.adoc[`operator!=`]
| Return `true` if the specified `lhs` list list has a different value from the specified `rhs` list, and `false` otherwise. Two lists A and B have different values if they have a different of elements, or if there exists an i in the range [0, numberOfElements) such that the i'th pair from the] front of A differs in key or data values from i'th pair from the front of B.
| xref:BloombergLP/bdlcc/operator_eq-05.adoc[`operator==`]
| Return `true` if the specified `lhs` list has the same value as the specified `rhs` list, and `false` otherwise. Two lists A and B have the same value if they have the same number of elements, and if for all i in the range [0, numberOfElements), the i'th pair from the front of A has the] same key and data values as the i'th pair from the front of B. Note that if there are duplicate key values in a list, the order of iteration over those pairs may be different than for another list that was constructed from the same sequence of values (and thus the lists may not compare equal).
|===


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