Articles & Books

Strict Weak Ordering and STL—Saurabh Singh

Saurabh Singh describes in a brief tutorial on how to correctly implement the comparator function for STL containers and algorithms. 

Strict Weak Ordering and STL

by Saurabh Singh

From the article:

If you had ever used a map or set or even std::sort I bet you would have to give a comparator function. (Or an overload to the < (less than) operator).
I will try to give an overview of how certain associative stl containers use this property for ordering the elements.
Almost all stl containers rely on strict weak ordering A strict weak ordering defines the relative position of elements in terms of precedence of one item over other. For eg. if you have a room full of person and you have to form a queue based on their height, a person with "lesser" height will "precede" the person with greater height. For a function to be satisfying strict weak ordering following conditions need to be met.

The PDF version of the document is available here.

Quick Q: What are rvalues, lvalues, xvalues, glvalues, and prvalues?

Quick A: Categories of values that determine what can be done with that value.

Some time ago on SO:

What are rvalues, lvalues, xvalues, glvalues, and prvalues?

What are these new categories of expressions?
The FCD (n3092) has an excellent description:

— An lvalue (so called, historically, because lvalues could appear on the left-hand side of an assignment expression) designates a function or an object. [ Example: If E is an expression of pointer type, then *E is an lvalue expression referring to the object or function to which E points. As another example, the result of calling a function whose return type is an lvalue reference is an lvalue. —end example ]

— An xvalue (an “eXpiring” value) also refers to an object, usually near the end of its lifetime (so that its resources may be moved, for example). An xvalue is the result of certain kinds of expressions involving rvalue references (8.3.2). [ Example: The result of calling a function whose return type is an rvalue reference is an xvalue. —end example ]

— A glvalue (“generalized” lvalue) is an lvalue or an xvalue.

— An rvalue (so called, historically, because rvalues could appear on the right-hand side of an assignment expressions) is an xvalue, a temporary object (12.2) or subobject thereof, or a value that is not associated with an object.

— A prvalue (“pure” rvalue) is an rvalue that is not an xvalue. [ Example: The result of calling a function whose return type is not a reference is a prvalue. The value of a literal such as 12, 7.3e5, or true is also a prvalue. —end example ]

Every expression belongs to exactly one of the fundamental classifications in this taxonomy: lvalue, xvalue, or prvalue. This property of an expression is called its value category. [ Note: The discussion of each built-in operator in Clause 5 indicates the category of the value it yields and the value categories of the operands it expects. For example, the built-in assignment operators expect that the left operand is an lvalue and that the right operand is a prvalue and yield an lvalue as the result. User-defined operators are functions, and the categories of values they expect and yield are determined by their parameter and return types. —end note

I suggest you read the entire section 3.10 Lvalues and rvalues though.
How do these new categories relate to the existing rvalue and lvalue categories?

Are the rvalue and lvalue categories in C++0x the same as they are in C++03?
The semantics of rvalues has evolved particularly with the introduction of move semantics.
Why are these new categories needed?
So that move construction/assignment could be defined and supported.

Quick Q: Does C++ final imply final in all aspects?

Quick A: Yes, a final class cannot have its methods overriden.

Recently on SO:

Does C++ final imply final in all aspects?

To quote the draft C++ standard from here [class.virtual/4]:

If a virtual function f in some class B is marked with the virt-specifier final and in a class D derived from B a function D::f overrides B::f, the program is ill-formed.
And here [class/3]:
If a class is marked with the class-virt-specifier final and it appears as a base-type-specifier in a base-clause (Clause [class.derived]), the program is ill-formed.
So, in answer to the question;


Does a final class implicitly imply its virtual functions to be final as well? Should it? Please clarify.

So, at least not formally. But attempts to violate either rule will be the same result in both cases; the program is ill-formed and so won't compile. A final class means the class cannot be derived from, so as a consequence of this, its virtual methods cannot be overridden.


Should it? Probably not, they are related but they not the same thing. There is also no need formally require the one to imply the other, the effect follows naturally. Any violations have the same result, a failed compile (hopefully with appropriate error messages to distinguish the two).

Quick Q: Need of a weak_ptr in C++11

Quick A: To keep a pointer on a ressource without owning it.

Recently on SO:

Need of a weak_ptr in C++11

The second half of that statement should be clear: if a pointer is not an owning pointer then the object it is pointing at might be deleted by whatever software is the owner - and then you'd have the standard dangling reference.

So this issue is: you've got objects owned by some piece of software which is letting other software have access to it - but the other software won't share the ownership. So the owner can delete it at any time and the other software needs to know it's pointer is no longer valid.

Maybe an example would help:

You've got some piece of software watching a camera pointing out your window to a bird feeder and it is identifying birds at the feeder, which come and go. Each bird at the feeder has an object created by this software when it arrives at the feeder, and the object is deleted when the bird flies away.

Meanwhile, some other software it taking a census. Every 10 seconds it grabs from the feeder-watching software a collection of the birds at the feeder. Every 100 seconds it emits a report of which birds were at the feeder for the entire 100 seconds.

Because the data for a bird is big the census-taker doesn't copy the data. It merely gets, every 10 seconds, a collection of pointers from the feeder-watcher.

To make it necessary to use weak pointers, let's say the feeder-watcher only provides pointers to birds which have arrived in the last ten seconds, not the ones which have been there. That is, there is no notification that birds have disappeared.

By using weak pointers it can know, at report time, which of the birds are still there, and when they arrived (but not when they left).

(Maybe I'll think of a better example later.)

Fast incremental sort—Lars Hagen

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 Ultimate Question of Programming, Refactoring, and Everything

Yes, you've guessed correctly - the answer is "42". In this article you will find 42 recommendations about coding in C++ that can help a programmer avoid a lot of errors, save time and effort.

The Ultimate Question of Programming, Refactoring, and Everything

by Andrey Karpov

From the article:

The scope of my interests − the C/C++ language and the promotion of code analysis methodology. I have been Microsoft MVP in Visual C++ for 5 years. The main aim of my articles and work in general - is to make the code of programs safer and more secure. I'll be really glad if these recommendations help you write better code, and avoid typical errors. Those who write code standards for companies may also find some helpful information here.