A place where programmers can discuss various programming topics and experiences.



Bitten by an STL Gotcha...again

I was recently using an STL map container and hit one of those "STL gotchas" that I had forgotten about.  I figured I would pass along what I found and the changes I made.  As everyone already knows an STL map is a sorted associated container which takes a key-value pair. The existing code I had, which was using an std::map, actually contained unique key-value pairs. What I mean is that each pair was only inserted into the map once and the pairs were never updated by inserting the same key twice. When I went to change this code I realized I would need to change the values of existing items in the map. Here's some sample code to explain what I was doing:


typedef std::map<std::wstring, std::wstring> MyMap;
typedef std::pair<std::wstring, std::wstring> MyMapEntry;

// Insert a value with key "MyKey".
MyMap theMap;
theMap.insert(MyMapEntry(L"MyKey", L"MyValue1"));

// Update the value associated with key "MyKey."
theMap.insert(MyMapEntry(L"MyKey", L"MyValue2"));

When I went to run this code and iterated through my map I noticed that the value associated with key "MyKey" was actually "MyValue1"!!! What the heck is going on? Well, the insert() routine is a little tricky here (evil if you ask me). If you are inserting a new item into the map, everything works fine. If you are attempting to overwrite an existing item, it sees that it is there and doesn't update it. Nice... So, I tried the use of operator[] to update my map and this worked. Here's what the second iteration (no pun intended) of the code looked like:


typedef std::map<std::wstring, std::wstring> MyMap;
typedef std::pair<std::wstring, std::wstring> MyMapEntry;

// Insert a value with key "MyKey".
MyMap theMap;
theMap[L"MyKey"] = L"MyValue1";

// Update the value associated with key "MyKey."
theMap[L"MyKey"] = L"MyValue2";

So, now that it is working I should just let it go right? Wrong. I remembered a Scott Meyer's article awhile back where he mentioned how each of the mechanisms for inserting/updating items in a map can affect efficiency based on how you use them. Here's the basic gist of things:

  • insert should only be used to insert new items into a map.
  • operator[] should only be used to update existing items.

But this is obviously a royal pain because how do you know if an item is already in a map without searching for it first? It can't be more efficient to search for an item first and then decide how to insert/update it? This is where lower_bound comes into play. This routine will return an iterator to the first element in a container with a key that is equal to or greater than a given key. Once you get an iterator to that point in the map you can determine if the key really exists by invoking key_comp. If the key matches, you know you've found your existing item and you can update it. If the key doesn't match you now have an iterator to where that item SHOULD be inserted into the map. So this "search" operation is not wasted after all. You can use this location "hint" to insert your new item into the map. Meyers also mentioned that insert will run in amortized constant-time because of the hint. So here's how you would write the earlier example given what we know now:


typedef std::map<std::wstring, std::wstring> MyMap;
typedef std::pair<std::wstring, std::wstring> MyMapEntry;

// Insert a value with key "MyKey".
MyMap theMap;
theMap.insert(MyMapEntry(L"MyKey", L"MyValue1"));

// Assume you don't know whether an item has already been inserted
// after this point *grin*
MyMap::iterator iter = theMap.lower_bound(L"MyKey");
if ((theMap.end() != iter) && 
     !(theMap.key_comp()(L"MyKey", iter->first)))
{
    iter->second = L"MyValue2";
}
else
{
    theMap.insert(iter, MyMapEntry(L"MyKey", L"MyValue2"));
}

Now the example above is pretty simple but when you have code that performs a number of insertions in numerous locations, it is easy to not know whether an item exists in a map. You could write a template function as well (which is what I did). Until next time...

- Gilemonster

Labels:

posted by Gilemonster @ 2:02 PM, , links to this post




ATL 7.0 String Conversion Classes

If you've ever written Win32 code that is compiled for both ANSI and Unicode you've probably used the ATL 3.0 string conversion classes and their macros (e.g. W2A, A2W, T2A, A2T, etc.). They have been very useful but unfortunately have problems. Microsoft has alleviated a number of these issues in ATL version 7.0. This article gives a brief overview of those fixes and how the use of these classes has improved in version 7.0.

ATL 3.0 string conversion had the following problems which are fixed in version 7.0.

