STL Containers
From CometWiki
m (→Initialization) |
m (→IB Reference) |
||
| Line 44: | Line 44: | ||
===IB Reference=== | ===IB Reference=== | ||
| - | ==== | + | ====Core==== |
| - | ==== | + | =====stlSize===== |
| - | + | =====stlEmpty===== | |
| - | ====stlEmpty==== | + | =====stlClear===== |
| - | ====stlClear==== | + | =====stlReset===== |
| - | ====stlReset==== | + | =====stlFront===== |
| - | ==== | + | =====stlBack===== |
| - | + | =====stlPush===== | |
| - | ====stlBack==== | + | =====stlPop===== |
| - | ====stlPush==== | + | =====operator(index/key)===== |
| - | ====stlPop==== | + | =====stlSet===== |
| - | ====operator()==== | + | =====stlPushFront===== |
| - | ====stlSet==== | + | =====stlPopFront===== |
| - | ====stlPushFront==== | + | ====Iteration==== |
| - | ====stlPopFront==== | + | =====stlFirst===== |
| - | ====stlFirst==== | + | =====stlLast===== |
| - | ====stlLast==== | + | =====stlNext===== |
| - | ====stlNext==== | + | =====stlPrev===== |
| - | ====stlPrev==== | + | =====stlReadKey===== |
| - | ====stlReadKey==== | + | =====stlRead===== |
| - | ====stlRead==== | + | =====stlWrite===== |
| - | ====stlWrite==== | + | ====Utility==== |
| + | =====stlSort===== | ||
Revision as of 01:07, 10 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.
STL Containers will automatically grow in size as needed. This means that although an insertion/addition operation will be efficient [ul]most of the time[/ul], sometimes the container will dynamically need to reallocate itself to new memory in order to contain the new value. In most small cases, this time is negligible, but in larger containers or containers with large values, it is possible that you might see a performance hit when this occurs.
All STL containers are iterable.
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.
Initialization
Containers are defined in the declarative section, using a similar syntax to formats with some extra options. Containers can be declared empty, with an initial size (except maps), or with initial values. You must provide the name you will use to reference the container, as well as the type of container it will be.
<container-name>: <container-type>[(<size>)] [<initial-value>; <initial-value>; ...] <map-name>: map [<initial-key>, <initial-value>; <initial-key>, <initial-value>; ...]
For example:
myVector: vector myList: list 10; 20; 30; 40 myStack: stack(10) myQueue: queue(5) 10; "twenty"; 30; 40; 50 myMap: map "key1", "value1"; "key2", 20
Are all valid declarations for STL containers.
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.
