C++: getting min/max values of boost::graph attributes

Just spend "some" time on some stupid issue on this problem, so I though I might as well post that here, if it can be useful to someone.

Say you have a boost::graph using so-called "bundled properties" (aka "inner properties) and you want to find the minimum and maximum value of the attributes. The standard library has this nice minmax_element() algorithm.

But... how can I use it on a graph inner properties ?

Say you have this kind of vertex, used in a graph definition (here undirected, but should also work for a directed graph):

struct vertex_properties
{
  int val;
};

typedef boost::adjacency_list<
    boost::vecS,
    boost::vecS,
    boost::undirectedS,
    vertex_properties
> graph_t;

typedef boost::graph_traits<graph_t>::vertex_descriptor vertex_t;

As an example, consider this program, creating a 3 vertices graph (and, yes, no edges here):

graph_t g;
    
vertex_t v1 = boost::add_vertex(g);
vertex_t v2 = boost::add_vertex(g);
vertex_t v3 = boost::add_vertex(g);
    
// Set vertex properties
g[v1].val = 1;
g[v2].val = 2;
g[v3].val = 3;

To find the min/max value of the attributes, just call the algorithm with the right lambda function:

auto pit = boost::vertices( g );
auto result = std::minmax_element(
 pit.first,
 pit.second,
 [&]                                              // lambda
 ( vertex_t v1, vertex_t v2 )
 {
  return( g[v1].val < g[v2].val );
 }
);

This will return a pair of iterators on the min and max graph indexes. So, to get the results:

    std::cout << "min=" << g[*result.first].val
     << " max=" << g[*result.second].val << '\n';

C++: erasing elements of std::vector using a lambda

Removing elements from a vector is a task that one can encounter pretty often and that isn't as easy as one could think.

The simplest case is when the index of the unwanted element is known. The std::vector class provides a first form of the erase() member function that takes an (const) iterator as argument.

Thus, if I want to remove, say the 10th element, it's as easy as:

    std::vector<whatever> myVec;
//... fill with more than 10 elements
    myVec.erase( myVec.begin() + 9 );

And if you want to remove the 3 elements between positions 10 and 12, it will be the second form of this function, which has two arguments:

    myVec.erase( myVec.begin() + 9, myVec.begin() + 12 );

(Yes, the second argument defines the first one you want to keep)

But what happens when you want to remove elements based on their value ? Say remove all elements that have value foo (assuming that value is of type whatever).

This is a task for std::remove(). It actually does not remove anything, it just switches element around so that the ones to be erased will be at the end, and it returns an iterator pointing on the first element to be erased. The next step is to feed that iterator to std::vector::erase().

The code will using its second form:

    myVec.erase(
        std::remove(            // returns iterator on
            myVec.begin(),      // first element to
            myVec.end(),        // be removed
            foo
        ),
        myVec.end()
    );

(This is known as the Erase–remove idiom.)

Next, what if you want to remove elements based on some property they have ? Consider for example a vector of vectors:

   std::vector<std::vector<Whatever>> myVec2;

And now the task is to remove elements that hold less than 2 elements. Okay, so we need to check every element, and decide to remove it or not.

This is a task for the second form of that same algorithm, remove_if(). Instead of a value, it takes as third argument a predicate, and will "remove" (move, actually) the considered element if that predicate returns "true". A predicate is usually implemented as a functor, which is an object of some class that defines the operator() and that returns a bool, based on the given value.

At first, this seems like a harsh constraint, as no one wants to declare a class for such a trivial task. But before C++11 came out, that was required (unless, maybe, using some Boost library). Or else, we needed to iterate through the vector and test each element, copy it or not, and swap:

   vector<vector<whatever>> newv;
   newv.reserve( myVec.size() ); // to avoid resizing when using push_back
      for( size_t i=0; i < myVec.size(); i++ )
         if( myVec[i].size()<MinSize )
            newv.push_back( myVec[i] );
   std::swap( myVec, newv );

This is where C++11 and lambdas come in. A lambda can be seen as a sort of "anonymous inline function", that captures variables in scope. Here, as the function iterates over all the elements, each of them will be a std::vector.

A lambda is made of three parts:

• [how capturing variables happens],
• (the functions arguments),
• {The body of the function}.

The complete code:

   std::size_t MinSize = ... (some value);
   myVec2.erase(
      std::remove_if(
         myVec2.begin(),
         myVec2.end(),
         [&]( const std::vector<whatever>& vw ) // lambda
            { return vw.size() < minsize; } 
     ),
     myVec2.end()
   );

More on c++ lambdas.

Subversion: colordiff fo html files

(Mostly a reminder:)

Say you have some software project, hosted on some Subversion repository. You happily edit your files, and before committing you want to have a quick look at the edits you have done.

No problem, as simple as:
> svn diff 

But this outputs lots of text, not easily readable. Ok, lets' go with colordiff:
> svn diff | colordiff

And then you get drowned under floods of nice and flashy colors, and you have to painfully scroll your terminal. Well, what else ? A simple redirecting in a file won't keep the colors.

This is where another magic tool shows up: aha. Yeah, that's his name. It's a "ANSI to HTML" converter. Install it with sudo apt-get install aha, and then, go:
svn diff | colordiff | aha >mydiff.html

For conveniency, you can now add a new target to you makefile:

diff:
     svn diff | colordiff | aha >mydiff.html
     xdg-open mydiff.html

Thus, entering make diff at the shell will show you the current edits you have done up to now.
xdg-open is just the Gnome app that opens the default application associated with a file type. On Windows, just use the file name alone, as this OS has some mechanism to open the file with the default application when given a file name.

Edit 20141224: a small improvement: in order to keep track of all these generated diff files, you can append date/time to the filename so that each new one doesn't erase the previous one. This can be done easily with bash (not that hard for Windows either, but no time at present to figure that out):

ifndef COMPSPEC
NOW=$(shell date +%Y%m%d_%H%M)
BROWSER=xdg-open
endif

diff:
     svn diff | colordiff | aha >mydiff_$(NOW).html
     $(BROWSER) mydiff_$(NOW).html

Notice the conditional, so that this makefile should also work out-of-the-box under Windows (except for the time/date, but if you send it to me, I'll publish it ;-) )

Writing portable makefiles

Edit 2016-10-21: I notice this post comes on first page of Google "portable makefile" request, so I thought I'd might add some context. This post was written when I was struggling with this kind of stuff, and should be taken as a "proof of concept" post. For me, this is definitely over, as I (almost) completely quit using Windows, being for several years now a happy GNU/Linux user. Readers must be aware that although some tricks are given here, it is certainly not the best approach for setting up a portable build system. If you are in that situation, the best way to go is probably CMake, as it is today the de facto standard tool.

This note is about GNU Make makefiles syntax, and how to write them to keep them OS-independent as much as possible.

1- Introduction: computers and file systems

When it comes to computers and their associated filesystem, there are two worlds on earth.
One that considers that a path to a file spells this way:
path/to/the/file
and the other world that considers that the correct syntax is:
path\to\the\file

This may sound silly (and it is) but it can lead to some complications. Not only because these two worlds use a different symbol, but mostly because they both have a special meaning for the other symbol.

To put it clearly, on a Linux machine (that uses the '/' path separator), the backslash has a special meaning in some situations (shell scripts, makefiles, ...) meaning "I have no more room on this line, lets keep on and continue the current command on next line" (and that trick is very valuable for readability). And it follows what is a convention in C and C++ source files.
 
In the other world (MS Windows), the default shell (cmd.exe) interprets the slash character as the option separator. For example: del /F path\to\file.txt

And, no, at least in XP, the Windows shell DOES NOT accept both path/to/file and path\to\file, as it is frequently said in many places. Try to do something like del path/to/file to check. Maybe this has changed with Windows 7, 8, 11 or 42, I'm not really interested, but with Windows XP's shell, it does-not-work.The cause of that misunderstanding is probably that system calls (that is, the functions you call from inside a program), DO accept forward slashes or backslashes in paths).

Anyway, the two shells (Linux/bash and Windows/cmd.exe) are sooo different, only insane people would consider trying to write a "compatible" script, running equally on both systems (1).

However, there is one situation where a same command semantic must be executed equally in those two different environments: makefiles

Basically, a makefile is a set of commands that are executed by the shell.
Say for one target, we want to erase some file, even "read-only" ones. On one environment, this must be done with the following command:
rm -f path/to/file
while on the other, it will be:
del /F path\to\file

The question is: how can a write that command in my makefile so that it expands in these two different syntaxes at runtime? And more generally, how do I write portable makefiles ?

2 - Handling command names

First, lets manage the different command names (and their options). That's the easiest. Just define a variable holding the name of the command, that will hold different values depending on platform. The easiest way to detect the platform is to check for the existence of a Windows-only environment variable, say ComSpec (but some sources relie on SystemRoot that can be used too).

ifdef ComSpec
    RM=del /F /Q
else
    RM=rm -f
endif

This will be in the upper part of the makefile, before any recipes. Then, in the recipes, just use $(RM) in place of the command.

3 - Handling paths

Secondly, you need to handle the path separator. Two situations need to be handled:
- paths to explicit files (the example above),
- automatic paths, build using make's wildcards and substitution functions.

Remember that you need to care for this only for system calls. Whatever the platform, GNU Make, gcc or other "regular" development tools handle very well paths with forward slashes, whatever the platform. To make it clear, say we have these lines that follow the classical target-prerequisite-command scheme:
mytarget: path/to/file
   $(SOMECOMMAND) path/to/file

The first line will do fine, but the second line will generate an error on Windows if SOMECOMMAND expands to a built-in shell command.

3.1 - Processing explicit paths

First, for the explicit paths, we can proceed with the same trick: define a variable holding the required separator ('\' or '/'), then use this variable in the commands.

ifdef ComSpec
    PATHSEP2=\
else
    PATHSEP2=/
endif

Ha. Unfortunatly, this does not work, because the backslash is interpreted by make as the "keep on same line!" request, and not as a character. Ok, so we need to escape that backslash, in order to fool make:

ifdef ComSpec
    PATHSEP2=\\
else
    PATHSEP2=/
endif

Funilly, this works half ways: the definition is accepted, but the variable holds the two backslashes! Fortunatly, the Windows shell accepts paths that looks like path\\to\\file (don't ask me why...)

Almost done. This still does not work: the above definition adds a trailing space at the end of the variable, i.e. its usage in:
path$(PATHSEP2)file
will expand into:
path/ file  (or  path\ file  on Windows)
and that will not be ok, for sure!

So finally, we need to add the following definition and function call, that removes that ugly trailing space:
PATHSEP=$(strip $(PATHSEP2))

That way, an explicit erasing command in a makefile (for example) can be portably written as:
$(RM) path$(PATHSEP)to$(PATHSEP)file

Ok, now how about paths that are automatically build.

3.2 - Processing generated paths

For example, you usually define a variable holding all the object files, that is build from all the source files. If these are in a folder named src, and the object files are in a folder named obj, then you can define the list of the source files with:
SRC_FILES=$(wildcard src/*.cpp)

and the list of corresponding object files with (2):
OBJ_FILES=$(patsubst src/%.cpp,obj/%.o,$(SRC_FILES))

But heres comes the problem, trying to erase all the object files with:
$(RM) $(OBJ_FILES)
will expand on Windows as something like:
del /F obj/file1.o obj/file2.o obj/file3.o
and that will throw an error, because the shell will consider that what is behind the slash as some option.

Two solutions can be used:

• either use PATHSEP in the "patsubst" function call above:

OBJ_FILES=$(patsubst src/%.cpp,obj$(PATHSEP)%.o,$(SRC_FILES))

• either use the "subst function", that replaces some pattern in a string with another:

OBJ_FILES_CORRECT=$(subst \,/,$(OBJ_FILES))

But this latter solution implies the creation of another variable, which can be error-prone in dense makefiles.

4 - Command separator

Another problem that needs to be handled is the command separator. In many make tutorials, you see commands written this way:
cd MyFolder; SomeCommand Some Arguments
which means: "get down into folder MyFolder, and execute SomeCommand with Some Arguments"
This is an invalid syntax on Windows where the command separator is &.
So, again, the variable trick:

ifndef ComSpec
    CMDSEP=;
else
    CMDSEP=&
endif


and the above command will be written:
cd MyFolder $(CMDSEP) SomeCommand Some Arguments

5 - Debugging makefiles

Portable makefiles are also tougher to debug that ordinary makefile. You will run into countless issues, and each one might require some special treatment.

As you may know, you can prefix each make command with the special symbol '@', that will suppress the default echo to terminal. This is useful for the makefile user, that doesn't want to see all the steps of the build process: he just wants to get the job done, as quickly as possible.
But while writing the makefile (an debugging it), you will need all this information, so you don't use that prefix, of course...
   ... until you're done ! Then you want to deliver a nice experience to the makefile user, and you carefully edit your code to prefix each command with '@'
And then... Ah. Something got broken in the makefile when this new build step was added, but where exactly ? So you start again removing all these stupid '@' characters that you spend so much time to add!

Don't. Instead use again the good'ol variable trick. Instead of using the special character '@', prefix right away all of your commands with $(L). For example:
obj/%.o : src/%.cpp
    $(L)$(CXX) -o $@ -c $< $(CFLAGS)


And add the following lines in the first part of the makefile:
ifeq "$(LOG)" ""
    LOG=no
endif

ifeq "$(LOG)" "no"
    L=@
endif


This way, launching make with no special option will run silently, and in case of trouble, just tell your mate to run:
make <target-name> LOG=yes
and all the commands that are launched will (magically) appear on screen (3).

6 - Conclusion

These are some hints that can help you design more portable makefiles. I'll finish with one remark. For "big" projects, maybe you should rely on "makefile generators", that is, programs that do all these low-level tasks (and much more). The most known are CMake and the GNU set of tools, but others can be used.

Finally, one quote from "Managing projects with GNU Make": "... there is no such thing as perfect portability, so it is our job to balance effort versus portability."


(1) Unless you use a non-native modern script langage such as Python of course.
(2) In real life, the folders name would also be stored in variables, i.e. :
OBJ_FILES=$(patsubst $(SRC_DIR)/%.cpp,$(OBJ_DIR)/%.o,$(SRC_FILES))
(3) Or in a text file if you redirect it, and that is usually a good idea when output starts to get large.

Des pièges de l'utilisation des références C++

Le langage C++ a introduit la notion de "référence", en sus des pointeurs du langage C. Les références permettent notamment la mise en oeuvre du polymorphisme, élément fondamental de la POO. De ce fait, on a parfois tendance à les considérer comme des "pointeurs-bis", permettant juste une syntaxe plus légère tout en ne "trimballant" que l'adresse de l'objet. Par exemple, lors d'un passage d'argument à une fonction:

void MaFonction( const MaClasse& objet )
{
   objet.FaireCeci();
}

Il y a cependant une petite subtilité, qui peut entraîner des erreurs. Cette particularité peu évidente pour le programmeur novice peut être résumée par la phrase:

La référence EST l'objet
Ce point clé trouve son illustration dans un cas fréquent, à savoir la permutation de deux objets selon une condition. La méthode naïve consiste à faire une permutation circulaire:

   MaClasse objet1;
   MaClasse objet2;
   ...
   if( condition )
   {
      MaClasse objetTemp( objet1 );
      objet1 = objet2;
      objet2 = objetTemp;
   }

Mais cette solution est évidemment peu adaptée en pratique: si les objets sont volumineux (comprendre:plusieurs ko ou plus), les performances sont médiocres: 3 copies de l'objet sont nécessaires.

La STL fournit aussi une solution: l'algorithme std::swap(). Mais en pratique, il fait la même chose.

On est alors tenté de travailler sur l'adresse de l'objet, et on pense alors naturellement aux pointeurs:

   MaClasse objet1;
   MaClasse objet2;

   MaClasse* p1 = &objet1;
   MaClasse* p2 = &objet2;

   if( condition )
   {
      p2 = &objet1;
      p1 = &objet2;
   }

// attention, dans la suite on doit travailler avec l'opérateur '->'
p1->FaireCeci();
p2->FaireCela();

Ceci fonctionne très bien.
Le piège consiste alors à se dire "les pointeurs, c'est mal, remplaçons tout ça par des références, c'est bien plus dans l'esprit du C++". Soit:

   MaClasse objet1;
   MaClasse objet2;

   MaClasse& r1 = objet1;
   MaClasse& r2 = objet2;

   if( condition )
   {
      r2 = objet1;
      r1 = objet2;
   }

// Ouf! Maintenant, je peux me passer de '->' et travailler avec '.'
   r1.FaireCeci();
   r2.FaireCela();

Et non! Le code ci-dessus est faux. En effet, comme indiqué précédemment, la référence EST l'objet. Donc si 'condition' est vrai, la première affectation (r2 = objet1;) écrase objet2, vu que r2 a été initialisé sur objet2: r2 et objet2 désignent le même espace mémoire. Son contenu est donc perdu, et on se retrouve avec deux objets identiques.

En conclusion, se souvenir que bien que leur utilisation soit bien moins fréquente que en C, l'utilisation des pointeurs reste parfois utile en C++.

A voir aussi:
* La FAQ Developpez
* LaFAQ de Marshall Cline, au paragraphe 8.5:
How can you reseat a reference to make it refer to a different object?
No way. You can't separate the reference from the referent.



Edit 201204: Comme noté ci-dessus, l'algo std::swap() réalisait des copies des objets, ce qui est inacceptable dans certains cas. La nouvelle norme du C++ (C++11) fournit l'algo std::move() qui s'appuie sur le fait que la "r-value" (objet temporaire situé à droite de l'opérateur d'affectation) n'est jamais réutilisé, et qu'on peut donc directement copier l'adresse. On peut donc désormais "encore plus" éviter les pointeurs bruts. Voir les détails ici.

C++ & STL : les pièges du conteneur 'vector'

Le conteneur 'vector' est très pratique d'utilisation mais souffre à mon avis d'un défaut majeur: il est trop tolérant avec l'utilisateur, ce qui se retourne après (souvent...) contre celui-ci.

Par exemple, l'opérateur [] est défini, ce qui rend l'usage de ce conteneur intuitif pour les programmeurs venant du C, en remplacement des tableaux. On pourra ainsi écrire:

vector<int> tab(10);
tab[0] = 3;

de la même façon qu'on écrivait en C:

int tab[10];
tab[0] = 3;

Mais ceci se révèle après coup TRES DANGEREUX. En effet il n'y a pas de vérification de la validité de l'indice dans cette notation. En vérifiant dans l'implémentation de Mingw, on y trouve le commentaire suivant:

This operator allows for easy, array-style, data access. Note that data access with this operator is unchecked and out_of_range lookups are not defined.

Ceci est d'ailleurs rappelé sur la page Wikipedia du conteneur 'vector'.

Et que ce passe-t-il en pratique ? Et bien, loi de Murphy oblige, ça arrive un jour ou l'autre (croyez moi...). Et donc, crash. Bon, un crash, soit, mais... et alors me direz vous ?
Et bien, ce type de crash est lié à une corruption mémoire, et le problème, c'est qu'il est extrêmement difficile à pister. Contre toute attente, le crash ne se produit pas lors de l'exécution de l'accès au vector, mais à un autre endroit du programme, là où rien de spécial n'est exécuté...

En conclusion, si vous avez moins de 5 ans d'expérience en C++, et que vous travaillez sur un projet conséquent en C++, ne jamais utiliser la notation '[]' mais TOUJOURS la méthode 'at()', qui effectue la vérification de validité d'indice.

* Liens:

• STL : voir wikipedia fr, ou wikipedia en.
• FAQ Developpez STL.
• un excellent cours de Bruno Garcia.

Edit 20121102: En fait, sous GCC, on peut activer le bound checking pour les conteneurs de la STL. Il suffit de compiler en définissant le symbole _GLIBCXX_DEBUG (soit l'ajout du flag -D_GLIBCXX_DEBUG). Ceci est décrit ici. Source: stackoverflow.com/questions/1290396.

Enhancement to the \todo command with doxygen

I use doxygen for my code development, and use a lot the \todo command: it allows me to quickly mention things that need to be done when I don't have time to do it at the moment. This way things don't get buried into my memory.

The problem is that this produces a list that is not sorted in any way: you can't distinguish between things that are important and things that are just some ideas that need to be tried. Just see an example of what an unordered list looks like, in some random project I came across: www.portaudio.com/docs/v19-doxydocs/todo.html.

If your list has 10 or less items, that's not too bad. However, if you manage a large project, you can easily end up with a list with several dozens of items, and this list then becomes useless: the day you happen to have some spare time, you just can't spot what's really important to do... I thought that there was some kind of feature lacking in doxygen, in order to produce some hierarchical "todo" list using different \todo commands (say, \todo1 for top-priority things to do, \todo2 for less important things, and so on).

So I suggested this feature on the doxygen list, to see if other people find it useful, and if it could be added to the wish-list (again, another "todo" list!)

I discovered that this was already possible, by defining an alias in the doxyfile. Thanks to Clemens Feige, he explained to me how to define new commands that do the job, based on the \xrefitem command.

Using this command is not obvious, so I post here the way to do it.

Using a text editor, open your doxyfile and find the ALIAS line, and add the following lines:

ALIASES += "todo1=\xrefitem todo1 \"High Priority Todo\" \"Todo high priority list\""
ALIASES += "todo2=\xrefitem todo2 \"Medium Priority Todo\" \"Todo medium priority list\""
ALIASES += "todo3=\xrefitem todo3 \"Low Priority Todo\" \"Todo low priority list\""

In your code, you can now use either \todo, that will end up in the classical unsorted "todo" page, or \todo1, \todo2, or \todo3. Run your doxyfile, and that's it!

For more about code documentation, you can check the following pages:

• docs.google.com/View?id=dgjz7z25_129f4sqrrdx
• en.wikipedia.org/wiki/Software_documentation
• en.wikipedia.org/wiki/Comparison_of_documentation_generators