Initialization/Termination order of globals and local statics.

Introduction

The previous blog post got into details about how to control the order of initializing globals in Visual Studio (in regards to the order in different translation units which is undefined by the C++ standard).

However, the standard doesn’t leave things completely at the compiler’s discretion when it comes to the order within a single translation unit.

This second blog post will describe this and also a not so widely known behavior of when static local objects are terminated.

Initialization order within a single translation unit

While the standard doesn’t define the order to initialize global objects in different translation units, it’s quite specific about the cases when initializing globals within the same translation unit (with the single exception of class template static data members). [1]

The rule for the order is quite simple: Objects are initialized exactly in the order they are defined.

Good practice therefore is to put a list of all definitions of globals at a single place within the cpp file (f.e. at the end). The order these globals are defined then provides a direct overview/documentation of the order these objects will be initialized.

[...]
namespace Foo
{
   class A {
      static std::string MyNumber;
   };
   [...]

   // initialization list
   std::string g_String;
   std::string A::MyNumber;
}

[...]

namespace Foo

{

class A {

static std::string MyNumber;

};

[...]

// initialization list

std::string g_String;

std::string A::MyNumber;

}

In this example, there are two global/static objects defined. Because of the order in the initialization list, g_String will be initialized before A::MyNumber.

Initialization order of static locals

Well known should be the fact that local statics get initialized only once and it’s ensured (by the standard) that the initialization is done prior to the local object being used. Hence, it’s common practice to write constructs like the following one, to ensure that costly operations are performed only on demand:

void foo()
{
   static Bar localBar;
   localBar.test();
}

void foo()

{

static Bar localBar;

localBar.test();

}

Assume the constructor of the class Bar would allocate some limited resource. Since Bar is defined as a local static, the developer surely expects that the resource is only allocated if foo() is called (and not, if the application doesn’t call foo() at runtime at all). Having dealt with quite a bunch of different build environments, that’s also the behavior the author always experienced in reality.

Regardless, the standard also allows a different behavior and explicitly permits implementations to perform the initialization of static local objects according to how globals are initialized. [2] In effect this means that localBar could get initialized by a certain compiler already when the application starts up.

Termination order of globals and static locals

If you ask 10 C++ developers in which order globals/statics are terminated, you most probably will have 9 out of these 10 tell you that these will be terminated in reverse order of how they were initialized. While this is true in most cases, it doesn’t stand for static locals in all situations.

Try out the following example:

#include <iostream>

class B
{
public:
   B()  { std::cout << "B - ctor" << std::endl; }
   ~B() { std::cout << "B - dtor" << std::endl; }
};

class A
{
public:
   static void Test()
   {
      std::cout << "A::Test()" << std::endl;
      static B b;
   }

   A()
   {
      std::cout << "A - ctor" << std::endl;
      Test();
   }
   ~A() { std::cout << "A - dtor" << std::endl; }
};

int main()
{
   return 0;
}

A a;

#include <iostream>

class B

{

public:

B() { std::cout << "B - ctor" << std::endl; }

~B() { std::cout << "B - dtor" << std::endl; }

};

class A

{

public:

static void Test()

{

std::cout << "A::Test()" << std::endl;

static B b;

}

A()

{

std::cout << "A - ctor" << std::endl;

Test();

}

~A() { std::cout << "A - dtor" << std::endl; }

};

int main()

{

return 0;

}

A a;

Running this sample code, you’ll get the following output:

A - ctor
A::Test()
B - ctor
A - dtor
B - dtor

A - ctor

A::Test()

B - ctor

A - dtor

B - dtor

What’s unexpected to most developers here is to see that the local object A is destroyed before B, even though the initialization order was the same (i.e. A was constructed before B).

If you’d slightly modify the example and call Test() inside main() rather than in the ctor for A, you’ll get the “usual” termination order and will see that the dtor of A is called after B’s dtor.

The explanation for this quite specific behavior can be found in the C++ standard as well. [3] In easier words than used in the standard it means that if a static locals is initialized during the construction of a global object, it will be terminated after the object which called the function with the static local in its ctor.

References

