The STL: Containers and Iterators

What are the two most important C++ libraries?

• Standard Library (STD)

• Standard Template Library (STL)

What basic constructs does core C++ provide?

• variables

• control flow

• functions

• classes

• pointers

What does the Streams Library provide?

• iostream

• fstream

• sstream

Console and file input/output

What does std::string provide?

Safer and dynamic text manipulation

What is the Standard Template Library (STL)?

A C++ library built around generic programming using templates that provides:

• containers

• algorithms

• iterators

• function objects

What does the C++ Standard Library (STD) provide?

• Streams library

• Strings library

• Memory management

What are the four main parts of STL?

• Containers

• Algorithms

• Iterators

• Function Objects

What problem do STL containers solve compared to normal arrays?

They automatically manage:

• resizing

• memory allocation

• copying

Why are resizing arrays using new[] error-prone?

It requires manually copying elements and can cause:

• memory leaks

• dangling pointers

What is the main difference between an array and a vector?

Array: fixed size
Vector: dynamic size and automatically manages resizing

What is a vector?

A dynamic array stored in one contiguous block of memory

When should you use a vector?

When you:

• read or iterate a lot

• need fast indexing

• insert/remove at the end

What is the syntax to create a vector?

std::vector<int> v{10, 3, 7};

• std::vector → container type

• int → element type

• v → vector name

• {} → initial values

What does push_back() do?

Adds an element to the end of a vector or deque

v.push_back(42);

What do insert() and erase() do in vectors?

insert() adds an element at a position

v.insert(v.begin()+2,111);

erase() removes an element

v.erase(v.begin());

What is a deque?

A double ended queue made of multiple memory blocks

When should you use a deque instead of a vector?

When you need efficient insert/remove at both ends while still wanting indexing

What are the main deque operations?

d.push_front(-5); // adds to beginning
d.push_back(42); // adds to end

What are container adapters?

Classes that constrain how containers work. They are wrappers around other containers

What is the difference between stack and queue?

Stack:

• LIFO (last in, first out)

Queue:

• FIFO (first in, first out)

What are the main stack functions?

s.push(10); // add element
s.top();    // access top element
s.pop();    // remove top element
s.empty();

What are the main queue functions?

q.push(10); 
q.front();  // first element
q.back();   // last element
q.pop();    // removes first element

Why do linked lists exist?

They allow efficient insertion/removal by storing elements in separate nodes connected by pointers

What is the main limitation of vectors and deques?

Inserting in the middle requires shifting many elements

What is a list in STL?

A doubly-linked list where nodes are linked with next/prev pointers

When should you use a list?

When you frequently insert/erase in the middle

Avoid when:

• you need fast indexing

• you do lots of traversal/reads

What is an iterator?

Provides a uniform way to traverse containers

What do these iterator operations do?

it++;
it--;
*it;

• it++ → move to next node

• it-- → move to previous node

• *it → access value

How do you create a list iterator?

std::list<int>::iterator it;

• std::list<int> → container type

• iterator → iterator type

• it → iterator name

How do you loop through a list using an iterator?

for(it = l.begin(); it != l.end(); it++)
{
    std::cout << *it;
}

• begin() → first element

• end() → after last element

What is a forward_list?

A singly linked list where each node points only to the next node

What are the main forward_list functions?

fl.before_begin(); // position before first element
fl.insert_after(it,111); // insert after position
fl.erase_after(it); // remove after position

Which container should you choose?

Need fast indexing + lots of reading:
→ vector

Need insert/remove at both ends:
→ deque

Need LIFO:
→ stack

Need FIFO:
→ queue

Need frequent middle insertion/removal:
→ list

Need lowest memory overhead linked list:
→ forward_list

Are container adapters (stack/queue) containers themselves?

No. They are wrappers around other containers that restrict how they can be used