这是bert hubert的系列文章，旨在帮助c代码人快速了解c++实用的新特性。原文链接：https://berthub.eu/

面向 C 程序员的 Modern C++ 系列第4部分

欢迎回来!在第3部分中,我讨论了类、多态性、引用和模板,最后用基本容器构建了一个源索引器,实现了60MB/s的索引速度。

在这一部分,我们将继续探讨C++的其他特性,您可以使用这些特性逐行增强代码,而无需立即使用《C++编程语言》的所有1400页。这里会频繁引用第3部分中的索引器示例,所以您可能需要确保自己了解它是关于什么的。

这里讨论的各种代码示例可在GitHub上找到。

如果您有任何想讨论的喜欢的事物或提出问题,请随时通过@bert_hu_bert或bert@hubertnet.nl与我联系。

Lambdas

我们之前已经遇到了这些看起来奇怪的代码片段,例如:

std::sort(vec.begin(), vec.end(), 
          [](const auto& a, const auto& b) { return a < b; }
         );

尽管lambda本质上是语法糖,但它们的可用性使modern C++成为一种更具表现力的语言。此外,正如第1部分所述,将代码片段作为函数指针传递会严重限制编译器优化代码的能力。所以lambda不仅可以减少代码行数,生成的二进制文件也可以更快。

C++ lambdas是一等公民,就像正常代码一样进行编译。脚本语言可以轻松实现lambda,因为它们自带运行时解释器,C++没有这种奢侈。那么它是如何工作的呢?

这里是解剖结构:[capture specification](parameters) { actual code }。capture specification可以为空,这意味着lambda中的代码只“看到”全局变量,这是一个非常好的默认设置。捕获可以是按值或按引用。通常,如果lambda需要捕获大量详细信息,请考虑它是否仍然是一个lambda。

对于参数,您经常会在那里使用auto,但这绝不是强制性的。

然后实际代码在{和}之间,唯一的特殊之处是返回类型是自动推导的,但如果您知道自己在做什么,也可以覆盖它。一个工作示例:

vector<string> v{"9", "12", "13", "14", "18", "42", "75"};
string prefix("hi ");  
for_each(v.begin(), v.end(), [&prefix](const auto& a) {
  cout << prefix + a << endl;
}); // 输出 hi 9, hi 12, hi 13 等

第一行使用了有趣的初始化器,允许modern C++快速填充容器。第二行创建一个前缀字符串。最后一行使用C++算法for_each遍历容器。

prefix变量是‘按引用捕获’。对于传递参数,const auto& a也可以是const std::string&。最后我们打印前缀和容器成员。

要按数字对这个字符串向量进行排序,我们可以这样做:

std::sort(v.begin(), v.end(), [](const auto& a, const auto& b)  
          {
            return atoi(a.c_str()) < atoi(b.c_str());
          });

lambda创建一个实际的对象,尽管是一种未指定的类型:

auto print = [](const vector<std::string>& c) {
  for(const auto& a : c)
    cout << a << endl;
};

cout<<"Starting order: "<<endl;
print(v);

我们现在已经将lambda存储在print中,我们可以传递它并在以后也可以使用它。但是print是什么?如果我们询问调试器,它可能会告诉我们:

(gdb) ptype print  
  struct <lambda(const std::vector<std::string>&)> {}

根据捕获的内容,类型会变得更加复杂。正因如此,lambda通常通过auto或泛型传递。

当需要存储lambda或任何可调用项时,有std::function:

std::function<void(const vector<std::string>&)> stored = print;
stored(v); // 与 print(v)相同

注意,我们也可以这样做:

void print2(const vector<string>& vec) 
{
  // ..
}

...

  std::function<void(const vector<std::string>&)> stored = print2;

std::function也可以存储其他可调用项,如定义了operator()的对象。std::function的缺点是它的速度不如直接调用函数或调用lambda快,所以如果可能的话,请尝试直接调用。

在类中使用的lambda可以捕获[this],这意味着它可以访问类成员。