[1] C++ 03 standard – 3.6.2 (1)
“[…]Other objects defined in namespace scope have ordered initialization. Objects defined within a single translation unit and with ordered initialization shall be initialized in the order of their definitions in the translation unit.[…]”
[2] C++ 03 standard – 6.7 (4)
“[…]An implementation is permitted to perform early initialization of other local objects with static storage duration […]. Otherwise such an object is initialized the first time control passes through its declaration;[…]”
[3] C++ 03 standard – 3.6.3 (1)
“[…] These objects [objects of static storage duration] are destroyed in the reverse order of the completion of their constructor […]. […] For an object of […] class type, all subobjects of that object are destroyed before any local object with static storage duration initialized during the construction of the subobject is destroyed. […]”

Initialization order of globals in Visual Studio.

Introduction

Any developer sooner or later will stumble across the issue of the undefined order global and static objects are initialized at.

A not so uncommon example is when using a custom memory management system. Usually you want the memory management system to be initialized prior to any allocation which occurs and after all the allocated memory was freed again.
This is problematic, if global/static objects rely on memory allocations.

The wrong approach

Assume you would initialize the memory manager as the first call in your main()-function and shut it down as the last step prior to returning from main().

The issue you will end up with is that other global objects are initialized prior to your initialization call in main(). You might consider it being a solution to perform some implicit initialization of the memory manager. Besides this coming with added complexity and some (unavoidable) performance penalty, it won’t help with the issue that when you shut down the program, the corresponding destruction of these globals will happen after the main() function already returned and the memory manager was shut down.

You might think of handling this too then, but that won’t work (at least not in a sane/clean way) because your memory manager will certainly require some resources which need to be freed at shutdown.

How about atexit()?

So you might consider the alternative approach and use an atexit()-registered function (your shutdown function). This is however especially bad for a memory manager because:

atexit()-registered functions are processed in LIFO order and so won’t change the behavior you faced above with calling the shutdown function last in your main() function
atexit uses heap-allocated memory which you presumably directed through your memory manager

Let’s use a global

So the third idea comes to mind and put the initialization and termination handling of the memory manager in a global object’s constructor/destructor itself.

The problem you are facing here is the issue of how you’d be able to control that this particular global object is initialized before all other global objects and destroyed last.

The solution

A common approach to prevent problems caused by the undefined order is to stop using global and static objects altogether (f.e. by relying on pointers and defining an explicit initialization order in the app’s main() function). However, this approach is not always feasible and comes with certain drawbacks (which are outside the scope for this blog post). [2]

A different solution is provided in Visual Studio (with the MS CRT) by means of the “init_seg”-pragma which can be used to control the initialization order. [1]

To understand how this works, you should know that global objects are initialized as part of the CRT initialization. [3]
In particular, the CRT adds the initializers for all globals in the “.CRT$XCU” [4] linker section. The trick is now to use the “init_seg”-pragma to specify that the initialization of globals in the corresponding translation unit should go in a different section (i.e. one before the “.CRT$XCU” section but after “.CRT$XCA” [5]).

That can be done by adding the following pragma to the particular cpp file containing the global initialization:

#pragma init_seg(".CRT$XCT")

This ensures that your globals in the translation unit will be initialized prior to other globals of your application.

A word of warning

However, be careful with that approach and be aware that your global objects constructors will be called prior to other global objects (including potentially global objects used by the CRT itself!). [6]

Also bare in mind that this is kind of an advanced feature which is not too widely used and is (as far as the author is concerned) not an officially supported approach/functionality. That means that different CRT versions (even different flavors like debug vs. release runtime) can emit different behavior by putting initialization code in different sections. Your application might just work fine for years but suddenly stops working and experiences crashes (f.e. after a security update to the CRT was released or after you ported your application to a later VS version).

The second concern you need to be aware of are interactions with 3rd-party libraries. If you use different libraries these could also use the trick to put their own initialization related code in the CRT linker section and your code might then run after (or before) the other lib was initialized.

It’s therefore important to consider which section you put your initialization code in. In general it shouldn’t be a bad idea to put it into the “.CRT$XCT” section (i.e. closest reasonable section just before the “.CRT$XCU” section where other globals will be initialized in) rather than trying to put it in the earliest one (i.e. “.CRT$XCB”). That way you should be on the safer side with regards to a not yet completely initialized CRT which could cause quite a couple of sleepless nights tracing down some weird undefined behavior in your application.

