C++ Data Structures: Vectors and the STL

Flashcards for reviewing C++ data structures, vectors, and the STL.

Data Structure Definition

A way of organizing and storing data in a computer so that it can be used efficiently.

Three Main Goals of Data Structures

Storage, Access, Manipulation.

Linear Data Structure

Elements are arranged in a sequential order.

Examples of Linear Data Structures

Arrays, Linked Lists, Stacks, Queues

Non-Linear Data Structures

Elements are not arranged sequentially, often using a hierarchy.

Examples of Non-Linear Data Structures

Trees, Graphs

Why Data Structures Matter

Saves time and resources by providing optimized methods for data operations; simplifies complex problems by organizing data in a logical way; enables programs to handle growing amounts of data effectively.

The C++ Standard Template Library (STL)

A collection of pre-built, generic classes and functions that implement common data structures and algorithms.

Key Components of the STL

Containers, Iterators, Algorithms

Containers (STL)

Objects that store data (e.g., vectors, lists, maps).

Iterators (STL)

Used to traverse elements within a container. They act like pointers, enabling you to move through the data.

Algorithms (STL)

Functions that perform operations on containers (e.g., sorting, searching).

What is a Vector?

A dynamic array that can change its size as needed during program execution.

Header File for Vectors in C++

Syntax for Creating a Vector

vector vectorName;

Methods for Accessing Vector Elements

[], .at(), .front(), .back(), .size()

.assign() (Vector Operation)

Fill a vector with new values.

.push_back() (Vector Operation)

Adds an element to the end of the vector.

.pop_back() (Vector Operation)

Removes the last element of the vector.

.insert() (Vector Operation)

Inserts elements at a specific position in the vector.

.clear() (Vector Operation)

Removes all elements from the vector.

.erase() (Vector Operation)

Removes elements at a specific position or range in the vector.

.empty() (Vector Operation)

Checks if the vector is empty (returns true if empty, false otherwise).

.resize() (Vector Operation)

Changes the size of the vector.

.rbegin() & .rend() (Vector Operation)

Reverse iterators for traversing the vector in reverse order.

.swap() (Vector Operation)

Swaps the contents of two vectors.

Ways to Access Vectors Using Loops

Using index-based for loop and range-based for loop (C++11 and later).

Iterator Definition

A special type of pointer that allows you to traverse the elements of a container without directly manipulating memory addresses.

Common Iterator Methods

.begin(), .end(), .rbegin(), .rend()

Different Types of Iterators

Input Iterators, Output Iterators, Forward Iterators, Bidirectional Iterators, Random Access Iterators

Dereferencing (*) (Iterator Operation)

Access the value the iterator points to.

Incrementing (++) (Iterator Operation)

Move to the next element.

Decrementing (--) (Iterator Operation)

Move to the previous element (bidirectional iterators).

Algorithms Definition (STL)

Generic functions in the STL that operate on ranges of elements within containers.

Header to Include for STL Algorithms

Common STL Algorithms

sort(), find(), copy(), transform(), count(), remove()

Linear Data Structures Definition

Store elements in a sequential or ordered manner.

Non-Linear Data Structures Definition

Do not store elements in a sequential order; elements are often organized in a hierarchical or networked manner.

.capacity() (Vector Operation)

Returns the number of elements the vector can hold without reallocating memory.

.reserve() (Vector Operation)

Requests that the vector allocate a specific amount of memory.

.shrinktofit() (Vector Operation)

Requests that the vector reduce its capacity to match its size.

.emplace_back() (Vector Operation)

Constructs an element in-place at the end of the vector.

.emplace() (Vector Operation)

Constructs an element in-place at a specified position in the vector.

.find() (Vector Operation)

Locates elements in a range.

std::distance() Definition

Calculates the distance between two iterators.