Collection (abstract data type)

Subtypes

Other abstract data types are more specific than collection.

Linear

Some collections maintain a linear ordering of items with access to one or both ends. The data structure implementing such a collection need not be linear. For example, a priority queue is often implemented as a heap, which is a kind of tree.

Notable linear collections include:

• list
• stack
• queue
• priority queue
• double-ended queue
• double-ended priority queue

Associative

Some collections are interpreted as a sort of function: given an input, the collection yields an output.

Notable associative collections include:

• set
• multiset
• associative array
• graph
• tree

A set can be interpreted as a specialized multiset, which in turn is a specialized associative array, in each case by limiting the possible values—considering a set as represented by its indicator function.

Implementation

As an abstract data type, collection does not prescribe an implementation, though type theory describes implementation considerations.

Some collection types are provided as primitive data types in a language, such as lists, while more complex collection types are implemented as composite data types in libraries, sometimes in a language's standard library. Examples include:

• C++: also known as containers, implemented in C++ Standard Library and earlier Standard Template Library
• Java: implemented in the Java collections framework, many of which reside in namespace java.util
• Oracle PL/SQL implements collections as programmer-defined types | author-link1 = Steven Feuerstein | publication-date = 2007 | access-date = 2017-06-26
• Python: some built-in, others implemented in the collections library
• .NET provides the and interfaces and implementations such as .
• Rust provides various collections (such as the and structs) in the namespace.

References

References

1. "Vec in std::vec - Rust".
2. "HashMap in std::collections - Rust".
3. "std::collections - Rust".