Category Archives: C++

C++17 News

Herb Sutter blogged about the Oulo ISO C++ meeting. There’s a link to an interview he did for the excellent CppCast podcast and also to a reddit post on features approved at the meeting.
CppCast

As Herb called out in the interview, I think the following two features will be widely used:
Structured Bindings
This is interesting because I’ve been using the std::tie syntax for a while, despite the clumsiness when you need to introduce new variables to take the return types (leaving them uninitialised until assignment). The proposal above avoids that problem.

tuple<T1,T2,T3> f(/*...*/) { /*...*/ return {a,b,c}; }

// BEFORE
T1 x;
T2 y;
T3 z;
std::tie( x, y, z ) = f();

// AFTER
auto [x,y,z] = f(); // x has type T1, y has type T2, z has type T3

Initialisation clause for if and switch
This proposal makes if/switch more consistent with for loops that allow separate initialisation/increment clauses as well as a condition. So now you can initialise a variable separately from the if condition, which also allows you to limit the scope of that variable.

// BEFORE
status_code c = bar();     
if (c != SUCCESS) 
{       
    return c;     
}

// AFTER
if (status_code c = bar(); c != SUCCESS) 
{     
  return c;   
}

Leave a comment

Filed under C++, Programming

How to initialise data concisely in C++

In the past, creating a collection of dates was a chore, because you had to individually insert them into a container (e.g. declaring a vector on one line and then pushing dates into it on subsequent lines). With features like std::initializer_list from C++11 onwards, it’s now much easier to do this concisely.

Here’s some simple, concise code to create dates without all the hassle:

struct Date
{
    std::string Event;

    int Year;
    int Month;
    int Day;
};

void print( const Date& date )
{
    std::cout << date.Event << ": "<< date.Year << "/" << date.Month << "/" << date.Day << "\n";
}

void print( const std::vector<Date>& dates )
{
    for ( auto date : dates )
    {
        print( date );
    }
}

void test()
{
    std::cout << "Print date:\n";
    print( { "Today", 2015, 5, 5 } );

    std::cout << "Print dates:\n";
    print( {
        { "Christmas", 2015, 12, 25 },
        { "Spring Bank Holiday", 2016, 6, 30 }
           } );
}

This style is particularly useful when writing tests – you can write a whole test, including setting up the data, on a single line (or at least, in a single function call).

Another compelling use case comes when creating test cases for graph algorithms. Suppose you have the following data structures for an undirected, weighted graph:

struct Edge
{
    const size_t end1;
    const size_t end2;
    const size_t cost;
};

struct Graph
{
    size_t source;
    size_t nodes;
    std::vector<Edge> edges;
};

Then creating a test graph to pass into an algorithm is as simple as:

shortest_path( { 0, 4, { {0,1,24}, {0,3,20}, {2,0,3}, {3,2,12} } })

Leave a comment

Filed under C++, C++ Code, Programming

How to efficiently find the n’th biggest element in a collection

Looking at std::nth_element the other day, I noticed that it’s complexity is O(n) for a collection of size n, and wondered how that was achieved. A basic implementation of an algorithm to find the ith-biggest element might start by sorting the collection and index to the ith afterwards – complexity O(n*log(n)):

int ith_element_by_sorting( std::vector<int> input, int i )
{
    std::sort( std::begin(input), std::end(input) );
    return input[i];
}

It’s a small step to realise then that you don’t need to sort all n elements of the collection – only the first i elements, so complexity O(n*log(i)):

int ith_element_by_partial_sort( std::vector<int> input, int i )
{
    std::partial_sort( std::begin( input ), std::begin( input ) + i + 1, std::end( input ) );
    return input[i];
}

But the real trick is that you don’t need to do any sorting at all. That’s the approach taken by quickselect, which is the selection sibling to quicksort, and achieves O(n) complexity on average:

