Chapter 9. Sequential Containers

Exercise 9.1

Which is the most appropriate—a vector, a deque, or a list—for the following program tasks?Explain the rationale for your choice.If there is no reason to prefer one or another container, explain why not.

    1. Read a fixed number of words, inserting them in the container alphabetically as they are entered. We’ll see in the next chapter that associative containers are better suited to this problem.
    1. Read an unknown number of words. Always insert new words at the back. Remove the next value from the front.
    1. Read an unknown number of integers from a file. Sort the numbers and then print them to standard output.
    1. std::set is the best. now, we can select list, better than vector or deque, cause we may need to insert elements in the middle frequently to keep sorted alphabetical.
    1. deque. If the program needs to insert or delete elements at the front and the back, but not in the middle, use a deque
    1. vector, no need that insert or delete at the front or back. and If your program has lots of small elements and space overhead matters, don’t use list or forward_list.

以下是对于每个任务最合适的容器的选择：

    1. 读取固定数量的单词，将它们按照字母顺序插入容器中。在输入时，按照字母顺序插入新的单词。在这种情况下，最合适的容器是 std::set，因为 std::set 是一个有序容器，它可以确保插入的元素按照字母顺序排列，并且不允许重复元素。通过使用 std::set，可以简单地将单词插入容器中，而无需担心排序或重复的问题。
    1. 读取未知数量的单词。始终将新单词插入到容器的末尾，并从容器的开头移除下一个值。在这种情况下，最合适的容器是 std::deque（双端队列）。std::deque 支持在容器的前端和后端高效地插入和删除元素，并且在不需要整个容器进行重新分配的情况下能够提供高效的内存管理。因此，通过使用 std::deque，可以实现在容器的末尾添加新值和从容器的开头移除值的操作。
    1. 从文件中读取未知数量的整数。对这些数字进行排序，然后将它们打印到标准输出。在这种情况下，最合适的容器是 std::vector。std::vector 是一个动态数组，它可以有效地存储大量的元素，并且可以通过使用标准库中的算法对元素进行排序。通过使用 std::vector，可以从文件中读取整数并将它们存储在容器中，然后使用 std::sort 算法对容器中的元素进行排序，最后将排序后的元素打印到标准输出。

Exercise 9.2

Define a list that holds elements that are deques that hold ints.

1
std::list<std::deque<int>> ldi;

Exercise 9.3

What are the constraints on the iterators that form iterator ranges?

two iterators, begin and end:

  • they refer to elements of the same container.
  • It is possible to reach end by repeatedly incrementing begin.

迭代器范围的迭代器有哪些约束？

形成迭代器范围的两个迭代器，即 begin 和 end：

它们引用同一容器中的元素。 可以通过反复递增 begin 达到 end。

Exercise 9.4

Write a function that takes a pair of iterators to a vector<int> and an int value. Look for that value in the range and return a bool indicating whether it was found.

编写一个函数，它接受一个指向 vector 的迭代器对以及一个 int 值作为参数。在指定的范围内查找该值，并返回一个 bool 值，指示是否找到了该值。

1
2
3
4
5
6
bool find(vector<int>::iterator beg, vector<int>::iterator end, int value)
{
    for (auto iter = beg; iter != end; ++iter)
        if (*iter == value) return true;
    return false;
}

Exercise 9.5

Rewrite the previous program to return an iterator to the requested element. Note that the program must handle the case where the element is not found.

重写上一个程序，以返回指向请求的元素的迭代器。注意，程序必须处理未找到元素的情况。

1
2
3
4
5
6
vector<int>::iterator find(vector<int>::iterator beg, vector<int>::iterator end, int value)
{
    for (auto iter = beg; iter != end; ++iter)
        if (*iter == value) return iter;
    return end;
}

Exercise 9.6

What is wrong with the following program? How might you correct it?

1
2
3
list<int> lst1;
list<int>::iterator iter1 = lst1.begin(), iter2 = lst1.end();
while (iter1 < iter2) /*ERROR: operator< can't be applied to iterator for list*/

Fixed:

1
while(iter1 != iter2)

Exercise 9.7

What type should be used as the index into a vector of ints?

1
vector<int>::size_type

在C++中，当我们使用vector<int>这样的容器时，通常使用vector<int>::size_type作为索引的类型。vector<int>::size_type是vector容器的成员类型，表示容器中元素的数量的数据类型。它是一个无符号整数类型，通常是unsigned int或unsigned long的别名，用于确保能够存储容器可能达到的最大大小。

使用vector<int>::size_type作为索引类型有几个好处：

  1. 跨平台兼容性： size_type是vector容器的成员类型，因此它能够保证在不同平台和不同编译器下的一致性。

  2. 避免符号问题： size_type是无符号整数类型，避免了使用有符号整数类型可能导致的符号问题，比如溢出或者负索引。

  3. 容量匹配： 使用容器的成员类型作为索引类型可以确保容器能够存储的最大元素数量，因为size_type是与容器类型相关联的。

使用vector<int>::size_type的一个示例是迭代访问vector<int>的元素：

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    for (std::vector<int>::size_type i = 0; i < vec.size(); ++i) {
        std::cout << "Element at index " << i << " is " << vec[i] << std::endl;
    }

    return 0;
}

在上面的示例中，i的类型被声明为vector<int>::size_type，这样可以确保对vec中所有可能的索引值进行正确的访问。

Exercise 9.8

What type should be used to read elements in a list of strings? To write them?

1
2
list<string>::iterator || list<string>::const_iterator // read
list<string>::iterator // write

在C++的STL（标准模板库）中，list是一个双向链表容器，用于存储元素。它提供了两种迭代器类型：list<string>::iterator和list<string>::const_iterator。

  1. list<string>::iterator: 这是list容器的迭代器类型，用于读取和修改容器中的元素。它允许对容器中的元素进行读写操作。通过iterator，可以遍历整个容器，并且可以通过解引用操作符(*)来访问元素，并且还可以使用成员访问操作符(->)访问元素的成员函数（如果元素类型有的话）。此外，iterator还可以用于修改元素的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <list>
#include <string>

int main() {
    std::list<std::string> mylist = {"apple", "banana", "orange"};

    // Using iterator to modify elements
    for (std::list<std::string>::iterator it = mylist.begin(); it != mylist.end(); ++it) {
        *it = "fruit";
    }

    // Display modified list
    for (const std::string& fruit : mylist) {
        std::cout << fruit << " ";
    }
    std::cout << std::endl;

    return 0;
}
  1. list<string>::const_iterator: 这是list容器的常量迭代器类型，用于只读访问容器中的元素。const_iterator不允许修改容器中的元素值。它可以用于遍历容器并读取元素的值，但不能用于修改元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <list>
#include <string>

int main() {
    std::list<std::string> mylist = {"apple", "banana", "orange"};

    // Using const_iterator for read-only access
    for (std::list<std::string>::const_iterator it = mylist.begin(); it != mylist.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

这两种迭代器都提供了一种遍历list容器中元素的方法，但是iterator允许修改元素值，而const_iterator只允许读取元素值。

Exercise 9.9

What is the difference between the begin and cbegin functions?

cbegin is a const member that returns the container’s const_iterator type.

begin is nonconst and returns the container’s iterator type.

在C++的STL（标准模板库）中，begin和cbegin是用于获取容器中元素的起始位置的成员函数。它们之间的主要区别在于返回的迭代器类型和对待容器的const性。

  1. begin：
    • begin是一个成员函数，用于获取容器中元素的起始位置的迭代器。
    • 返回的迭代器类型是容器的非const版本，即返回的是容器的iterator类型。
    • 如果调用begin的容器是const类型，返回的迭代器也可以用于修改容器中的元素。
    • 例如，在vector或list等容器中，如果调用begin，将得到一个可用于修改容器中元素的iterator。
  2. cbegin：
    • cbegin也是一个成员函数，用于获取容器中元素的起始位置的迭代器。
    • 返回的迭代器类型是容器的const版本，即返回的是容器的const_iterator类型。
    • 即使调用cbegin的容器是非const类型，返回的迭代器也只能用于读取容器中的元素，不能修改容器中的元素。
    • 这意味着即使容器是const类型，也可以使用cbegin来获取一个只读的迭代器，以确保不会对容器的内容进行修改。

以下是一个示例说明两者之间的区别：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // Using begin to get an iterator
    std::vector<int>::iterator it = vec.begin();
    *it = 10; // Valid, modifies the value in the vector

    // Using cbegin to get a const_iterator
    std::vector<int>::const_iterator cit = vec.cbegin();
    // *cit = 10; // Error! Attempting to modify a const object

    // Display modified vector
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

在上面的示例中，begin返回的迭代器可以修改vector中的元素值，而cbegin返回的迭代器只能用于读取vector中的元素值，任何尝试修改元素值的操作都会导致编译错误。

Exercise 9.10

What are the types of the following four objects?

1
2
3
4
vector<int> v1;
const vector<int> v2;
auto it1 = v1.begin(), it2 = v2.begin();
auto it3 = v1.cbegin(), it4 = v2.cbegin();

it1 is vector<int>::iteratorit2,it3andit4arevector::const_iterator

Exercise 9.11

Show an example of each of the six ways to create and initialize a vector. Explain what values each vector contains.

1
2
3
4
5
6
vector<int> vec;    // 0
vector<int> vec(10);    // 0
vector<int> vec(10,1);  // 1
vector<int> vec{1,2,3,4,5}; // 1,2,3,4,5
vector<int> vec(other_vec); // same as other_vec
vector<int> vec(other_vec.begin(), other_vec.end()); // same as other_vec

Exercise 9.12

Explain the differences between the constructor that takes a container to copy and the constructor that takes two iterators.

  • The constructor that takes another container as an argument (excepting array) assumes the container type and element type of both containers are identical. It will also copy all the elements of the received container into the new one:
  • 构造函数接受另一个容器作为参数（除数组外），假设两个容器的容器类型和元素类型相同。它还会将接收到的容器的所有元素复制到新容器中。
1
2
3
4
list<int> numbers = {1, 2, 3, 4, 5};
list<int> numbers2(numbers);        // ok, numbers2 has the same elements as numbers
vector<int> numbers3(numbers);      // error: no matching function for call...
list<double> numbers4(numbers);     // error: no matching function for call...

  • The constructor that takes two iterators as arguments does not require the container types to be identical. Moreover, the element types in the new and original containers can differ as long as it is possible to convert the elements we’re copying to the element type of the container we are initializing. It will also copy only the object delimited by the received iterators.

  • 接受两个迭代器作为参数的构造函数不要求容器类型相同。此外，新容器和原始容器中的元素类型可以不同，只要我们正在复制的元素可以转换为我们正在初始化的容器的元素类型即可。它还仅复制由接收到的迭代器限定的对象。

    这意味着，当我们使用这种构造函数时，我们可以从一个类型不同的容器中复制元素到另一个容器中，只要能够进行元素类型的转换。它提供了更大的灵活性，因为我们只需复制迭代器指定的范围内的元素，而不必复制整个容器。

1
2
3
4
5
list<int> numbers = {1, 2, 3, 4, 5};
list<int> numbers2(numbers.begin(), numbers.end);        // ok, numbers2 has the same elements as numbers
vector<int> numbers3(numbers.begin(), --numbers.end());  // ok, numbers3 is {1, 2, 3, 4}
list<double> numbers4(++numbers.beg(), --numbers.end());        // ok, numbers4 is {2, 3, 4}
forward_list<float> numbers5(numbers.begin(), numbers.end());   // ok, number5 is {1, 2, 3, 4, 5}

Exercise 9.13

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//! @author @shbling @Alan
//!
//! Exercise 9.13:
//! How would you initialize a vector<double> from a list<int>?
//! From a vector<int>?
//! Write code to check your answers.
//!
#include <iostream>
#include <string>
#include <vector>
#include <list>

using std::list;
using std::vector;
using std::cout;
using std::endl;

int main()
{
    list<int> ilst(5, 4);
    vector<int> ivc(5, 5);

    //! from list<int> to vector<double>
    vector<double> dvc(ilst.begin(), ilst.end());
    for (auto i : ilst) cout << i;
    cout << endl;
    for (auto t : dvc) cout << t;
    cout << endl;

    //! from vector<int> to vector<double>
    vector<double> dvc2(ivc.begin(), ivc.end());
    for (auto i : ivc) cout << i;
    cout << endl;
    for (auto t : dvc2) cout << t;

    return 0;
}

Exercise 9.14

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//! @Alan @pezy
//!
//! Exercise 9.14:
//! Write a program to assign the elements from a list of char* pointers
//! to C-style character strings
//!
//! @Notice C-style character strings should use const char*, otherwise warning.
//!

#include <iostream>
#include <string>
#include <vector>
#include <list>

int main()
{
    std::list<const char*> l{"Mooophy", "pezy", "Queeuqueg"};
    std::vector<std::string> v;
    v.assign(l.cbegin(), l.cend());

    for (const auto& ch : v) std::cout << ch << std::endl;

    return 0;
}

这段代码的目标是将一个存储了char*指针的list中的元素赋值给一个存储了std::string的vector。下面是代码的解释：

  1. 首先，我们创建了一个list<const char*>，其中存储了几个指向C风格字符串（即以空字符结尾的字符数组）的指针。

  2. 然后，我们创建了一个空的vector<std::string>。

  3. 我们使用assign函数将list的元素范围赋值给了vector。由于list的元素类型是const char*，而vector的元素类型是std::string，所以在赋值时会自动进行转换，将C风格字符串转换为std::string对象。

  4. 最后，我们遍历vector中的元素，并将它们打印出来。

Exercise 9.15

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//! @file   Exercise 9.15
//! @author pezy
//! @date   2014-12-02
//! @Brief  Write a program to determine whether two vector<int>s are equal.

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> vec1{1, 2, 3, 4, 5};
    std::vector<int> vec2{1, 2, 3, 4, 5};
    std::vector<int> vec3{1, 2, 3, 4};

    std::cout << std::boolalpha << (vec1 == vec2) << std::endl;
    std::cout << std::boolalpha << (vec1 == vec3) << std::endl;

    return 0;
}

通过std::boolalpha操纵符来将布尔值打印为true或false，并将比较结果打印出来。

Exercise 9.16

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//! @file   Exercise 9.16
//! @author pezy
//! @date   2014-12-02
//! @Brief  Repeat the previous program, but compare elements in a list<int> to
//! a vector<int>.

#include <iostream>
#include <vector>
#include <list>

int main()
{
    std::list<int> list{1, 2, 3, 4, 5};
    std::vector<int> vec1{1, 2, 3, 4, 5};
    std::vector<int> vec2{1, 2, 3, 4};

    std::cout << std::boolalpha
              << (std::vector<int>(list.begin(), list.end()) == vec1)
              << std::endl;
    std::cout << std::boolalpha
              << (std::vector<int>(list.begin(), list.end()) == vec2)
              << std::endl;
}

Exercise 9.17

Assuming c1 and c2 are containers, what (if any) constraints does the following usage place on the types of c1 and c2?

假设c1和c2是容器，以下用法对c1和c2的类型有什么（如果有的话）限制？

First, there must be the identical container and same type holded. Second,the type held must support relational operation. (@Mooophy)

Both c1 and c2 are the containers except the unordered associative containers.(@pezy)

首先，必须是相同类型的容器并且持有相同类型的元素。其次，所持有的类型必须支持关系运算。

Exercise 9.18

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//
//  ex9_18.cpp
//  Exercise 9.18
//
//  Created by pezy on 12/3/14.
//  Copyright (c) 2014 pezy. All rights reserved.
//
//  @Brief  Write a program to read a sequence of strings from the standard
//  input into
//          a deque. Use iterators to write a loop to print the elements in the
//          deque.

#include <iostream>
#include <string>
#include <deque>

using std::string;
using std::deque;
using std::cout;
using std::cin;
using std::endl;

int main()
{
    deque<string> input;
    for (string str; cin >> str; input.push_back(str))
        ;
    for (auto iter = input.cbegin(); iter != input.cend(); ++iter)
        cout << *iter << endl;

    return 0;
}

Exercise 9.19

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//
//  ex9_19.cpp
//  Exercise 9.19
//
//  Created by pezy on 12/3/14.
//  Copyright (c) 2014 pezy. All rights reserved.
//
//  @Brief  Rewrite the program from the previous exercise to use a list.
//          List the changes you needed to make.
//  @See    ex9_18.cpp

#include <iostream>
#include <string>
#include <list>

using std::string;
using std::list;
using std::cout;
using std::cin;
using std::endl;

int main()
{
    list<string> input;
    for (string str; cin >> str; input.push_back(str))
        ;
    for (auto iter = input.cbegin(); iter != input.cend(); ++iter)
        cout << *iter << endl;

    return 0;
}

Exercise 9.20

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//
//  ex9_20.cpp
//  Exercise 9.20
//
//  Created by pezy on 12/3/14.
//  Copyright (c) 2014 pezy. All rights reserved.
//
//  @Brief  Write a program to copy elements from a list<int> into two deques.
//          The even-valued elements should go into one deque and the odd ones
//          into the other.

#include <iostream>
#include <deque>
#include <list>
using std::deque;
using std::list;
using std::cout;
using std::cin;
using std::endl;

int main()
{
    list<int> l{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    deque<int> odd, even;
    for (auto i : l) (i & 0x1 ? odd : even).push_back(i);

    for (auto i : odd) cout << i << " ";
    cout << endl;
    for (auto i : even) cout << i << " ";
    cout << endl;

    return 0;
}

Exercise 9.21

Explain how the loop from page 345 that used the return from insert to add elements to a list would work if we inserted into a vector instead.

It's the same.

The first call to insert takes the string we just read and puts it in front of the element denoted by iter. The value returned by insert is an iterator referring to this new element. We assign that iterator to iter and repeat the while, reading another word. As long as there are words to insert, each trip through the while inserts a new element ahead of iter and reassigns to iter the location of the newly inserted element. That element is the (new) first element. Thus, each iteration inserts an element ahead of the first element in the vector.

Exercise 9.22

Assuming iv is a vector of ints, what is wrong with the following program? How might you correct the problem(s)?

1
2
3
4
vector<int>::iterator iter = iv.begin(), mid = iv.begin() + iv.size()/2;
while (iter != mid)
    if (*iter == some_val)
        iv.insert(iter, 2 * some_val);

Problems:

  1. It's a endless loop. iter never equal mid.
  2. mid will be invalid after the insert.

FIXED:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <vector>
using std::vector;

void insertDoubleValue(vector<int>& iv, int some_val)
{
    auto cursor = iv.size() / 2;
    auto iter = iv.begin(), mid = iv.begin() + cursor;
    while (iter != mid) {
        if (*iter == some_val) {
            iter = iv.insert(iter, 2 * some_val);
            ++iter;
            ++cursor;
            mid = iv.begin() + cursor;
        }
        ++iter;
    }
}

void print(const vector<int>& iv)
{
    for (auto i : iv) std::cout << i << " ";
    std::cout << std::endl;
}

int main()
{
    vector<int> iv = {1, 1, 1, 1, 1, 7, 1, 9};
    insertDoubleValue(iv, 1);
    print(iv);
}

Exercise 9.24

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//! @Yue Wang @pezy
//!
//! Exercise 9.24:
//! Write a program that fetches the first element in a vector using at,
//! the subscript operator, front, and begin. Test your program on an empty
//! vector.
//!
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v;
    std::cout << v.at(
        0); // terminating with uncaught exception of type std::out_of_range
    std::cout << v[0];       // Segmentation fault: 11
    std::cout << v.front();  // Segmentation fault: 11
    std::cout << *v.begin(); // Segmentation fault: 11
    return 0;
}

这段代码的目标是从一个空的vector中获取第一个元素，使用了at、下标运算符、front和begin四种不同的方式。下面是代码的解释：

  1. std::cout << v.at(0);：使用at成员函数尝试获取第一个元素。但是，由于vector是空的，因此调用at(0)会抛出std::out_of_range异常，因为索引0超出了vector的范围。

  2. std::cout << v[0];：使用下标运算符尝试获取第一个元素。但是，由于vector是空的，因此访问索引0处的元素会导致段错误（Segmentation fault），因为访问了不存在的内存位置。

  3. std::cout << v.front();：使用front成员函数尝试获取第一个元素。但是，由于vector是空的，因此调用front()会导致段错误（Segmentation fault），因为尝试访问空向量的第一个元素。

  4. std::cout << *v.begin();：使用begin成员函数获取指向第一个元素的迭代器，然后通过解引用操作符*来获取该元素的值。但是，由于vector是空的，尝试对空向量的第一个元素进行解引用会导致段错误（Segmentation fault）。

总的来说，由于vector是空的，因此在尝试访问其第一个元素时，所有四种方法都会导致错误。

Exercise 9.25

In the program on page 349 that erased a range of elements, what happens if elem1 and elem2 are equal? What if elem2 or both elem1 and elem2 are the off-the-end iterator?

if elem1 and elem2 are equal, nothing happened.

if elem2 is the off-the-end iterator, it would delete from elem1 to the end.

if both elem1 and elem2 are the off-the-end iterator, nothing happened too.

Exercise 9.26

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//!
//! @author @huangjuncmj @Yue Wang
//! @date   19.11.2014
//!
//! Exercise 9.26:
//! Using the following definition of ia, copy ia into a vector and into a list.
//! Use the single-iterator form of erase to remove the elements with odd values
//! from your
//! list and the even values from your vector.
//!
#include <iostream>
#include <vector>
#include <list>

using std::vector;
using std::list;
using std::cout;
using std::endl;
using std::end;

int main()
{
    int ia[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89};

    //! init
    vector<int> vec(ia, end(ia));
    list<int> lst(vec.begin(), vec.end());

    //! remove odd value
    for (auto it = lst.begin(); it != lst.end();)
        if (*it & 0x1)
            it = lst.erase(it);
        else
            ++it;

    //! remove even value
    for (auto it = vec.begin(); it != vec.end();)
        if (!(*it & 0x1))
            it = vec.erase(it);
        else
            ++it;

    //! print
    cout << "list : ";
    for (auto i : lst) cout << i << " ";
    cout << "\nvector : ";
    for (auto i : vec) cout << i << " ";
    cout << std::endl;

    return 0;
}

Exercise 9.27

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//! @file   Exercise 9.27
//! @author pezy
//! @date   2014-12-03
//! @Brief  Write a program to find and remove the odd-valued elements in a
//! forward_list<int>.

#include <iostream>
#include <forward_list>

using std::forward_list;
using std::cout;
using std::endl;

int main()
{
    forward_list<int> flst = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    for (auto prev = flst.before_begin(), curr = flst.begin();
         curr != flst.end();)
        if (*curr & 0x1)
            curr = flst.erase_after(prev);
        else
            prev = curr++;

    for (auto i : flst) cout << i << " ";
    cout << endl;
}

before_begin() 和 begin() 是 forward_list 类的成员函数，它们分别用于获取指向第一个元素之前的元素（即头节点）和指向第一个元素的迭代器。

  1. before_begin()：
    • 返回一个指向第一个元素之前的元素的迭代器。
    • 这个迭代器通常用于在列表中插入元素时，因为 forward_list 没有提供 push_front() 函数，插入操作需要在指定位置之前插入，这时就需要用到 before_begin() 获取头节点的位置。
    • 如果列表为空，则返回的迭代器将和 begin() 返回的迭代器相同。
  2. begin()：
    • 返回一个指向第一个元素的迭代器。
    • 这个迭代器用于遍历列表中的元素，或者指定列表中的第一个元素。
    • 如果列表为空，则返回的迭代器将和 before_begin() 返回的迭代器相同。

综上所述，before_begin() 和 begin() 的区别在于它们所返回的迭代器指向的位置不同：before_begin() 返回的是第一个元素之前的位置，而 begin() 返回的是第一个元素的位置。

Exercise 9.28

Write a function that takes a forward_list<string> and two additional string arguments. The function should find the first string and insert the second immediately following the first. If the first string is not found, then insert the second string at the end of the list.

编写一个函数，该函数接受一个forward_list<string>和另外两个字符串参数。该函数应该查找第一个字符串，并将第二个字符串立即插入到第一个字符串之后。如果未找到第一个字符串，则将第二个字符串插入到列表末尾。

1
2
3
4
5
6
7
8
void find_and_insert(forward_list<string> &list, const string& to_find, const string& to_add)
{
    auto prev = list.before_begin();
    auto size = std::distance(list.begin(), list.end());
    for (auto curr = list.begin(); curr != list.end(); prev = curr++)
        if (*curr == to_find) list.insert_after(curr, to_add);
    if (size == std::distance(list.begin(), list.end())) list.insert_after(prev, to_add);
}

这段代码定义了一个名为 find_and_insert 的函数，该函数接受一个 forward_list<string> 类型的列表以及两个额外的字符串参数：to_find 和 to_add。

函数的功能是在列表中查找第一个字符串 to_find，如果找到了，则在该字符串之后立即插入第二个字符串 to_add；如果未找到，则将第二个字符串插入到列表末尾。

下面是代码的解释：

  • auto prev = list.before_begin();：初始化一个迭代器 prev，指向头节点之前的位置。

  • auto size = std::distance(list.begin(), list.end());：计算列表的大小，即列表中元素的个数。

  • for (auto curr = list.begin(); curr != list.end(); prev = curr++)：使用循环遍历列表中的元素，curr 是当前迭代器，prev 则指向当前迭代器的前一个位置。

  • if (*curr == to_find) list.insert_after(curr, to_add);：如果当前元素等于要查找的字符串 to_find，则在当前元素之后插入字符串 to_add。

  • if (size == std::distance(list.begin(), list.end())) list.insert_after(prev, to_add);：如果列表的大小没有变化，说明没有找到要查找的字符串，此时将字符串 to_add 插入到列表末尾。

综上所述，这段代码实现了在 forward_list<string> 中查找并插入字符串的功能，并根据查找结果将字符串插入到合适的位置。

Exercise 9.29

Given that vec holds 25 elements, what does vec.resize(100) do? What if we next wrote vec.resize(10)?

1
2
vec.resize(100);    // adds 75 items to the back of vec. These added items are value initialized.
vec.resize(10);     // erases 90 elements from the back of vec

Exercise 9.30

What, if any, restrictions does using the version of resize that takes a single argument place on the element type?

If the container holds elements of a class type and resize adds elements, we must supply an initializer or the element type must have a default constructor.

如果容器保存的是类类型的元素，并且resize添加了元素，那么我们必须提供一个初始化器或者元素类型必须有一个默认构造函数。

Exercise 9.31

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//
//  ex9_31.cpp
//  Exercise 9.31
//
//  Created by pezy on 12/3/14.
//  Copyright (c) 2014 pezy. All rights reserved.
//
//  @Brief  The program on page 354 to remove even-valued elements and
//          duplicate odd ones will not work on a list or forward_list. Why?
//          Revise the program so that it works on these types as well.
//  @list   iter += 2; -> advance(iter, 2);
//

#include <iostream>
#include <list>

using std::list;
using std::cout;
using std::endl;
using std::advance;

int main()
{
    list<int> vi = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    auto iter = vi.begin();
    while (iter != vi.end()) {
        if (*iter % 2) {
            iter = vi.insert(iter, *iter);
            advance(iter, 2);
        }
        else
            iter = vi.erase(iter);
    }

    for (auto i : vi) cout << i << " ";

    return 0;
}

这段代码的目标是在一个list<int>中删除偶数元素并复制奇数元素。下面是代码的解释：

  1. 首先，我们定义了一个list<int>，命名为vi，并初始化了它。

  2. 接着，我们定义了一个迭代器iter，初始化为列表的开始位置。

  3. 然后，我们使用while循环遍历列表中的每个元素。在循环中，我们检查当前元素是否为奇数，如果是奇数，则在当前位置插入一个与当前元素相同的元素，并将迭代器向前移动两个位置；如果是偶数，则删除当前元素。

  4. 最后，我们使用范围for循环打印更新后的列表中的元素。

需要注意的是，为了在list中实现插入操作，我们不能直接使用iter + 2来移动迭代器，因为list不支持随机访问迭代器。因此，我们使用了advance函数来将迭代器移动两个位置。

总的来说，这段代码演示了如何在list<int>中删除偶数元素并复制奇数元素，并且使用了适用于list的插入和删除操作。

Exercise 9.32

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//
//  ex9_32.cpp
//  Exercise 9.32
//
//  Created by pezy on 12/3/14.
//  Copyright (c) 2014 pezy. All rights reserved.
//
//  @Brief  In the program on page 354 would it be legal to write the call to
//  insert as follows?
//          If not, why not?
//          iter = vi.insert(iter, *iter++);
//  @Answer the statement is illegal, cause as said in Standard [5.2.2] :
//          "The order of evaluation of arguments is unspecified."
//          As a result, after entering function insert,
//          iter could be its original value or original value + 1 or even
//          anything else,
//          depending on how compiler implemented.
//          correct it as follows:
//  @Discuss    https://github.com/Mooophy/Cpp-Primer/issues/125

#include <iostream>
#include <vector>

using std::vector;
using std::cout;
using std::endl;

int main()
{
    vector<int> vi = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    auto iter = vi.begin();
    while (iter != vi.end()) {
        if (*iter % 2) {
            iter = vi.insert(iter, *iter);
            iter += 2;
        }
        else
            iter = vi.erase(iter);
    }

    for (auto i : vi) cout << i << " ";

    return 0;
}

Exercise 9.33

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//
//  ex9_33.cpp
//  Exercise 9.33
//
//  Created by pezy on 12/3/14.
//  Copyright (c) 2014 pezy. All rights reserved.
//
//  @Brief  In the final example in this section what would happen
//          if we did not assign the result of insert to begin?
//          Write a program that omits this assignment to see if your
//          expectation was correct.
//  @Answer crash, cause the iterator is invalid after insert. Because
//  Iterators, pointers, and references to a
//          vector or string are invalid if the container was reallocated.

#include <iostream>
#include <vector>

using std::vector;
using std::cout;
using std::endl;

int main()
{
    vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9};
    auto begin = v.begin();
    while (begin != v.end()) {
        ++begin;
        /*begin = */ v.insert(begin, 42);
        ++begin;
    }

    for (auto i : v) cout << i << " ";

    return 0;
}

