实现字典合并工具

假设我们有一个已经排序的列表，有人有另一个已排序的列表，我们想要将这两个列表进行共享。那么最好的方式就是将这两个列表合并起来。我们需要合并后的列表也是有序的，这样我们查找元素就会十分方便。

为了将两个已排序列表中的元素进行合并，我们本能的会想需要创建一个新的列表来放置这两个列表中的元素。对于要加入的元素，我们需要将队列中的元素进行对比，然后找到最小的那个元素将其放到列表的最前面。不过，这样输出队列的顺序会被打乱。下面的图就能很好的说明这个问题：

实现字典合并工具 - 图1

std::merge算法就可以直接来帮助我们做这个事情，这样我们就无需过多的参与。本节我们将展示如何使用这个算法。

How to do it…

我们将创建一个简单的字典，其为英语单词和德语单词一对一的翻译，之后将其存储在std::deque数据结构中。程序将标注输入中获取这个字典，并且打印合并之后的字典。

  1. 包含必要的头文件，并声明所使用的命名空间。

    1. #include <iostream>
    2. #include <algorithm>
    3. #include <iterator>
    4. #include <deque>
    5. #include <tuple>
    6. #include <string>
    7. #include <fstream>
    9. using namespace std;

  2. 字典是一对字符串，两两对应：

    1. using dict_entry = pair<string, string>;

  3. 我们将在屏幕上打印这个组对，并且要从用户输入中读取这个组对，所以我们必须要重载>>和<<操作符：

    1. namespace std {
    2. ostream& operator<<(ostream &os, const dict_entry p)
    3. {
    4.     return os << p.first << " " << p.second;
    5. }
    6. istream& operator>>(istream &is, dict_entry &p)
    7. {
    8.     return is >> p.first >> p.second;
    9. }
    10. }

  4. 这里需要创建一个辅助函数，其能接受任何流对象作为输入，帮助我们构建字典。其会构建一个std::deque来存放一对一的字符串对，并且其会读取标准输入中的所有字符。并在返回字典前，对字典进行排序：

    1. template <typename IS>
    2. deque<dict_entry> from_instream(IS &&is)
    3. {
    4.     deque<dict_entry> d {istream_iterator<dict_entry>{is}, {}};
    5.     sort(begin(d), end(d));
    6.     return d;
    7. }

  5. 这里使用不同的输入流，创建两个不同的字典。其中一个是从dict.txt文件中读取出的字符，我们先假设这个文件存在。其每一行为一个组对，另一个流就是标准输入：

    1. int main()
    2. {
    3.     const auto dict1 (from_instream(ifstream{"dict.txt"}));
    4.     const auto dict2 (from_instream(cin));

  6. 作为辅助函数from_instream将返回给我们一个已经排过序的字典，这样我们就可以将两个字典直接放入std::merge算法中。其能通过给定两个的begin和end迭代器组确定输入的范围，并在最后给定输出。这里的输出将会打印在用户的屏幕上：

    1.     merge(begin(dict1), end(dict1),
    2.         begin(dict2), end(dict2),
    3.         ostream_iterator<dict_entry>{cout, "\n"});
    4. }

  7. 可以编译这个程序，不过在运行之前，我们需要创建dict.txt文件，并且写入如下内容：

    1. car auto
    2. cellphone handy
    3. house haus

  8. 现在我们运行程序了，输入一些英文单词，将其翻译为德文。这时的输出仍旧是一个排序后的字典，其可以将输入的所有单词进行翻译。

    1. $ echo "table tisch fish fisch dog hund" | ./dictionary_merge
    2. car auto
    3. cellphone handy
    4. dog hund
    5. fish fisch
    6. house haus
    7. table tisch

How it works…

std::meger算法接受两对begin/end迭代器，这两对迭代器确定了输入范围。这两对迭代器所提供的输入范围也必须是已排序的。第五个参数就是输出容器的迭代器，其接受两段范围合并的元素。

其有一个变体std::inplace_merge。两个算法几乎一样，不过这个变体只需要一对迭代器，并且没有输出，和其名字一样，其会直接在输入范围上进行操作。比如对{A, C, B, D}这个序列来说，可以将第一个子序列定义为{A, C}，第二个子序列定义为{B, D}。使用std::inplace_merge算法将两个序列进行合并，其结果为{A, B, C, D}。