Introduction
In our last lesson, we explored the time-space trade-off and saw how an STL container like std::unordered_map could drastically improve an algorithm's efficiency. This highlighted a core principle for coding interviews: choosing the right data structure is often the key to an optimal solution.
Today, we will build on that foundation by taking a deep dive into two of the most indispensable tools in the C++ Standard Template Library: std::vector and std::string. While you may have a general awareness of them, mastering their capabilities is non-negotiable for solving algorithmic problems effectively. This lesson will equip you with a solid understanding of their APIs and common usage patterns, moving you from basic familiarity to confident application in interview-style questions.
The Workhorse of STL: std::vector
At its core, std::vector is the C++ way of representing a dynamic array. It encapsulates the behavior of a contiguous block of memory that can grow or shrink as needed, freeing you from the manual and error-prone memory management of C-style arrays. For most problems requiring a sequence of elements where the size isn't fixed at compile time, std::vector is the default choice.
The following decision tree provides a great visual overview of where std::vector fits within the broader ecosystem of STL containers. Notice it's the "Default Choice" under sequence containers.
To get a practical introduction to std::vector, let's watch a segment from a CodeBeauty video that contrasts it with static and dynamic arrays and then walks through its basic usage.
STL vector (Relationship between Static array, Dynamic array and STL vector) with examples
This video provides a clear, step-by-step guide to using std::vector. What to watch: What is a vector? : The video explains how std::vector acts as a dynamic array and how to declare one. Adding and Printing: : Watch how to add elements with push_back and then see a simple range-based for loop for printing the contents. This is the most common way to populate and iterate over a vector. Essential Methods: : This part covers several key functions: size(): gets the number of elements. empty(): checks if the vector is empty. [] and at(): for direct element access. front() and back(): to get the first and last elements. clear(): to remove all elements. Inserting and Erasing: : Finally, see how to use insert(), erase(), and pop_back() to modify the vector at specific positions or at the end.
The video gives a great tour of the most common functions. For a more detailed textual reference and to introduce the crucial concept of iterators, let's turn to a classic TopCoder tutorial.
This article provides a comprehensive look at the std::vector API and introduces iterators, a fundamental concept for all STL containers.
Please read the following sections: Vector section: Start your reading at the heading Vector and continue until you reach the sentence discussing function parameters. This part covers initialization, size, push_back, resize, and clear. Pay close attention to the final paragraphs about passing vectors to functions by reference (const vector<int>& v)—this is a critical performance and best-practice point. Iterators section: Now, find the heading Iterators. Read this entire section to understand what iterators are, why they are like "smart pointers" for containers, and how they are used with begin() and end() to define a range. This concept is essential for using many STL algorithms. Data manipulation section: Finally, read the short section Data manipulation in vector. This will reinforce what you saw in the video about using insert() and erase() with iterators to modify the vector.
By now, you should have a solid grasp of std::vector. The key takeaway is that it provides a safe, flexible, and powerful alternative to raw arrays, equipped with a rich set of functions for common operations.
The Powerhouse for Text: std::string
Much like std::vector improves upon C-style arrays, std::string is the modern C++ object for handling sequences of characters. It behaves like a container and shares many methods with std::vector (like size(), empty(), clear(), begin(), end()), but it also includes a wealth of functions specifically designed for text manipulation.
The video below from Bro Code provides a rapid-fire showcase of many useful string functions. It's a great way to quickly get a sense of what's available.
C++ useful string functions (#8) 🧵
This video is a quick tour of common std::string member functions. What to watch: length() and empty(): : See how to get the string's length and check if it's empty. clear() and append(): : Learn how to erase a string's content and how to add another string to its end. at() and substr(): : Watch how to access a character at a specific position and how to extract a portion (substring) of a string. insert(), find(), and erase(): : These functions allow you to insert content, find the position of a substring, and remove parts of the string.
Applying String Functions to Algorithmic Problems
Knowing the function names is one thing; applying them to solve problems is another. Your goal is to prepare for coding interviews, so let's look at how these functions are used to implement solutions for common challenges. The following exercises are taken from a practical guide. You don't need to code them all yourself right now, but focus on understanding the logic and how a specific std::string or STL algorithm feature makes the solution elegant and efficient.
27 C++ String Coding Exercises with Solutions – PYnative
This resource provides practical examples of string manipulation in the context of coding problems. Focus on the "Explanation" for each solution.
Review the following exercises: Reverse a String: In the "Table of contents", find and click on Exercise 6: Reverse String. Read the problem and the solution. The explanation highlights the idiomatic C++ way to reverse any sequence container using std::reverse with iterators (begin() and end()). Palindrome Check: Go to Exercise 10: Palindrome Check (Simple). This is a classic interview question. The solution cleverly combines the std::reverse technique from the previous exercise with a simple string comparison. Word Count: Go to Exercise 11: Word Count. The solution here introduces a very useful technique: using std::stringstream to easily tokenize a string by whitespace. This is a powerful pattern for problems involving word parsing. Remove Spaces: Go to Exercise 9: Remove Spaces. The explanation describes the "erase-remove" idiom (str.erase(std::remove_if(...))). This is a highly efficient, in-place method for filtering elements from any sequence container and is considered a staple of modern C++. Find and Replace Substring: Finally, look at Exercise 12: Find Substring and Exercise 13: Replace Substring. These two demonstrate the powerful combination of .find() to locate a substring and .replace() to modify it. The loop in the "replace" exercise to handle all occurrences is a common pattern.
These examples show that proficiency with the STL isn't just about memorizing function names. It's about recognizing which function or algorithm best fits the problem at hand, allowing you to write code that is not only correct but also concise, readable, and efficient.
Conclusion
In this lesson, we've armed you with a practical understanding of std::vector and std::string, the two most fundamental containers in the C++ STL. You've seen how their rich APIs go far beyond what's offered by basic C-style arrays and character pointers, enabling elegant solutions to common algorithmic tasks.
Key Takeaways:
std::vectoris your default choice for a dynamic array. It manages its own memory and provides essential functions likepush_back,size,insert, anderase.std::stringis a specialized container for text that offers a powerful suite of manipulation functions likesubstr,find, andreplace, in addition to standard container methods.- Iterators (
begin(),end()) are the universal mechanism for traversing and manipulating STL containers. They are the bridge that connects your data to powerful generic algorithms likestd::sortandstd::reverse. - Effective problem-solving in C++ often involves identifying the right STL function or algorithm for the job, such as using
std::stringstreamfor word parsing or the "erase-remove" idiom for filtering.
In our next lesson, we will start applying this knowledge directly. We'll learn the two-pointer technique, a classic and highly efficient approach for solving a wide variety of problems on arrays and strings, which are often represented by std::vector and std::string.