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.
Understanding how a language has evolved helps us understand the motivations behind the choices made over the years. With that in mind, let’s explore how C++ algorithms have been written from the language’s early days in the 1980s to the present. One way to take this historical journey is to search Google for relevant keywords using custom date ranges.
Between 1985 and 1990
Let’s explore the C++ code between 1985 and 1990. After setting a custom 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 provided so many valuable resources for mastering 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 around 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 many C++ projects were implemented in much the same way as C projects. At that time, no mature libraries existed to facilitate the implementation of algorithms, and all the necessary utilities had to be developed in-house from scratch.
Between 1990 and 1995
When searching for source code between these dates, we can see that many implementations are similar to the example cited above. C still dominated algorithm implementations, even though major changes to C++ had opened up new ways to write 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 small number of C++ experts were interested in the generic programming paradigm, and few publications discussed 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 is the motivation described 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 movement led by a few C++ pioneers was already underway, ultimately giving us an efficient C++ library for coding algorithms: the Standard Template Library.
Between 1995 and 2000
Thanks to the efforts and remarkable 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 useful features for modernizing C++ code and made C++ algorithm implementations increasingly distinct from their C counterparts.
Between 2000 and 2010
In 1998 a proposal for a C++ Library Repository Web Site was posted by Beman G. Dawes. The original vision aimed to achieve 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 data 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;
}Boost also provided common utilities that simplified algorithm implementations, such as the join function:
#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 the present
For many years, the facilities for developing 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 the 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++!