Exercise 9.34

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//
//  ex9_32.cpp
//  Exercise 9.32
//
//  Created by pezy on 12/3/14.
//  Copyright (c) 2014 pezy. All rights reserved.
//
//  @Brief  Assuming vi is a container of ints that includes even and odd
//  values,
//          predict the behavior of the following loop.
//          After you've analyzed this loop, write a program to test whether
//          your expectations were correct.
//
//			iter = vi.begin();
//			while (iter != vi.end())
//				if (*iter % 2)
//					iter = vi.insert(iter, *iter);
//				++iter;
//
//  @Answer "infinite loop". Casue the `++iter` out of the `while` loop. But
//  even through add brackets it is still infinite loop.
//          Fixed following.

#include <iostream>
using std::cout;
using std::endl;

#include <vector>
using std::vector;

int main()
{
    vector<int> vi = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    auto iter = vi.begin();
    while (iter != vi.end()) {
        if (*iter % 2) {
            iter = vi.insert(iter, *iter);
            ++iter;
        }
        ++iter;
    }

    for (auto i : vi) cout << i << " ";

    return 0;
}

Exercise 9.35

Explain the difference between a vector’s capacity and its size.

The size of a container is the number of elements it already holds;

The capacity is how many elements it can hold before more space must be allocated.