int partition( std::vector<int>& values, int left, int right, int pivot )
{
     auto pivotValue = values[ pivot ];

     std::swap( values[pivot], values[right] ); // Move pivot to end
     auto store_pos = left;

     for ( int j = left; j < right; ++j )
     {
         if ( values[j] < pivotValue )
         {
             std::swap( values[ store_pos ], values[j] );
             ++store_pos;
         }
     }

     std::swap( values[right], values[ store_pos ] );  // Move pivot to its final place

     return store_pos;
}

int quickselect( std::vector<int> values, int left, int right, int i )
{
    // Unordered - no need to sort values at all, 
    // instead we recursively partition only the subset of values
    // containing the i'th element, until we have either
    // a) trivial subset of 1
    // b) pivot is moved to exactly the location we wanted 
    while( 1 )
    {
         if ( left == right )
         {
             return values[left];
         }

         // Pick a pivot from middle of values.
         // Better options are a random pivot or median of 3
         auto pivot = (left + right)/2; 

         // Move anything smaller than values[pivot] to the left of pivot,
         // and return updated position of pivot
         pivot = partition( values, left, right, pivot );

         if ( pivot == i )
         {
             return values[i];
         }
         else if ( i < pivot )
         {
             right = pivot - 1;
         }
         else
         {
             left = pivot + 1;
         }
    }
}

int ith_element_by_quickselect( const std::vector<int>& input, int i )
{
    return quickselect( input, 0, input.size()-1, i );
}

int ith_element( const std::vector<int>& input, int i )
{
    if ( i < 0 || i >= input.size() )
    {
        std::ostringstream ss;
        ss << "Input '" << i << "' outside range [0," << input.size() << ")";
        throw std::out_of_range( ss.str() );
    }

    return ith_element_by_quickselect( input, i );
}

Here’s some test code to check that the implementation works:

template <typename F, typename T>
void should_be( T t, F f, const std::string& message )
{
    try
    {
        std::ostringstream ss;

        auto got = f();
        if ( got != t )
        {
            ss << message << " got " << got << ", expected " << t;
            throw std::runtime_error( ss.str() );
        }
        else
        {
            ss << "OK: " << message << ": got " << got;
            std::cout << ss.str() << "\n";
        }
    }
    catch( const std::exception& ex )
    {
        // Report error if either f() threw or we found unexpected value
        std::cout << "ERROR: " << ex.what() << "\n";
    }
}

template <typename F>
void should_throw( F f, const std::string& message )
{
    try
    {
        f();
    }
    catch( const std::exception& ex )
    {
        std::cout << "OK: " << message << ": threw \"" << ex.what() << "\"\n";
        return;
    }

    std::cout << "ERROR: " << message << " should have thrown\n";
}

#define SHOULD_BE( t, expr ) should_be( t, [](){ return expr; }, #expr )
#define SHOULD_THROW( expr ) should_throw( [](){ expr; }, #expr )

void testIthElement()
{
    SHOULD_THROW( ith_element( {}, 0 ) );
    SHOULD_THROW( ith_element( {1,2}, -1 ) );
    SHOULD_THROW( ith_element( {1,2,3}, 3 ) );

    SHOULD_BE( 1, ith_element( {1}, 0 ) );
    SHOULD_BE( 0, ith_element( {0,1,2,3,4,5,6,7,8}, 0 ) );
    SHOULD_BE( 2, ith_element( {0,1,2,3,4,5,6,7,8}, 2 ) );
    SHOULD_BE( 6, ith_element( {5,4,7,6,1,2,0,8,3}, 6 ) );
    SHOULD_BE( 8, ith_element( {5,4,7,6,1,2,0,8,3}, 8 ) );
    SHOULD_BE( 5, ith_element( {5,5,5,5,5,5}, 1 ) );
}

Here’s the output:
QuickSelect

In fact, reviewing old posts on this blog, I found this link that dates back to 2013, when std::nth_element was only required by the standard to have worst-case O(N^2) complexity, with O(N) on average – precisely what you’d get from quickselect. Now though, thanks to introselect, O(N) is possible.

Leave a comment

Filed under C++, C++ Code, Programming

Tech Book: Effective Modern C++, Scott Meyers

