Before the initial standardization in 1998, C++ was developed by Bjarne Stroustrup at Bell Labs since 1979, as an extension of the C language as he wanted an efficient and flexible language similar to C
In 1983, “C with Classes” was renamed to “C++” , adding new features that included virtual functions, function name and operator overloading, references, constants, type-safe free-store memory allocation (new/delete), improved type checking.
It’s interesting to know the evolution of a language to understand the motivations behind the choices made over years. For that let’s discover how the C++ algorithms were written from the first use of the language the 80s until now and the best way to do a flashback is to ask google for some keywords by specifying a custom date range.
Between 1985 and 1990
Let’s explore the C++ code between 1985 and 1990. After customizing the dates range we have a few results for the keyword “C++ algorithm”. For example we have this link from Dr Dobbs journal published in 1990. Dr Dobbs was a major actor promoting the C++ language for many years, special thanks to all the contributors who give 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 “Microsoft Word 1.1” source code released in the same time. Microsoft released recently the “Microsoft Word 1.1″ source code in the Computer History Museum.
These code snippets are very similar and the implementation of many C++ projects are similar to the C ones. At this time no mature libraries existed to facilitate the algorithms implementation and all the needed utilities were developed in house and from scratch.
Between 90 and 95
When searching some source code between these dates, we can remark that many implementations are the same as the example cited before. C still dominate the algorithms implementations even if a big change was down to the language which opened a new ways to code the 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 if the templates were introduced in 1991 only few C++ experts are interested at the generic programming paradigm and few publications talked about it.
Alexandre Stephanov was a pioneer C++ expert who try to explore the generic programming possibilities to provide a modern approach to develop the C++ projects.
Here’s an interesting document entitled “Algorithm-Oriented Generic Libraries” published in 1993 by Alexandre 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 the 1991 to 1994 a revolution driven by a few C++ pioneers to modernize the C++ is in its way to give us an efficient C++ library to code the algorithms. It’s The Standard Template Library.
Between 95 and 2000
The effort and amazing work of Alexandre Stephanove , David Musser, Meng Lee and the C++ standardization committee, a first release version of STL was released 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 many algorithms implementations begin to use the features of the STL library, and many algorithms implementations looks 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 to the C++ developers, it provided many interesting features needed to modernize the C++ code which makes the C++ algorithms implementations different to the C implementations 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 overused by many algorithms to iterate over the 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 the algoritms to simplify their implementations 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 comes from the libraries like STL and Bosst. Indeed, After the 2.0 update, C++ evolved relatively slowly until, in 2011 and C++ has been stagnated for many years, and many developers were confident that the language would have the same destiny as Cobol, Fortran, and VB6. On the contrary and against all odds, C++ is reborned from its ashes and the new standards are importantly changing how the language is used.
Many interesting utilities were added to the Algorithms library. And the algorithms implementations looks 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 comes from the libraries like STL and Boost. From 2011 many features were added to the standard, we can enumerate C++11, C++14, C++17 and the coming C++20. it is now the turn of the libraries to provides efficient implementations based on the new standards, Folly is a good example of the modern C++ libraries. 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 kind of applications, fortunately it was supported and promoted by many big companies. Many C++ experts contributed to evolve and maintain its libraries and the new standards give us new ways and possibilities to modernize the C++ code base to have efficient implementations.
C++ was declared dead many times but in the reality it reborn again and again. Finally we hope a Long live to C++.
