1998年の初めての標準化以前、C++は1979年からBell LabsでBjarne Stroustrupによって、C言語の拡張として開発されていました。彼はCに似た、効率的で柔軟な言語を求めていたからです。
1983年、「C with Classes」は「C++」へと改名され、仮想関数、関数名と演算子のオーバーロード、参照、定数、型安全なフリーストアメモリ割り当て（new/delete）、改善された型チェックなどの新機能が追加されました。
言語がどのように進化してきたかを理解することは、長年にわたって行われてきた選択の背景にある動機を理解するのに役立ちます。その観点から、1980年代の黎明期から現在まで、C++のアルゴリズムがどのように書かれてきたかを見ていきましょう。この歴史的な旅をする1つの方法は、カスタム日付範囲を使って関連キーワードを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は最近、「Microsoft Word 1.1」のソースコードを公開しました。公開先は コンピュータ歴史博物館
です。これらのコードスニペットは非常に似ており、多くのC++プロジェクトはCプロジェクトとほぼ同じ方法で実装されていました。当時、アルゴリズムの実装を容易にする成熟したライブラリは存在せず、必要なユーティリティはすべて社内でゼロから開発しなければなりませんでした。
1990年から1995年
これらの日付の間のソースコードを検索すると、多くの実装が上記の例と似ていることが分かります。C++への大きな変更がアルゴリズムを書く新しい方法を切り開いていたにもかかわらず、アルゴリズム実装ではCが依然として支配的でした。実際、1989年にC++ 2.0がリリースされ、続いて1991年に The C++ Programming Language の改訂第2版が出版されました。2.0の新機能には、多重継承、抽象クラス、静的メンバー関数、constメンバー関数、protectedメンバーが含まれていました。1990年には、 The Annotated C++ Reference Manual が出版されました。この著作は将来の標準の基礎となりました。その後の機能追加には、 テンプレート、例外、名前空間、新しいキャスト、ブール型が含まれていました。
テンプレートは1991年に導入されましたが、ジェネリックプログラミングパラダイムに関心を持っていたC++エキスパートはごく少数で、それについて論じる出版物もほとんどありませんでした。
Alexander Stepanovは、ジェネリックプログラミングの可能性を探求し、C++プロジェクト開発への現代的なアプローチを提供した先駆的なC++エキスパートです。
こちらは興味深い ドキュメント で、1993年にAlexander A. StepanovとDavid R. Summerによって発表された「Algorithm-Oriented Generic Libraries」と題されています。
著者らが説明する動機は次のとおりです：
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++ライブラリが生まれました： Standard Template Library。
1995年から2000年
Alexander Stepanov、David Musser、Meng Lee、そしてC++標準化委員会の努力と卓越した仕事のおかげで、1994年にSTLの最初のリリースが公開されました。
The Standard Template Library （STL）は、C++プログラミング言語向けのソフトウェアライブラリであり、C++標準ライブラリの多くの部分に影響を与えました。これは、次の4つのコンポーネントを提供します： アルゴリズム、 コンテナ、 関数、および イテレータ。
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年に、Beman G. Dawesによって C++ライブラリリポジトリWebサイトの提案 が投稿されました。当初のビジョンには、2つの主要な目標がありました：
- 無料のC++クラスライブラリのリポジトリを含む世界的なWebサイトは、C++コミュニティに大きな利益をもたらすでしょう。他のサイトは特定のライブラリを提供したり、ライブラリへのリンクを提供したりしていますが、現在、C++ライブラリの一般的なリポジトリとして機能する有名なWebサイトはありません。そのビジョンとは、プログラマーが必要なライブラリを見つけ、共有したいライブラリを投稿でき、革新的なC++ライブラリ開発を促す中心的な場として機能するサイトです。最小限の官僚主義でライブラリの品質を確保するため、オンラインのピアレビュープロセスが構想されています。
- 副次的な目標には、効果的なプログラミング技術を奨励すること、そしてC++プログラマーがより広いコミュニティに参加するための中心地点を提供することが含まれます。さらに、そのようなサイトは、既存の実践の確立を助けることで、C++標準化活動を促進する可能性があります。
Boost は、線形代数、疑似乱数生成、マルチスレッド、画像処理、正規表現、ユニットテストなどのタスクやデータ構造をサポートする、C++プログラミング言語向けのライブラリ集です。80を超える個別のライブラリが含まれています。
たとえば、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へのアップデート後、C++は2011年まで比較的ゆっくりと進化しました。言語は長年停滞し、多くの開発者は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ライブラリのコードスニペットです。
結論
C++は、多くの種類のアプリケーションを開発できる驚くべき言語です。幸いなことに、多くの大手企業によってサポート・推進されてきました。多くのC++エキスパートがライブラリの進化と保守に貢献し、新しい標準は、効率的な実装でC++コードベースをモダナイズするための新しい方法と可能性をもたらしています。
C++は何度も死んだと宣言されてきましたが、実際には何度もよみがえっています。C++万歳！