OOP C3 Container

Collection objects are objects that can store an arbitrary number of other objects.

STL

Standard Template Library, STL: Part of the ISO Standard C++ Library and Data Structures and algorithms for C++.

Advantages

• Reduce development time: Data-structures already written and debugged.
• Code readability: Fit more meaningful stuff on one page.
• Robustness: STL data structures grow automatically.
• Portable, Maintainable code
• Easy

Components

The library includes:

• A Pair class (pairs of anything, e.gint/int, int/char, etc)
• Containers:
  • Vector: expandable array
  • Deque: expandable array at both ends
  • List: double-linked
  • Sets and Maps
• Basic Algorithms like sort, search, etc

All identifiers in library are in std namespace: using namespace std;

In summary, the three parts of STL are: Containers, Algorithms and
Iterators.

All Sequential Containers

• vector: variable array
• deque : dual-end queue
• list : double-linked-list
• forward_list : as it
• array : as “array”
• string : char. array

Vector

#include<vector>
vector<ElementType> myVec;

When declaring a collection,we need to specify the type of the collection itself vector and the type of the elements that we plan to store in the collection.

Property

• increase its internal capacity as required: as more items are added, it simply makes enough room for them.
• keeps its own private count of how many items it is currently storing. Its size method returns the number of objects currently stored in it.
• maintains the order of items you insert into it. You can later retrieve them in the same order.

Operations

Constructors

vector<ElemType> c; 
vector<ElemType> c1(c2);  //construct with another vec

Simple Methods

c.size( ); // num items 
c.empty( ); // empty? 
==, !=, <, >, <=, >=  //betwn vecs!
c.swap(v1); // swap

Iterators

c.begin( ); // first position
c.end( ); // last position

Element access

c.at(index); //item at index  
c[index]; 
c.front(); // first item 
c.back( ); // last item 

Add/Remove/Find

c.push_back(e);	  	 //push e at the end of c, grow tails automatically 
c.pop_back();   	 //pop the last inserted element
c.insert(pos, e); 	 //insert e at pos
c.erase(pos);		//erase element at pos
c.clear( );			//make c empty
c.find(first, last, item); //find item from pos first to last 

List

Property

Same basic concepts as vector and similar constructors, ability to compare lists (== , != , < , <= , > , >= ) and ability to access front and back of list.

#include<list>
list<ElementType> myList;
list<char> d;
d.front(); // first item 
d.back();  // last item 
d.begin( ); // first position
d.end( ); // last position

BUT additional ability on Add/Remove/Find.

d.push_back(e);
d.push_front(e);
d.pop_back();
d.pop_front();
d.insert(pos,e);
d.remove(e);
d.erase(pos);

Map

Maps: collections that contain pairs of values.
Pairs: consisting of a key and a value. Supplying a key, a value paired will be retrieved.

#include <map> 
#include <string>
map<string,float> price; 
price[“snapple”] = 0.75; 
price[“coke”] = 0.50; 
string item; 
double total=0; 
while ( cin >> item )
	total += price[item];

Iterator

list<int> L;
L.push_back(1);
L.push_back(2);
list<int>::iterator li; //declaring
li = L.end();           //end
li = L.begin();         //front
++li;                   //increment
*li = 5;                //derenferenced

as arguments

list<int> L; 
vector<int> V; 
// put list in vector 
copy( L.begin(), L.end(), V.begin());

Loop

• for-each loop:

  for(ElementType varName: array/vector/...Name) {
  	loop statements ...
  }
  for(int i : L) // auto 
  { 
      cout<<i<<" ";
  }

  A for-each loop iterates over the elements of arrays, vectors, or any other data sets. It assigns the value of the current element to the variable iterator declared inside the loop.

  Pros and Cons

  • Advantages
    • Eliminates the possibility of errors
    • Makes the code more readable.
    • Easy to implement
    • No pre-initialization of the iterator
  • Disadvantages
  • Cannot directly access the corresponding element indices
  • Cannot traverse the elements in reverse order
  • Doesn’t allow the user to skip any element as it traverses over each one

Typdef

• Annoying to type long names
• Simplify with typedef typedef.
• Easy to change implementation.

Sevral Pitfalls

Accessing an invalid

• use push_back()
• Preallocate with constructor.
• Reallocate with reserve()
• Check capacity()

Inadvertently inserting into map<> .

foo["bob"]==1 will silently created entry “bob” with value 1!

• Use count() to check for a key without creating a new entry.

Forget using empty() on list<>

• empty() is garuanted to be done in constant time, while size()/count() doesn’t !

Use invalid iterator

list<int> L; 
list<int>::iterator li; 
li = L.begin(); 
L.erase(li); 
++li; // WRONG
// Use return value of erase
li = L.erase(li); //Right