On top of this, it’s also good practice to keep the constructor/destructor of such global objects as simple as possible and defer any initialization/termination code to be done as part of the normal program flow (i.e. during main()). This ensures that you are less likely to run into issues due to an incompletely initialized dependent global object (which could be part of the CRT or a dependent 3rd-party library).

Verifying whether you run into an issue with the global initialization order

If you run into a crash with the callstack pointing to the dynamic initializer list when starting your program which wasn’t present without the pragma statement, it probably means you did overlook such a global object dependency. To validate this, you can make use of the linker’s map output file and review which CRT-linker sections are used.

To do this, first you comment out the “init_seg”-pragma statement and then rebuild the program with the map output file. Using a text editor you should be able to locate the “.CRT$XC” sections at the top of the map file which could look like this:

[...]
 0003:00000000 00000104H .CRT$XCA                DATA
 0003:00000104 00000104H .CRT$XCAA               DATA
 0003:00000208 00000104H .CRT$XCB                DATA
 0003:0000030c 00000104H .CRT$XCC                DATA
 0003:00000410 00000104H .CRT$XCZ                DATA
[...]

[...]

0003:00000000 00000104H .CRT$XCA DATA

0003:00000104 00000104H .CRT$XCAA DATA

0003:00000208 00000104H .CRT$XCB DATA

0003:0000030c 00000104H .CRT$XCC DATA

0003:00000410 00000104H .CRT$XCZ DATA

[...]

These are sorted alphabetically and you’d see if there’s a section which unexpectedly comes before the section you put your global in. If so, simply change the section you use to a later one.

If you found this information interesting, you might also be interested in this follow-up blog post regarding further details related to the initialization order of globals.

References / Footnotes

[1] https://docs.microsoft.com/en-us/cpp/preprocessor/init-seg?view=vs-2017
[2] https://stackoverflow.com/questions/6939989/global-c-object-initialization#6940356
[3] https://docs.microsoft.com/en-us/cpp/c-runtime-library/crt-initialization?view=vs-2017
[4] To be precise the section name is actually .CRT with XCU being the section group.
[5] The XCA group specifies the __xc_a pointer which marks the start of the global initialization list and therefore no initialization should be put into that group.
[6] https://developercommunity.visualstudio.com/content/problem/335311/access-violation-with-mtd-and-init-seg-pragma.html

The trouble of separate module atexit-stacks

The demo project (Visual Studio 2015 solution) demonstrating the behavior in this article can be downloaded here.

Introduction

Using atexit() to specify functions to be called if an application terminates is quite common practice. This is especially true for libraries since the C-standard specified atexit()-function is a way for the library to register its cleanup logic without relying on the 3rd-party application to properly call a specific cleanup function.

This is also what the library the author was working with did. Since the usage of the atexit()-function is nothing uncommon, it was quite surprising to observe that obviously the cleanup handling (which got registered via the atexit()-function) occurred after some resources were already freed when compiling the code with Microsoft’s Universal C runtime. In this particular case, this fact resulted in the cleanup function being stuck in an endless loop with the result of the app never terminating.

Well known behavior of atexit()

To understand the root cause of the problem, let’s first take a look at a simple case of using an atexit()-registered function to stop a thread and wait until the thread terminated before the hosting application closes cleanly:

#define WIN32_LEAN_AND_MEAN
#include <windows.h>
#include <iostream>

static int threadCounter = 0;
static HANDLE handle = nullptr;
static bool running = true;

static void terminateThread(void)
{
  running = false;
  WaitForSingleObject(handle, INFINITE);
  std::cout << "done waiting - counter is: " << threadCounter << "\n";
}

static DWORD WINAPI dummy_worker(void*)
{
  threadCounter++;

  while (running) { Sleep(1000); }

  threadCounter--;
  return 0;
}

int main(void)
{
  atexit(&terminateThread);

  handle = CreateThread(NULL, 0, &dummy_worker, nullptr, 0, nullptr);
  Sleep(100);
  return 0;
}

#define WIN32_LEAN_AND_MEAN

#include <windows.h>

#include <iostream>

static int threadCounter = 0;

static HANDLE handle = nullptr;

static bool running = true;