向量（vector）的 size 表示它当前所保存的元素数量，即它已经持有的元素数量。

而 capacity 表示向量当前内存空间的大小，即它能够容纳的元素数量上限。当向量中的元素数量达到了 capacity，即向量已经占满了当前内存空间，如果需要再添加元素，就需要重新分配更大的内存空间来容纳更多的元素。

因此，size 表示已经使用了多少内存空间，而 capacity 表示总共有多少内存空间可供使用。

Exercise 9.36

Can a container have a capacity less than its size?

cannot.

Exercise 9.37

Why don’t list or array have a capacity member?

list elements does not store contiguously. array has the fixed size, thus cannot added elements to it.

Exercise 9.38

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//! @Alan
//!
//! Exercise 9.38:
//! Write a program to explore how vectors grow in the library you use.
//!

#include <iostream>
#include <string>
#include <vector>

int main()
{
    std::vector<std::string> v;
    std::string word;

    while (std::cin >> word) {
        v.push_back(word);
        std::cout << v.capacity() << "\n";
    }

    return 0;
}

Exercise 9.39

Explain what the following program fragment does:

1
2
3
4
5
6
vector<string> svec;
svec.reserve(1024);
string word;
while (cin >> word)
    svec.push_back(word);
svec.resize(svec.size()+svec.size()/2);

