VisaSpark
Sign in
advanced20 min

The STL: std::vector and <algorithm>

C++'s resizable array type, and two everyday functions from the algorithms library.

What you'll learn

  • Create and iterate over a std::vector, a resizable, type-safe array
  • Use std::sort from <algorithm> to sort a vector in place
  • Use std::find from <algorithm> together with an iterator to locate a value

Explanation

std::vector<T> (from <vector>) is the STL's resizable, type-safe array -- the modern, memory-safe alternative to a raw C-style array that this course's earlier lessons covered. It manages its own memory, tracks its own size (.size()), and grows automatically as you add elements, the same way Go's slice does conceptually, though the mechanics differ.

An iterator is an object that points to a position within a container, generalizing the idea of "a position you can step through," and it's how most STL algorithms operate on a container without needing to know its exact type. vec.begin() returns an iterator to the first element, and vec.end() returns an iterator to one position past the last element (never a valid element itself) -- begin()/end() together define the range an algorithm should operate over.

<algorithm> provides many reusable operations that work over that begin/end range. std::sort(vec.begin(), vec.end()) sorts the vector's elements in place, in ascending order by default. std::find(vec.begin(), vec.end(), value) searches for the first element equal to value, returning an iterator to it if found, or exactly vec.end() if not found -- comparing the result against vec.end() is the standard way to check whether find actually succeeded. Subtracting one iterator from another (it - vec.begin()) gives you the numeric index of the position it refers to.

Guided lab

Predict: Sorting and searching a vector

C++Not executed
This lab does not run in your browser or on VisaSparkSchools's servers. Read the code, predict what it does, then reveal the real expected output.

Read this program and predict exactly what it prints, including spacing.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> nums = {5, 2, 8, 1};
    std::sort(nums.begin(), nums.end());

    std::cout << "Sorted: ";
    for (int n : nums) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    auto it = std::find(nums.begin(), nums.end(), 8);
    if (it != nums.end()) {
        std::cout << "Found 8 at index " << (it - nums.begin()) << std::endl;
    }

    return 0;
}

Stuck? Get a hint.

Common mistakes

  • Using a raw C-style array where a std::vector would be safer and more convenient -- vector manages its own memory and resizing automatically.
  • Forgetting that vec.end() points one position past the last real element, and is never itself a valid element to dereference.
  • Forgetting to compare std::find's result against vec.end() to check whether the search actually succeeded, and using the iterator as if it were always valid.

Knowledge check

Knowledge check

1. What does vec.end() refer to for a std::vector?
2. What does std::find return if the value being searched for isn't in the range?
3. What does std::vector offer that a raw C-style array doesn't?

Takeaway

std::vector is a resizable, memory-safe array; std::sort and std::find (both operating over a begin()/end() iterator range) are two of <algorithm>'s everyday tools for working with it.

Summary

std::vector manages its own resizing and memory; <algorithm> functions like std::sort and std::find operate generically over a container's begin()/end() iterator range.

References

Your notes

Notes save automatically.

Finished this lesson?

Mark it complete to track your progress and schedule a future review.

Next: Inheritance and Virtual Functions →