Page Comparison

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.

...

Lists: A container that stores elements in a linked list. Lists are efficient for inserting or removing elements at any position, but accessing elements is slower than with arrays or vectors.

...

Maps: A container that stores key-value pairs in a sorted order. Maps are efficient for searching and retrieving data based on a key.

...

Sets: A container that stores unique elements in a sorted order. Sets are useful when you need to maintain a collection of elements without duplicates.

...

Queues: A container that stores elements in a FIFO (first-in, first-out) order. Queues are useful when you need to process elements in the order they were added.

...

• 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

...

Stacks: A container that stores elements in a LIFO (last-in, first-out) order. Stacks are useful when you need to process elements in reverse order.

Each of these containers has its own set of methods and functions that can be used to manipulate the data it stores. For example, you can add elements to a vector using the push_back method, or remove elements from a list using the erase method. Choosing the right container for your needs depends on the specific requirements of your program, such as the type of data being stored, the operations that need to be performed, and the expected size and complexity of the container.

1. Lists: Lists are especially useful when you need to perform frequent insertions and deletions in the middle of the sequence, and you do not need to access elements by their position. For example, you might use a list in a system for managing a to-do list, where tasks can often be inserted or removed in the middle of the list, and there's typically no need to access tasks by their position.

2. Pair: Pairs are great for associating two items together that might not naturally fit into a class or structure. For instance, a pair could be useful if you wanted to keep track of a student's name and their corresponding grade.

3. Map: Maps are commonly used when there is a key-value relationship between elements and you need to frequently look up values by their corresponding keys. For instance, you could use a map to associate students' names with their grades in a gradebook application, where you need to quickly find a student's grade by their name.

4. Set: Sets are helpful when you need to maintain a collection of elements, but you care more about whether or not an item is in the collection than about its order or position. Sets ensure that each element is unique and allows for efficient lookup of elements. For instance, you might use a set to represent a group of students in a class and check whether a particular student is in the class.

5. Queue: Queues are useful when you need to maintain a FIFO (First In First Out) order of elements. They're used in scenarios like CPU scheduling, Disk Scheduling, and more. A real-life example could be a print queue, where print tasks are removed for printing in the order they were added (i.e., the first document added is the first one to be printed).

6. Deque: Deques are useful when you need to frequently add or remove elements from both ends of the sequence, such as in certain specific algorithms like the 'sliding window' algorithm. The random access operation (accessing an element at a certain index) is also efficient in a deque, so if your problem involves such operations, a deque would be a better choice than a list or a forward_list.

\uD83D\uDCD8 Outline

\uD83D\uDCCB To Do

...

Containers Active Reading

...

Review Student Notes

...

• 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.