Vector Container Overview

Vector is a sequence container in the C++ Standard Template Library that behaves similarly to a dynamic array. Unlike traditional static arrays, vector containers can automatically expand their storage capacity as needed.

Dynamic Expansion Mechanism:

When a vector runs out of space, it doesn't simply append data to the existing memory block. Instead, it allocates a larger memory segment, copies all existing elements to the new location, and releases the original memory. This behavior ensures efficient memory management but involves copying overhead during reallocation.

Vector provides random-access iterators, supporting operations like begin(), end(), rbegin(), rend(), along with element access methods such as front(), back(), insert(), push_back(), and pop_back().

Vector Constructors

Header: #include <vector>

Constructor Signatures:

• vector<T> v; — Default constructor creating an empty container.
• vector(v.begin(), v.end()); — Copies elements from the [begin, end) range.
• vector(n, elem); — Creates a container with n copies of elem.
• vector(const vector &vec); — Copy constructor.

Example:

void displayContents(const std::vector<int>& container) {
    for (auto iter = container.begin(); iter != container.end(); ++iter) {
        std::cout << *iter << " ";
    }
    std::cout << std::endl;
}

void demonstration01() {
    std::vector<int> emptyContainer;
    for (int i = 0; i < 8; ++i) {
        emptyContainer.push_back(i * 2);
    }
    displayContents(emptyContainer);

    std::vector<int> rangeCopy(emptyContainer.begin() + 2, emptyContainer.end() - 1);
    displayContents(rangeCopy);

    std::vector<int> filledContainer(6, 42);
    displayContents(filledContainer);

    std::vector<int> copiedContainer(filledContainer);
    displayContents(copiedContainer);
}

Vector Assignment Operations

Assignment Methods:

• vector& operator=(const vector &vec); — Assignment operator overloading.
• assign(beg, end); — Assigns elements from the [beg, end) range.
• assign(n, elem); — Assigns n copies of elem.

Example:

void displayContents(const std::vector<int>& container) {
    for (auto iter = container.begin(); iter != container.end(); ++iter) {
        std::cout << *iter << " ";
    }
    std::cout << std::endl;
}

void demonstration02() {
    std::vector<int> source;
    for (int i = 0; i < 8; ++i) {
        source.push_back(i * 3);
    }
    displayContents(source);

    std::vector<int> target = source;
    displayContents(target);

    std::vector<int> rangeAssigned;
    rangeAssigned.assign(source.begin(), source.end());
    displayContents(rangeAssigned);

    std::vector<int> elemAssigned;
    elemAssigned.assign(5, 77);
    displayContents(elemAssigned);
}

Vector Capacity and Size

Capacity Management Functions:

• empty(); — Returns true if the container is empty.
• capacity(); — Returns the current storage capacity.
• size(); — Returns the number of elements.
• resize(int num); — Resizes container to num elements. New positions filled with default values; excess elements removed. Capacity remains unchanged.
• resize(int num, elem); — Same as above, but fills new positions with elem.

Example:

void displayContents(const std::vector<int>& container) {
    for (const auto& val : container) {
        std::cout << val << " ";
    }
    std::cout << std::endl;
}

void demonstration03() {
    std::vector<int> numbers;
    for (int i = 0; i < 12; ++i) {
        numbers.push_back(i * 5);
    }
    displayContents(numbers);

    if (numbers.empty()) {
        std::cout << "Container is empty" << std::endl;
    } else {
        std::cout << "Container is not empty" << std::endl;
        std::cout << "Capacity: " << numbers.capacity() << std::endl;
        std::cout << "Size: " << numbers.size() << std::endl;
    }

    numbers.resize(18, 100);
    displayContents(numbers);

    numbers.resize(6);
    displayContents(numbers);
}

Note that capacity is typically slightly larger than the actual size to accommodate future growth without immediate reallocation.

Vector Insertion and Deletion

Manipulation Functions:

• push_back(ele); — Appends element at the end.
• pop_back(); — Removes the last element.
• insert(const_iterator pos, ele); — Inserts ele at the position pointed by iterator.
• insert(const_iterator pos, int count, ele); — Inserts count copies of ele.
• erase(const_iterator pos); — Removes element at the postiion.
• erase(const_iterator start, const_iterator end); — Removes elements in the [start, end) range.
• clear(); — Removes all elements.

Example:

void displayContents(const std::vector<int>& container) {
    for (const auto& val : container) {
        std::cout << val << " ";
    }
    std::cout << std::endl;
}

