Previous Lecture lect11 Next Lecture

Relevant topics in the textbook:

Data Structures and Other Objects Using C++ Chapters 5.6, 7, 8

Standard Libarary Containers

There are many implementations of containers.

std::Vector

// main.cpp
#include<vector>

using namespace std;

int main() {
	vector<int> v; // a vector containing int elements
return 0;
}

Under-the-hood, vectors are implemented using arrays and behave similar to arrays.

Adding to a vector example

// main.cpp
#include<iostream>
#include<vector>

using namespace std;

template <class T>
void printVector(vector<T> &v) {
	for (int i = 0; i < v.size(); i++) {
		cout << "v[" << i << "] = " << v[i] << endl;
	}
}

int main() {
	vector<int> v;
	for (int i = 0; i < 5; i++) // it could be any reasonable size…
		v.push_back(i);

	printVector(v);
	return 0;
}

Example

cout << v.at(4) << endl;
cout << v.at(5) << endl; // EXCEPTION THROWN
cout << v[5] << endl; // JUNK

Other supported operations are:

cout << "v.front() = " << v.front() << endl;
cout << "v.back() = " << v.back() << endl;
v.pop_back();
printVector(v);

Vector Initialization

push_back() is one way to create elements in a vector. Though it’s not the only way

Example:

vector<int> v1(100); // initializes vector with 100 elements.
vector<int> v2(100, 1); //initializes vector with 100 elements = 1

Example creating a vector on the heap with a pointer reference to the vector contents on the heap

vector<int>* v = new vector<int>(10,1); // vector on heap with 10 elements initialized to 1
cout << v->size() << endl; // 10
cout << sizeof(v) << endl; // 8 bytes since v is a pointer
printVector(*v);

vector<int> w;
cout << sizeof(w) << endl; // 24 since w is a vector object

Iterators

Example

vector<string> v2;

v2.push_back("Hello.");
v2.push_back("My");
v2.push_back("name");
v2.push_back("is");
v2.push_back("Batman");

for (vector<string>::iterator i = v2.begin(); i < v2.end(); i++) {
	cout << *i << " "; // string value
	cout << i->size() << endl; // prints the size of the strings
}

In the above example, we’ve seen vector functions that deal specifically with iterators.

Example (Showing different ways to index elements using iterators):

vector<string>::iterator i = v2.begin();
cout << v2[4] << endl; 		// Batman
cout << i[4] << endl;		// Batman
cout << *(i + 4) << endl;	// Batman

In order to erase items in the vector, there is an erase method that requires iterators to do this

Example of erasing elements

// Removing 2nd index of the vector
// v2.erase(v2.begin() + 2); // remove "name"
// printVector(v2);

// Removing 1st and 2nd index - [1,3)
v2.erase(v2.begin() + 1, v2.begin() + 3);
printVector(v2);

Stack

#include<iostream>
#include<stack>

using namespace std; 
  
void printStack(stack<int> s) 
{ 
    while (!s.empty()) 
    { 
        cout << s.top() << endl; 
        s.pop(); 
    } 
} 
  
int main () 
{ 
    stack <int> s; 
    s.push(1); 
    s.push(2); 
    s.push(3); 
    s.push(4); 
    s.push(5); 
  
    cout << "Current content of stack: " << endl; 
    printStack(s); 
  
    cout << "Size of stack: " << s.size() << endl; 
    cout << "Top of the stack " << s.top() << endl; 
  
    s.pop(); 
    
    cout << "Current content of stack:" << endl; 
    printStack(s); 
  
    return 0; 
} 

#Queue

#include<iostream>
#include<queue>

using namespace std; 
  
void printQueue(queue<int> q) 
{ 
    while (!q.empty()) 
    { 
        cout << q.front() << endl; 
        q.pop(); 
    } 
} 
  
int main () 
{ 
    queue <int> q; 
    q.push(1); 
    q.push(2); 
    q.push(3); 
    q.push(4); 
    q.push(5); 
  
    cout << "Current content of queue: " << endl; 
    printQueue(q); 
  
    cout << "Size of queue: " << q.size() << endl; 
    cout << "Front of the queue " << q.front() << endl; 
    cout << "Back of the queue " << q.back() << endl;
  
    q.pop(); 
    
    cout << "Current content of queue:" << endl; 
    printQueue(q); 
  
    return 0; 
}