The while loop will read words from cin and store them in out vector. Even if we initially reserved 1024 elements, if there are more words read from cin, our vector's capacity will be automatically increased (most implementations will double the previous capacity) to accommodate them.

And now comes the catch. resize() is different from reserve(). In this case resize() will add another svec.size()/2 value initialized elements to svec. If this exceeds svec.capacity() it will also automatically increase it to accommodate the new elements.

Exercise 9.40

If the program in the previous exercise reads 256 words, what is its likely capacity after it is resized? What if it reads 512? 1,000? 1,048?

read size capacity
256 384 1024
512 768 1024
1000 1500 2000(clang is 2048)
1048 1572 2048

Exercise 9.41

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//
//  ex9_41.cpp
//  Exercise 9.41
//
//  Created by pezy on 12/4/14.
//  Copyright (c) 2014 pezy. All rights reserved.
//
//  @Brief  Write a program that initializes a string from a vector<char>.

#include <iostream>
#include <vector>
#include <string>

using std::vector;
using std::cout;
using std::endl;
using std::string;

int main()
{
    vector<char> vec{'p', 'e', 'z', 'y'};
    string str(vec.begin(), vec.end());

    cout << str << endl;

    return 0;
}

Exercise 9.42

Given that you want to read a character at a time into a string, and you know that you need to read at least 100 characters, how might you improve the performance of your program?

Use member reserve(120) to allocate enough space for this string.

假设你想逐个字符地读入一个字符串，并且你知道你至少需要读取100个字符，你如何提高程序的性能？

可以使用成员函数 reserve(120) 来为这个字符串分配足够的空间。

Exercise 9.43

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//
//  ex9_43.cpp
//  Exercise 9.43
//
//  Created by pezy on 6/18/15.
//  Updated by sanerror on 10/16/16.
//  Copyright (c) 2014 pezy. All rights reserved.
//
//  @Brief  Write a function that takes three strings, s, oldVal, and newVal.
//          Using iterators, and the insert and erase functions replace
//          all instances of oldVal that appear in s by newVal.
//          Test your function by using it to replace common abbreviations,
//          such as "tho" by "though" and "thru" by "through".

#include <string>
using std::string;

#include <iostream>

