UPI Study › Courses › C++ Programming › Free lessons › Lesson 7.7 Free with a free account
Dynamic Vectors Challenge
C++ Programming · Chapter 7: Text and Applied CollectionsSection 7.7 · lesson 49 of 84video coming soon
← Validating User InputNext lesson: Arrays With Text Processing →
In this lesson
Building, sorting, and searching vectors.
- Construct and reshape a vector, minding shifting positions
- Implement and trace bubble and selection sort
- Search linearly, and by halving sorted data
- Find extremes, reverse, and remove duplicates
Transcript
Everything said in the video, section by section (1,535 words). Read along, or search it.
Lesson Overview
Everything a Dynamic Vector Can Do
A collection that grows and shrinks on demand changes what's worth writing. This lesson is the full working set: building and reshaping a vector, arranging its contents two ways by hand and once with the library, and finding a value in it. Quickly if it's sorted, and reliably either way. The exercise at the end asks for all of it, in one program.
Construction
Parentheses Versus Braces in Constructors
Here are five ways to construct a vector, with different results. A is empty, with size 0. B, with 5 in parentheses, holds 5 items, each zero. C, with 5 and 7 in parentheses, holds 5 items, each 7. D, with 5 and 7 in braces, holds 2 items, exactly as listed. And e, with just 5 in braces, holds one item: the value 5. Parentheses and braces mean different things here. V, 5 in parentheses, asks for 5 items. V, 5 in braces, asks for the item 5: a vector of size 1. The difference is a single character, and the results share nothing. This is the one place where the brace habit gives the wrong answer.
Core Operations
Push, Pop, Insert, Erase, and Clear
Here's the working set, on the starting vector 4, 8, 1, 6. Push back adds an item at the end, and nothing else moves. Pop back removes the last item. On an empty vector, that's undefined, so check empty first. Insert puts an item at a position, and everything from there onward shifts up by one. Insert 5 at position 1, and 8, 1 and 6 all move. Erase removes an item, and everything after it shifts down. That's why erasing inside a loop needs care: positions you were part-way through slide under you. Clear removes everything; the vector still exists. Front and back give the first and last items, undefined when the vector is empty.
Access Methods
Looping and Reaching Items Safely
There are two ways to loop over a vector. An index loop, with square brackets, is fast and unchecked. A range loop visits every item, with no positions involved. Use it when positions don't matter, which is most of the time. And there are two ways to reach one item. At 99 stops the program with an exception, because the position is out of range. Here we catch it and report. Square brackets with 99 give no complaint. That's undefined behavior: it may read whatever happens to be there, or crash, so we don't run it. Prefer at while developing, and while reading input from outside the program. Being stopped with a clear message beats a wrong answer that appears to work.
Nested Vectors
A Grid Built from Vectors
A vector of vectors is a grid that carries its own shape. Here, 3 rows, each a vector of 4 zeros. Grid 1, 2 is set to 9. The inner loop asks each row for its own width, rather than assuming a shared one, because rows are independent vectors, and need not be the same length. In fact, pushing a fourth row only 2 wide is allowed. So write the inner loop that way as a habit. It costs nothing, and stays correct if the rows change.
Bubble Sort
Swapping Neighbors Until Nothing Moves
Both hand-written sorts produce the same result, and differ in how they get there. Implementing them isn't about beating the library. It's about reasoning precisely over positions. Bubble sort repeatedly swaps neighbors that are out of order. Each pass compares neighboring pairs, and swaps any that are the wrong way round. The inner loop shrinks each pass, because the tail is already settled. And a swapped flag records whether anything moved. Trace it on 5, 1, 4, 2. Pass one swaps three times: 1, 4, 2, 5. Five has reached its final place. Pass two swaps four and two. Pass three makes no swaps. That proves the vector is in order, and the flag breaks the loop.
Selection Sort
Finding the Smallest and Placing It
Selection sort works differently. Find the smallest remaining item, put it in place, and repeat. For each position i, search from i onward for the smallest item. If it isn't already at i, swap it there. On 5, 1, 4, 2: round one searches all four positions, finds 1 at position 1, and swaps it to the front. 1, 5, 4, 2. Round two finds 2 at position 3 and swaps it. Round three finds 4 already in place, so there's no swap. Notice how few swaps it makes.
Sort Comparison
Counting Comparisons and Swaps
Compare the two on 6 items. Bubble sort makes up to n times n minus one over two comparisons, but as few as n minus one on sorted data. Selection sort always makes n times n minus one over two, whatever the data. For 6 items, that's 15 every time. Bubble sort makes one swap for every pair that's out of order, potentially many. Selection sort swaps at most n minus one times. Bubble sort detects sorted data with its flag; selection sort does the same work regardless. In real work, use the library: std::sort, then std::reverse for largest first. Two library calls, and the arranging is done.
Search Methods
Linear Search Versus Binary Search
Now searching. Linear search makes no assumptions at all. It examines each item in turn. If one equals the target, it returns that position. If it reaches the end without finding it, it returns minus 1, the agreed answer for not present. It works on any vector, sorted or not. Binary search requires sorted data. It keeps a low and a high position. While low is at most high, it looks at the middle. If the middle item is the target, it's found. If it's smaller, the answer is to the right, so low moves past the middle. Otherwise high moves below the middle. Finding 24 in 7 sorted values: look one, position 3 holds 18. That's less, so keep the right half. Look two, position 5 holds 30: too big. Look three, position 4: found. Three looks instead of five. Each look throws away half of what's left, which is why it scales so well.
Binary Search Pitfall
Silent Failure on Unsorted Data
But binary search on unsorted data doesn't complain. It runs, it finishes, and it reports not present for a value sitting right there. Here is the same list, shuffled. Linear search still finds 24 at position 4. Binary search looks at the middle, gets confused, and returns minus 1. Nothing checks the precondition, because checking every item would cost as much as a linear search. So sort first, or use linear search. And if a function requires sorted input, say so in its name or a comment above it.
Search Payoff
When Halving Beats Scanning
The payoff is large. For 10 items, linear search examines up to 10, and binary up to 4. For a thousand, a thousand against ten. For a million, a million against twenty. But sorting costs more than a single linear search. So searching once in unsorted data is best done linearly. Binary search wins when the same collection is searched repeatedly.
Small Tasks
Largest, Reverse, and Remove Duplicates
Three small jobs round out the set. To find the largest, track its position, not just its value, updating whenever a bigger item appears. To reverse in place, walk in from both ends, swapping as you go, until the two positions meet. To remove duplicates from a sorted vector, build a new one. Push each item unless it equals the one before it. Deduplication wants sorted input because every copy then sits next to its twin. And building a second vector avoids positions shifting under you.
Common Mistakes
Recognizing Typical Vector Faults
A few faults are worth recognizing. Five zeros where one item was wanted: parentheses used instead of braces. A search reporting not present for a value you can see: binary search on unsorted data. Items skipped while erasing in a loop: positions shifting down. Build a new vector, or step backward. A sort that does nothing to the caller's data took its vector by value. And a loop that misbehaves on an empty vector computed size minus 1. Test empty first.
Graded Exercise
One Program Built in Stages
The graded exercise is one program, built in stages. Each stage must run before you start the next. A: read values until minus 1 with push back, and report how many. B: total, mean, and extremes with their positions. For 12, 5, 9, 5, 20, the largest is 20 at position 4. C: sort two copies, with bubble and selection, counting comparisons and swaps. D: search linearly on the unsorted copy, and by halving on the sorted one. E: deduplicate and reverse. F, which is required: run binary search on the unsorted copy for a value you know is there, and explain the wrong answer. G, the stretch: rows of unequal length.
Quick Check
Looking Up 41 in Seven Values
Quick check. Binary search for 41 in the same seven sorted values: 3, 7, 11, 18, 24, 30, 41. How many looks does it take, and how many would linear search need? Pause and predict. Three. Look one, position 3 holds 18: too small, so low moves past the middle. Look two, position 5 holds 30: still too small. Look three, position 6: found. Linear search would need all seven looks.
Key Takeaways
Main Points to Remember
To summarize. V, 5 in parentheses, is 5 items. V, 5 in braces, is one item. Insert and erase shift every later position. Bubble sort stops early on sorted data, and selection sort makes the fewest swaps. In real work, use the library sort. And binary search needs sorted data, and won't tell you when it hasn't got it.
About C++ Programming at UPI Study
C++ Programming (Computer Science 242) is a self-paced online course of 84 video lessons in 11 chapters, from your first program to decisions, loops, arrays, functions, classes, files, pointers and inheritance. It carries a NCCRS credit recommendation for 3 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus Every course with PRO →
Why take it here
Why students take C++ Programming with UPI Study
Where the credit goes
Universities that work with NCCRS
C++ Programming carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About Dynamic Vectors Challenge
What is the difference between vector<int> v(5) and vector<int> v{5} in C++?
How do bubble sort and selection sort differ when sorting a vector?
Why does binary search return -1 for a value that is in my vector?
Why do items get skipped when I call erase inside a loop over a vector?
About the C++ Programming course
How many college credits is C++ Programming?
How much does C++ Programming cost and what is included?
Which universities accept UPI Study credits?
How long does C++ Programming take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in C++ Programming.
84 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →