Dynamic sets are collections of elements that can change over time — elements can be inserted, removed, or searched for. Unlike mathematical sets, which are static, algorithms often need sets that grow or shrink during execution.
Each element in a dynamic set is represented as an object. One attribute of this object is typically a key, which uniquely identifies the element and may come from a totally ordered domain. Keys may also carry extra satellite data, which the set stores but doesn’t use for ordering or searching.
Different applications require different operations. The most common set operations include:
Queries return information without modifying the set, while modifying operations change it.
Some data structures assume a total ordering so they can efficiently support operations involving minimum, maximum, or successor relationships.
The time cost of operations depends on how the set is implemented. Arrays are simple but often inefficient:
An array is stored in memory as a contiguous block of bytes. If the first element has index s, the array starts at address a, and each element uses b bytes, then the i-th element’s memory location can be calculated directly.
Because of this direct addressing, array access takes constant time, regardless of the index.
Most programming languages require array elements to have the same size. If elements have different sizes, the array instead stores pointers, each of fixed size, and each pointer refers to a separate object in memory.
Multidimensional arrays can be stored in different ways: