Chapter.10

Answers for chapter 10

Exercise 10.1: The algorithm header defines a function named count that, like find, takes a pair of iterators and a value. count returns a count of how often that value appears. Read a sequence of ints into a vector and print the count of how many elements have a given value.

CODE: Q.1.

Exercise 10.2: Repeat the previous program, but read values into a list of strings.

CODE: Q.1.

Exercise 10.3: Use accumulate to sum the elements in a vector<int>.

CODE: Q.1.

Assuming v is a vector<double>, what, if anything, is wrong with calling accumulate(v.cbegin(), v.cend(), 0)?

Well, The calculation will be performed as long as the elements can be added to the third parameter. However, the calculation will truncate all “double” elements into integers, since the element type must match the third parameter, which in this case is integer 0. Therefore, the call may lose the decimal parts:

vector<double> vd{1.1, 2.1, 3.1, 4.1}; //a expected result is 10.4
accumulate(vd.cbegin(), vd.cend(), 0); //the result is integer 10

Exercise 10.5: In the call to equal on rosters, what would happen if both rosters held C-style strings, rather than library strings?

As C-string does not overload the == operation, even doing so will pass compilation, so it is actually comparing the addresses of the C-strings. If the strings are different, the comparsion is undefined. When comparing C-strings it is good practice to use strcmp().

CODE: test file.

#output
root@Hare:/CppPrimer_5th/ch10# ./a.out
1 #two vectors refer to the same c-string
0 #two vectors refer to the different c-strings but same content

Exercise 10.6: Using fill_n, write a program to set a sequence of int values to 0.

CODE: Q.1.

Exercise 10.7: Determine if there are any errors in the following programs and, if so, correct the error(s):

/* (a) */
vector<int> vec; list<int> lst; int i;
	while (cin >> i)
		lst.push_back(i);
copy(lst.cbegin(), lst.cend(), vec.begin());

vector<int> vec; list<int> lst; int i;
	while (std::cin >> i)
		lst.push_back(i);
copy(lst.cbegin(), lst.cend(), back_inserter(vec));

/* (b) */
vector<int> vec; list<int> lst; int i;
vector<int> vec;
vec.reserve(10); // reserve is covered in § 9.4 (p. 356)
fill_n(vec.begin(), 10, 0);

vector<int> vec;
vec.resize(10, 1); 
fill_n(vec.begin(), 10, 0);

Exercise 10.8: We said that algorithms do not change the size of the containers over which they operate. Why doesn’t the use of back_inserter invalidate this claim?

In reality, algorithms only work with the iterator in this case. Two steps are actually involved here:

• The algorithm created an iterator and bound it to the container.
• A new element was added to the container by the iterator itself using the container memeber push_back()

Obviously, the operation of algorithms is limited to the iterators. From this perspective, using back_inserter does not invalidate the claim since the algorithm has nothing to do with creating the element.

Exercise 10.9: Implement your own version of elimDups. Test your program by printing the vector after you read the input, after the call to unique, and after the call to erase.

CODE: Q.1.

Exercise 10.10: Why do you think the algorithms don’t change the size of containers?

Algorithms are designed to operate iterators only. In reality, they aren't generic if they could do the container size change operation, becuase the size change operation is highly container-dependent.

Exercise 10.11: Write a program that uses stable_sort and isShorter to sort a vector passed to your version of elimDups. Print the vector to verify that your program is correct.

CODE: Q.1.

Exercise 10.12: Write a function named compareIsbn that compares the isbn() members of two Sales_data objects. Use that function to sort a vector that holds Sales_data objects.

CODE: header source

Exercise 10.13: The library defines an algorithm named partition that takes a predicate and partitions the container so that values for which the predicate is true appear in the first part and those for which the predicate isfalse appear in the second part. The algorithm returns an iterator just past the last element for which the predicate returned true. Write a function thattakes a string and returns a bool indicating whether the string has fivecharacters or more. Use that function to partition words. Print the elements that have five or more characters.

CODE: Q.1.

Exercise 10.14: Write a lambda that takes two ints and returns their sum.

[](int a, int b) { return a + b; } ;
[](int a, int b) -> int { return a + b; }; //with explicit return type

Exercise 10.15: Write a lambda that captures an int from its enclosing function and takes an int parameter. The lambda should return the sum of the captured int and the int parameter.

void 
sum(const int i) {
	auto i_sum = [i](int ib) { return i + ib; };
}

Exercise 10.16: Write your own version of the biggies function using lambdas.

CODE: Q.1.

Exercise 10.17: Rewrite exercise 10.12 from § 10.3.1 (p. 387) to use a lambda in the call to sort instead of the compareIsbn function.

CODE: Q.1.

Exercise 10.18: Rewrite biggies to use partition instead of find_if. We described the partition algorithm in exercise 10.13 in § 10.3.1 (p.387).

CODE: Q.1.

Exercise 10.19: Rewrite the previous exercise to use stable_partition, which like stable_sort maintains the original element order in the paritioned sequence.

CODE: Q.1.

Exercise 10.20: The library defines an algorithm named count_if. Like find_if, this function takes a pair of iterators denoting an input range and a predicate that it applies to each element in the given range. count_ifreturns a count of how often the predicate is true. Use count_if to rewritethe portion of our program that counted how many words are greater thanlength 6.

CODE: Q.1.

Exercise 10.21: Write a lambda that captures a local int variable and decrements that variable until it reaches 0. Once the variable is 0 additional calls should no longer decrement the variable. The lambda should return a bool that indicates whether the captured variable is 0.

CODE: Q.1.

Exercise 10.22: Rewrite the program to count words of size 6 or less using functions in place of the lambdas.

CODE: Q.1.

How many arguments does bind take?

bind() will take 1 callable, plus the number of the placeholder, plus the number of the local variable to be passed.

Exercise 10.24: Use bind and check_size to find the first element in a vector of ints that has a value greater than the length of a specified string value.

CODE: Q.1.

Exercise 10.25: In the exercises for § 10.3.2 (p. 392) you wrote a version of biggies that uses partition. Rewrite that function to use check_size and bind.

CODE: Q.1.

Exercise 10.26: Explain the differences among the three kinds of insert iterators.

• inserter: It takes an iterator and uses it to denote the initial insert position. Assignments to the inserter will insert an element before the insert position. call the insert().
• back_inserter: The insert position is fixed and at the end of the container. call the push_back().
• front_inserter: The insert position is fixed and at the beginning of the container. The lastest inserted element will be at the frontmost of the container. call the push_front().

Exercise 10.27: In addition to unique (§ 10.2.3, p. 384), the library defines function named unique_copy that takes a third iterator denoting a destination into which to copy the unique elements. Write a program that uses unique_copy to copy the unique elements from a vector into an initially empty list.

CODE: Q.1.

Exercise 10.28: Copy a vector that holds the values from 1 to 9 inclusive, into three other containers. Use an inserter, a back_inserter, and a front_inserter, respectivly to add elements to these containers. Predict how the output sequence varies by the kind of inserter and verify your predictions by running your programs.

CODE: Q.1.

Exercise 10.29: Write a program using stream iterators to read a text file into a vector of strings.

CODE: Q.1.

Exercise 10.30: Use stream iterators, sort, and copy to read a sequence of integers from the standard input, sort them, and then write them back to the standard output.

CODE: Q.1.

Exercise 10.31: Update the program from the previous exercise so that it prints only the unique elements. Your program should use unqiue_copy (§ 10.4.1, p. 403).

CODE: Q.1.

Exercise 10.32: Rewrite the bookstore problem from § 1.6 (p. 24) using a vector to hold the transactions and various algorithms to do the processing. Use sort with your compareIsbn function from § 10.3.1 (p. 387) to arrange the transactions in order, and then use find and accumulate to do the sum.

CODE: Q.1.

Exercise 10.33: Write a program that takes the names of an input file and two output files. The input file should hold integers. Using an istream_iterator read the input file. Using ostream_iterators, write the odd numbers into the first output file. Each value should be followed by a space. Write the even numbers into the second file. Each of these values should be placed on a separate line.

CODE: Q.1.

Exercise 10.34: Use reverse_iterators to print a vector in reverse order.

CODE: Q.1.

Exercise 10.35: Now print the elements in reverse order using ordinary iterators.

CODE: Q.1.

Exercise 10.36: Use find to find the last element in a list of ints with value 0.

CODE: Q.1.

Exercise 10.37: Given a vector that has ten elements, copy the elements from positions 3 through 7 in reverse order to a list.

CODE: Q.1.

Exercise 10.38: List the five iterator categories and the operations that each supports.

• Inuput Iterator: single pass read, ++, *, !=, ==, →
• Output Iterator:single pass write, ++, *, !=, ==, → (++, * has no effect on the iterator).
• Forward iterator: all above plus multi-ass r/w
• Bidirectional Iterator: all above plus backward read & write (–)
• Random access Iterator: all ablove plus +, -, +=, -=, <, ≤, >,>=, iter1-iter2, iter[n]

Exercise 10.39: What kind of iterator does a list have? What about a vector?

* list iterators: Bidirectional iterator

• vector iterators: Random Access iterator

Exercise 10.40: What kinds of iterators do you think copy requires? What about reverse or unique?

//std::copy needs an output_iterator
template<class InputIt, class OutputIt>
OutputIt copy(InputIt first, InputIt last, 
              OutputIt d_first)
{
    while (first != last) {
        *d_first++ = *first++;
    }
    return d_first;
}

//std::reverse needs a bidirectional iterator
template<class BidirIt>
constexpr // since C++20
void reverse(BidirIt first, BidirIt last)
{
    using iter_cat = typename std::iterator_traits<BidirIt>::iterator_category;
    
    if constexpr (std::is_base_of_v<std::random_access_iterator_tag, iter_cat>) {
        if (first == last)
            return;
        for (--last; first < last; (void)++first, --last) {
            std::iter_swap(first, last);
        }
    }
    else {
        while ((first != last) && (first != --last)) {
            std::iter_swap(first++, last);
        }
    }
}

//std::unique needs a forward_iterartor
template<class ForwardIt>
ForwardIt unique(ForwardIt first, ForwardIt last)
{
    if (first == last)
        return last;
 
    ForwardIt result = first;
    while (++first != last) {
        if (!(*result == *first) && ++result != first) {
            *result = std::move(*first);
        }
    }
    return ++result;
}

Exercise 10.41: Based only on the algorithm and argument names, describe the operation that the each of the following library algorithms performs:

//replace all old_val in [beg, end) to new_val
replace(beg, end, old_val, new_val);
//replace all elements that satisfied pred to new_val
replace_if(beg, end, pred, new_val);
//replace all old_val in [beg, end) to new_val, then write the sequence to dest
replace_copy(beg, end, dest, old_val, new_val);
//replace all elements that satisfied pred to new_val, then write the sequence to dest
replace_copy_if(beg, end, dest, pred, new_val);

Exercise 10.42: Reimplement the program that eliminated duplicate words that we wrote in § 10.2.3 (p. 383) to use a list instead of a vector.

CODE: Q.1.