void Replace(string& s, const string& oldVal, const string& newVal)
{
    for (auto beg = s.begin(); std::distance(beg, s.end()) >=
                               std::distance(oldVal.begin(), oldVal.end());) {
        if (string{beg, beg + oldVal.size()} == oldVal) {
            beg = s.erase(beg, beg + oldVal.size());
            beg = s.insert(beg, newVal.cbegin(), newVal.cend());
            std::advance(beg, newVal.size());
        }
        else
            ++beg;
    }
}

int main()
{
    {
        string str{"To drive straight thru is a foolish, tho courageous act."};
        Replace(str, "thru", "through");
        Replace(str, "tho", "though");
        std::cout << str << std::endl;
    }
    {
        string str{
            "To drive straight thruthru is a foolish, thotho courageous act."};
        Replace(str, "thru", "through");
        Replace(str, "tho", "though");
        std::cout << str << std::endl;
    }
    {
        string str{"To drive straight thru is a foolish, tho courageous act."};
        Replace(str, "thru", "thruthru");
        Replace(str, "tho", "though");
        std::cout << str << std::endl;
    }
    {
        string str{"my world is a big world"};
        Replace(str, "world",
                "worldddddddddddddddddddddddddddddddddddddddddddddddd");
        std::cout << str << std::endl;
    }
    return 0;
}

这段代码实现了一个函数Replace，其作用是将字符串s中所有出现的子字符串oldVal替换为newVal。具体实现如下：

  1. 遍历字符串s，通过迭代器beg来查找每个可能出现oldVal的位置。

  2. 在遍历过程中，使用string的构造函数构造一个子字符串，与oldVal进行比较，如果相等，则表示找到了要替换的子字符串。

  3. 如果找到了要替换的子字符串，则使用erase函数删除原字符串中的旧值，然后使用insert函数将新值插入到相应位置。这里需要注意的是，insert函数的返回值是指向新插入元素后面的迭代器，因此需要将beg更新为这个迭代器指向的位置，以便继续搜索剩余的字符串。

  4. 如果没有找到要替换的子字符串，则直接将迭代器beg向前移动一位，继续搜索。

最后，通过多次调用Replace函数，测试了不同的字符串和替换规则，验证了函数的正确性。

Exercise 9.44

采用库函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//
//  ex9_44.cpp
//  Exercise 9.44
//
//  Created by pezy on 12/4/14.
//  Copyright (c) 2014 pezy. All rights reserved.
//
//  @Brief  Rewrite the previous function using an index and replace.
//  @See    9.43

#include <iostream>
#include <string>

using std::cout;
using std::endl;
using std::string;
using std::prev;

void Replace(string& s, string const& oldVal, string const& newVal)
{
    for (string::size_type i = 0; i != s.size(); ++i)
        if (s.substr(i, oldVal.size()) == oldVal) {
            s.replace(i, oldVal.size(), newVal);
            i += newVal.size() - 1;
        }
}

int main()
{
    string str{"To drive straight thru is a foolish, tho courageous act."};
    Replace(str, "tho", "though");
    Replace(str, "thru", "through");
    cout << str << endl;
}

Exercise 9.45

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//! @author @TungWah @Alan
//! @date   4 Oct,2014.
//!
//! Exercise 9.45:
//! Write a funtion that takes a string representing a name and two other
//! strings representing a prefix, such as “Mr.” or “Ms.” and a suffix,
//! such as “Jr.” or “III”. Using iterators and the insert and append functions,
//! generate and return a new string with the suffix and prefix added to the
//! given name.
//!

#include <iostream>
#include <string>

//! Exercise 9.45
std::string pre_suffix(const std::string& name, const std::string& pre,
                       const std::string& su);

int main()
{
    std::string name("alan");
    std::cout << pre_suffix(name, "Mr.", ",Jr.") << std::endl;

    return 0;
}

inline std::string pre_suffix(const std::string& name, const std::string& pre,
                              const std::string& su)
{
    auto ret = name;
    ret.insert(ret.begin(), pre.begin(), pre.end());
    ret.append(su);

    return ret;
}

这段代码实现了一个名为pre_suffix的函数，其功能是接受一个表示姓名的字符串以及两个表示前缀和后缀的字符串，然后生成并返回一个新的字符串，其中包含给定名字、前缀和后缀。

具体实现如下：

  1. 首先，在main函数中定义了一个名为name的字符串，表示姓名，然后调用pre_suffix函数，并输出返回的结果。

  2. 在pre_suffix函数中，首先创建了一个名为ret的字符串，用于存储生成的结果。然后，利用insert函数将前缀插入到ret字符串的开头，利用append函数将后缀追加到ret字符串的末尾。

  3. 最后，将生成的字符串ret返回给调用者。

这样，函数pre_suffix就实现了将前缀和后缀添加到给定姓名字符串中，并返回生成的新字符串的功能。

Exercise 9.46

库函数实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//
//  ex9_46.cpp
//  Exercise 9.46
//
//  Created by pezy on 12/5/14.
//  Copyright (c) 2014 pezy. All rights reserved.
//
//  @Brief  Rewrite the previous exercise using a position and length to manage
//  the strings.
//          This time use only the insert function.
//  @See    9.45

#include <iostream>
#include <string>

std::string pre_suffix(const std::string& name, const std::string& pre,
                       const std::string& su)
{
    std::string ret(name);
    ret.insert(0, pre);
    ret.insert(ret.size(), su);

    return ret;
}

int main()
{
    std::string name("alan");
    std::cout << pre_suffix(name, "Mr.", ",Jr.");

    return 0;
}

Exercise 9.47

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//
//  ex9_47_1.cpp
//  Exercise 9.47
//
//  Created by pezy on 12/5/14.
//  Copyright (c) 2014 pezy. All rights reserved.
//
//  @Brief  Write a program that finds each numeric character
//          and then each alphabetic character in the string "ab2c3d7R4E6".
//          Write two versions of the program. The first should use
//          find_first_of,
//          and the second find_first_not_of.
//  @Version find_first_of

#include <string>
#include <iostream>

using std::string;
using std::cout;
using std::endl;

int main()
{
    string numbers{"0123456789"};
    string alphabet{"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"};
    string str{"ab2c3d7R4E6"};

    cout << "numeric characters: ";
    for (string::size_type pos = 0;
         (pos = str.find_first_of(numbers, pos)) != string::npos; ++pos)
        cout << str[pos] << " ";
    cout << "\nalphabetic characters: ";
    for (string::size_type pos = 0;
         (pos = str.find_first_of(alphabet, pos)) != string::npos; ++pos)
        cout << str[pos] << " ";
    cout << endl;

    return 0;
}

这个程序的目标是在字符串 "ab2c3d7R4E6" 中找到每个数字字符和每个字母字符，并分别打印出来。该程序使用了 find_first_of 函数来实现。

程序的主要步骤如下：

  1. 首先，定义了三个字符串变量：numbers 表示数字字符，alphabet 表示字母字符，str 表示目标字符串 "ab2c3d7R4E6"。

  2. 然后，通过循环遍历 str 中的字符，使用 find_first_of 函数在 numbers 和 alphabet 中查找当前字符的位置。

  3. 如果找到了数字字符，将其打印输出；如果找到了字母字符，也将其打印输出。

  4. 循环直到找不到匹配的字符为止。