static void terminateThread(void)

{

running = false;

WaitForSingleObject(handle, INFINITE);

std::cout << "done waiting - counter is: " << threadCounter << "\n";

}

static DWORD WINAPI dummy_worker(void*)

{

threadCounter++;

while (running) { Sleep(1000); }

threadCounter--;

return 0;

}

int main(void)

{

atexit(&terminateThread);

handle = CreateThread(NULL, 0, &dummy_worker, nullptr, 0, nullptr);

Sleep(100);

return 0;

}

(Sidenote on this code: The code is kept as simple as possible to demonstrate the actual problem. The fact that it’s not really thread-safe is not relevant for this topic.)

As we see, the test case is quite simple.
main() spawns a simple worker thread (dummy_worker()) which increments a threadCounter when it’s started, waits until running is set to false just to decrement the threadCounter again.
In main() we register the terminateThread()-function using atexit() so to make sure that we cleanly shut down the running thread.
To do that, terminateThread() sets running to false and waits until the thread got signaled (i.e. terminated) via WaitForSingleObject() just to print out the current thread counter value (which we certainly expect to be 0 at this point).
Right before we return from main() we give the thread some time to ensure it’s started.

Running this app, we see it behaves as we expected and get the output:
done waiting – counter is: 0

No big surprise here.

atexit() and DLLs

Now let’s make things a bit more interesting and move that code inside a DLL (into the startThread()-function) and call that from the application’s main()-function.

#define WIN32_LEAN_AND_MEAN
#include <windows.h>
#include "testdll.h"

int main(void)
{
  startThread();
  Sleep(100);
  return 0;
}

#define WIN32_LEAN_AND_MEAN

#include <windows.h>

#include "testdll.h"

int main(void)

{

startThread();

Sleep(100);

return 0;

}

#define WIN32_LEAN_AND_MEAN
#include <windows.h>
#include <iostream>

static int threadCounter = 0;
static HANDLE handle = nullptr;
static bool running = true;

static void terminateThread(void)
{
  running = false;
  WaitForSingleObject(handle, INFINITE);
  std::cout << "done waiting - counter is: " << threadCounter << "\n";
}

static DWORD WINAPI dummy_worker(void*)
{
  threadCounter++;

  while (running) { Sleep(1000); }

  threadCounter--;
  return 0;
}

void startThread(void)
{
  atexit(&terminateThread);

  handle = CreateThread(NULL, 0, &dummy_worker, nullptr, 0, nullptr);
}

#define WIN32_LEAN_AND_MEAN

#include <windows.h>

#include <iostream>

static int threadCounter = 0;

static HANDLE handle = nullptr;

static bool running = true;

static void terminateThread(void)

{

running = false;

WaitForSingleObject(handle, INFINITE);

std::cout << "done waiting - counter is: " << threadCounter << "\n";

}

static DWORD WINAPI dummy_worker(void*)

{

threadCounter++;

while (running) { Sleep(1000); }

threadCounter--;

return 0;

}

void startThread(void)

{

atexit(&terminateThread);

handle = CreateThread(NULL, 0, &dummy_worker, nullptr, 0, nullptr);

}

Certainly we expect to see the same behavior we saw before. So let’s get the console output:
“done waiting – counter is: 1”

This is not quite what we expected to see. In the end we did cleanly terminate the thread… Or didn’t we?

Understanding what’s going on

To get a better feeling of what’s going on here, let’s add some debug output.

We add another atexit()-registered function (in the application’s main()-function).
We add some output to DllMain() to see how attaching and detaching of threads/processes works.
We print out the state of returning from main() right before it returns.
We add some output at the start of the terminateThread()-function.

#define WIN32_LEAN_AND_MEAN
#include <windows.h>
#include <iostream>
#include "testdll.h"

void atExitMainPorcess(void)
{
  std::cout << "atExitMainProcess\n";
}

int main(void)
{
  atexit(&atExitMainPorcess);

  startThread();
  Sleep(100);

  std::cout << "returning from process main\n";
  return 0;
}

#define WIN32_LEAN_AND_MEAN

#include <windows.h>

#include <iostream>

#include "testdll.h"

void atExitMainPorcess(void)

{

std::cout << "atExitMainProcess\n";

}

