A concurrent, sorted, unique‐key associative container.

Synopsis

Declared in <folly/ConcurrentSkipList.h>

template<
    typename T,
    typename Comp = std::less<T>,
    typename NodeAlloc = SysAllocator<char>,
    int MAX_HEIGHT = 24>
class ConcurrentSkipList;

Description

This is a lock‐free‐read skip list that stores unique keys in sorted order, similar to std::set. Reads (find, count, iteration) are lock‐free; writes (add, remove) take locks local to the affected nodes. Removed nodes are reclaimed lazily once the last Accessor is destroyed, so all access goes through an Accessor or Skipper.

Types

Name

Description

Accessor

Provides stdlib‐like access to a ConcurrentSkipList.

Skipper

Traverses a ConcurrentSkipList by skipping to lower‐bound positions.

Type Aliases

Name

Description

NodeType

The internal node type holding a single element.

const_iterator

Read‐only forward iterator over the elements of the list.

iterator

Forward iterator over the elements of the list.

key_type

The key type used to order and look up elements.

value_type

The element type stored in the list.

Member Functions

Name

Description

ConcurrentSkipList [constructor]

Constructs a skip list whose head node has the given height.

~ConcurrentSkipList [destructor]

Destroys the list and its nodes.

empty

Returns whether the list has no elements.

size

Returns the number of elements in the list.

Static Member Functions

Name

Description

create

Creates a new instance and returns an Accessor to it.

createInstance

Creates a shared skip list with the given initial head height.

Template Parameters

Name

Description

T

The element (key) type stored in the list.

Comp

The comparison functor used to order elements.

NodeAlloc

The allocator used for nodes; it must be thread‐safe.

MAX_HEIGHT

The maximum number of skip‐list levels, in [2, 64).]

Created with MrDocs