The main reason why ATL 3.0 had issues relates to where strings are stored and when they are freed. All converted strings were stored on the stack and they were not freed until the calling function returned. This means that if you had a routine that never returned (i.e. a separate "watch-dog" thread that never returns unless your application stops running) your converted strings were never freed. This could put tremendous strain on a thread's stack because of how large a string is and how often they are allocated. In version 7.0, the ATL now destructs the string when the object goes out of scope. It also checks the size of the string and if it is too large for the stack, it will store the string on the heap. So, small strings will be stored on the stack, but large ones will be allocated on the heap. Because the strings are destructed when they go out of scope, it is now safe to use the classes in loops because you know that when a loop iteration completes, the string will be destructed. This also makes them safe for use in exception handling code (e.g. catch(MyException &e)). Another nice improvement is the ability to leave that pesky USES_CONVERSION definition out of your code. It always annoyed me and I'm glad to see it go. :-)

Now that we've seen a quick overview of how the new classes are safer, let's look at how to use them because it is drastically different and if used like the older macro code you will get undefined results. If you want to use the new macros, you'll need to change your code. Below is the form of the macros that I stole from the MSDN:

CSourceType2[C]DestinationType[EX]

where:

Here are some simple examples of how to use the new macros. Note: I hate LPCSTR and LPWCSTR so you'll always see me use char * and wchar_t * whenever I can (probably not a good practice though). :-)

// Figure 1:
// Convert a UNICODE string to ANSI.
void 
ConvertUnicodeToAnsi(wchar_t * pszWStr)
{
   // Create a local instance of the CW2AEX class and construct
   // it using a wchar_t *.
   // Note:  Here you will notice that I am using CW2A which is 
   // a typedef macro of the CW2AEX class.
   CW2A pszAStr(pszWStr);

   // Note: pszAStr will become invalid when it goes out of 
   // scope.  In this example, that is when the function
   // returns.
}
// Figure 2:
// How to use a temporary instance of the CA2WEX class.
void
UseTempConvertedString(char * pszAStr)
{
   // Create a temporary instance of the CA2WEX class
   // and use it as a parameter in a function call.
   SomeSampleFunction(CA2W(pszAStr));

   // Note the temporary instance created in the
   // above call is only valid in the SomeSampleFunction
   // body.  Once the function returns, the temporary
   // string is destructed and no longer valid.
}
// Figure 3:
// How NOT to use the conversion macros and classes.  This
// example uses the new classes but applied using the old
// programming style.
void
BadFunction(wchar_t * pszWStr)
{
   // Create a temporary instance of CW2A, save a 
   // pointer to it and then use it.
   char * pszAStr = CW2A(pszWStr);

   // The pszAStr variable in the following line is an invalid pointer,
   // as the instance of CW2A has gone out of scope.
   ExampleFunctionA(pszAStr);
}

Figures 1 and 2 are pretty straight forward, but Figure 3 should be discussed further. In ATL 3.0, this is how we used the conversion classes. It should be noted that this code structure is no longer valid and will produce undefined results. Because of the new scoping of the conversion libraries, an invocation of the CW2AEX constructor cannot be used as we would expect. Figure 3 shows that the pszAStr variable does not contain a valid pointer even though it appears it should. If you need a converted string throughout the scope of a function, you should declare a local instance of the CW2AEX class on the stack and use the appropriate parameters during object construction (e.g. CW2A pszAStr(pszWStr);).

Specify a Custom Buffer Size
The default buffer size for the new ATL classes is 128 characters. If you need to change the default buffer size for certain types of conversions, use the EX macros and specify a new buffer size. This is defined as a C++ template. Here is an example:

// Figure 5:
// Specify a new buffer size with C++ template syntax.
void
UseCustomBufferSize(wchar_t * pszWStr)
{
   // Use a 16-character buffer.
   SomeFunction(CW2CAEX< 16 >(pszWStr));
}

The new ATL 7.0 string conversion classes are a much needed improvement over their 3.0 siblings. Of course you don't have to change all your code to use them if you don't want to. If you are concerned about application performance then you should consider updating your code. You will be able to use the classes in a number of places previously unavailable and that is pretty convenient. You can remove your old "work-around" code because of the safety of the new classes. I plan on looking at my own code and estimating how much it will take to upgrade my ATL usage to version 7.0. I might not be able to make the full change but I am least going to look at what the cost/benefit ratio is. And for new code I'll only use the new 7.0 classes. You should at least consider the same. Until next time...

