Containers

Common C++ Containers

Arrays

• Description: Fixed-size containers that store elements of the same data type in contiguous memory locations.

• Characteristics:

  • Size must be known at compile time.

  • Fast access to elements using indices.

• Use Case Example: Storing a fixed number of sensor readings where the number of readings doesn't change.

Vectors

• Description: Dynamic arrays that can grow or shrink in size as elements are added or removed.

• Characteristics:

  • Elements are stored contiguously.

  • Provides fast random access to elements.

  • Supports dynamic resizing.

• Use Case Example: Managing a list of user inputs where the number of inputs isn't known beforehand.

Lists

• Description: Doubly linked lists that allow efficient insertion and deletion of elements anywhere in the sequence.

• Characteristics:

  • Non-contiguous memory storage.

  • No direct access to elements by index (requires traversal).

• Use Case Example: Implementing a task scheduler where tasks can be added or removed from any position.

Deques

• Description: Double-ended queues that allow insertion and deletion of elements at both the front and back.

• Characteristics:

  • Combines features of vectors and lists.

  • Efficient insertion/removal at both ends.

  • Provides random access to elements.

• Use Case Example: Implementing a sliding window algorithm where elements are frequently added and removed from both ends.

Stacks

• Description: Adapters that provide LIFO (Last-In, First-Out) access to elements.

• Characteristics:

  • Based on other containers like vectors or deques.

  • Only allows access to the top element.

• Use Case Example: Evaluating expressions in compilers where the most recent operation needs to be processed first.

Queues

• Description: Adapters that provide FIFO (First-In, First-Out) access to elements.

• Characteristics:

  • Based on other containers like lists or deques.

  • Only allows access to the front element.

• Use Case Example: Managing print jobs in a printer queue where documents are printed in the order they were submitted.

Priority Queues

• Description: Adapters that store elements with priorities, allowing quick access to the highest-priority element.

• Characteristics:

  • Elements are ordered based on priority.

  • Efficient retrieval of the top-priority element.

• Use Case Example: Task scheduling systems where tasks with higher priority need to be executed first.

Sets

• Description: Containers that store unique elements in a specific order.

• Characteristics:

  • Automatically sorts elements.

  • No duplicate elements allowed.

  • Provides fast search, insertion, and removal.

• Use Case Example: Keeping track of unique user IDs in a system.

Maps

• Description: Associative containers that store key-value pairs in a sorted order based on the keys.

• Characteristics:

  • Keys are unique and sorted.

  • Provides fast retrieval of values based on keys.

• Use Case Example: Storing configuration settings where each setting has a unique name (key) and a value.

Unordered Sets and Maps

• Description: Similar to sets and maps but do not maintain order; instead, they use hashing for faster access.

• Characteristics:

  • Faster insertion and retrieval on average.

  • Elements are not sorted.

• Use Case Example: Implementing a cache where quick access is more important than element order.

Choosing the Right Container

Selecting the appropriate container depends on your specific needs:

• Need Fast Access by Index: Use vectors or deques.

• Need Frequent Insertions/Deletions at Ends: Use deques.

• Need Frequent Insertions/Deletions in Middle: Use lists.

• Need Unique Elements with Fast Lookup: Use sets or unordered_sets.

• Need Key-Value Associations: Use maps or unordered_maps.

• Need LIFO or FIFO Access: Use stacks (LIFO) or queues (FIFO).

Real-World Examples

• Lists in To-Do Applications:

  • Use Case: Managing tasks that can be added or removed from any position.

  • Container: list

• Maps in Configuration Management:

  • Use Case: Storing settings where each setting has a name and a value.

  • Container: map

• Sets in User Management:

  • Use Case: Maintaining a collection of unique usernames.

  • Container: set

• Queues in Print Spooling:

  • Use Case: Managing print jobs to ensure documents are printed in order.

  • Container: queue

• Deques in Algorithm Implementation:

  • Use Case: Implementing algorithms like sliding window where elements are added and removed from both ends.

  • Container: deque

C++ containers provide a versatile and efficient way to handle collections of data. By understanding the features and characteristics of each container, you can choose the most suitable one for your application's needs, leading to better performance and more maintainable code.

In this module, we'll explore these containers in detail, covering:

• How to use each container effectively.

• The advantages and trade-offs of different containers.

• Practical examples and use cases.

• Best practices for container selection and usage.