这样，程序通过使用 find_first_of 函数实现了在目标字符串中找到并输出数字字符和字母字符的功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//
//  ex9_47_2.cpp
//  Exercise 9.47
//
//  Created by pezy on 12/5/14.
//  Copyright (c) 2014 pezy. All rights reserved.
//
//  @Brief  Write a program that finds each numeric character
//          and then each alphabetic character in the string "ab2c3d7R4E6".
//          Write two versions of the program. The first should use
//          find_first_of,
//          and the second find_first_not_of.
//  @Version find_first_not_of

#include <string>
#include <iostream>

using std::string;
using std::cout;
using std::endl;

int main()
{
    string numbers{"0123456789"};
    string alphabet{"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"};
    string str{"ab2c3d7R4E6"};

    cout << "numeric characters: ";
    for (string::size_type pos = 0;
         (pos = str.find_first_not_of(alphabet, pos)) != string::npos; ++pos)
        cout << str[pos] << " ";
    cout << "\nalphabetic characters: ";
    for (string::size_type pos = 0;
         (pos = str.find_first_not_of(numbers, pos)) != string::npos; ++pos)
        cout << str[pos] << " ";
    cout << endl;

    return 0;
}

这个程序的目标是在字符串 "ab2c3d7R4E6" 中找到每个数字字符和每个字母字符，并分别打印出来。该程序使用了 find_first_not_of 函数来实现。

程序的主要步骤如下：

  1. 首先，定义了三个字符串变量：numbers 表示数字字符，alphabet 表示字母字符，str 表示目标字符串 "ab2c3d7R4E6"。

  2. 然后，通过循环遍历 str 中的字符，使用 find_first_not_of 函数在 alphabet 和 numbers 中查找当前字符的位置。

  3. 如果找到了非字母字符（即数字字符），将其打印输出；如果找到了非数字字符（即字母字符），也将其打印输出。

  4. 循环直到找不到匹配的字符为止。

这样，程序通过使用 find_first_not_of 函数实现了在目标字符串中找到并输出数字字符和字母字符的功能。

Exercise 9.48

Given the definitions of name and numbers on page 365, what does numbers.find(name) return?

string::npos

Exercise 9.49

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//! @file   Exercise 9.49
//! @author pezy
//! @date   2014-12-05
//! @Brief  A letter has an ascender if, as with d or f, part of the letter
//! extends above the middle of the line.
//          A letter has a descender if, as with p or g, part of the letter
//          extends below the line.
//          Write a program that reads a file containing words and reports the
//          longest word that contains
//          neither ascenders nor descenders.

#include <string>
#include <fstream>
#include <iostream>

using std::string;
using std::ifstream;
using std::cout;
using std::endl;

int main()
{
    ifstream ifs("../data/letter.txt");
    if (!ifs) return -1;
    string longest_word;
    for (string word; ifs >> word;)
        if (word.find_first_not_of("aceimnorsuvwxz") == string::npos &&
            word.size() > longest_word.size())
            longest_word = word;

    cout << longest_word << endl;
}

word.find_first_not_of("aceimnorsuvwxz")是一个字符串成员函数find_first_not_of()的调用，它用于在给定字符串中查找第一个不在指定字符集合中的字符，并返回该字符在字符串中的位置。

在这个程序中，word.find_first_not_of("aceimnorsuvwxz")被用于检查单词是否包含除了指定的字符（即"aceimnorsuvwxz"）以外的字符。如果找到了任何不在指定字符集合中的字符，则find_first_not_of()返回该字符的位置；如果找不到这样的字符，则返回string::npos。

Exercise 9.50

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//! @Yue Wang
//!
//! Exercise 9.50:
//! Write a program to process a vector<string>s whose elements represent
//! integral values.
//! Produce the sum of all the elements in that vector.
//! Change the program so that it sums of strings that represent floating-point
//! values.
//!

#include <iostream>
#include <string>
#include <vector>

int sum_for_int(const std::vector<std::string> &v)
{
    int sum = 0;
    for (auto const& s : v) sum += std::stoi(s);
    return sum;
}

float sum_for_float(const std::vector<std::string> &v)
{
    float sum = 0.0;
    for (auto const& s : v) sum += std::stof(s);
    return sum;
}

int main()
{
    std::vector<std::string> v = {"1", "2", "3", "4.5"};
    std::cout << sum_for_int(v) << std::endl;
    std::cout << sum_for_float(v) << std::endl;

    return 0;
}

这个程序的目标是处理一个vector<string>，其中的元素表示整数值或浮点数值，并且计算这些值的总和。

  1. 原始版本的sum_for_int函数用于处理vector<string>中的整数值。它首先将总和sum初始化为0，然后使用循环遍历向量中的每个字符串元素，将其转换为整数并累加到总和中。最后返回总和。

  2. sum_for_float函数与sum_for_int类似，但它用于处理向量中的浮点数值。它将总和sum初始化为0.0，然后使用循环遍历向量中的每个字符串元素，将其转换为浮点数并累加到总和中。最后返回总和。

  3. 在main函数中，我们定义了一个包含整数值和浮点数值的字符串向量v。然后分别调用sum_for_int和sum_for_float函数，并输出它们的返回值，即整数值和浮点数值的总和。

总的来说，这个程序演示了如何处理包含整数值和浮点数值的字符串向量，并计算它们的总和。

Exercise 9.51

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// Exercise 9.51:
// Write a class that has three unsigned members representing year, month, and day.
// Write a constructor that takes a string representing a date. Your constructor should handle a
// variety of date formats, such as January 1, 1900, 1/1/1900, Jan 1, 1900, and so on.

#include <array>
#include <iostream>
#include <string>

class Date {
public:
    explicit Date(const std::string& str = "");
    void Print();
    unsigned year = 1970;
    unsigned month = 1;
    unsigned day = 1;

private:
    std::array<std::string, 12> month_names{"Jan", "Feb", "Mar", "Apr", "May", "Jun",
                                            "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"};
    unsigned MonthFromName(const std::string& str);
};

Date::Date(const std::string& str)
{
    if (str.empty()) return;
    std::string delimiters{" ,/"};
    auto month_day_delim_pos = str.find_first_of(delimiters);
    if (month_day_delim_pos == std::string::npos)
        throw std::invalid_argument("This format is not supported now.");
    month = MonthFromName(str.substr(0, month_day_delim_pos));
    auto day_year_delim_pos = str.find_first_of(delimiters, month_day_delim_pos + 1);
    auto day_len = day_year_delim_pos - month_day_delim_pos - 1;
    day = std::stoi(str.substr(month_day_delim_pos + 1, day_len));
    year = std::stoi(str.substr(day_year_delim_pos + 1));
}

void Date::Print()
{
    std::cout << year << "-" << month << "-" << day << "\n";
}

unsigned Date::MonthFromName(const std::string& str)
{
    if (str.empty()) return 0;
    if (std::isdigit(str[0])) return std::stoi(str);
    for (size_t i = 0; i != 12; ++i) {
        if (str.find(month_names[i]) != std::string::npos) return i + 1;
    }
    return 0; //  not found
}