为了进一步促进C互操作性,如果lambda没有捕获任何内容,它会衰减为普通C函数指针,这导致能够执行此操作:

std::vector<int> v2{3, -1, -4, 1, -5, -9, -2, 6, -5};
qsort(&v2[0], v2.size(), sizeof(int), [](const void *a, const void* b)
      {
        if(abs(*(int*)a) < abs(*(int*)b)) 
          return -1;
        if(abs(*(int*)a) > abs(*(int*)b))
          return 1;
        return 0;
      });

总的来说,lambda非常棒,但最好将它们用于小型、内联的构造。如果发现自己捕获了大量内容,使用functor(可以调用的类实例,因为它重载了operator())可能会更好。

扩展我们的索引器

在第3部分中的索引器中,我们最终得到:

struct Location  
{
  unsigned int fileno;
  size_t offset;
};

std::unordered_map<string, vector<Location>> allWords;

这包含在索引的文件中找到的所有单词的无序列表,每个单词都有一个Location向量,表示找到该单词的位置。我们使用无序映射,因为它比有序映射快40%。

然而,如果我们想执行诸如“main*”的查找以匹配所有以“main”开头的内容,我们也需要一个有序单词列表:

std::vector<string> owords;
owords.reserve(allWords.size()); // 节省malloc调用
for(const auto& w : allWords)
  owords.push_back(w.first); 
sort(owords.begin(), owords.end());

请注意,这使用范围for构造遍历allWords无序映射的键,并将其插入一个尚未排序的向量,我们在最后一行对其进行排序。

有趣的是,我们没有失去40%的速度提升,因为“排序完成后”比“一直保持排序”更快。

如果我们有兴趣,我们可以尝试更智能一点。如上所述,每个单词现在在内存中出现两次,一次在allWords中,一次在owords中。

采用C风格的语法，则如下:

std::vector<const string*> optrwords; 
optrwords.reserve(allWords.size());
for(const auto& w : allWords)
  optrwords.push_back(&w.first);
sort(optrwords.begin(), optrwords.end(), 
     [](auto a, auto b) { return *a < *b;}
    );

使用这段代码,我们存储allWords无序映射键的const指针。然后对optrwords进行排序,它包含指针,使用lambda解引用这些指针。

如果我们索引Linux源代码树,其中包含大约600,000个唯一单词,这确实为我们节省了大约14兆字节的内存,这很好。

然而,缺点是我们现在将原始指针直接存储在另一个容器(allWords)中。只要我们不修改allWords,这是安全的。并且对于某些容器,即使我们做出更改也是安全的。这碰巧是std::unordered_map的情况,只要我们不实际删除存储指针的条目就可以。

我认为这说明了使用modern C++的一个关键点。如果“你知道自己在做什么”,可以节省14兆字节的内存,但我强烈建议,只有在真正需要时才使用这种“C语言”技巧袋。但如果是这种情况,了解可以这样做是很好的。

容器和算法

到目前为止,我们已经看到了各种容器(例如std::vector,std::unordered_map)。此外,还有大量可以对这些容器进行操作的算法。关键是,通过使用模板,算法实际上与它们所操作的容器完全分离。

这种分离使标准能够规定比平常更多的泛用算法。我们已经遇到了std::for_each和std::sort,但这里还有一个更奇特的std::nth_element。

回到我们的索引器,我们有一个单词列表及其出现频率。假设我们想打印出现频率最高的20个单词,我们通常会取整个单词列表,根据频率对其排序,然后打印前20个。

有了std::nth_element,我们可以得到我们需要的。首先,让我们收集要排序的数据,并定义比较函数:

vector<pair<string, size_t>> popcount;
for(const auto& w : allWords)
  popcount.push_back({w.first, w.second.size()}); 

auto cmp = [](const auto& a, const auto& b)  
{
  return b.second < a.second; 
};

我们定义了一个包含pair的vector。pair是一个方便的模板化结构,包含两个成员,称为first和second。我发现pair占据了一个非常有用的甜点地带,一个具有公知名称的“无名结构”。当对嵌套成对的对或使用std::tuple(std::pair的加强版)感到困惑时,会出现混淆。超过两个简单的成员,请创建具有命名成员的结构。

