Stl Containers

Stl Containers - Transcript

STL Data Types in C
Vectors lists and queues G64OOS

vector
A dynamic list type

include iostream include string include vector include algorithm using namespace std int main string s vector string v cout Enter lines of text to be sorted n cout followed by the word stop n for getline cin s if s stop break v push back s for sort v begin v end cout The lines after sorting n for int i 0 i v size i cout v i endl return 0

vector
using namespace std include string include vector include algorithm vector string v declaration v push back s add on end sort v begin v end call to sort v size no of elements v i access to vector elements

STL containers
vector Array list Doubly linked list slist Singly linked list queue FIFO first in first out structure deque Array like structure with efficient insertion and removal at both ends set Set of unique elements stack LIFO last in first out structure

Insert and remove
push front first pop front push back pop back Inserts element before the not available for vector Removes the first element not available for vector Inserts element after the last Removes the last element

vector and deque
Subscripting access without bounds checking at Subscripting access with bounds checking

Other methods
empty size insert erase clear resize front back Boolean indicating if the container is empty Returns the number of elements Inserts an element at a particular position Removes an element at a particular position Removes all the elements Resizes the container Returns a reference to the first element Returns a reference to the last element

Using iterators
In the STL there are a special class of access types called iterators that act as pointers to the special classes like vectors These are declared with the syntax
vector string iterator i

I is for our vector of strings

Using an iterator
vector string iterator i for i v begin i v end i cout i endl

v end is one past the end

Reverse iterators
It is possible to go backwards through a vector using a reverse iterator This is declared
vector string reverse iterator i

It would be used as follows
for i v rbegin i v rend i cout i endl

This would go backward through the vector despite the operation

Vectors Lists and Deques
The above are known as container adaptors They all offer efficient means of storage and retrieval The simplest change to our program would have been to use a deque instead of a vector The following program shows how slight in syntax that program is

include iostream include string include deque include algorithm using namespace std int main string s deque string v cout Enter lines of text to be sorted n cout followed by the word stop n for getline cin s if s stop break v push back s for sort v begin v end cout The samelines after sorting n for deque string iterator i v begin i v end i cout i endl return 0

Vectors lists and deques
vectors permit data to be added deleted at the end of the vector Can randomly access data deques permit data to be added deleted at the beginning or end Can randomly access data List can add or delete data at any position in the list Cannot randomly access data

Vectors lists and deques
vector type

Insert Delete here deque type

Insert Delete here list type

Insert Delete at Any position

Points to note with list
The use of
list int const iterator i

The member functions
push front push back insert erase

const iterator
The difference from an ordinary iterator is that the function now returns a reference to a constant value which will prevent client code from modifying the returned value

Maps
include iostream include map include string using namespace std int main map string int freq map of words and their frequencies string word input buffer for words Read words tokens from input stream while cin word freq word Write the count and the word map string int const iterator iter for iter freq begin iter freq end iter cout iter second iter first endl return 0 end main

There is also a multimap
There can be more than one key with the same value We won t cover this as it is a bit specialised