STL Containers
From CometWiki
m (→Container Types) |
|||
| Line 1: | Line 1: | ||
===Introduction=== | ===Introduction=== | ||
| - | The | + | The Standard Template Library (STL) in C++ provides a variety of containers for storing sets of data. The concept is similar to arrays, but each container is designed with a specific purpose in mind, and implemented to be most efficient for that purpose. |
| + | |||
| - | |||
====Initialization==== | ====Initialization==== | ||
| Line 11: | Line 11: | ||
===Container Types=== | ===Container Types=== | ||
| - | The following containers have been implemented in Comet32. | + | The following containers have been implemented in Comet32. Containers come in two forms: sequence containers maintain a specific order (generally the order of inserted items), and associative containers which do not maintain an order but instead rely on an associated key to retrieve the value. |
====Vector==== | ====Vector==== | ||
| - | + | A vector is an indexable, sequence container that behaves like an array, but will grow as required. Like arrays, vectors store their contents in a contiguous storage location, meaning you can efficiently access a value with an index. | |
====List==== | ====List==== | ||
| - | + | A list is a sequence container in which each value points to the next value. This way, lists allow for fast insertion and deletion anywhere in the container, but do now allow for random access via an index like arrays/vectors. | |
====Stack==== | ====Stack==== | ||
| - | Stacks are | + | Stacks are containers designed for LIFO (Last In, First Out) access, which means that you are adding and removing elements at the "back" of the container. Internally, the stack is implemented using a double-ended queue (deque), which is sort of a hybrid between a vector and a list. Essentially, a deque allows for random access via an index (like arrays/vectors), and also allows for efficient addition/removal of elements at the beginning or end of the container. Insertions/removals from the middle of the container are not as efficient as lists. |
====Queue==== | ====Queue==== | ||
| - | Queues are | + | Queues are containers designed for FIFO (First In, First Out) access, which means that you are adding elements at the "back" of the container, and removing them from the "front" of the container. Internally, the stack is implemented using a double-ended queue (deque), which is sort of a hybrid between a vector and a list. Essentially, a deque allows for random access via an index (like arrays/vectors), and also allows for efficient addition/removal of elements at the beginning or end of the container. Insertions/removals from the middle of the container are not as efficient as lists. |
====Map==== | ====Map==== | ||
| - | + | A map is an associative container consisting of key/value pairs. A map is basically a vector that uses a string index instead of a numerical index. Maps are designed for efficient access to values using their key, unlike sequence containers which are more efficient at accessing elements by their position (index). Keys are unique - that is there will never be two values associated with the same key. | |
===IB Reference=== | ===IB Reference=== | ||
Revision as of 23:09, 9 November 2011
Contents |
Introduction
The Standard Template Library (STL) in C++ provides a variety of containers for storing sets of data. The concept is similar to arrays, but each container is designed with a specific purpose in mind, and implemented to be most efficient for that purpose.
Initialization
Containers are defined with a similar syntax to formats, with a few added options.
General Usage
Once initialized, there is a standard set of functions that provide access to the STL containers. In general, there are functions that store and access data in the containers, and there are also functions to iterate over and read data from the containers.
Container Types
The following containers have been implemented in Comet32. Containers come in two forms: sequence containers maintain a specific order (generally the order of inserted items), and associative containers which do not maintain an order but instead rely on an associated key to retrieve the value.
Vector
A vector is an indexable, sequence container that behaves like an array, but will grow as required. Like arrays, vectors store their contents in a contiguous storage location, meaning you can efficiently access a value with an index.
List
A list is a sequence container in which each value points to the next value. This way, lists allow for fast insertion and deletion anywhere in the container, but do now allow for random access via an index like arrays/vectors.
Stack
Stacks are containers designed for LIFO (Last In, First Out) access, which means that you are adding and removing elements at the "back" of the container. Internally, the stack is implemented using a double-ended queue (deque), which is sort of a hybrid between a vector and a list. Essentially, a deque allows for random access via an index (like arrays/vectors), and also allows for efficient addition/removal of elements at the beginning or end of the container. Insertions/removals from the middle of the container are not as efficient as lists.
Queue
Queues are containers designed for FIFO (First In, First Out) access, which means that you are adding elements at the "back" of the container, and removing them from the "front" of the container. Internally, the stack is implemented using a double-ended queue (deque), which is sort of a hybrid between a vector and a list. Essentially, a deque allows for random access via an index (like arrays/vectors), and also allows for efficient addition/removal of elements at the beginning or end of the container. Insertions/removals from the middle of the container are not as efficient as lists.
Map
A map is an associative container consisting of key/value pairs. A map is basically a vector that uses a string index instead of a numerical index. Maps are designed for efficient access to values using their key, unlike sequence containers which are more efficient at accessing elements by their position (index). Keys are unique - that is there will never be two values associated with the same key.