EffectiveModernC++When Scott Meyers announced his retirement from C++ duties, I thought I’d get a copy of his latest book. There’s plenty in it to interest even seasoned C++ developers – as always, Scott’s insight and in-depth examples are worth studying. I’ve tried out most of the C++11 features, but still learnt a lot working through this book.

Uniform Initialisation and Auto
Meyers points out that compared to parentheses or just plain “=”, braced initialisation can be used in the most contexts, avoids his famous “C++’s most vexing parse”, and will issue compiler errors if narrowing occurs. However, for types that can take a std::initialiser_list in their constructor, the compiler is required to favour std::initialiser_list over any other interpretation. That’s a deterrent to use of braced initialisation with types that have a std::initializer_list constructor – and also precludes using auto with braced initialisation.

auto x = { 4 }; // type of x is inferred to be std::initializer_list&lt;int&gt;!

How to use the new “= delete” idiom
Meyers recommends declaring deleted methods as public to get better error messages from compilers that check for accessibility before deleted status. He also points out that you can declare non-member functions as deleted (I’d only seen examples of copy-constructor/copy-assignment operator as deleted before).

Use of noexcept on move operations
This one is a classic example of a combination of language features having an unexpected effect. std::vector::push_back offers the strong exception guarantee. It can achieve this using any copy constructor and being sure not to change the original contents of the vector until any new elements or copies have been constructed. Hence, move constructors are only preferred if it is exception-safe to do so – which means they must be marked as noexcept (and if that isn’t appropriate, you just won’t get move semantics pushing instances of your type into a std::vector).

Recursion with constexpr
Having toyed with template meta-programming in the past, this use of constexpr appeals to me:

constexpr int pow( int b, int exp ) noexcept
{
    return (exp == 0 ? 1 : b * pow( b, exp-1 ));
}
constexpr auto eight = pow( 2, 3 );

void testConstExpr()
{
    std::cout &lt;&lt; &quot;2^3 = &quot; &lt;&lt; eight &lt;&lt; &quot;\n&quot;;
}

It’s much more succinct than the equivalent TMP version, and still performs the calculation at compile time.

Summary
In the past, I’ve recommended Effective C++ for developers who have little experience of the language and wish to improve their skills. I think this book is a bit too advanced for that, particularly given the chapters on template type deduction and decltype being in the first part of the book! So read this book if you’ve got a few years’ experience of C++ already, but look at Effective C++ (3rd Edition) to improve on the basics.

Four stars

Leave a comment

Filed under C++, C++ Code, Programming, Tech Book

C++14 Language Extensions

Whilst reading Scott Meyers’ Effective Modern C++, I was looking for some clarification on ‘generalised lambda capture’ and came across this C++ 14 feature list. It was interesting to compare to the list of expected features that Bjarne Stroustrup presented at the ACCU 2013 conference – he described all of the following, which made it into C++14:

  • Generalised return type deduction for normal functions, not just lambdas
  • Generic (polymorphic) lambdas
  • Generalised constexpr functions (listed as Extended constexpt on the feature list)
  • Binary Literals
  • Digit Separators
  • Deprecated Attribute

However, this one appears not to have made the cut:

  • Runtime-sized arrays

This would be a great new feature and I blogged about it at the time – but it appears the work has stalled.

Leave a comment

Filed under C++, Programming

Scott Meyers – Good to go

I just read that Scott Meyers has announced he is stepping back from active involvement with C++.   I’ve been a big fan of Scott’s work, I attended his C++ training sessions at DevWeek, London in the late 90’s, and I’ve read his Effective C++|More C++|STL books – except for the most recent one, his take on Effective Modern C++. My copy is now on order. 

Leave a comment

Filed under C++, Programming

How to write generic, duck-typing code in F#

When writing generic code in C++, it’s easy to imply constraints in the generic type when developing a template. For example:

template<class T> 
class Announcer{
public:
	static void announce( const T& t )
	{
		std::cout << "And now from " <<  t.country << ", we have: ";
		bool first = true;
		for ( auto person : t.people )
		{
			std::cout << person;
			if (!first) std::cout << "\n";
			first = false;
		}
	}
};