- Gilemonster

Labels:

posted by Gilemonster @ 12:10 PM, , links to this post




Exception Handling Warnings in Visual Studio

Have you ever seen this cryptic little C++ compiler warning before in Visual Studio 7.x (.NET 2003)?

cl: Command line warning D4025: overriding '/EHs' with '/EHa'

I've seen it a number of times but always ignored it because other articles have said that "the compiler knows better." Well, the compiler might know better but I want to know why it knows better. So let's dissect this warning.

In Visual Studio, you can specify the Exception Handling model in the Code Generation property page of a C++ project. What you are selecting is whether or not the compiler uses an asynchronous exception model or a synchronous exception model. The asynchronous model is an older exception handling mechanism where the compiler assumes any instruction can generate an exception (hardware). This significantly increases the overall code size because the compiler must have mechanics for tracking the lifetime of objects that cannot unwind. The synchronous model is new and tells the compiler that exceptions can only be thrown with a throw statement. Because the compiler can now assume that exceptions will only be thrown by a throw statement or at a function call, all that extra object lifetime tracking code is not supplied by the compiler. The MSDN states that hardware exceptions can still be caught using the synchronous model, "... However, some of the unwindable objects in the function where the exception occurs may not get unwound, if the compiler judges their lifetime tracking mechanics to be unnecessary for the synchronous model."

So how in the world did you get the aforementioned compiler warning in the first place? There are a couple of things to look for.

Note: Structured exception translators (for the uninitiated) are used so that C exceptions (raised always as of type unsigned int as opposed to C++ exceptions which can be raised of any type) can be handled by a C exception wrapper class and therefore attributed a type. This allows a matching C++ catch handler to catch a C exception. If you have C code mixed in your C++ project that uses structured exception translators, you will have to use the asynchronous exception model or the compiler will throw the above warning.

In VS 7.x, it has been documented that the inability to select the asynchronous exception model ('/EHa') in the project properties dialog was a bug. To get around this in 7.x, you need to select "No" for the "Enable C++ Exceptions" property. Then go to the "Command Line" property and add "/EHa" in the "Additional options" section. This will allow you to enable C++ exceptions in your projects. Here's a screenshot of the VS 2003 .NET C++ Code Generation properties dialog. This bug was fixed in version 8 and you can now select "Yes" to the "Enable C++ Exceptions" property with a value of "Yes With SEH Exceptions (/EHa)." Here's a screenshot of the updated dialog.

For my particular project, I had some C code that used structured exception translators. So that was the reason for my warning. Therefore, I disabled the option above, and added "/EHa" as an additional command line property option. In general, enabling C++ exceptions in your VS projects should always be considered thoroughly (required in my opinion) and you should never disregard warnings like this one (as I did). For this particular case, the compiler was smart enough to fix the setting at build time, but that is not always the case. Know and understand your project settings and fix all warnings if possible. Until next time...

- Gilemonster

Labels:

posted by Gilemonster @ 11:08 PM, , links to this post




Quick Observation on STL string Comparisons

I was looking through some code this week and I noticed a few lines of code that caught my eye. The lines of code were doing basic STL string comparison using the non-member overloaded operator== function. I remembered that the STL also provides an overloaded set of compare functions for strings and wondered why you would use the overloaded operator functions instead of compare. I did a bit of reading and found that there are reasons for using one over the other.

The easiest of the comparison mechanisms is obviously to use operator==. You can use it to compare string objects, string literals that are quoted, and traditional C-style string pointers. The nice thing is that it (and other operator routines) doesn't have to create temporary string objects. Here's a simple example:

#include <string>
using namespace std;

std::wstring strFirstName = L"Billy";

if (L"Billy" == strFirstName)
{
    // Do something
}
else if (L"BILLY" == strFirstName)
{
    // Do something else
}
else if (L"BillyBoy" == strFirstName)
{
    // Do something else
}

