Before its initial standardization in 1998, C++ had been developed by Bjarne Stroustrup at Bell Labs since 1979, as an extension of the C language, because he wanted an efficient and flexible language similar to C.
In 1983, “C with Classes” was renamed “C++”, adding new features that included virtual functions, function name and operator overloading, references, constants, type-safe free-store memory allocation (new/delete), and improved type checking.
It’s interesting to know the evolution of a language to understand the motivations behind the choices made over the years. For that, let’s discover how C++ algorithms were written from the first uses of the language in the 80s until now; and the best way to do a flashback is to ask Google for some keywords with a custom date range.
Between 1985 and 1990
Let’s explore the C++ code between 1985 and 1990. After customizing the date range we get a few results for the keyword “C++ algorithm”. For example, this link from Dr. Dobb’s Journal, published in 1990. Dr. Dobb’s was a major force promoting the C++ language for many years — special thanks to all the contributors who gave us many interesting resources to master C++. Unfortunately the publication ceased at the end of 2014.
Here's a snippet of the code.
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');
}
}
Let’s compare this code snippet with the “Microsoft Word 1.1” source code released at the same time. Microsoft recently released the “Microsoft Word 1.1″ source code to the Computer History Museum.
These code snippets are very similar, and the implementation of many C++ projects was similar to the C ones. At that time no mature libraries existed to facilitate the implementation of algorithms, and all the needed utilities were developed in-house and from scratch.
Between 1990 and 1995
When searching for source code between these dates, we can see that many implementations are the same as the example cited before. C still dominated algorithm implementations even though a big change was made to the language, which opened new ways to code algorithms. Indeed, in 1989 C++ 2.0 was released, followed by the updated second edition of The C++ Programming Language in 1991. New features in 2.0 included multiple inheritance, abstract classes, static member functions, const member functions, and protected members. In 1990, The Annotated C++ Reference Manual was published. This work became the basis for the future standard. Later feature additions included templates, exceptions, namespaces, new casts, and a boolean type.
Even though templates were introduced in 1991, only a few C++ experts were interested in the generic programming paradigm, and few publications talked about it.
Alexander Stepanov was a pioneering C++ expert who explored the possibilities of generic programming to provide a modern approach to developing C++ projects.
Here’s an interesting document entitled “Algorithm-Oriented Generic Libraries” published in 1993 by Alexander A. Stepanov and David R. Summer.
Here’s the motivation from the document, as explained by the authors:
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.From 1991 to 1994, a revolution driven by a few C++ pioneers to modernize C++ was on its way to giving us an efficient C++ library for coding algorithms: the Standard Template Library.
Between 1995 and 2000
Thanks to the effort and amazing work of Alexander Stepanov, David Musser, Meng Lee and the C++ standardization committee, the first release of the STL came out in 1994.
The Standard Template Library (STL) is a software library for the C++ programming language that influenced many parts of the C++ Standard Library. It provides four components called algorithms, containers, functions, and iterators.
The STL provides a set of common classes for C++, such as containers and associative arrays, that can be used with any built-in type and with any user-defined type that supports some elementary operations (such as copying and assignment). STL algorithms are independent of containers, which significantly reduces the complexity of the library.
From 1995 on, many algorithm implementations began to use the features of the STL library, and many of them look like this one published in 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;
}
}
The STL was a breath of fresh air for C++ developers; it provided many interesting features needed to modernize C++ code, which made C++ algorithm implementations different from the C ones.
Between 2000 and 2010
In 1998 a proposal for a C++ Library Repository Web Site was posted by Beman G. Dawes. The original vision aims to satisfy two major goals:
- A world-wide website containing a repository of free C++ class libraries would be of great benefit to the C++ community. Although other sites supply specific libraries or provide links to libraries, there is currently no well-known website that acts as a general repository for C++ libraries. The vision is this: a site where programmers can find the libraries they need, post libraries they would like to share, and which can act as a focal point to encourage innovative C++ library development. An online peer review process is envisioned to ensure library quality with a minimum of bureaucracy.
- Secondary goals include encouraging effective programming techniques and providing a focal point for C++ programmers to participate in a wider community. Additionally, such a site might foster C++ standards activity by helping to establish existing practice.
Boost is a set of libraries for the C++ programming language that provide support for tasks and structures such as linear algebra, pseudorandom number generation, multithreading, image processing, regular expressions, and unit testing. It contains over eighty individual libraries.
For example, Boost provided the Foreach facility, widely used by many algorithms to iterate over containers.
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;
}And also some common utilities used by algorithms to simplify their implementation, like the join method:
#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 to now
For many years, the facilities to develop efficient algorithms came from libraries like the STL and Boost. Indeed, after the 2.0 update, C++ evolved relatively slowly until 2011; the language stagnated for many years, and many developers were convinced that it would have the same fate as Cobol, Fortran, and VB6. On the contrary, and against all odds, C++ rose from its ashes, and the new standards are significantly changing how the language is used.
Many interesting utilities were added to the Algorithms library, and algorithm implementations now look like this one:
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));
}What's next
From 1991 to 2011 the language evolved slowly, and the evolution came from libraries like the STL and Boost. From 2011 on, many features were added to the standard: C++11, C++14, C++17 and the upcoming C++20. It is now the turn of libraries to provide efficient implementations based on the new standards; Folly is a good example of a modern C++ library. Here’s the motivation behind its creation:
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.Here's a code snippet from the folly library.
Conclusion
C++ is an amazing language with which we can develop many kinds of applications; fortunately, it was supported and promoted by many big companies. Many C++ experts contributed to evolving and maintaining its libraries, and the new standards give us new ways and possibilities to modernize C++ code bases with efficient implementations.
C++ was declared dead many times, but in reality it is reborn again and again. Long live C++!