Giao diện tối
20.x — Chapter 20 summary and quiz
🎯 Mục Tiêu Bài Học
- Nắm vững bản chất lý thuyết và cơ chế hoạt động của Chapter 20 summary and quiz trong tiêu chuẩn ISO C++.
- Hiểu rõ cách máy tính tổ chức bộ nhớ (RAM, CPU registers) khi thực thi mã nguồn liên quan.
- Nhận biết các cạm bẫy lỗi kinh điển (Undefined Behavior, Memory Leak, Bug logic) và cách phòng tránh.
- Áp dụng các quy tắc thực hành tốt nhất (Best Practices) chuẩn công nghiệp và cập nhật C++20/C++23 hiện đại.
20.x — Chapter 20 summary and quiz
Chapter Review
Another chapter down! There’s just this pesky quiz to get past…
Function đối số can be passed by value, tham chiếu or address. Use truyền theo giá trị for fundamental các kiểu dữ liệu and enumerators. Use pass by tham chiếu for structs, classes, or when you need the hàm to modify an đối số. Use pass by address for passing các con trỏ or built-in arrays. Make your pass by tham chiếu and address tham số const whenever possible.
Values can be returned by value, tham chiếu, or address. Most of the time, return by value is fine, however return by tham chiếu or address can be useful when working with dynamically allocated data, structs, or classes. If returning by tham chiếu or address, remember to make sure you’re not returning something that will go out of phạm vi truy cập (scope).
Function các con trỏ allow us to pass a hàm to another hàm. This can be useful to allow the caller to customize the behavior of a hàm, such as the way a list gets sorted.
Dynamic memory is allocated on the vùng nhớ Heap (Free Store).
The call ngăn xếp Stack keeps track of all of the active các hàm (those that have been called but have not yet terminated) from the start of the program to the current point of execution. Local các biến are allocated on the ngăn xếp Stack. The ngăn xếp Stack has a limited size. std::vector can be used to implement ngăn xếp Stack-like behavior.
A recursive hàm is a hàm that calls itself. All recursive các hàm need a termination condition.
Command line đối số allow users or other programs to pass data into our program at startup. Command line đối số are always C-style strings, and have to be converted to numbers if numeric values are desired.
Ellipsis allow you to pass a biến number of đối số to a hàm. However, ellipsis đối số suspend type checking, and do not know how many đối số were passed. It is up to the program to keep track of these details.
Lambda các hàm are các hàm that can be nested inside other các hàm. They don’t need a name and are very useful in combination with the algorithms library.
Hệ thống Câu hỏi & Quiz Tự Luyện
Câu hỏi #1
Write hàm prototypes for the following cases. Use const if/when necessary.
a) A hàm named max() that takes two doubles and returns the larger of the two.
Xem lời giải (Solution)
cpp
double max(double x, double y);b) A hàm named swap() that swaps two integers.
Xem lời giải (Solution)
cpp
void swap(int& x, int& y);c) A hàm named getLargestElement() that takes a dynamically allocated array of integers and returns the largest number in such a way that the caller can change the value of the element returned (don’t forget the length tham số).
Xem lời giải (Solution)
cpp
// Note: array can't be const in this case, because returning a non-const reference to a const element would be a const violation.
int& getLargestElement(int* array, int length);Câu hỏi #2
What’s wrong with these programs?
a)
cpp
int& doSomething()
{
int array[]{ 1, 2, 3, 4, 5 };
return array[3];
}Xem lời giải (Solution)
doSomething() returns a tham chiếu to a local biến that will be destroyed when doSomething terminates.
b)
cpp
int sumTo(int value)
{
return value + sumTo(value - 1);
}Xem lời giải (Solution)
hàm sumTo () has no termination condition. Variable value will eventually go negative, and the hàm will loop infinitely until the ngăn xếp Stack overflows.
c)
cpp
float divide(float x, float y)
{
return x / y;
}
double divide(float x, float y)
{
return x / y;
}Xem lời giải (Solution)
The two divide các hàm are not distinct, as they have the same name and same tham số. There is also a potential divide by 0 issue.
d)
cpp
#include <iostream>
int main()
{
int array[100000000]{};
for (auto x: array)
std::cout << x << ' ';
std::cout << '\n';
return 0;
}Xem lời giải (Solution)
The array is too large to be allocated on the ngăn xếp Stack. It should be dynamically allocated.
e)
cpp
#include <iostream>
int main(int argc, char* argv[])
{
int age{ argv[1] };
std::cout << "The user's age is " << age << '\n';
return 0;
}Xem lời giải (Solution)
argv[1] may not exist. If it does, argv[1] is a string đối số, and can’t be converted to an integer via phép gán.
Câu hỏi #3
The best algorithm for determining whether a value exists in a sorted array is called binary search.
Binary search works as follows:
Look at the center element of the array (if the array has an even number of elements, round down).
If the center element is greater than the target element, discard the top half of the array (or recurse on the bottom half)
If the center element is less than the target element, discard the bottom half of the array (or recurse on the top half).
If the center element equals the target element, return the index of the center element.
If you discard the entire array without finding the target element, return a sentinel that represents “not found” (in this case, we’ll use -1, since it’s an invalid array index).
Because we can throw out half of the array with each iteration, this algorithm is very fast. Even with an array of a million elements, it only takes at most 20 iterations to determine whether a value exists in the array or not! However, it only works on sorted arrays.
Modifying an array (e.g. discarding half the elements in an array) is expensive, so typically we do not modify the array. Instead, we use two integers (min and max) to hold the indices of the minimum and maximum elements of the array that we’re interested in examining.
Let’s look at a sample of how this algorithm works, given an array { 3, 6, 7, 9, 12, 15, 18, 21, 24 }, and a target value of 7. At first, min = 0, max = 8, because we’re searching the whole array (the array is length 9, so the index of the last element is 8).
Pass 1) We calculate the midpoint of min (0) and max (8), which is 4. Element #4 has value 12, which is larger than our target value. Because the array is sorted, we know that all elements with index equal to or greater than the midpoint (4) must be too large. So we leave min alone, and set max to 3.
Pass 2) We calculate the midpoint of min (0) and max (3), which is 1. Element #1 has value 6, which is smaller than our target value. Because the array is sorted, we know that all elements with index equal to or lesser than the midpoint (1) must be too small. So we set min to 2, and leave max alone.
Pass 3) We calculate the midpoint of min (2) and max (3), which is 2. Element #2 has value 7, which is our target value. So we return 2.
In C++20, calculating the midpoint can be done via calling std::midpoint. Prior to C++20, you’ll need to calculate the midpoint yourself -- in this case you can use min + ((max - min) / 2) to avoid overflow (when min and max are both positive).
Given the following code:
cpp
#include <iostream>
#include <iterator>
// array is the array to search over.
// target is the value we're trying to determine exists or not.
// min is the index of the lower bounds of the array we're searching.
// max is the index of the upper bounds of the array we're searching.
// binarySearch() should return the index of the target element if the target is found, -1 otherwise
int binarySearch(const int* array, int target, int min, int max)
{
}
int main()
{
constexpr int array[]{ 3, 6, 8, 12, 14, 17, 20, 21, 26, 32, 36, 37, 42, 44, 48 };
// We're going to test a bunch of values to see if the algorithm returns the result we expect
// Here are the test values
constexpr int testValues[]{ 0, 3, 12, 13, 22, 26, 43, 44, 48, 49 };
// And here are the results that we expect for those test values
int expectedResult[]{ -1, 0, 3, -1, -1, 8, -1, 13, 14, -1 };
// Make sure we have the same number of test values and expected results
static_assert(std::size(testValues) == std::size(expectedResult));
int numTestValues { std::size(testValues) };
// Loop through all of the test values
for (int count{ 0 }; count < numTestValues; ++count)
{
// See if our test value is in the array
int index{ binarySearch(array, testValues[count], 0, static_cast<int>(std::size(array)) - 1) };
// If it matches our expected value, then great!
if (index == expectedResult[count])
std::cout << "test value " << testValues[count] << " passed!\n";
else // otherwise, our binarySearch() function must be broken
std::cout << "test value " << testValues[count] << " failed. There's something wrong with your code!\n";
}
return 0;
}a) Write an iterative version of the binarySearch hàm.
Hint: You can safely say the target element doesn’t exist when the min index is greater than the max index.
Xem lời giải (Solution)
cpp
#include <cassert>
#include <iostream>
#include <numeric> // for std::midpoint
// array is the array to search over.
// target is the value we're trying to determine exists or not.
// min is the index of the lower bounds of the array we're searching.
// max is the index of the upper bounds of the array we're searching.
// binarySearch() should return the index of the target element if the target is found, -1 otherwise
int binarySearch(const int* array, int target, int min, int max)
{
assert(array); // make sure array exists
while (min <= max)
{
// implement this iteratively
int midpoint{ std::midpoint(min, max) };
// Before C++20
// int midpoint{ min + ((max-min) / 2) }; // this way of calculating midpoint avoids overflow
if (array[midpoint] > target)
{
// if array[midpoint] > target, then we know the number must be in the lower half of the array
// we can use midpoint - 1 as the upper index, since we don't need to retest the midpoint next iteration
max = midpoint - 1;
}
else if (array[midpoint] < target)
{
// if array[midpoint] < target, then we know the number must be in the upper half of the array
// we can use midpoint + 1 as the lower index, since we don't need to retest the midpoint next iteration
min = midpoint + 1;
}
else
{
return midpoint;
}
}
return -1;
}b) Write a recursive version of the binarySearch hàm.
Xem lời giải (Solution)
cpp
#include <cassert>
#include <numeric> // for std::midpoint
// array is the array to search over.
// target is the value we're trying to determine exists or not.
// min is the index of the lower bounds of the array we're searching.
// max is the index of the upper bounds of the array we're searching.
// binarySearch() should return the index of the target element if the target is found, -1 otherwise
int binarySearch(const int* array, int target, int min, int max)
{
assert(array); // make sure array exists
// implement this recursively
if (min > max)
return -1;
int midpoint{ std::midpoint(min, max) };
// Before C++20
// int midpoint{ min + ((max-min) / 2) }; // this way of calculating midpoint avoids overflow
if (array[midpoint] > target)
{
return binarySearch(array, target, min, midpoint - 1);
}
else if (array[midpoint] < target)
{
return binarySearch(array, target, midpoint + 1, max);
}
return midpoint;
}Tip
std::binary_search returns true if a value exists in a sorted list.
std::equal_range returns the iterators to the first and last element with a given value.
Don’t use these các hàm to solve the quiz, but use them in the future if you need a binary search.
💡 Tóm Tắt Quy Tắc Vàng (Core Guidelines)
- Luôn hiểu rõ vòng đời và quyền sở hữu (Ownership) của dữ liệu trước khi viết code.
- Ưu tiên khởi tạo đồng nhất với dấu ngoặc nhọn
{}để ngăn chặn lỗi thu hẹp kiểu dữ liệu (Narrowing conversions). - Bật toàn bộ cờ cảnh báo
-Wall -Wextra -Wpedanticđể compiler giúp bạn phát hiện bug từ sớm!