博客 阅读时间 9 分钟

C++ 算法的演进:一段历史回顾

分享本文
C++ Algorithm Evolution: A Historical Flashback

在 1998 年首次标准化之前,C++ 自 1979 年起就由 Bjarne Stroustrup 在贝尔实验室开发。它是 C 语言的扩展,因为他想要一门像 C 一样高效而灵活的语言。

1983 年,“带类的 C”(C with Classes)更名为“C++”,并加入了新特性,包括虚函数、函数名与运算符重载、引用、常量、类型安全的自由存储内存分配(new/delete),以及改进的类型检查。

了解一门语言的演进历程,有助于我们理解多年来各种选择背后的动机。本着这个思路,让我们来探究从 20 世纪 80 年代语言诞生之初至今,C++ 算法是如何编写的。进行这次历史之旅的一个方法,是使用自定义日期范围在 Google 上搜索相关关键词。

1985 年至 1990 年间

让我们看看 1985 至 1990 年间的 C++ 代码。设置自定义日期范围后,我们找到了一些关键词“C++ algorithm”的结果。例如,这个链接来自 1990 年出版的《Dr. Dobb’s Journal》。Dr. Dobb’s 多年来一直是推广 C++ 语言的中坚力量——特别感谢所有为掌握 C++ 提供了如此多宝贵资源的贡献者。遗憾的是,该刊物于 2014 年底停刊。

下面是其中一段代码。

WriteFraction(n) long n;
{
   unsigned short i, low, digit; unsigned long k;
   putchar(n < 0 ? '-' : ' '); n = abs(n);
   putchar((n>>fractionBits) + '0'); putchar('.');
   low = k = n << (longBits-fractionBits); /* align octal point at left */
   k >>= 4; /* shift to make room for a decimal digit */
   for (i=1; i<=8; ++i)
   {
      digit = (k *= 10L) >> (longBits-4);
      low = (low & 0xf) * 10;
      k += ((unsigned long) (low>>4)) - ((unsigned long) digit <<   (longBits-4));
      putchar(digit+'0');
   }
}

让我们把这段代码片段与大约同一时期发布的“Microsoft Word 1.1”源代码做个比较。微软最近把“Microsoft Word 1.1”的源代码捐赠给了计算机历史博物馆

c1

。这些代码片段非常相似;许多 C++ 项目的实现方式与 C 项目几乎一模一样。当时没有成熟的库来简化算法的实现,所有必需的工具都必须在内部从零开发。

1990 年至 1995 年间

搜索这个时间段内的源代码时,可以看到许多实现都与上面引用的例子相似。C 仍然主导着算法的实现,尽管 C++ 的重大变化已经为编写算法开辟了新的方式。事实上,1989 年 C++ 2.0 发布,随后《C++ 程序设计语言》于 1991 年推出了更新的第二版。2.0 的新特性包括多重继承、抽象类、静态成员函数、const 成员函数和 protected 成员。1990 年,《带注释的 C++ 参考手册》出版。这部著作成为了未来标准的基础。后来加入的特性包括模板、异常、命名空间、新式类型转换和布尔类型。

尽管模板在 1991 年就被引入,但只有少数 C++ 专家对泛型编程范式感兴趣,讨论它的出版物也寥寥无几。

Alexander Stepanov 是一位开拓性的 C++ 专家,他探索了泛型编程的种种可能性,为开发 C++ 项目提供了一种现代化的方法。

这里是一份有趣的文档,题为《面向算法的泛型库》(Algorithm-Oriented Generic Libraries),由 Alexander A. Stepanov 和 David R. Summer 于 1993 年发表。

下面是作者描述的动机:

We outline an approach to construction of software libraries in which generic algorithms (algorithmic abstractions) play a more central role than in conventional software library technology or in the object-oriented programming paradigm. Our approach is to consider algorithms first, decide what types and access operations they need for efficient execution, and regard the types and operations as formal parameters that can be instantiated in many different ways, as long as the actual parameters satisfy the assumptions on which the correctness and efficiency of the algorithms are based. The means by which instantiation is carried out is language dependent; in the C + + examples in this paper, we instantiate generic algorithms by constructing classes that define the needed types and access operations. By use of such compile-time techniques and careful attention to algorithmic issues, it is possible to construct software components of broad utility with no sacrifice of efficiency.

从 1991 年到 1994 年,一场由几位 C++ 先驱引领的运动已经展开,最终为我们带来了一个用于编写算法的高效 C++ 库:标准模板库(STL)。

1995 年至 2000 年间

得益于 Alexander Stepanov、David Musser、Meng Lee 以及 C++ 标准化委员会的努力和杰出工作,STL 的第一个版本于 1994 年问世。

标准模板库(STL)是 C++ 编程语言的一个软件库,它影响了 C++ 标准库的许多部分。它提供四个组件,分别称为算法、容器、函数和迭代器。

STL 为 C++ 提供了一组通用类,比如容器和关联数组,它们可以用于任何内置类型,也可以用于任何支持某些基本操作(如复制和赋值)的用户自定义类型。STL 算法独立于容器,这大大降低了库的复杂度。

从 1995 年起,许多算法实现开始使用 STL 库的特性,其中许多看起来就像这个1997 年发表的例子。

template <class RandomAccessIterator, class T, class Distance>
void __introsort_loop(RandomAccessIterator first,
RandomAccessIterator last, T*,
Distance depth_limit) {
     while (last - first > __stl_threshold) {
        if (depth_limit == 0) {
            partial_sort(first, last, last);
            return;
         }
     --depth_limit;
     RandomAccessIterator cut = __unguarded_partition
     (first, last, T(__median(*first, *(first + (last - first)/2),
     *(last - 1))));
     __introsort_loop(cut, last, value_type(first), depth_limit);
     last = cut;
    }
}

STL 为 C++ 开发者带来了一股清新的空气。它提供了许多让 C++ 代码现代化的实用特性,并让 C++ 算法的实现与 C 语言的实现越来越泾渭分明。

2000 年至 2010 年间

1998 年,一份关于建立 C++ 库仓库网站的提案由 Beman G. Dawes 发布。最初的愿景旨在实现两大目标:

  • 一个包含免费 C++ 类库仓库的全球性网站,将使 C++ 社区受益匪浅。尽管其他网站提供特定的库或库链接,但目前还没有一个知名的网站充当 C++ 库的通用仓库。愿景是这样的:一个让程序员能找到所需库、发布想分享的库的网站,并能充当一个汇聚点,鼓励创新性的 C++ 库开发。设想中还包含一个在线同行评审流程,以最少的官僚程序确保库的质量。
  • 次要目标包括鼓励有效的编程技术,并为 C++ 程序员提供一个参与更广阔社区的汇聚点。此外,这样的网站还可能通过帮助确立既有实践,促进 C++ 的标准化活动。

Boost是 C++ 编程语言的一组库,为线性代数、伪随机数生成、多线程、图像处理、正则表达式和单元测试等任务与数据结构提供支持。它包含八十多个独立的库。

例如,Boost 提供了Foreach设施,被许多算法广泛用于遍历容器。

std::deque<int> deque_int( /*...*/ );
int i = 0;
BOOST_FOREACH( i, deque_int )
{
    if( i == 0 ) return;
    if( i == 1 ) continue;
    if( i == 2 ) break;
}

Boost 还提供了简化算法实现的常用工具,比如 join 函数:

#include <boost/algorithm/string/join.hpp>
#include <vector>
#include <iostream>

int main()
{
    std::vector<std::string> list;
    list.push_back("Hello");
    list.push_back("World!");

    std::string joined = boost::algorithm::join(list, ", ");
    std::cout << joined << std::endl;
}

2010 年至今

多年来,开发高效算法的设施来自 STL 和 Boost 这样的库。事实上,在 2.0 更新之后,直到 2011 年,C++ 的演进相对缓慢;这门语言停滞了许多年,许多开发者都深信它会落得与 Cobol、Fortran 和 VB6 同样的命运。然而,出乎意料地,C++ 浴火重生,新标准正在显著改变这门语言的使用方式。

许多实用的工具被加入算法库,算法实现如今看起来是这样的:

template<class FwdIt, class Compare = std::less<>>
void quick_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    auto const N = std::distance(first, last);
    if (N <= 1) return;
    auto const pivot = *std::next(first, N / 2);
    auto const middle1 = std::partition(first, last, [=](auto const& elem){ 
        return cmp(elem, pivot); 
    });
    auto const middle2 = std::partition(middle1, last, [=](auto const& elem){ 
        return !cmp(pivot, elem);
    });
    quick_sort(first, middle1, cmp); // assert(std::is_sorted(first, middle1, cmp));
    quick_sort(middle2, last, cmp);  // assert(std::is_sorted(middle2, last, cmp));
}

接下来会怎样

从 1991 年到 2011 年,这门语言演进缓慢,演进的动力来自 STL 和 Boost 这样的库。从 2011 年起,许多特性被加入标准:C++11、C++14、C++17 以及即将到来的 C++20。现在轮到各个库基于新标准提供高效的实现了;Folly 就是现代 C++ 库的一个好例子。下面是它诞生的动机:

Folly (acronymed loosely after Facebook Open Source Library) is a library of C++11 components designed with practicality and efficiency in mind. It complements (as opposed to competing against) offerings such as Boost and of course std. In fact, we embark on defining our own component only when something we need is either not available, or does not meet the needed performance profile.

下面是 folly 库的一段代码。

c0

结语

C++ 是一门神奇的语言,我们可以用它开发各种各样的应用程序;幸运的是,它得到了许多大公司的支持和推广。许多 C++ 专家为其库的演进和维护做出了贡献,而新标准为用高效实现来现代化 C++ 代码库提供了新的方式和可能。

C++ 曾被多次宣告死亡,但实际上它一次次地浴火重生。C++ 万岁!

#algorithm-evolution#c++#cpp#programming
分享本文