范围for循环展示了一个新特性,“brace initialization”,这意味着w.first和w.second.size()(这个单词的出现次数)用于构造我们的pair。这可以节省大量输入。

最后,我们定义一个比较函数,并将其称为cmp以便我们可以重用它。请注意,它以相反的顺序进行比较。

接下来是实际的排序和打印:

int top = std::min(popcount.size(), (size_t)20);
nth_element(popcount.begin(), popcount.begin() + top, popcount.end(), cmp);  
sort(popcount.begin(), popcount.begin() + top, cmp);

int count=0;
for(const auto& e : popcount) {
  if(++count > top)
    break;
  cout << count << "\t" << e.first << "\t" << e.second << endl;
}

调用std::nth_element需要一些解释。如前所述,迭代器是容器中的“位置”。begin()是第一个条目,首尾一致,end()在最后一个条目之后。在空容器上,begin() == end()。

我们向nth_element传递三个迭代器: 开始排序的位置, 我们的“前20名”的截止点 , 容器的结尾。nth_element然后确保前20个完全位于容器的前20个位置。但是,它不保证前20个本身已排序。出于这个原因,我们对前20个条目进行快速排序。

最后6行打印实际的前20名,顺序正确。

C++带有许多有用的算法,允许您编写强大的程序。例如：std::set_difference、std::set_intersection和 std::set_symmetric_difference可以轻松编写“diff”类工具或找出从一种状态变化到另一种状态的内容。

同时,std::inplace_merge和std::next_permutation等算法可以防止您不得不拿出Knuth的书籍。

在进行任何数据操作或分析之前,我建议您浏览现有算法的列表,您可能会发现里面大部分已可满足您的需要。

查找 – STL中的查找算法

例如,回想一下我们创建了一个排序单词列表以进行前缀查找。所有单词都在std::vector<string> owords中结束。我们可以通过几种方式查询这个平面(因此非常高效)容器:

std::binary_search(begin, end, value) 将让您知道值是否在里面。

std::equal_range(begin, end, value) 返回一对迭代器,跨越所有完全匹配的条目。

std::lower_bound(begin, end, value) 返回一个指向可以插入value而不改变排序顺序的第一个地方的迭代器。upper_bound返回最后一个迭代器,这同样适用。

只要我们的容器中没有多个等效条目,lower_bound和upper_bound是相同的。要从我们的排序向量owords列出所有以“main”开头的词,我们可以执行:

string val("main");
auto iter = lower_bound(owords.begin(), owords.end(), val);
for(; iter != owords.end() && !iter->compare(0, val.size(), val); ++iter)
  cout<<" "<<*iter<<endl;

std::lower_bound在这里完成繁重的工作,在我们排序的std::vector上执行二进制搜索。for循环需要一点解释。第一个检查iter != owords.end()将在lower_bound没有找到任何内容时停止我们。

第二个检查使用iter->compare执行候选单词的子字符串匹配,最多为前4个字符。一旦不再匹配,我们已经迭代超出以“main”开头的单词。

更多的容器

在前面的示例中,我们使用了非常基本的std::vector,它在内存中是连续的,与C兼容,以及std::unordered_map,这是一个相当快速的键/值存储,但没有顺序。

还有几个有用的容器:

std::map一个有序映射,您可以在希望时传递比较函数,例如获取不区分大小写的排序。您将看到的许多例子不必要地使用std::map。这是因为2011年之前,C++没有无序容器。当您需要排序时,有序容器是非常好的,但在其他情况下会带来不必要的开销。

std::set这就像一个std::map<string,void>,换句话说,它是一个没有值的键值存储。与std::map一样,它是有序的,这通常是不需要的。幸运的是,还有std::unordered_set。

std::multimap和std::multiset。这些的工作原理与常规set和map完全一样,但允许多个等效键。这意味着不能使用[]查询这些容器,因为它只支持单个键。