int main(void)

{

atexit(&atExitMainPorcess);

startThread();

Sleep(100);

std::cout << "returning from process main\n";

return 0;

}

static int threadCounter = 0;
static HANDLE handle = nullptr;
static bool running = true;

static void terminateThread(void)
{
  std::cout << "terminating thread\n";
  running = false;
  WaitForSingleObject(handle, INFINITE);
  std::cout << "done waiting - counter is: " << threadCounter << "\n";
}

static DWORD WINAPI dummy_worker(void*)
{
  threadCounter++;

  while (running) { Sleep(1000); }

  threadCounter--;
  return 0;
}

void startThread(void)
{
  atexit(&terminateThread);

  handle = CreateThread(NULL, 0, &dummy_worker, nullptr, 0, nullptr);
}

BOOL APIENTRY DllMain( HMODULE hModule,
                       DWORD  ul_reason_for_call,
                       LPVOID lpReserved
                     )
{
  switch (ul_reason_for_call)
  {
  case DLL_PROCESS_ATTACH:
    std::cout << "process attach\n";
    break;
  case DLL_THREAD_ATTACH:
    std::cout << "thread attach\n";
    break;
  case DLL_THREAD_DETACH:
    std::cout << "thread detach\n";
    break;
  case DLL_PROCESS_DETACH:
    std::cout << "process detach\n";
    break;
  }
  return TRUE;
}

static int threadCounter = 0;

static HANDLE handle = nullptr;

static bool running = true;

static void terminateThread(void)

{

std::cout << "terminating thread\n";

running = false;

WaitForSingleObject(handle, INFINITE);

std::cout << "done waiting - counter is: " << threadCounter << "\n";

}

static DWORD WINAPI dummy_worker(void*)

{

threadCounter++;

while (running) { Sleep(1000); }

threadCounter--;

return 0;

}

void startThread(void)

{

atexit(&terminateThread);

handle = CreateThread(NULL, 0, &dummy_worker, nullptr, 0, nullptr);

}

BOOL APIENTRY DllMain( HMODULE hModule,

DWORD ul_reason_for_call,

LPVOID lpReserved

)

{

switch (ul_reason_for_call)

{

case DLL_PROCESS_ATTACH:

std::cout << "process attach\n";

break;

case DLL_THREAD_ATTACH:

std::cout << "thread attach\n";

break;

case DLL_THREAD_DETACH:

std::cout << "thread detach\n";

break;

case DLL_PROCESS_DETACH:

std::cout << "process detach\n";

break;

}

return TRUE;

}

Running that code, we get the following output (numbers represent line numbers for reference):
1: process attach
2: thread attach
3: returning from process main
4: atExitMainProcess
5: process detach
6: terminating thread
7: done waiting – counter is: 1

We see that atExitMainProcess() gets called after main() returns, followed by the process detach signal the DLL got, followed by the call to terminateThread() which we registered in the DLL via atexit().

This gives us two interesting hints:

there is no output for the detaching of the thread
the atexit()-registered function of the DLL is called after the atexit()-registered function from the main process

Digging into the depths

To understand the first part, we’ve to know that terminating a process issues a call to ExitProcess() in the VS runtime if the process returned from main(). [1]
The first thing ExitProcess() does is to terminate all threads of the process (excluding the calling thread) WITHOUT receiving a DLL_THREAD_DETACH notification. [2]
That explains the fact that we do not receive the thread detach output.
Keep in mind the following additional facts to understand the conclusion further down:

after threads were terminated, they become signaled
for all DLLs the process-detach notification is sent (that corresponds to line 5 in the output)
Note, that before that step in the ExitThread() processing, the atexit()-registered function in main() was called (output: line 4)

Let’s keep these facts in mind and take a look at the second part now:

We got the output from the process’ atexit()-registered function BEFORE the output of the function we registered via the atexit()-call in startThread(), even though atexit() is defined to run the registered functions in LIFO order [3]. So why did we not get the call to terminateThread() before atExitMainProcess() was called?

The explanation is that in the VC runtime each module (i.e. each DLL and each process) has its own separate atexit-stack (as Dough Harrison explains in these threads [4/8]). This minor detail makes a fundamental difference in this scenario because it means that the order of the registered atexit()-functions is not only dependent on the order of atexit()-calls, but also in which context (i.e. module) they got called.