The above sample shows the simplicity of using operator==. It also should show that its use should be limited to comparing simple character sets or single characters. A value of true will only be returned when the two character sets being compared match identically with respect to length and ASCII character code (meaning "A" != "a").

The compare routines provide a mechanism for performing lexical comparisons and other more precise string comparisons. Instead of returning true or false, three values are returned.

  • 0: the operand string is lexically equal to the parameter string.
  • 1: the operand string is greater than the parameter string.
  • -1: the operand string is less than the parameter string.

You can also use the other overloaded compare routines to further specify what your lexical queries compare. Here are some examples.

#include <string>
using namespace std;

wstring strOperand = L"Billy Bob",
        strParameter = L"Billy Bob's Barbecue";

// Standard use of compare
int intComparisonVal = strOperand.compare(strParameter);

// Further specification examples
size_type iOperandStartIndex = 0,
          iNumOperandCharsToCompare = 5;

// The second example specifies the starting index of the operand
// string and how many characters in the operand string to compare.  
// So you can compare part of the operand string with the parameter
// string.
intComparisonVal = strOperand.compare(iOperandStartIndex,
                                      iNumOperandCharsToCompare,
                                      strParameter);

// The third example goes further by also specifying the starting 
// index of the parameter string and how many characters to compare 
// in the parameter string.  So you can specify part of the operand
// string with part of the parameter string.
size_type iParamStartIndex = 0,
          iNumParamCharsToCompare = 5;
intComparisonVal = strOperand.compare(iOperandStartIndex,
                                      iNumOperandCharsToCompare,
                                      strParameter,
                                      iParamStartIndex,
                                      iNumParamCharsToCompare);

// My last example shows how to compare the operand string against
// a standard C-style string.
const wchar_t * strParameterCStyle = L"Billy Bob's Barbecue";
intComparisonVal = strOperand.compare(strParameterCStyle);

There are other examples that further demonstrate the remaining overloaded compare routines which I have left out for simplicity. And you can see that they give you the ability to lexically compare STL strings and C-style strings with greater precision than using the non-member operator==. But, when do you choose one over the other and what are the details? Here's what I have learned as a set of general guidelines concerning STL string comparisons:

  • When doing simple string comparisons where you want to exclude any unneeded overhead, use the operator routines. They first compare the operand and parameter string lengths and only if they are equal does it do a character by character ASCII value code comparison.
  • When you need more precise comparisons, use the compare routines as desired. You can compare substrings which is more useful than an "all or nothing" string comparison where applicable.

So, after reading all this mess I went back and examined the code mentioned at the beginning of this article. The code was written correctly and the string comparison was being used correctly. Anyway, I thought this was a quick and simple topic. Until next time...

- Gilemonster

Labels:

posted by Gilemonster @ 1:18 PM, , links to this post




Know Your C++: Virtual Functions

Polymorphism is one of three programming paradigms that give a language the ability to support object-oriented programming. In C++ this is implemented via virtual functions. Before we can understand virtual functions, we must first learn about function call binding.

When writing code, we frequently implement function declarations and definitions. In order for the code to compile, the compiler must match up the function call with the address of the associated function body. This process is known as binding. When the compiler and linker are able to successfully match the two before code execution, it is called early binding. Because polymorphism requires binding at runtime, C++ must provide an additional mechanism in order to support this. Matching the function call with its associated body at runtime is called late binding. C++ uses virtual functions to support late binding. When a function has the keyword virtual prepended to its declaration, the C++ compiler knows that function call binding will occur at runtime. Since compiler and linker know that a function body address will not be matched with an associated call at compile/link time, it creates a unique VTABLE for each object type that contains virtual functions. This table contains the addresses of each virtual function body for a particular object type. Along with the VTABLE, a vpointer (e.g. VPTR) is created/added to each object that is instantiated. The vpointer points to the appropriate VTABLE for that particular object type. So, for each object you create (that contains virtual functions), a vpointer is created, which knows the correct VTABLE to which it must point. And, this VTABLE contains the addresses of all the function bodies for that object type. So at runtime, your are guaranteed that your code will always have an associated function body for each function call. Still with me? Let's look at an example to clarify the concept.

class Base
{
public:
    Base();
    ~Base();

    void PrintStuff();

