C++ 标准库与凡人制作的代码 + 我在哪里可以找到源代码？

Question

两个，也许是微不足道的问题:

1.为什么我打不过STD功能？

真的。我在过去三天里实现了一些比 std::sort 更快的东西，只是为了这样做。它应该是一个 introsort，我怀疑它在内部使用了单枢轴版本的快速排序。史诗般的失败。我的至少慢了一倍。

在我极度的痛苦中，我什至复制粘贴了其他一流的程序员代码。徒劳无功。我也对我的其他算法进行了基准测试……我的二进制搜索和 upper_bound、lower_bound 版本被精简到不能用更少的指令真正实现。不过，它们的速度大约是原来的两倍。

我问，为什么，为什么，为什么？这引出了我的下一个问题......

2。在哪里可以找到STL库函数的源代码？

当然，我想看看他们的来源!是否有可能编写比这些代码更高效的代码，或者我是否处于抽象级别，我的“简单”main.cpp 无法达到 STL 库使用的优化？

我的意思是，例如...让我们以 map ...为例，它们是简单的关联容器。文档说它是用红黑树实现的。现在...是否值得尝试实现我自己的红黑树，或者他们带走了我的快乐:-)，我应该把我得到的所有数据都扔到 map 容器中？

我希望这是有道理的。如果不是，请见谅。

---

Answer 1

简短的回答是“如果可以编写更快的代码来做同样的事情，那么标准库早就可以做到了”。

标准库是由聪明人设计的，它成为 C++ 一部分的原因是其他聪明人认为它很聪明。从那时起，15 年过去了，其他聪明人试图采用这些规范并编写绝对最有效的代码来实现它们。

您要与之竞争的是很多聪明才智。 ;)

所以 STL 中没有魔法，他们不会作弊，也不会使用您无法使用的技巧。它经过精心设计以最大限度地提高性能。

C++ 本身并不是一种快速的语言。如果您不小心，很容易引入各种低效问题:虚函数调用、缓存未命中、过多的内存分配、不必要的对象复制，如果您不小心，所有这些都会削弱 C++ 代码的性能。

只要小心，您就可以编写与 STL 一样高效的代码。这不是特别的。但总的来说，要获得更快 代码的唯一方法是更改​​需求。标准库必须是通用的，以便在所有 用例中尽可能良好地工作。如果您的要求更具体，有时可以编写有利于这些特定情况的专门代码。但随后的权衡是，在其他情况下，代码要么不起作用，要么效率低下。

最后一点是，STL 之所以如此聪明并被纳入标准的一个关键部分是它几乎是零开销。许多语言的标准库“足够快”，但不如手写代码快。他们有一个排序算法，但速度不如您自己就地编写。它可能使用一些与公共(public)“对象”基类之间的转换，或者可能对值类型使用装箱。 STL 的设计使得几乎所有内容都可以由编译器内联，生成的代码相当于您自己手动编写的代码。它使用模板专门针对您正在使用的类型，因此没有转换为容器或算法可以理解的类型的开销。

这就是它难以与之竞争的原因。这是一个非常高效的图书馆，它必须如此。按照普通 C 或 C++ 程序员的心态，尤其是 10-15 年前，没有人会使用 std::vector 如果它比原始数组。没有人会使用迭代器和标准算法，如果它们不如自己编写循环那么快的话。

因此，STL 开创了许多聪明的 C++ 技巧，以便变得与手工编写的 C 代码一样高效。