Understanding the behavior

Now we got to the point of understanding what is going on here.

Upon the process termination, the process’ atexit()-function stack is processed (ouput: line 4).
ExitProcess() is called and terminates our thread without the thread-detach notification.
The thread is signaled.
The process detached notification is sent to the DLL (output: line 5).
The DLL is unloaded and processes its own atexit()-function-stack which calls our terminateThread() function (output: line 6).
The call to WaitForSingleObject() returns immediately (since the thread got signaled already).

Hence, we end up with threadCounter still being set to 1.

What the standard says

The question would arise whether this behavior actually violates the C or C++ standard.
As far as the author can determine there is no violation of the standard. Actually it turns out that the termination of threads prior to their atexit()-functions being called is to prevent undefined behavior as it’s specified in the standard itself [5] which explicitly states that threads can be terminated prior to the execution of std::atexit registered functions in order to prevent undefined behavior. This is particular noted to allow thread managers as static-storage-duration objects.

On the other side the specification of atexit() [6/7] doesn’t prevent the usage of different atexit()-function-stacks per module. So again, there’s no standard violation here.

That said: It’s an implementation detail that there are multiple different atexit-stacks and it’s also an implementation detail when the atexit-functions are called in relation to when threads are terminated.

How developers can deal with the facts

For library developers it seems that there are limited options to cope with the situation. Here’s a list of possible approaches to compensate for the difference in when atexit()-registered functions are called:

ensure your cleanup code actually handles the scenarios where resources were freed already prior to the cleanup function having been called
do not use atexit() at all (or at least not in the context of DLLs) but rather provide your own cleanup function which is documented to be required to be called by 3rd-party applications utilizing your library to ensure proper resource cleanup
do not provide means to do explicit cleanup, but rather leave that task with the OS (which implicitly will cleanup resources eventually)

Conclusion

The combination of using separate per module atexit-stacks and the fact that threads which are registered from a module are killed (without notifications) prior to the module’s atexit()-registered functions having been called, makes the usage of atexit()-registered functions kind of unsuitable in situations without complete control about how the code is utilized (i.e. in libraries).

The lack of explicit requirements from the C/C++ standard in this regards, which might have been intentional and done that way for completely valid and sound reasons (which however would be beyond the author’s knowledge) does not help much with the situation unfortunately. It also raises the question whether this behavior makes sense from a design point of view and whether such a behavior doesn’t defeat the purpose of the atexit-design/-purpose (and therefore could be argued to be a defect in the standard).

The usage of per module exit stacks is at least questionable in the opinion of the author, because as it stands, at least for platform and compiler independent library development the lack of an explicit requirement in the standard adds additional complexity to the design requirements of functions being utilized via atexit()-calls.

Acknowledgments

The author would like to thank Branko Čibej and Bert Huijben for their contributions in investigating the topic and sharing their own opinions on this matter.

References

[1] = Windows Kits 10.0.10240.0 source code: ucrt/startup/exit.cpp: exit_or_terminate_process()
[2] = https://msdn.microsoft.com/en-us/library/windows/desktop/ms682658(v=vs.85).aspx
[3] = https://msdn.microsoft.com/en-us/library/tze57ck3.aspx
[4] = https://groups.google.com/d/msg/microsoft.public.vc.language/Hyyaz2Jpx-Q/t1ADCsPTikoJ
[5] = C++ Working Draft N3242=00-0012 – 3.6.3 paragraph 4
[6] = C++ Working Draft N3242=00-0012 – 18.5 paragraph 5-8
[7] = WG14/N1256 Cinnuttee Draft — September 7, 2007 ISO/IEC 9899:TC3 – 7.20.4.2
[8] = https://groups.google.com/forum/?hl=en#!msg/microsoft.public.vc.mfc/iRo37usY3vU/4Txo3KHfi0MJ

STL and the <-operator

Introduction

The Standard Template Library (STL) adds a lot of fundamental functionality to C++. One of its most prominent features are containers. Containers can be used to store any kind of objects. Various different containers are available for the different requirements a developer might have. Some of the containers are optimized for random access, while others are very efficient when it comes to sorting objects.
To be able to sort objects, the STL containers (and functions) make use of comparators and/or an object’s <-operator. That way it becomes quite easy for developers to create classes which can be stored in a container. But there are a couple of requirements for these comparators, as this paper lays out.

