STL Containers
From CometWiki
Contents |
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.
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 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.
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.
