Home » Blog » 2014 » December

December 2014

How to implement classic sorting algorithms in modern C++? -- TemplateRex

By Blog Staff | Dec 31, 2014 12:13 PM | Tags: None

Back in the summer we had this SO question:

How to implement classic sorting algorithms in modern C++?

by TemplateRex

From the article:

How to implement classic sorting algorithms in modern C++?

The std::sort algorithm (and its cousins std::partial_sort and std::nth_element) from the C++ Standard Library is in most implementations a complicated and hybrid amalgation of more elementary sorting algorithms, such as selection sort, instertion sort, quick sort, merge sort, or heap sort.

There are many questions here and on sister sites such as http://codereview.stackexchange.com/ related to bugs, complexity and other aspects of implementations of these classic sorting algorithms. Most of the offered implementations consist of raw loops, use index manipulation and concrete types, and are generally non-trivial to analyze in terms of correctness and efficiency.

Question: how can the above mentioned classic sorting algorithms be implemented using modern C++?

  • no raw loops, but combining the Standard Library’s algorithmic building blocks from <algorithm>
  • iterator interface and use of templates instead of index manipulation and concrete types
  • C++14 style, including the full Standard Library, as well as syntactic noise reducers such as auto, template aliases, transparant comparators and polymorphic lambdas

...

Testing

Here are four Live Examples (C++14, C++11, C++98 and Boost, C++98) testing all five algorithms on a variety of inputs (not meant to be exhaustive or rigorous). Just note the huge differences in the LOC: C++11/C++14 need around 120 LOC, C++98 and Boost 180 (+50%) and C++98 more than +100% (note that heap sort could not even be done in terms of standard algorithms).

 

EDG C++ front end 4.10 released, adds more C++14 support

By Blog Staff | Dec 30, 2014 01:35 PM | Tags: None

Announced today, just in time for the new year:

EDG C++ front end 4.10 released

Version 4.10 of the EDG C++ Front End has been released.

This version provides the following new features:

1) This version provides the following new C++14 features:

Lambdas can specify expressions, not just local variables, to be captured. For example:

       auto l = [x = 42]{ return x + 1; };

Generic lambdas are accepted, allowing auto parameters to define a call operator template.  For example:

        auto l = [](auto p) { return p*2; };

Binary literals and apostrophes as digit separators in numeric literals are accepted.

        int i = 0b0110;
        long l = 123'456'789; // Equivalent to 123456789

2) __cpluplus in C++14 modes:

The standard for C++14 has now been approved and specifies the value of the __cplusplus predefined macro as 201402L.  The front end uses that value when --c++14 mode is specified, except that in Microsoft and GNU    modes it adopts the value set by those compilers.  See the Changes file for more details.

3) GNU statement expressions with class type results:

Version 4.9 of the front end enabled the ability to have destructible entities in GNU statement expressions (GSEs), but with the restriction that the result expression of a GSE cannot be of a class type requiring nontrivial copy construction or nontrivial destruction.  This restriction has been removed.  For example:

     struct D { D(D const&); };
     D g(D d) {
       return ({ d; });  // Now accepted.
    }

4) Performance improvements:

As part of what will be an ongoing effort, a number of changes were made to improve the overall speed of the front end.  This has generally resulted in an improvement between 1 and 6 percent in our testing, but can be significantly more for some IA-64 mangling cases.

As usual, we have fixed bugs, added many minor features, and continued to improve our various compatibility modes.

C++ Now talk submission deadline extended to January 11

By Blog Staff | Dec 30, 2014 10:54 AM | Tags: None

Just a reminder: In case you missed the original December 21 deadline for C++ Now proposal submissions, you still have time... the deadline has been extended to January 11.

(revised) 2015 Call for Submissions

Submission Deadline Extended!

The C++Now Program Committee is very excited about the quality this year’s submissions, but to increase the quantity of submissions, we are announcing an extension of the submission deadline until January 11th. We still hope to meet our February deadline for notifications.

Quick Q: Can recompiling C++98 code as modern C++ get you performance for free? -- StackOverflow

By Blog Staff | Dec 30, 2014 10:42 AM | Tags: None

Quick A: Yup.

Just before Christmas on StackOverflow:

Can modern C++ get you performance for free?

It is sometimes claimed that C++11/14 can get you a performance boost even when merely compiling C++98 code. The justification is usually along the lines of move semantics, as in some cases the rvalue constructors are automatically generated or now part of the STL. Now I'm wondering whether these cases were previously actually already handled by RVO or similar compiler optimizations.

My question then is if you could give me an actual example of a piece of C++98 code that, without modification, runs faster using a compiler supporting the new language features. I do understand that a standard conforming compiler is not required to do the copy elision and just by that reason move semantics might bring about speed, but I'd like to see a less pathological case, if you will.