Strict Weak Ordering

Let’s assume we have a simple class called “Car”:

class Car
{
        // member variables
private:
        int m_Color;
        int m_Type;

        // constructors
public:
        Car(int color, int type) : m_Color(color), m_Type(type) { }
};

class Car

{

// member variables

private:

int m_Color;

int m_Type;

// constructors

public:

Car(int color, int type) : m_Color(color), m_Type(type) { }

};

Next we define a <-operator for our “Car”-class by sorting it by its color and its type:

class Car
{
        // member variables
private:
        int m_Color;
        int m_Type;

        // constructors
public:
        Car(int color, int type) : m_Color(color), m_Type(type) { }

        // operators
public:
        bool operator<(const Car& operand2) const { return m_Color < operand2.m_Color || m_Type < operand2.m_Type; }
};

class Car

{

// member variables

private:

int m_Color;

int m_Type;

// constructors

public:

Car(int color, int type) : m_Color(color), m_Type(type) { }

// operators

public:

bool operator<(const Car& operand2) const { return m_Color < operand2.m_Color || m_Type < operand2.m_Type; }

};

Now we create 2 instances of the class:

Car car1(1, 1);
Car car2(1, 2);

1 2	Car car1(1, 1); Car car2(1, 2);

If we’d call: bool bsmaller = car1 < car2; // bsmaller = true the result would be as expected (since car1.m_Type < car2.m_Type).
Now let’s put these cars in a set:

std::set<Car> Carpark;
Carpark.insert(car1);
Carpark.insert(car2);

std::set<Car> Carpark;

Carpark.insert(car1);

Carpark.insert(car2);

So far, so good. We have a container with two cars, so what? — Let’s put another one into the container and see what happens:

Car car3(2, 1);
Carpark.insert(car3);

1 2	Car car3(2, 1); Carpark.insert(car3);

Outch… That results in a runtime error at best, or undefines behavior at worst.

<-operator requirements

What went wrong?
Well, the problem lies within our defined <-operator and the fact that the set-container uses it to try to put our cars into an order. If we compare car2 with car3, we get contradictory results:

bool compare1 = car2 < car3; // compare1 = true: 1 < 2 || 2 < 1;
bool compare2 = car3 < car2; // compare2 = true: 2 < 1 || 1 < 2;

1 2	bool compare1 = car2 < car3; // compare1 = true: 1 < 2 \|\| 2 < 1; bool compare2 = car3 < car2; // compare2 = true: 2 < 1 \|\| 1 < 2;

Therefore, the set doesn’t know how to sort these objects in its internal red/black-tree.
For most of the STL functions/template classes which require a comparator, a so called strict weak ordering comparator is required. Such a comparator is defined by fulfilling the following requirements:

the <-operator imposes an order:
if (a < b) then !(b < a)
an object is never smaller than itself (i.e. it can’t be ordered before itself):
a < a = false
the <-operator can be used to check objects for equality:
if (!(a < b)) && !(b < a)) then a == b
the ordering is transitive:
if (a < b) && (b < c) then (a < c)

So one might come to the following great solution to the problem and say: “Let’s sort objects by their memory address!”

bool operator<(const Car& operand2) const
{
        return this < &operand2;
}

bool operator<(const Car& operand2) const

{

return this < &operand2;

}

Nice idea. That comparator meets all the above given requirements, since an object’s address is unique, if run on a single PC (at no time two objects can occupy the same memory address) plus this idea has the advantage that no additional memory (for instance for a unique identifier used to order the objects) is required.
As long as there is no special requirement to keep objects sorted in a special order within a container this can be a feasible solution. However, it’s not completely safe under all circumstances, as the following chapter will uncover.

Copy Constructor and =-operator

