Abstract Data Types - summary

Bag

No requirement on elements; no uniqueness restriction; no defined order

• create empty, create as copy, destroy
• size, isEmpty
• iterate (forward)
• add (by value)
• remove (by iterator)

Sequence (List and Vector)

Well defined order of elements inside the container.

• create empty, create copy, destroy
• size, isEmpty
• iterate (froward or bi-directional; random access for vector)
• get/set value at index (at least for Vector)
• insert at position (by index or by iterator; before or after?; at begin, at end)
• remove at position (by index or by iterator)

Note: Vector offers fast get/set by index; List offers fast insert and remove in the middle. There is no qualitative difference.

Set

Elements must be equality comparable. Elements must be unique (two equal elements are not allowed). Order in collection is undefined.

• create empty, create copy, destroy
• size, isEmpty
• iterate (froward); note: values are read-only
• contains value
• find value (return iterator)
• add (by value)
• remove (by iterator or by value)

Sorted Set

Elements must be equality comparable and less-than comparable. No duplicate are allowed. Order in collection is defined by the less-then comparison.

• create empty, create copy, destroy
• size, isEmpty
• iterate (froward or bi-directional); note: values are read-only
• contains value
• add (by value)
• remove (by iterator or by value)

Map (Dictionary) and Sorted Map

Elements are key-value pairs. Keys are equality comparable (less-than comparable for ordered map). No duplicate keys are allowed. Order is defined by the less-than comparison on keys.

• create empty, create copy, destroy
• size, isEmpty
• iterate (froward or bi-directional); note: keys are read-only, while values can be modified
• contains key
• get/set vallue by key
• add (key/value pair)
• remove (by iterator or by key)

Stack, queue

No restriction on elements. Order is defined by LIFO (last in, first out) or FIFO (first in, first out) strategy.

• create empty, destroy
• isEmpty
• add value (push, enqueue)
• extract value (pop, dequeue)

Double-ended queue

Like for stack and queue, but allowing adding and removing at both ends.

• create empty, destroy
• isEmpty
• pushFront, pushBack
• popFront, popBack