void demonstration04() {
    std::vector<int> data;
    for (int i = 1; i < 7; ++i) {
        data.push_back(i * 10);
    }
    displayContents(data);

    data.pop_back();
    displayContents(data);

    data.insert(data.begin(), 5);
    displayContents(data);

    data.insert(data.begin() + 1, 3, 88);
    displayContents(data);

    data.erase(data.begin() + 2);
    displayContents(data);

    data.erase(data.begin(), data.end() - 2);
    displayContents(data);

    data.clear();
    displayContents(data);
}

Vector Data Access

Access Methods:

• at(int idx); — Returns element at index idx with bounds checking.
• operator[]; — Returns element at index idx without bounds checking.
• front(); — Returns the first element.
• back(); — Returns the last element.

Example:

void demonstration05() {
    std::vector<int> values;
    for (int i = 1; i < 7; ++i) {
        values.push_back(i * 10);
    }

    for (std::size_t i = 0; i < values.size(); ++i) {
        std::cout << values[i] << " ";
    }
    std::cout << std::endl;

    for (std::size_t i = 0; i < values.size(); ++i) {
        std::cout << values.at(i) << " ";
    }
    std::cout << std::endl;

    std::cout << "First element: " << values.front() << std::endl;
    std::cout << "Last element: " << values.back() << std::endl;
}

Vector Container Swap

Swap Function:

• swap(vec); — Exchanges all elements between the container and vec.

Example:

void showElements(const std::vector<int>& container) {
    for (std::size_t i = 0; i < container.size(); ++i) {
        std::cout << container[i] << " ";
    }
    std::cout << std::endl;
}

void demonstration06() {
    std::vector<int> collectionA;
    for (int i = 1; i < 8; ++i) {
        collectionA.push_back(i * 10);
    }

    std::vector<int> collectionB;
    for (int i = 1; i < 8; ++i) {
        collectionB.push_back(i * 100);
    }

    std::cout << "Before swap:" << std::endl;
    showElements(collectionA);
    showElements(collectionB);

    collectionA.swap(collectionB);

    std::cout << "After swap:" << std::endl;
    showElements(collectionA);
    showElements(collectionB);
}

Memory Shrinking via Swap

Technique:

void demonstration07() {
    std::vector<int> data;
    for (int i = 0; i < 100000; ++i) {
        data.push_back(i);
    }
    std::cout << "Initial capacity: " << data.capacity() << std::endl;
    std::cout << "Initial size: " << data.size() << std::endl;

    data.resize(3);
    std::cout << "After resize(3) capacity: " << data.capacity() << std::endl;
    std::cout << "After resize(3) size: " << data.size() << std::endl;


    std::vector<int>(data).swap(data);

    std::cout << "After shrink capacity: " << data.capacity() << std::endl;
    std::cout << "After shrink size: " << data.size() << std::endl;
}

The expression std::vector<int>(data).swap(data) creates a temporary vector initialized with data's actual size, then swaps with the original. The temporary object is destroyed after the line, releasing the excess memory.

Vector Reserve Space

Purpose:

Pre-allocates memory to reduce reallocation次数 during frequent insertions.

Function:

• reserve(int len); — Allocates storage for len elements. These positions are uninitialized and cannot be accessed.

Example:

void demonstration08() {
    std::vector<int> numbers;
    int reallocationCount = 0;
    int* previousAddress = nullptr;

    for (int i = 0; i < 100000; ++i) {
        numbers.push_back(i);
        int* currentAddress = &numbers[0];
        if (previousAddress != currentAddress) {
            previousAddress = currentAddress;
            ++reallocationCount;
        }
    }

    std::cout << "Capacity: " << numbers.capacity() << std::endl;
    std::cout << "Size: " << numbers.size() << std::endl;
    std::cout << "Reallocation count: " << reallocationCount << std::endl;
}

void demonstration09() {
    std::vector<int> numbers;
    numbers.reserve(100000);

    int reallocationCount = 0;
    int* previousAddress = nullptr;

    for (int i = 0; i < 100000; ++i) {
        numbers.push_back(i);
        int* currentAddress = &numbers[0];
        if (previousAddress != currentAddress) {
            previousAddress = currentAddress;
            ++reallocationCount;
        }
    }

    std::cout << "Capacity: " << numbers.capacity() << std::endl;
    std::cout << "Size: " << numbers.size() << std::endl;
    std::cout << "Reallocation count: " << reallocationCount << std::endl;
}

Without reserve(), the container expands incrementally, resulting in multiple reallocations. Pre-reserivng space ensures only a single allocation occurs, significantly improving performance for large datasets.