Some of the STL functions/containers make use of an object’s assignment-operator or its copy constructor. For instance there is a function called make_heap(). That function creates a copy of the first object and in addition uses the assignment operator of the class of the contained objects to swap objects. That way a heap is created. So why is this problematic?
Well, the functions are designed under the following assumption:
The <-operator compares objects based on their content AND neither the copy constructor nor the assignment operator alter the object’s order.
Given as a general example, the assertion in the following code is expected to be true: if (a < b) { c = a; a = b; b = c; assert(b < a); }
If we use the object’s address within our <-operator, that’s no longer true. Assume a and b have the following addresses: a = 0x1; b = 0x2;
To make it easier to see the problem further assume that each object stores one integer: a.i = 1; b.i = 2;
Before the swap, a is considered smaller than b (since 0x1 < 0x2). Now we swap the objects: c = a; a = b; b = c;
As you see, the objects changed their content: a.i = 2; b.i = 1; but switching should not have an impact on the comparator; hence, assert(b < a) should be true since b now contains the content of a and a contains the content of b, but it isn’t!
Remember, we wrote the <-operator to compare the objects based on their addresses — and these haven’t changed — so a is still smaller than b (since 0x1 < 0x2).
So we changed the order of the objects and the STL functions don’t know what to do about it (resulting in an error or undefined behavior). We need another way to come up with an implementation for our operator.

Comperator Template

Though our initial <-operator meets the first two requirements, it lacks transitivity and therefore can’t be used to put objects into a unique order. We can correct this, by using the following template to write a comparator which sorts an object based on comparing multiple member variables:
For an object of class “A” with “n” member variables m[0, n) where each member variable type provides a <-operator:

bool operator<(const A& operand2) const
{
        return (m[0] < operand2.m[0]) ||
                !(operand2.m[0] < m[0]) && ((m[1] < operand2.m[1]) ||
                !(operand2.m[1] < m[1]) && ((m[2] < operand2.m[2]) ||
                [...]
                !(operand2.m[n-2] < m[n-2]) && (m[n-1] < operand2.m[n-1])[...])));
}

bool operator<(const A& operand2) const

{

return (m[0] < operand2.m[0]) ||

!(operand2.m[0] < m[0]) && ((m[1] < operand2.m[1]) ||

!(operand2.m[1] < m[1]) && ((m[2] < operand2.m[2]) ||

[...]

!(operand2.m[n-2] < m[n-2]) && (m[n-1] < operand2.m[n-1])[...])));

}

The function compares the object’s first member variable. If the current object’s first member variable is less than the second object’s one, it returns true. If it isn’t, it checks both member variables for equality by making use of the second requirement for <-operators (if (!(a < b)) && !(b < a)) then a == b).
Due to the order of the parentheses in the expression, only in case that the first member variable is equal, it compares the second member variable and returns true, if the first one’s is smaller than the second one’s. The procedure is then repeated for all remaining member variables.
Applying that template to our “Car”-class, would result in the following operator:

bool operator<(const Car& operand2) const
{
        return (m_Color < operand2.m_Color) ||
                !(operand2.m_Color < m_Color) && (m_Type < operand2.m_Type));
}

bool operator<(const Car& operand2) const

{

return (m_Color < operand2.m_Color) ||

!(operand2.m_Color < m_Color) && (m_Type < operand2.m_Type));

}

That’s it. We now have a working strict weak ordering operator.

Conclusion

Writing a <-operator helps a lot to more conveniently work with STL-containers. However, the developer has to be aware of the additional requirements for the implementation and must be careful to make sure that these requirements are met. Failure to do so can easily result in bugs introduced into the code which are really hard to trace down, since they can occur randomly and not all of the logical errors of an <-operator can be traced down by additional checks within the STL implementation.
Nevertheless, having a properly written <-operator at hand is the basis to make use of most of the STL-functions and improves productivity as well as increases code maintainability.

References

[1] S. Kuhlins, M. Schader, 2005. Die C++ Standardbibliothek. 4th ed. Berlin, Heidelberg, New York: Springer. Ch.1.3.
[2] Accredited Standards Committee WG21/N1043, 1996, Working Paper for Draft Proposed International Standard for Information Systems–Programming Language C++. [internet] Available at: http://www.open-std.org/jtc1/sc22/open/n2356/
[Accessed 23 February 2009]. Ch.23.1.2.
[3] P. J. Plauger, A. Stepanov, M. Lee, D. R. Musser, 2001. The C++ Standard Template Library. ed. Upper Saddle River: Prentice-Hall p.134