C++ STL Containers Overview

Standard Template Library (STL) Containers in C++

• The C++ Standard Template Library (STL) provides a rich set of container classes. These containers are designed for efficient storage and manipulation of data.
• Containers are categorized based on their data organization and supported operations.
• Common containers handled by the STL:
  • vector: Dynamically sized array-like structure.
  • list: Doubly linked list.
  • map: Associates keys with values in a sorted manner (using red-black trees).
  • unordered_map: Associates keys with values in a hash table, providing faster average lookup compared to map.
  • set: Stores unique elements in a sorted manner (using red-black trees).
  • unordered_set: Stores unique elements in a hash table.
  • stack: LIFO (Last-In, First-Out) data structure.

Vector

• Provides contiguous storage of elements.
• Elements can be accessed using their index.
• Offers methods to dynamically resize as needed.
• Efficient for sequential access and random access.
• Not efficient for insertions or deletions in the middle.
• Example Usage:

  #include <vector>
  std::vector<int> myVector;
  myVector.push_back(1);
  myVector.push_back(2);
  myVector.push_back(3);
  std::cout << myVector[1] << std::endl; // Output: 2
  

List

• Implements a doubly linked list.
• Elements stored not contiguously in memory.
• Efficient for insertions, deletions, and iterating over the list.
• Less efficient for random access compared to vectors.
• Example Usage:

  #include <list>
  std::list<int> myList;
  myList.push_back(1);
  myList.push_back(2);
  myList.push_back(3);
  std::list<int>::iterator it = myList.begin();
  ++it;
  std::cout << *it << std::endl; // Output: 2
  

Map

• Stores key-value pairs in a sorted manner using a balanced binary search tree (usually a red-black tree).
• Keys must be unique.
• Guaranteed sorted order.
• Elements accessed using keys.
• Example Usage:

  #include <map>
  std::map<std::string, int> myMap;
  myMap["apple"] = 1;
  myMap["banana"] = 2;
  std::cout << myMap["banana"] << std::endl; // Output: 2
  

Unordered Map

• Stores key-value pairs in a hash table.
• Keys do not need to be unique.
• Average time complexity for insertion, deletion, and search is O(1), but worst-case complexity can be O(n) in the presence of hash collisions.
• Elements are not ordered.
• Example Usage:

  #include <unordered_map>
  std::unordered_map<std::string, int> myUnorderedMap;
  myUnorderedMap["apple"] = 1;
  myUnorderedMap["banana"] = 2;
  std::cout << myUnorderedMap["banana"] << std::endl; // Output: 2
  

Set

• Stores unique elements in a sorted manner using a balanced binary search tree (often a red-black tree).
• Only stores the unique keys without values, ensuring uniqueness.
• Example Usage:

  #include <set>
  std::set<int> mySet;
  mySet.insert(1);
  mySet.insert(2);
  mySet.insert(1);  // Duplicate is ignored
  std::cout << mySet.size() << std::endl;  // Output: 2
  

Unordered Set

• Similar to set, but stores elements in a hash table.
• Does not maintain order.
• Efficient for checking the presence of an element.
• Example Usage:

  #include <unordered_set>
  std::unordered_set<int> myUnorderedSet;
  myUnorderedSet.insert(1);
  myUnorderedSet.insert(2);
  myUnorderedSet.insert(1); // Duplicate is ignored
  
  std::cout << myUnorderedSet.size() << std::endl; //Output 2
  

Stack

• LIFO (Last-In, First-Out) data structure.
• Elements added to (pushed) and removed from (popped) the top.
• Example Usage:

  #include <stack>
  std::stack<int> myStack;
  myStack.push(1);
  myStack.push(2);
  std::cout << myStack.top() << std::endl; // Output: 2
  myStack.pop();
  std::cout << myStack.top() << std::endl; // Output: 1
  

This quiz covers the various container classes provided by the C++ Standard Template Library (STL). Learn about the key features and uses of containers such as vectors, lists, maps, and sets. Test your knowledge on how these containers efficiently store and manipulate data.