STL Containers

From CometWiki

Revision as of 20:45, 10 November 2011

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.

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.

Stack

Stacks are deque (double-ended queue) containers designed for LIFO (Last In, First Out) access, which means that you are adding and removing elements at the "back" of the container. A stack should be used when the last element you added to the container is the first one you want back out again. Deques are a sort of vector-list hybrid that allow for random access via an index (like arrays/vectors), and also allow 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 deque 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. A queue should be used when the first element you added is the first one you want back out again. Deques are a sort of vector-list hybrid that allow for random access via an index (like arrays/vectors), and also allow 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.

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.

Initial Values All containers can be declared with initial values. These values will be automatically inserted into the container at the beginning of the program, and the container's size will be accurately reflected.

Initial Size All containers except maps can be declared with an initial size. The container will initialize with the specified size, but will contain blank values.

<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.

IB Reference

Core

stlSize

stlEmpty

stlClear

stlReset

stlFront

stlBack

stlPush

stlPop

operator(index/key)

stlSet

stlPushFront

stlPopFront

Iteration

stlFirst

stlLast

stlNext

stlPrev

stlReadKey

stlRead

stlWrite

Utility

stlSort