Home » Blog » Categories » News

News

Fast incremental sort -- Lars Hagen

By larshagencpp | Apr 24, 2016 05:34 AM | Tags: performance efficiency

Lars Hagen describes in his blog post a strategy to solve the problem of a fast incremental sort.

Fast incremental sort

by Lars Hagen

From the article

I recently came across the need for an incremental sorting algorithm, and started to wonder how to do it optimally.

The incremental sorting problem is described here, and is an “online” version of partial sort. That is, if you have already sorted kk elements, you should be able to quickly sort k+1k+1 elements, and so on.

Incremental sorts can be useful for a number of cases:

  • You want sorted items, but you don’t know how many elements you’ll need. This could often happen when you are filtering the resulting sequence, and you don’t know how many items will be filtered out.
  • You are streaming the sequence, so even though you want the whole sequence, you want the first elements as quickly as possible.

We’ll see how branch misprediction and other constant factors can make the naive asymptotically optimal version far slower than a practical implementation.

The status of reflection in C++ -- Axel Naumann

By Axel | Apr 19, 2016 03:08 PM | Tags: None

Axel Naumann writes about the state of the reflection in C++ in his recent article.

The status of reflection of C++

by Axel Naumann

From the article:

When the C++ committee met in Jacksonville two months ago, something big happened: the reflection study group, SG7, decided what the basic “language" of reflected C++ should look like. What does that mean? Why do you care? Let me, the co-author of the only “blessed proposal", explain...

Schedule for ACCU 2016 has been published

By Mantosh Kumar | Apr 17, 2016 09:45 PM | Tags: None

The schedule for the annual ACCU Conference has just been published. The conference will be held at Marriott Hotel  City Centre, in Bristol, UK, on April 19-23, 2016. The conference is focused on professionalism in programming, but as always the schedule contains a lot of talks about C++.

 

ACCU is a small and friendly conference, typically 400+ attendees living together in the same hotel for a week discussing everything about programming. Most of the talks(60+) are 90 minutes, with long breaks inbetween, inviting to deep and insightful discussions both during and after the sessions. If you are into programming, especially C++, this is a conference that you might want to consider.

 

 

Overload 132 is now available

By Adrien Hamelin | Apr 12, 2016 01:59 PM | Tags: intermediate community

ACCU’s Overload journal of April 2016 is out. It contains the following C++ related articles.

Overload 132

From the journal:

The Tao of Scratch
Scratch is an environment designed to help young people learn to code. Patrick Martin walks us through it. by Patrick Martin

Knowledge-Sharing Architects As An Alternative to Coding Architects
Should architects write code? Sergy Ignatchenko explores this controversial subject. by Sergey Ignatchenko

QM Bites: Understand Windows OS Identification Preprocessor Macros
There’s confusion between user-defined and predefined Windows 32/64-bit operating-system identification macros. Matthew Wilson shines light on the issue. by Matthew Wilson

Why Collaboration is Key for QA Teams in an Agile World
Agile processes can have an impact on QA departments. Greg Law considers how they can adapt to survive and even thrive. by Greg Law

How to Diffuse Your Way Out of a Paper Bag
Diffusion models can be used in many areas. Frances Buontempo applies them to paper bag escapology. by Frances Buontempo

Stufftar
How do you quickly transfer data from one machine to another? Ian Bruntlett shows us the bash script he uses. by Ian Bruntlett

QM Bites: looping for-ever
Never-ending loop constructs can confound user and compiler in subtle ways. Matthew Wilson offers advice to maximise portability and transparency.

Using Enum Classes as Bitfields
Scope enums have many advantages over standard enums. Anthony Williams shows how to use them as bitmasks. by Anthony Williams

9.7 Things Every Programmer Really, Really Should Know
Most of us have heard of the twelve step program. Teedy Deigh introduces a 9.7 step plan for programmers.

Quick Q: Is Stephen Lavavej's Mallocator the same in C++11?

By Adrien Hamelin | Apr 12, 2016 11:41 AM | Tags: intermediate c++11

Quick A: No, it has changed.

Recently on SO:

Is Stephen Lavavej's Mallocator the same in C++11?

STL himself has an answer to this question in his STL Features and Implementation techniques talk at CppCon 2014 (Starting at 26'30).

The slides are on github.

I merged the content of slides 28 and 29 below:

#include <stdlib.h> // size_t, malloc, free
#include <new> // bad_alloc, bad_array_new_length
template <class T> struct Mallocator {
  typedef T value_type;
  Mallocator() noexcept { } // default ctor not required
  template <class U> Mallocator(const Mallocator<U>&) noexcept { }
  template <class U> bool operator==(
    const Mallocator<U>&) const noexcept { return true; }
  template <class U> bool operator!=(
    const Mallocator<U>&) const noexcept { return false; }

  T * allocate(const size_t n) const {
      if (n == 0) { return nullptr; }
      if (n > static_cast<size_t>(-1) / sizeof(T)) {
          throw std::bad_array_new_length();
      }
      void * const pv = malloc(n * sizeof(T));
      if (!pv) { throw std::bad_alloc(); }
      return static_cast<T *>(pv);
  }
  void deallocate(T * const p, size_t) const noexcept {
      free(p);
  }
};

Note that it handles correctly the possible overflow in allocate.