Understanding Vectors and Their Applications

Sep 14, 2024

Complete DSA Series - Lecture on Vectors

Introduction

  • Today's topic: Vectors
  • Vectors are the next data structure being studied in detail.
  • They are dynamic in nature, unlike arrays which have a fixed size.

Vectors vs Arrays

  • Vectors and arrays have similar visualization: blocks of data with indices.
  • Dynamic Size: Vectors can change size while arrays cannot.

Standard Template Library (STL)

  • STL in C++: A library with pre-implemented data structures (stack, hash table, queue, etc.).
  • Usage of STL is allowed in placements and interviews.
  • STL containers include vectors, queues, stacks, sets, etc.

Vector Basics

  • Declaration Syntax: vector<type> vectorName;
  • Initial Size: Vectors start with size 0 by default.
  • Header File: Must include <vector> to avoid errors.

Vector Initialization

  1. Empty Vector: Starts with size 0.
  2. Initialized Vector: vector<type> vectorName = {elements};
  3. Fixed Size Vector: vector<type> vectorName(size, value);

Iterating Over Vectors

  • Use for-each loop: for(auto &value : vectorName)
  • Iterates over values, not indices.

Vector Functions

  • Size: vector.size() returns the current size.
  • Push Back: vector.push_back(value) adds an element to the end.
  • Pop Back: vector.pop_back() removes the last element.
  • Front/Back: vector.front(), vector.back() access the first and last elements.
  • At: vector.at(index) accesses elements by index safely.

Memory Allocation

  • Static vs Dynamic Allocation:
    • Static: Compile time (e.g., arrays on stack).
    • Dynamic: Runtime (e.g., vectors in heap).
  • Internal Vector Implementation:
    • Vectors are dynamic arrays internally.
    • Array size doubles when more space is needed.

Size and Capacity

  • Size: Number of elements in the vector.
  • Capacity: Total space allocated, doubles when capacity is exceeded.
  • Functions: vector.capacity() to get the capacity.

Problem Solving with Vectors

  • Example Problem: Find a single number in a vector where each element except one appears twice.
  • Use XOR operation to find unique elements: XOR properties cancel out duplicates.
  • Implementation:
    • Initialize result = 0.
    • XOR all elements in the vector.
    • Final result will be the unique number.

Conclusion

  • Discussed STL, vectors, their usage in memory, and problem-solving.
  • Homework:
    • Implement linear search on a vector.
    • Implement reverse of a vector using functions and understand pass-by-reference.

Homework and Practice

  • Practice solving easy level problems on platforms like Leetcode, Codeforces, etc.
  • Start with easy problems before moving to medium and hard levels.

This lecture focused on understanding vectors, their dynamic nature, usage with C++ STL, and their implementation in memory. It also introduced practical problem-solving using vectors and bitwise operations.