STL Containers

From CometWiki

Revision as of 23:31, 10 November 2011

Introduction

The Standard Template Library (STL) in C++ provides a variety of containers for storing collections of data. The concept of a container is similar to an array, but the STL containers are more robust in terms of functionality, and some are designed for a more specific purpose than the more general array structure. All containers grow dynamically, negating the need for a declared length and memory management. Each of the containers is designed to be accessed in the most efficient way using different functions, but all containers support a standard set of iteration functions that allow you to access each element in the container.

The three major containers are the vector, the list, and the map. A vector is a collection made of contiguous memory, allowing for efficient access with a numeric index. A list is a collection where each element contains a value plus a pointer to the next value in the list, allowing for extremely efficient insertion into and removal from anywhere in the container. A map is a collection of key/value pairs, mapping a string index to a value.

We have also provided a stack and a queue, which are specialized containers with a more specific purpose in mind.

Initialization

STL 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>)] [value1; value2; ...]

<container-name> (Required) Name used to reference this container in your program.

<container-type> (Required) One of the following: vector, list, map, stack, queue.

<size> (Optional) All containers except maps can be declared with an initial size. The container will initialize with the specified size, containing empty values for uninitialized values.

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.

Vector

A vector is an indexable, sequence container that behaves like an array, but will grow as required. Like arrays, vectors store their data in contiguous memory, which is why access with a numeric index is so efficient, but unlike arrays you get all of the robust functionality of an STL container.

When a vector is created, it has an initial size (either declared in the program or a default specified by the library implementation). Reads/Writes in this space are all very efficient, until the vector fills up and a new value is added. When this happens, the vector automatically allocates another contiguous memory block, and copies the current values. This means that most of the time, adding to a vector is very efficient, but every once in a while this reallocation will take place. Note that a performance hit will only be noticeable on very large vectors.

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.

Lists are implemented as doubly-linked lists, and since each value points to other values, the data does not need to be in contiguous storage like vectors. Thus unlike vectors, lists are more efficient for programs that require consistent insertion/removal functionality, as a vector will have to perform dynamic reallocation (described above) as its size changes.

Map

A map is an associative container consisting of key/value pairs. A string index is "mapped" to the value specified, making the syntax similar to arrays and vectors.

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

Internally, stacks utilize deque (double-ended queue) containers to provide 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

Internally, queues utilize deque (double-ended queue) containers to provide 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.