std::deque。双端队列,是实现任何类型队列的好帮手。存储不是连续的,但从任一端弹出和推送元素都是快速的。

可以在此处找到标准容器的完整列表

Boost容器

尽管本系列文章侧重于“核心”C++,但在此处不谈及Boost的一些部分会令我很遗憾。Boost是一个大型的C++代码集合,其中一些代码非常出色(并倾向于进入C++标准,该标准由一些Boost作者编辑),一些代码不错,然后还有一些不幸运的部分。

但好消息是,Boost的大部分都非常模块化:它不是一个框架类库—如果您使用其中一部分,就要使用全部。事实上,许多最有趣的部分仅包含头文件,不需要链接库。Boost普遍可用且免费授权。

首先是Boost容器库,它不是一个库而是一个包含文件集合。它提供了与标准库容器几乎完全兼容但在匹配您的使用案例时提供具体优势的定制容器。

例如,boost::container::flat_map(和set)与std::map和std::set类似,除了它们使用连续内存块以提高缓存效率。这使它们在插入时比较慢,但在查找时非常快。

另一个例子,boost::container::small_vector经过优化,用于存储少量(可模板化)元素,这可以节省大量malloc流量。

可以在此处找到更多Boost容器。

Boost.MultiIndex

其次,在本系列的第1部分中,我承诺会避免奇异用法和“模板元编程”。但我必须与您分享一个珍珠,我认为这是衡量编程语言强大程度的黄金标准 — 该语言是否足够强大以实现Boost.MultiIndex?

简而言之,我们经常需要以多种方式查找对象。例如,如果我们有一个开放TCP会话的容器,我们可能希望根据“完整源IP、源端口、目标IP、目标端口”元组查找会话,但也可能只根据源IP或目标IP。我们还可能希望按时间顺序获取/关闭旧会话。

“手动”执行此操作的方法是维护多个容器,对象存在其中,并使用各种键通过这些容器查找对象:

map<pair<IPEndpoint,IPEndpoint>, TCPSession*> d_sessions;
map<IPEndpoint, TCPSession*> d_sessionsSourceIP;
map<IPEndpoint, TCPSession*> d_sessionsDestinationIP;
multimap<time_t, TCPSession*> d_timeIP;

auto tcps = new TCPSession;
d_sessions[{srcEndpoint, dstEndpoint}] = tcps;
d_sessionsSourceIP[srcEndpoint] = tcps;  
d_sessionsDestinationIP[dstEndpoint] = tcps;
...

虽然这可行,但我们突然必须做很多管理工作。例如,如果要删除一个TCPSession,我们必须记住从所有容器中删除它,然后释放指针。

Boost.MultiIndex是一件艺术品,它不仅提供了可以通过多种方式同时搜索的容器,还提供了(无)有序、唯一和非唯一索引,以及局部键查找,以及使您可以使用char *查找std::string键的“备用键”等功能。

以下是我们查找TCP会话的方式。首先让我们做一些基础工作(完整代码):

struct AddressTupleTag{};
struct DestTag{}; 
struct TimeTag{};

struct Entry
{
  IPAddress srcIP;
  uint16_t srcPort;
  IPAddress dstIP;
  uint16_t dstPort;
  double time;
};

三个Tag提供了标识容器上我们将定义的三种不同索引的类型。然后我们定义Boost.MultiIndex容器将包含的结构。请注意,我们要搜索的键实际上在容器本身中——这里键和值没有区分。

接下来是容器的承认很难的模板定义。您可能会花一个小时才能把它做对,但一旦正确,一切都很简单:

typedef multi_index_container<
  Entry,
indexed_by<
  ordered_unique<
  tag<AddressTupleTag>,
composite_key<Entry, 
member<Entry, IPAddress, &Entry::srcIP>,
member<Entry, uint16_t, &Entry::srcPort>,
member<Entry, IPAddress, &Entry::dstIP>,
member<Entry, uint16_t, &Entry::dstPort>  
  >
  >,
ordered_non_unique<
  tag<DestTag>,