    // Virtual function declaration
    virtual long MorphMePlease();
};

// Virtual function definition
long
Base::MorphMePlease()
{
    return 0;
}

class Derived : public Base();
{
public:
    Derived();
    ~Derived();

    // Derived implements its own version of the
    // virtual function by using the same function
    // signature and removing the keyword virtual 
    long MorphMePlease();
};

// Derived function definition that overrides the Base class'
// virtual function.
long
Derived::MorphMePlease()
{
    return 1;
}

// A non-class member function.
long 
SomeNonMemberFunction(Base * ptrObj)
{
    // If a Base pointer is passed to this function,
    // Base::MorphMePlease() is called.  If a Derived
    // pointer is passed to this function, Derived::MorphMePlease()
    // is called.
    return (ptrObj->MorphMePlease());
}

In the above example you see that our Base class implements a virtual function called MorphMePlease() and that our Derived class overrides that function with its own implementation. Depending on what you pass into the non-member function SomeNonMemberFunction() either the Base or the Derived class' function can be called. How is that? When a pointer to a Derived object is passed in, it is implicitly upcast to a Base pointer. Even though the cast is performed, the object's vpointer is unchanged, and therefore still points to the VTABLE of Derived function addresses. This type of functionality demonstrates the ability to change functional behavior based on object type at runtime. This is the polymorphism we mentioned earlier.

So what happens with pure virtual functions? If by definition, they don't have a default definition, how does the compiler treat them? Well, as we mentioned earlier, the compiler must guarantee that every function call be associated with a corresponding function body address. If this were not guaranteed, we'd have all kinds of runtime errors when a function call was invoked that had no body (imagine the madness...). When the compiler sees that an object type has a pure virtual function, it reserves a row in the VTABLE for the associated function body, but doesn't actually insert the address (b/c there isn't one). Of course, this makes the VTABLE for that object type incomplete. Since the table is incomplete, the compiler cannot guarantee safe execution of that object's code. Because of this, the compiler will throw an error if an object of that type is instantiated anywhere in the compiled code. Because you cannot actually instantiate this object type, it becomes what is known as an abstract class type. Let's take a look at our previous example using pure virtual functions instead.

class Base
{
public:
    Base();
    ~Base();

    void PrintStuff();

    // Pure virtual functions require that a 
    // derived class define the function body.
    virtual long MorphMePlease() = 0;
};

class Derived : public Base();
{
public:
    Derived();
    ~Derived();

    // Derived class defines the function body
    // and is therefore allowed to be instantiated.
    long MorphMePlease();
};

// Derived function definition that defines the 
// Base class' pure virtual function
long
Derived::MorphMePlease()
{
    return 1;
}

In our updated example above, we notice the Base::MorphMePlease() function declaration is assigned to zero. That assignment signals to the compiler that a function is pure virtual (and therefore makes the class abstract). You will also notice that the Base::MorphMePlease() function definition is not provided. If you tried to provide one the compiler would barf and say you need to make up your mind b/w virtual and pure virtual functions (paraphrasing of course *grin*). If you were to remove the declaration and definition of the Derived::MorphMePlease() function, the Derived class would also become abstract and therefore not instantiatable. This is because the Derived object type's VTABLE would be incomplete as well.

Now that virtual functions and call binding have been explained, there are a few more points that need mentioning. First, the initialization of the VTABLE and vpointer structures is performed during object construction. The compiler provides this hidden code for you in your constructor and therefore you don't have to write it. Second, be careful about how you cast objects up/down the inheritance tree. Casting down or casting from a base object to a derived object is not guaranteed to work and has additional performance overhead. This is because there is no runtime information which guarantees the downcast to succeed. Therefore, an explicit cast is required. It is safest to use the dynamic_cast() function to cast a base object to its derived type. dynamic_cast() performs a runtime check to verify the cast will succeed and then performs the operation. This additional runtime type verification is the performance overhead I hinted at earlier. If you know more about your object hierarchy during downcasting you might be able to save the performance overhead of dynamic_cast() and substitute it with static_cast(). static_cast() doesn't perform the runtime check and there isn't guaranteed to be a safe operation. The benefit is that it is faster than dynamic_cast(). If the downcast fails, it re