EDIT: Just to be clear, I am not asking whether new compilers are faster than old compilers, but rather if there is code whereby adding -std=c++14 to my compiler flags it would run faster (avoid copies, but if you can come up with anything else besides move semantics, I'd be interested, too)

Two fundamental implementations for one conceptual task

By Mark | Dec 30, 2014 09:18 AM | Tags: intermediate

From the Modern Maintainable Code blog:

Two fundamental implementations for one conceptual task

by Mark Isaacson

Summary:

This is the second article of a series on code reuse. This article provides a discussion of how to approach the problem of having multiple implementations of a single idea and how to programmatically select between them based on patterns in the type information of the parameters.

Out in the real world, functions like use the same techniques discussed to leverage std::memcpy internally when it's safe to do so.

<span 1;"="">You can find the previous article of the series here, and the prelude to the next, which looks at solving the same problem for structs instead of functions, here.

Five Popular Myths about C++ -- Bjarne Stroustrup

By Blog Staff | Dec 29, 2014 11:39 AM | Tags: None

Earlier this month, Bjarne Stroustrup posted his new "Five Popular Myths about C++" paper here on isocpp.org in three parts: part 1, part 2, and part 3.

He has now posted the complete paper on his publications page, including typo fixes and some additional comments at the end.

Five Popular Myths about C++

by Bjarne Stroustrup

From the article:

Here, I will explore, and debunk, five popular myths about C++:

  1. “To understand C++, you must first learn C”
  2. “C++ is an Object-Oriented Language”
  3. “For reliable software, you need Garbage Collection”
  4. “For efficiency, you must write low-level code”
  5. “C++ is for large, complicated, programs only”

If you believe in any of these myths, or have colleagues who perpetuate them, this short article is for you...

...

Postscript

The 10 sections of this article was posted on isocpp.org in three installments and reposted widely. It attracted a quite varied set of comments. I have now fixed a few typos that were reported. Thanks.

This postscript is my observations on some of the comments posted.

The comments prove – yet again – that the “Myths” paper was needed. People keep repeating the old hairy rationalizations. Unfortunately, many programmers don’t read long papers and dismiss short ones for being incomplete. The unwillingness of many programmers to read a long paper was the reason I released this paper in three separate parts.

This paper is not a research paper carefully outlining every alternative and carefully documenting every detail. I said that right up front:

Each myth requires a long paper or even a book to completely debunk, but my aim here is simply to raise the issues and to briefly state my reasons.

However, many seems to confuse the examples used to illustrate a point with the point itself. Many tried to “debunk the debunking” by changing examples, by changing the constraints on the examples, or by deeming the examples trivial. The examples are small – they have to be to fit into a short paper – but they are not unrepresentative of code found as part of real-world programs.

Many commenters quickly did a shift from the C++11/C++14 that I base my arguments on to some older version. C++14 is not the C++ of the 1980s. It is not what most people were first taught. It is not the C++ that people is presented with in most beginning C++ courses today. It is not what most people see when they look at a large code base. I want to change that. Not being able to do some example that I present in an antique version of C++ or with an outdated compiler is unfortunate, but better versions of the major compiler ship (typically for free) today. I showed no examples of “bleeding edge” code.

The problem of code in older styles is one that every successful programming language must face, so please don’t judge C++ exclusively based on 20-year-old techniques and 10-year old compilers. Look at modern C++ and find ways of getting it into use – many has already. You almost certainly used a program today that was written using C++11. There are C++11 in many steps of the chain between the computer on which I write this and the computer on which you read it.

Quite a few comments were along the lines of “Language X has a feature that does exactly that” and “Library Y in language X does exactly that.” Obviously, if you have a language that provides a simpler solution to the best you can do in C++, with acceptable performance, portability, and tool-chain constraints for what you want to do, use it. However, no language and library is perfect for everything and everybody.

I present examples of general problems and general techniques. Matching a single example in some way is not necessarily significant. My points are general and the examples only simple illustrations. Given a sufficiently good library, just about any programming task can be simple and pleasant. Given a sufficiently constrained task, we can always design a specialized language to be more elegant than a general-purpose one. For example, the asio library I used in §6.1 is a flexible, efficient, general-purpose networking library. For any one task, I could wrap it in a far simpler function (or small set of functions) to make that task significantly more convenient. The code I showed would then be the implementation. My key point in §6.2 is that the C++ library development community could do many programmers a favor by spending a little more tome making simple things simple. For example 99% of the time I prefer sort(v) to sort(v.begin(),v.end()).

Performance

My comments about performance caused quite a stir in places. Many people tried to dismiss them with arguments or mere counter-assertions. I don’t accept performance arguments unsupported by measurements. My comments have been validated by real performance measures in many contexts over years. Many can be found in the literature. My main performance points hold over a wide range of similar examples and scale.

Please note that I assume a modern, standards-conforming C++ implementation. For example, when I talk about the performance of the short-string optimization, I don’t mean a pre-C++11 standard library without that optimization. Also, I take no notice of comments to the effect that C++ facilities such as std::sort() or std::string are slow if you don’t use an optimizer – of course they are, but talking about performance of unoptimized code is silly. If you use GCC or Clang use –O2; for Microsoft, use release mode.

C

I know C and its standard library pretty well. I wrote considerable amounts of C before many of today’s students were even born and contributed significantly to the C language: function prototypes, const, inline, declarations in for-statement, declarations as statements, and more came from my work. I have followed its development and the evolution programming styles in C.

Yes, the C versions of compose() fails to check malloc()’s return value. I did ask if you thought I got it right. I did not present production-quality code, and I knew that. Failing to check results is a major source of errors, so my “mistake” failing to check the result of malloc() was deliberate illustrates a real problem. As in this case, exceptions can often help.

Yes, you could write the C version of compose() differently using less well known standard-library functions, and yes, you can avoid the use of free store if you let the caller supply a buffer allocated on the stack and let the caller deal with the problem of string arguments that would overflow the buffer. However, such alternatives completely miss the point: it is harder to write such code than the C++ version, and far harder to get it right. Novices get the C++ version right the first time, but not any of the C versions, especially not the C versions that rely on standard-library function not commonly taught to novices.

C++ use

C++ has been used for demanding embedded systems and critical systems for years, examples are The Mars Rovers (scene analysis and autonomous operations), The F-35s and F-16s (flight controls), and many, many more: http://www.stroustrup.com/applications.html. And, yes, the Orion space capsule is programmed in C++.

Libraries

Yes, libraries vary in quality and it can be extremely hard to choose from the large selection of libraries beyond the standard. This is a major problem. However, such libraries exist and researching them is often more productive than simply barging ahead and reinventing yet-another wheel.

Unfortunately, C++ Libraries are often not designed for interoperability with other libraries.

Unfortunately, there is not a single place to go to look for C++ Libraries.

Teaching

I have observed students being taught by the “C first” approach for many years and seen the programs written by such students for decades. I have taught C++ as the first programming language to thousands of students over several years. My claims about the teachability of C++ are based on significant experience, rather than introspection.

C++ is easier to teach to beginners than C because of a better type system and more notational support. There are also fewer tricks and workarounds to learn. Just imagine how you would teach the styles of programming you use in C using C++; C++’s support for those is better.

I would never dream of giving a beginner’s C++ course that

  • didn’t include a thorough grounding in memory management, pointers, etc.
  • didn’t give the students a look at “plain C”’ and some idea of how to use it
  • didn’t present a rationale for the major features
  • tried to teach all of C++ and every C++ technique

Similarly, good C teachers do not try to teach all of C and all C techniques to beginners.

http://www.stroustrup.com/programming.html is my answer to the question “How would you teach C++ to beginners?” It works.

For a rather old paper comparing aspects of teachability of C and C++, see B. Stroustrup: Learning Standard C++ as a New Language. C/C++ Users Journal. pp 43-54. May 1999 (www.stroustrup.com/papers.html). Today, I could write the C version a bit better and the C++ version quite a bit better. The examples reflect common styles of the time (and were reviewed by expert C and C++ programmers).

C++ today is ISO Standard C++14, rather than what I described 30 years ago or what your teacher may have taught you 20 years ago. Learn C++11/C++14 as supported by current mainstream compilers and get used to it. It is a far better tool than earlier versions of C++. Similarly, C today is ISO Standard C11, rather than K&R C (though I am not sure if the C compilers today are as close to C11 as the C++ compilers are close to C++14).

I am appalled by much that is taught as “good C++.”

C++ is not (and never were meant to be) an “OOP” language. It is a language that supports OOP, other programming techniques, and combinations of such techniques.

If you are an experienced programmer, I recommend A Tour of C++ [12] as a quick overview of modern C++.

A Corollary on Overloading -- Mark Isaacson

By Mark | Dec 24, 2014 08:38 AM | Tags: intermediate

From the Modern Maintainable Code Blog:

A corollary on overloading

by Mark Isaacson

Summary from the article:

1) You can extend or adapt other people's code with overloading.

2) It's easy to accidentally eliminate overloads from overload resolution (the set of overloads the compiler considers when calling a function), especially when doing the above. We'll discuss a simple technique to ensure that you don't leave your users in an unfortunate position by accidentally being too specific.

We'll also discuss a few other things along the way, like one reason why non-member functions are more flexible than member functions. We'll highlight why the modern C++11 guideline: 'prefer using the non-member std::begin, std::end, and std::swap functions' exists and why things like non-member std::size are in our near future.

C++ Portable Components Release 1.6.0

By Alex Fabijanic | Dec 24, 2014 08:36 AM | Tags: None

POCO 1.6.0 is now available:

POCO Release 1.6.0 is out

by POCO Team

This release is the culmination of the work done on GitHub over the last two years, including five development releases. It includes major new features from new contributors, like the JSON and MongoDB libraries, much improved Data library, CMake support, as well as numerous other new features and fixes. A big Thank You to everyone who contributed to this release.