Block 1 – Sequence Containers and Container Adapters

Sequence containers store elements in a linear order. Container adapters provide restricted interfaces on top of other containers.

1.1 Sequence Containers

Sequence containers maintain the order of insertion and allow sequential access.

The main sequence containers are:

std::vector
std::deque
std::list

1.1.1 std::vector

Purpose

std::vector is a dynamic array that automatically resizes.

Characteristics

Elements stored in contiguous memory
Supports fast random access
Efficient insertion at the end
Reallocation occurs when capacity is exceeded

Common Operations

Function	Description
`push_back()`	Add element at end
`pop_back()`	Remove last element
`size()`	Number of elements
`capacity()`	Allocated storage
`clear()`	Remove all elements
`at()`	Access element with bounds checking
`[]`	Direct access

Example

#include <iostream>
#include <vector>int main() {
    std::vector<int> v;    v.push_back(10);
    v.push_back(20);
    v.push_back(30);    std::cout << v[1]; 
}

Time Complexity

Operation	Complexity
Access	O(1)
Insert end	O(1) amortized
Insert middle	O(n)

1.1.2 std::deque

Purpose

std::deque (double-ended queue) allows efficient insertion/removal at both ends.

Characteristics

Not stored in one contiguous memory block
Supports random access
Efficient front and back operations

Common Operations

Function	Description
`push_front()`	Insert at front
`push_back()`	Insert at end
`pop_front()`	Remove first element
`pop_back()`	Remove last element

Example

#include <iostream>
#include <deque>int main() {
    std::deque<int> d;    d.push_back(10);
    d.push_front(5);    std::cout << d.front();
}

1.1.3 std::list

Purpose

std::list implements a doubly linked list.

Characteristics

Elements stored in separate memory locations
Fast insertion and deletion anywhere
No random access

Common Operations

Function	Description
`push_front()`	Insert at beginning
`push_back()`	Insert at end
`insert()`	Insert at position
`erase()`	Remove element
`remove()`	Remove specific value

Example

#include <iostream>
#include <list>int main() {
    std::list<int> l = {1,2,3};    l.push_front(0);
    l.push_back(4);
}

1.2 Container Adapters

Container adapters provide restricted interfaces using underlying containers.

Adapters include:

std::stack
std::queue
std::priority_queue

They usually use deque or vector internally.

1.2.1 std::stack

Purpose

Implements LIFO (Last In First Out) structure.

Characteristics

Access only the top element
Cannot iterate directly
Built on top of deque by default

Operations

Function	Description
`push()`	Add element
`pop()`	Remove top
`top()`	Access top element
`empty()`	Check if empty

Example

#include <stack>std::stack<int> s;s.push(10);
s.push(20);std::cout << s.top();

1.2.2 std::queue

Purpose

Implements FIFO (First In First Out) structure.

Operations

Function	Description
`push()`	Add element
`pop()`	Remove front
`front()`	Access first
`back()`	Access last

Example

#include <queue>std::queue<int> q;q.push(1);
q.push(2);std::cout << q.front();

1.2.3 std::priority_queue

Purpose

Stores elements based on priority order.

By default:

largest element has highest priority

Operations

Function	Description
`push()`	Insert element
`pop()`	Remove highest priority
`top()`	Access highest priority

Example

#include <queue>std::priority_queue<int> pq;pq.push(10);
pq.push(30);
pq.push(20);std::cout << pq.top();

Output:

1.3 Applying Standard Methods

Common operations across containers:

Operation	Example
Insertion	`push_back()`, `push_front()`
Deletion	`pop_back()`, `pop_front()`
Access	`front()`, `back()`
Size	`size()`
Clear	`clear()`

Example:

std::vector<int> v;v.push_back(10);
v.push_back(20);v.pop_back();

1.4 Using Iterators

Iterators allow traversal through containers.

Types of Iterators

Iterator	Description
`begin()`	First element
`end()`	After last element
`rbegin()`	Reverse start
`rend()`	Reverse end

Example

std::vector<int> v = {1,2,3};for(auto it = v.begin(); it != v.end(); ++it)
{
    std::cout << *it;
}

Range-based loop:

for(int x : v)
{
    std::cout << x;
}

1.5 Using Simple and Complex Data Types

Containers can store:

Built-in types

std::vector<int> numbers;
std::deque<double> values;

User-defined types

struct Person
{
    std::string name;
    int age;
};std::vector<Person> people;

Example

people.push_back({"Venkat", 35});

1.6 Accessing and Modifying Elements

Elements can be accessed using:

Member functions

std::vector<int> v = {1,2,3};v[1] = 10;
v.at(2) = 20;

Iterator access

for(auto it = v.begin(); it != v.end(); ++it)
{
    *it = *it * 2;
}

Example result:

2 4 6

Summary

Container	Access	Insert	Memory
vector	Fast random	Fast end	contiguous
deque	Random	Fast both ends	segmented
list	Sequential	Fast anywhere	linked nodes

Adapters:

Adapter	Structure
stack	LIFO
queue	FIFO
priority_queue	Highest priority first