![](\"http:\/\/www.cppdepend.com\/img\/google.png\")
<\/p>\nBefore the initial standardization in 1998, C++ was developed by\u00a0Bjarne Stroustrup\u00a0at\u00a0Bell Labs\u00a0since 1979, as an extension of the\u00a0C language\u00a0as he wanted an efficient and flexible language similar to C<\/p>\n
In 1983, “C with Classes” was renamed to “C++” , adding new features that included\u00a0virtual functions, function name and\u00a0operator overloading, references, constants, type-safe free-store memory allocation (new\/delete), improved type checking.<\/p>\n
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\u00a0 were written from the first use of the language\u00a0the 80s until now and the best way to do a flashback is to ask google for some keywords by specifying a custom\u00a0 date range.<\/p>\n
<\/p>\n
Between 1985 and 1990<\/strong><\/p>\n Let’s explore the C++ code between 1985 and 1990.\u00a0 After customizing the dates range we have a few results for the keyword “C++ algorithm”. For example we have this link\u00a0<\/a>\u00a0from\u00a0 Dr Dobbs journal published in 1990.\u00a0 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\u00a0the publication ceased at the end of 2014.<\/p>\n Here’s a snippet of the code.<\/p>\n Let’s compare this code\u00a0snippet with “Microsoft Word 1.1” source code\u00a0released in the same time.\u00a0Microsoft released recently the \u201cMicrosoft Word 1.1\u2033 source code \u00a0in the \u00a0Computer History Museum.<\/a><\/p>\n These code snippets are very similar and the implementation of many C++ projects\u00a0 are similar to the C ones.\u00a0 At this time no mature libraries existed to facilitate the algorithms implementation and all the needed utilities were developed in house and from scratch.<\/p>\n Between\u00a090 and 95<\/strong><\/p>\n When searching some source code between these dates, we can remark that many implementations are the same as the example cited before. C\u00a0 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,\u00a0In 1989, C++ 2.0 was released, followed by the updated second edition of\u00a0The C++ Programming Language<\/i>\u00a0in 1991.New features in 2.0 included multiple inheritance, abstract classes, static member functions,\u00a0const member functions, and protected members. In 1990,\u00a0The Annotated C++ Reference Manual<\/i>\u00a0was published. This work became the basis for the future standard. Later feature additions included\u00a0templates<\/strong>,\u00a0exceptions,\u00a0namespaces, new\u00a0casts, and a\u00a0boolean type.<\/p>\n 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.<\/p>\n Alexandre Stephanov was\u00a0a pioneer C++ expert who try to explore the generic programming possibilities to provide a modern approach to develop the\u00a0 C++ projects.<\/p>\n Here’s an interesting document<\/a>\u00a0entitled “Algorithm-Oriented Generic Libraries” published in 1993 by Alexandre A Stepanov and David R Summer.<\/p>\n Here’s the motivation from the document as explained by the authors:<\/p>\n 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 S<\/strong>tandard T<\/strong>emplate L<\/strong>ibrary.<\/p>\n Between 95 and 2000<\/strong><\/p>\n The effort and amazing work of Alexandre Stephanove , David Musser,\u00a0Meng Lee and the\u00a0C++ standardization committee, a first release version of STL was released in 1994.<\/p>\n The\u00a0Standard Template Library<\/b>\u00a0(STL<\/b>) is a\u00a0software library\u00a0for the\u00a0C++\u00a0programming language that influenced many parts of the\u00a0C++ Standard Library. It provides four components called\u00a0algorithms<\/i>,\u00a0containers<\/i>,\u00a0functions<\/i>, and\u00a0iterators<\/i>.<\/p>\n The STL provides a set of common\u00a0classes\u00a0for C++, such as containers and\u00a0associative 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.<\/p>\n From 1995 many algorithms implementations begin to use the features of the STL library, and many algorithms implementations looks like\u00a0this one published in 1997<\/a> .<\/p>\n The STL was\u00a0a 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 \u00a0different to the C\u00a0 implementations ones.<\/p>\n Between 2000 and 2010<\/strong><\/p>\n In 1998 a\u00a0proposal for \u00a0a C++ Library Repository Web Site<\/a>\u00a0was posted by\u00a0Beman G. Dawes. The original vision aims to satisfy two major goals:<\/p>\n Boost<\/b>\u00a0is a set of\u00a0libraries\u00a0for the\u00a0C++\u00a0programming language that provide support for tasks and structures such as\u00a0linear algebra,\u00a0pseudorandom number generation, multithreading,\u00a0image processing,\u00a0regular expressions, and\u00a0unit testing. It contains over eighty individual libraries.<\/p>\nWriteFraction(n) long n;\r\n{\r\n unsigned short i, low, digit; unsigned long k;\r\n putchar(n < 0 ? '-' : ' '); n = abs(n);\r\n putchar((n>>fractionBits) + '0'); putchar('.');\r\n low = k = n << (longBits-fractionBits); \/* align octal point at left *\/\r\n k >>= 4; \/* shift to make room for a decimal digit *\/\r\n for (i=1; i<=8; ++i)\r\n {\r\n digit = (k *= 10L) >> (longBits-4);\r\n low = (low & 0xf) * 10;\r\n k += ((unsigned long) (low>>4)) - ((unsigned long) digit << (longBits-4));\r\n putchar(digit+'0');\r\n }\r\n}\r\n<\/pre>\n![\"c1\"](\"http:\/\/www.javadepend.com\/Blog\/wp-content\/uploads\/c11.png\")
<\/p>\nWe 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.<\/pre>\n
template <class RandomAccessIterator, class T, class Distance>\r\nvoid __introsort_loop(RandomAccessIterator first,\r\nRandomAccessIterator last, T*,\r\nDistance depth_limit) {\r\n while (last - first > __stl_threshold) {\r\n if (depth_limit == 0) {\r\n partial_sort(first, last, last);\r\n return;\r\n }\r\n --depth_limit;\r\n RandomAccessIterator cut = __unguarded_partition\r\n (first, last, T(__median(*first, *(first + (last - first)\/2),\r\n *(last - 1))));\r\n __introsort_loop(cut, last, value_type(first), depth_limit);\r\n last = cut;\r\n }\r\n}\r\n<\/pre>\n\n