Wednesday, March 23, 2011

STL- Containers

- Vectors are a kind of sequence containers. As such, their elements are ordered following a strict linear sequence.
- Vector containers are implemented as dynamic arrays; Just as regular arrays, vector containers have their elements stored in contiguous storage locations, which means that their elements can be accessed not only using iterators but also using offsets on regular pointers to elements.
- But unlike regular arrays, storage in vectors is handled automatically, allowing it to be expanded and contracted as needed.
- Vectors are good at:
* Accessing individual elements by their position index (constant time).
* Iterating over the elements in any order (linear time).
* Add and remove elements from its end (constant amortized time).
- Compared to arrays, they provide almost the same performance for these tasks, plus they have the ability to be easily re-sized. Although, they usually consume more memory than arrays when their capacity is handled automatically
Element access:
1 - operator[] - Access element at a particular locattion(ofset)
2 - at - Access element at a particular locattion(ofset)(throws exception, if fails).
3 - front - Access first element
4 - back - Access last element

- Internally, vectors -like all containers- have a size, which represents the amount of elements contained in the vector. But vectors, also have a capacity, which determines the amount of storage space they have allocated, and which can be either equal or greater than the actual size. When number of elements exhausted the capacity of Vector, reallocation of vectors will be required.
- Re-allocations may be a costly operation in terms of performance, since they generally involve the entire storage space used by the vector to be copied to a new location. Therefore, whenever large increases in size are planned for a vector, it is recommended to explicitly indicate a capacity for the vector using member function vector::reserve.
- How vector size is managed ? is it a continuous memory allocation or memory blocks are linked?
- Vectors are dynamic arrays, which have pre-defined capacity in the memory. when the elements are exhausted the capacity, the whole vector will be copied to new place for reallocation of the capacity.

- Lists are a kind of sequence containers. As such, their elements are ordered following a linear sequence.
- List containers are implemented as doubly-linked lists; Doubly linked lists can store each of the elements they contain in different and unrelated storage locations. The ordering is kept by the association to each element of a link to the element preceding it and a link to the element following it.
- This provides the following advantages to list containers:
* Efficient insertion and removal of elements anywhere in the container (constant time).
* Efficient moving elements and block of elements within the container or even between different containers (constant time).
* Iterating over the elements in forward or reverse order (linear time).
- Compared to other base standard sequence containers (vectors and deques), lists perform generally better in inserting, extracting and moving elements in any position within the container, and therefore also in algorithms that make intensive use of these, like sorting algorithms.
- The main drawback of lists compared to these other sequence containers is that they lack direct access to the elements by their position.

- Sets are a kind of associative containers that stores unique elements, and in which the elements themselves are the keys.
- Internally, the elements in a set are always sorted from lower to higher following a specific strict weak ordering criterion set on container construction.
- Sets are typically implemented as binary search trees.
- Therefore, the main characteristics of set as an associative container are:
* Unique element values: no two elements in the set can compare equal to each other. For a similar associative container allowing for multiple equivalent elements, see multiset.
* The element value is the key itself. For a similar associative container where elements are accessed using a key, but map to a value different than this key, see map.
* Elements follow a strict weak ordering at all times. Unordered associative arrays, like unordered_set, are available in implementations following TR1.

- Map is a Sorted Associative Container that associates objects of type Key with objects of type Data.
- Map is a Pair Associative Container, meaning that its value type is pair.
- It is also a Unique Associative Container, meaning that no two elements have the same key.
- Internally, the elements in the map are sorted from lower to higher key value following a specific strict weak ordering criterion set on construction
- As associative containers, they are especially designed to be efficient accessing its elements by their key
- Iterators are using to access the mapped value based on key.
- Iterators to elements of map,access to both the key and the mapped value

No comments:

Post a Comment