Here, we’re assuming that T has two properties, ‘country’ and ‘people’, with the latter being enumerable (i.e. supports begin/end methods and iterators). This is one of the attractions of C++ for generic code – although, in the future, concepts will enable you to document the constraints in order to make it easier for developers to use your library, and for the compiler to give clearer errors.

What about something similar in F#? I found Tomas Petricek’s post from StackOverflow very useful.

type IHasCountryProperty =
    abstract Country : string

type Announcer<'T when 'T :> IHasCountryProperty>( item : 'T) =
    member this.Announce() =
        printfn "And now the party from %s" item.Country

let inline countrifiedItem<'T when 'T : (member Country : string)> (item : 'T) =
    {
        new IHasCountryProperty with
            member this.Country = (^T : (member Country : string) item)
    }

type London() =
    member this.Country = "England"

// Use it
let city = London()
Announcer( countrifiedItem city ).Announce()

The Announcer class uses a member constraint with statically resolved type parameters which bind to the Country property. Then, the inline static function ‘countrifiedItem’ uses static member constraints to capture the existing Country property on any other type, even if like ‘London’ it doesn’t support the IHasCountryProperty. The consensus seems to be that this approach is encouraged because it documents the requirements on ‘T in an interface.

Leave a comment

Filed under C++, C++ Code, F#, Programming

ACCU Meetup: Quicker Sorting, Dietmar Kühl

Meetup - Quicker SortingI was lucky to get an invite to this month’s ACCU London meet-up on the topic of sorting. Dietmar Kuhl hosted the presentation at the plush Bloomberg offices on Finsbury Circus. The talk brought together a sample of approaches to speeding up QuickSort:

  • insertion sort
  • sentinel partitioning
  • hand-rolled sorting for small collections

Overall, these changes (and others) made an impressive improvements, such that the combined algorithm rivalled std::sort for sorting std::vectors of integer. However, the algorithm wasn’t as competitive for other important element types such as std::string.

Dietmar intended the talk to be accessible to all, rather than an in-depth presentation using advanced C++ techniques. I think it was a good example of how you can iterate and bring in multiple techniques to optimise an algorithm for a specific use case.

Leave a comment

Filed under C++, Meetup, Programming

ACCU: CVU magazine 266

Catching up on back copies of ACCU’s CVU magazine, there was plenty of good material in January 2015’s edition.
CVU Jan 2015

  • Simplicity Through Immutability – Chris Oldwood provides a worked example of the benefits of introducing an immutable type. The example is pretty simple, but experience with F# shows that this approach frequently simplifies logic (most of the time without noticeable performance penalties)
  • Delayed Copy Pattern – Vassili Kaplan compares ways to push huge objects into an STL container, with timings showing that a delayed-copy wrapper is comparable in performance to emplace-back (and the wrapper can be used for older compilers)
  • Standards Report – I was particularly taken by Mark Radford’s note on Operator Dot. At first sight, it could be dismissed as a typical C++ programmer’s wish to overload any operator available, which is currently prohibited for operator dot. However, Bjarne Stroustrup himself is named on the paper, and the motivating case is for ‘smart reference’ classes.
  • Scott Meyers Interview – more than just a subtle book plug, gives an insight into Scott’s introduction to programming and C++.

[The links to CVU articles are accessible to ACCU members only]

Leave a comment

Filed under C++, Programming

ACCU: Introducing Concepts for C++

Overload 129October 2015’s edition of Overload includes an excellent article by Andrew Sutton on Concepts for C++. I first heard about Concepts at the ACCU 2013 conference and it’s exciting to hear that they have reached Technical Specification stage.

There’s no doubt in my mind that concepts will play a huge role for those involved in generic programming. In F#, we already have the ability to state constraints on template arguments e.g. to ensure that ‘T satisfies the comparison constraint:

type Container<'T when 'T : comparison>( items : 'T[] ) =
    // ...

However, I wasn’t expecting the ability to use concepts for placeholders (so that, once you’ve defined a concept, you can use it where you might have used auto to gain the benefits of type deduction without the loss of information).

Leave a comment

Filed under C++, F#, Programming