composite_key<Entry,
member<Entry, IPAddress, &Entry::dstIP>,
member<Entry, uint16_t, &Entry::dstPort> 
  >
  >,

ordered_non_unique<
  tag<TimeTag>,
member<Entry, double, &Entry::time>
  >
  tcpsessions_t;

这定义了三个索引,一个有序且唯一,两个有序且非唯一。第一个索引是TCP会话的“4元组”。第二个仅目标会话的目标。最后一个是时间戳。

重要的是要注意,此模板定义在编译时为容器生成全部代码。所有这一切导致的代码就像您自己编写的一样高效,正如模板化容器通常的情况一样。实际上,Boost.MultiIndex容器通常比std::map更快。

让我们用一些数据填充它:

tcpsessions_t sessions; 
double now = time(0);
Entry e{"1.2.3.4"_ipv4, 80, "4.3.2.1"_ipv4, 123, now};
sessions.insert(e);

sessions.insert({"1.2.3.4"_ipv4, 81, "4.3.2.5"_ipv4, 1323, now+1.0}); 
sessions.insert({"1.2.3.5"_ipv4, 80, "4.3.2.2"_ipv4, 4215, now+2.0});

第一行使用typedef使我们的容器的实际实例,第二行获取当前时间并将其放入double中。

然后发生一些名为用户定义字面量的魔术,这意味着"1.2.3.4"_ipv4被转换为0x01020304 - 在编译时。要观察这是如何工作的,请转到GitHub上的multi.cc。这些派对的诡计是C++的可选项,但constexpr编译时代码执行确实很酷。

运行此操作后,我们的sessions容器中有3个条目。让我们以时间顺序全部列出:

auto& idx = sessions.get<TimeTag>();
for(auto iter = idx.begin(); iter != idx.end(); ++iter)
  cout << iter->srcIP << ":" << iter->srcPort<< " -> "<< iter->dstIP <<":"<<iter->dstPort << "\n";

这会打印:

1.2.3.4:80 -> 4.3.2.1:123
1.2.3.4:81 -> 4.3.2.5:1323
1.2.3.5:80 -> 4.3.2.2:4215

在第一行中,我们请求TimeTag索引的引用,在第二行中像往常一样迭代它。

让我们在“main”(第一个)索引上进行部分查找,该索引基于完整的4元组:

cout<<"Search for source 1.2.3.4, every port"<<endl;
auto range = sessions.equal_range(std::make_tuple("1.2.3.4"_ipv4));
for(auto iter = range.first; iter != range.second ; ++iter)
  // 打印

通过仅使用一个成员创建元组std::make_tuple,我们指示我们仅希望根据4元组的第一部分进行查找。如果我们添加了“, 80”到std::make_tuple,我们只会找到一个匹配的TCP会话,而不是两个。请注意,此查找使用前面在本页描述的equal_range。

最后,根据TCP会话的目标搜索:

cout<<"Destination search for 4.3.2.1 port 123: "<<endl; 
auto range2 = sessions.get<DestTag>().equal_range(std::make_tuple("4.3.2.1"_ipv4, 123));
for(auto iter = range2.first; iter != range2.second ; ++iter)
  // 打印

这请求DestTag索引,然后使用它来找到目标为4.3.2.1:123的会话。

我希望您可以原谅我这次跨出标准C++的范畴,但由于Boost.MultiIndex几乎参与了我编写的所有代码,我觉得有必要分享它。

总结

在这长长的第4部分中,我们已经深入探讨了lambdas的一些细枝末节,以及它们如何用于自定义排序,如何存储以及何时是个好主意。

其次,我们通过增强代码索引器以查找部分词的能力,通过将无序词容器排序到一个平面向量中,探索了算法和容器之间的交互。我们还研究了如何使用某些“C式”技巧来使此过程既节省内存又更危险。

我们还查看了C++提供的丰富算法数组,这得益于代码在容器和算法之间的分离。在进行任何数据操作之前,请查看现有算法,如果已经有满足您需求的算法就直接使用它。

最后,我们介绍了Boost中的其他容器,包括最神奇和强大的Boost.MultiIndex。