1.1 Sequence Containers in C++

1️⃣ std::vector

Purpose:
std::vector is a dynamic array that stores elements in contiguous memory and allows fast random access.

Characteristics

• Elements stored in continuous memory
• Fast random access using index (O(1))
• Efficient insertion/removal at end
• Slower insertion/removal at beginning or middle
• Automatically resizes when capacity is exceeded

Example

#include <iostream>
#include <vector>int main() {
    std::vector<int> v = {10, 20, 30};    v.push_back(40);   // add element at end    std::cout << v[1]; // random access
}

Complexity

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

When to use

✔ Best general-purpose container
✔ When random access is required
✔ When mostly adding elements at the end

---

2️⃣ std::deque

Purpose:
std::deque (double-ended queue) allows efficient insertion and deletion at both ends.

Characteristics

• Elements not stored in one contiguous block
• Fast insertion/removal at front and back
• Supports random access
• Slightly slower than vector for access

Example

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

Complexity

Operation	Complexity
Access	O(1)
Insert front/back	O(1)
Insert middle	O(n)

When to use

✔ When you frequently insert/remove at both ends
✔ For queue-like structures

---

3️⃣ std::list

Purpose:
std::list is a doubly linked list that allows efficient insertion and deletion anywhere.

Characteristics

• Elements stored in non-contiguous memory
• Each element linked with previous and next pointers
• No random access
• Fast insertion/deletion anywhere if iterator known

Example

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

Complexity

Operation	Complexity
Access	O(n)
Insert	O(1)
Delete	O(1)

When to use

✔ When frequent insertions/deletions in the middle
✔ When iterators must remain valid after insertions

---

📊 Comparison

Feature	vector	deque	list
Memory layout	Contiguous	Segmented	Non-contiguous
Random access	Yes	Yes	No
Insert front	Slow	Fast	Fast
Insert end	Fast	Fast	Fast
Insert middle	Slow	Slow	Fast
Memory usage	Low	Medium	High

---

✅ Summary

• std::vector → best general container, fast random access
• std::deque → efficient insertion/removal at both ends
• std::list → efficient insertion/deletion anywhere but no random access