Tom Lachecki

Keeping it low-key this week, let's re-iterate (lol) the conventional map-erase idiom in C++.

Iterating through the elements of a std::map is easy enough, but complication arises when you want to delete a few elements as you go.

The first naive approach might look a little like this:

#include <map></p> <p>int main() { typedef std::map<int, int> M; typedef M::iterator I; M m; /<em> (populate m..) </em>/</p> <pre><code>for (I it = m.begin(), end = m.end(); it != end; ++it) { if (it->first == 3) m.erase(it); // remove elements whose key is '3' }</code></pre> <p>}

Unfortunately, after you've erased the element from the map, the iterator pointing to it is invalidated. When the loop goes to run ++it ready for the next iteration, this invokes UB… meaning you should never do it. It's invalid.

So what to do? If you do ++it before performing the erase, then it's safe, but then you don't have the iterator to erase any more. You can use a copy:

for (I it = m.begin(), end = m.end(); it != end; ) { if (it->first == 3) { M::iterator copy = it; ++it; // increment ready for the next iteration m.erase(copy); // remove via original iterator } else { ++it; // just increment } }

Note the important change to the for declaration. The increment on each loop is replaced by the conditional increment in the body.

A shorter version of the same thing is:

for (I it = m.begin(), end = m.end(); it != end; ) { if (it->first == 3) m.erase(it++); else ++it; }

This works because it++ inherently makes a copy, performing the increment after the original value is sent to erase, but before the erase actually occurs.

Coming soon…

Other standard containers make this a lot easier; the next C++ standard, due for completion this year (or possibly in 2012), will fix this omission for std::map by allowing m.erase to return the next iterator automatically:

for (I it = m.begin(), end = m.end(); it != end; ) { if (it->first == 3) it = m.erase(it); else ++it; }

In an unprecedented feat of miraculousness, Freenode's ##C++ discussion channel saw — in the space of no more than twenty minutes — the same question asked twice of one of C++'s more subtle features. Just how do you declare a friend from the global namespace?

To demonstrate the scenario, consider the following code:

namespace N { struct S { friend ostream& operator<<(ostream& os, const S&); S() : x(0) {}; private: int x; }; } ostream& operator<<(ostream& os, const N::S& s) { return os << s.x; }</p> <p>int main() { N::S s; std::cout << s; // error: 'int N::S::x' is private }

Although the member variable N::S::x is marked private, friending the operator<< function should allow access to it; therefore, the expected output is "1". But not so!

The reason is almost disappointingly inelaborate. friend statements are, in fact, function declarations too.

That means that when you write friend ostream& operator<<(ostream& os, const S&) you're saying "there's a function with this signature, and it's allowed to access stuff in me". The problem here is that the function declaration is inside the namespace N, so you've managed to implicitly declare a function ostream& N::operator<<(ostream& os, const S&)… but your actual operator<< is in the global namespace. You've declared a function that you never define nor use.

Phew!

In itself this is harmless, but it does mean that your friend statement has nothing to do with the global operator<< that you actually use. Consequently, access to private or protected members from within it is still prohibited.

The most obvious fix here is to explicitly specify that you're declaring and friending a function in the global namespace, using the "::" operator (line 6):

namespace N { struct S; } ostream& operator<<(ostream& os, const N::S& s);</p> <p>namespace N { struct S { friend ostream& ::operator<<(ostream& os, const S&); S() : x(0) {}; private: int x; }; } ostream& operator<<(ostream& os, const N::S& s) { return os << s.x; }</p> <p>int main() { N::S s; std::cout << s; }

(I've also added a couple of now-necessary forward declarations.)

Going further

This is all well and good, but let's take a look at what happens when we befriend a different function. I've picked a simple one called F that takes a ref-to-const-S and returns an int:

namespace N { struct S; } int F(const N::S& s);</p> <p>namespace N { struct S { friend int ::F(const S& s); S() : x(0) {}; private: int x; }; } int F(const N::S& s) { std::cout << s.x; return 0; }</p> <p>int main() { N::S s; F(s); }

All that's really changed is that the function has a different signature.

The key difference here is that our operator<< returned ostream&, whereas our F returns int. One is a reference, and one is not. And the problem relates to parsing.

Let's take a look at the two friend statements side by side:

friend ostream& ::operator<<(ostream& os, const S&); friend int ::F(const S& s);

In the first example, it's clear to the compiler what you are doing. ostream& can only be a type (due to the placement of the & symbol, and a few other things) and the rest falls into place.

But in the second example things aren't quite so clear. The compiler doesn't care about spaces quite as much as you or I, and in fact the code would mean the same in all the following variations:

friend int ::F(const S& s); friend int :: F(const S& s); friend int:: F(const S& s); friend int::F(const S& s);

Notice how int::F could be seen as a function F inside a namespace int. However, int is a keyword and this would be quite illegal. The compiler knows this, so the example compiles successfully and means what you expect.

But what if we didn't use int? Still returning by value, let's use a return type that isn't a keyword:

namespace N { struct S; } N::S F(const N::S& s); // ^ note: yes, forward declaration is enough for // return-by-value in a function declaration!</p> <p>namespace N { struct S { friend S ::F(const S& s); S() : x(0) {}; private: int x; }; } N::S F(const N::S& s) { std::cout << s.x; return s; }</p> <p>int main() { N::S s; F(s); // error: ISO C++ forbids declaration of 'F' with no type }

The compiler now sees a declaration and befriending of a function S::F that returns nothing, which is illegal. Parsing fails. And although we've tweaked around with the code a couple of times, we've ended up with something otherwise completely valid: this code structure is hardly unusual.

The solution to rule them all

Fortunately, we can rely on our trusty parentheses to put the topic to rest once and for all. Check out the new friend statement:

namespace N { struct S; } N::S F(const N::S& s);</p> <p>namespace N { struct S { friend S (::F)(const S& s); S() : x(0) {}; private: int x; }; } N::S F(const N::S& s) { std::cout << s.x; return s; }</p> <p>int main() { N::S s; F(s); }

Bootnote

It may seem like I've been describing an edge case, but this really does come up more often than one might think. Hopefully this article can serve as some kind of reference for when that day comes.

For a while now, I've had a slightly frustrating problem with Windows key mappings. This week it became irritating, so I finally decided to look into a fix… or, at the very least, a workaround.

No Rights

It started with my work laptop. All the keys on it worked normally; I could select text by holding down either of the shift keys and pressing an arrow key. I could open a Remote Desktop connection to my PC at home and the keys still worked normally.

But there was just one stubborn Windows server in the lab that, over Remote Desktop, refused to listen to the right shift key. It's as if the right shift key did not exist.

It agreed that the left shift key definitely exists; of course, learning to type with a key on the other side of the keyboard, with a different hand, would be to undo over a decade of muscle memory.

Fortunately, I didn't have to use that lab server terribly often, and usually not for very long. So I would just get on with it.

Argh

At home I use a brilliant piece of software called Synergy to mate my work laptop to my personal desktop machine; it's essentially a KVM switch implemented in software, and without the 'M'.

I have a mouse and keyboard connected to my PC as usual, and when I take the mouse to the right-hand edge of my PC's screen, it jumps to the laptop screen and keyboard control goes with it. If I then take the mouse to the left-hand edge of my laptop screen, control jumps back to my PC. It's a brilliant way to fake a two-desktop solution across computers connected only by a LAN. Aside from some unreliable clipboard synchronisation, I've not had a problem with it.

Anyway, after swapping out my desktop PC and settling down with a new installation of Windows 7, I noticed that the keyboard mapping over Synergy was no longer behaving. When passing input through to my laptop, I could type capitals with either the left or the right shift key, but attempting to select text with the right shift key was a non-starter.

I failed to find any specific documentation on the issue and got increasingly fed up.

The work-around

Content at this point to work-around the issue in lieu of truly solving it, I turned to one of the many good keyboard re-mapping tools out there on the web: KeyTweak allowed me to trick my computer into thinking that Right Shift is actually Left Shift, which — after forcing a reboot on me — finally saw the end of this debacle.

If you run Windows Vista or Windows 7 and want to re-map your keyboard, be sure to get KeyTweak v2.3.0; many of the typical freeware download sites provide v2.2.0 and there doesn't appear to be a centralised homepage for the project.