int main()
{
    { //  default case
        auto date = Date();
        date.Print();
    }
    { //  case 0: January 1, 1900
        auto date = Date("January 1, 1900");
        date.Print();
    }
    { //  case 1: 1/1/1900
        auto date = Date("1/1/1900");
        date.Print();
    }
    { //  case 2: Jan 1, 1900
        auto date = Date("Jan 1, 1900");
        date.Print();
    }
}

这个程序定义了一个表示日期的Date类，并实现了一个可以处理各种日期格式的构造函数。

  1. Date类有三个成员变量，分别代表年、月和日，都是无符号整数类型。

  2. 构造函数Date::Date(const std::string& str)接受一个字符串参数，用于表示日期。构造函数首先检查字符串是否为空，如果为空则直接返回。然后，它使用指定的分隔符来查找月和日之间的分隔位置，并解析出月份。接着，它使用相同的分隔符来查找日和年之间的分隔位置，并解析出日和年。解析完毕后，将解析出的年、月和日赋值给成员变量。

  3. Date::Print()函数用于打印日期的年、月和日。

  4. Date::MonthFromName(const std::string& str)函数根据月份的名称字符串返回对应的月份值。

在main()函数中，我们创建了几个Date对象，并传入不同的日期字符串作为参数。程序将会打印出解析后的日期。

总的来说，这个程序演示了如何使用类来处理不同格式的日期字符串，并将其解析为年、月和日。

1
2
3
4
5
6
7
8
9
10
if (str.empty()) return;
  std::string delimiters{" ,/"};
  auto month_day_delim_pos = str.find_first_of(delimiters);
  if (month_day_delim_pos == std::string::npos)
      throw std::invalid_argument("This format is not supported now.");
  month = MonthFromName(str.substr(0, month_day_delim_pos));
  auto day_year_delim_pos = str.find_first_of(delimiters, month_day_delim_pos + 1);
  auto day_len = day_year_delim_pos - month_day_delim_pos - 1;
  day = std::stoi(str.substr(month_day_delim_pos + 1, day_len));
  year = std::stoi(str.substr(day_year_delim_pos + 1));

这段代码是构造函数Date::Date(const std::string& str)中的一部分，它的作用是解析传入的日期字符串并初始化类的成员变量。

具体来说，这段代码做了以下几件事情：

  1. 首先，如果传入的日期字符串为空，那么直接返回，因为无法解析空字符串。

  2. 然后，定义了一个包含可能的日期分隔符的字符串delimiters，其中包括空格、逗号和斜杠。

  3. 使用find_first_of(delimiters)函数找到日期字符串中第一个出现的分隔符的位置month_day_delim_pos。如果找不到分隔符，即find_first_of()返回std::string::npos，说明日期字符串的格式不受支持，程序将抛出std::invalid_argument异常。

  4. 接着，使用str.substr(0, month_day_delim_pos)提取出月份的子字符串，并调用MonthFromName()函数将其转换为对应的月份值，然后将其赋值给month成员变量。

  5. 再次使用find_first_of(delimiters, month_day_delim_pos + 1)函数找到日期字符串中第二个分隔符的位置day_year_delim_pos，以确定日和年之间的分隔位置。

  6. 使用str.substr(month_day_delim_pos + 1, day_len)提取出日的子字符串，并将其转换为整数值，然后将其赋值给day成员变量。

  7. 最后，使用str.substr(day_year_delim_pos + 1)提取出年的子字符串，并将其转换为整数值，然后将其赋值给year成员变量。

这段代码的作用是将传入的日期字符串解析为年、月和日，并存储到类的成员变量中。

1
2
3
4
5
6
if (str.empty()) return 0;
   if (std::isdigit(str[0])) return std::stoi(str);
   for (size_t i = 0; i != 12; ++i) {
       if (str.find(month_names[i]) != std::string::npos) return i + 1;
   }
   return 0; //  not found

这段代码是Date::MonthFromName(const std::string& str)函数中的一部分，用于根据传入的字符串判断月份。

具体来说，这段代码做了以下几件事情：

  1. 首先，如果传入的字符串为空，那么直接返回0，表示未找到对应的月份。

  2. 然后，检查传入的字符串的第一个字符是否是数字，如果是数字，说明传入的是数字表示的月份，直接将其转换为整数并返回。

  3. 如果传入的字符串不是数字，则说明传入的是月份的名称。接着，使用一个循环遍历预定义的月份名称数组month_names，查找传入的字符串是否包含在数组中的任何一个月份名称中。如果找到了对应的月份名称，则返回该月份在数组中的索引值加1，表示该月份的序号。注意这里索引值加1的原因是月份是从1开始计数的。

  4. 如果传入的字符串既不是数字表示的月份，也不是包含在月份名称数组中的名称，则返回0，表示未找到对应的月份。

总的来说，这段代码的作用是根据传入的字符串判断月份，并返回对应的月份值。如果传入的是数字表示的月份，则直接返回该数字；如果传入的是月份的名称，则查找预定义的月份名称数组，找到对应的月份名称并返回对应的月份值。

Exercise 9.52

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//
//  ex9_52.cpp
//  Exercise 9.52
//
//  Created by pezy on 12/5/14.
//  Copyright (c) 2014 pezy. All rights reserved.
//
//  @Brief  Use a stack to process parenthesized expressions.
//          When you see an open parenthesis, note that it was seen.
//          When you see a close parenthesis after an open parenthesis,
//          pop elements down to and including the open parenthesis off the
//          stack.
//          push a value onto the stack to indicate that a parenthesized
//          expression was replaced.

#include <stack>
using std::stack;

#include <string>
using std::string;

#include <iostream>
using std::cout;
using std::endl;

int main()
{
    auto& expr = "This is (Mooophy(awesome)((((wooooooooo))))) and (ocxs) over";
    auto repl = '#';
    auto seen = 0;

    stack<char> stk;

    for (auto c : expr) {
        stk.push(c);
        if (c == '(') ++seen;   // open
        if (seen && c == ')') { // pop elements down to the stack
            while (stk.top() != '(') stk.pop();
            stk.pop();      // including the open parenthesis
            stk.push(repl); // push a value indicate it was replaced
            --seen;         // close
        }
    }

    // Test
    string output;
    for (; !stk.empty(); stk.pop()) output.insert(output.begin(), stk.top());
    cout << output << endl; // "This is # and # over"
}

这个程序使用栈来处理带有括号的表达式。具体步骤如下：

  1. 首先，定义了一个字符串expr表示待处理的带有括号的表达式，以及一个字符repl表示替换括号的字符，和一个整数seen表示已经看到的括号的数量。

  2. 创建了一个字符类型的栈stk用于处理括号。

  3. 使用for循环遍历表达式中的每个字符，并将其依次压入栈中。

  4. 如果遇到了开括号'('，则增加seen计数表示已经看到了一个开括号。

  5. 如果seen不为0且当前字符是闭括号')'，则从栈顶开始弹出字符直到遇到与当前闭括号匹配的开括号。弹出过程包括了开括号，然后将替换字符repl压入栈中以表示这个被替换的括号已经处理。

  6. 遍历结束后，将栈中的字符依次弹出并组成字符串输出，以验证处理结果。

最终，输出的字符串中所有的括号及其内部的内容都被替换成了替换字符，而其他字符保持不变。