Jump to content
  • Advertisement
  • entries
    146
  • comments
    435
  • views
    198844

Checked Standard Algorithms and Iterators

Sign in to follow this  
Washu

406 views

The standard library in C++ is replete with many different algorithms. The majority of these algorithms take in iterators which indicate a range over which the algorithm will operate. An example of this would be the std::copy method.

These ranges have a problem though, how can we guarantee that they are valid? What is to prevent you from passing in a set of iterators that were invalid? The answer is nothing. Furthermore, invalidating iterators is ridiculously easy in some containers, like std::vector. This, of course, is a consequence of the containers definition, and is unavoidable. But, with all of these potential bombs lying around our code, how can we ensure that we don't detonate one of them by accident?

The answer to this is to use a checked standard library. In a checked library alternative iterators and algorithms are provided that allow for runtime checks to ensure the validity of the ranges being addressed and the operations being performed. Since the checks are determined by flags at compile time, there is no inherit overhead in a release build, as they can be disabled.

For the standard library implementation I'll be looking at, the checked members exist in the stdext namespace (standard extensions). The checked members, under the stdext namespace, all begin with checked_. There also exist, in the stdext namespace, algorithms labeled unchecked_. These algorithms are provided for those times when you need to use an unchecked iterator somewhere, but wish to enforce safety throughout the program in all other cases.

With Visual Studio 2005 (the checked implementation I'll be dealing with) you can define a macro, _SECURE_SCL, to be 1. In this case only checked algorithms will be used, except in cases where you explicitly specify an alternative. Standard functions will automatically route to the checked versions, and container iterators will be checked iterators. Calls to checked functions with unchecked iterators will result in compile time messages.

Pointers and arrays are not checked, and must be wrapped in checked iterators in order to pass them to checked algorithms. As you can see in the example below

int myArray[10];
stdext::checked_generate_n(myArray, 10, IncrementalFillOp(1)); //Error C4996
stdext::generate_n(myArray, 10, IncrementalFillOp(1)); //Error C4996

stdext::checked_generate_n(stdext::checked_array_iterator(myArray, 10), 10, IncrementalFillOp(1)); //safe
stdext::generate_n(stdext::checked_array_iterator(myArray, 10), 10, IncrementalFillOp(1)); //safe

The error message is quite confusing, so just remembering the error code should be sufficient (although it can be caused by other functions, such as using the insecure versions of the CRT functions). The error will occur twice, once on the line where the function was used, and once where the function is declared.

Using the unchecked algorithms, for instance when you need performance and have already assured the validity of your arguments, is just as simple as using the original standard algorithms, as shown below

int myArray[10];
stdext::unchecked_generate_n(myArray, 10, IncrementalFillOp(1)); //Unsafe, but no error

While you can use the unchecked algorithms as much as you want, it is not recommended except for extreme cases. What is the point of using a checked standard library, if you are just going to bypass it in the first place. Performance aside, you aren't likely to notice any difference at all, since you're in a debug build ANYWAYS.

Added Container Access Safety
There is one nagging problem, something like...

std::vector myVector;
myVector[1] = 2;

Can still result in malformed runtime behavior. To combat this there is another compile time flag that you can specify. When _SECURE_SCL_THROWS is defined as being 1 then access operations, like the vector index operator, will throw exceptions (the same exception as the at() member function would).

std::vector myVector;
try {
myVector[0] = 1;
} catch(std::out_of_range& ex) {
std::cout<}


While this doesn't provide 100% error proofing, as you can still take the address of the first element and then add a value to that pointer that would place it past the bounds of the vector, it does allow for code that is much more secure, while preserving performance in the areas where it is important.

Some Notes on Performance
As is most likely the case, some of you are thinking something along the lines of... 'Well, that's all nice and dandy, but I am making the next uber monster killer awesome game! I will need all the performance I can eek out of the system!' Well, news for you, your performance bottlenecks won't be on the checked portions for the most part, and those areas where PROFILING indicates it is a problem, you can just switch it over to the unchecked operations. The biggest performance killer in an application is improper choice of an algorithm or data-structure. Simply changing what algorithm or data-structure you use can get you performance gains that all the SSE2 code in the world would never have obtained. The trick here is to profile first, then optimize the bottlenecks.

Anyways, I know some of you are probably wondering where the XSLT journal entry vanished too...well, I could tell you, but then I would have to kill a newbie and Fruny has informed me that I am to NOT poach on his hunting grounds anymore, so.... it will have to stay a mystery for a bit longer.
Sign in to follow this  


2 Comments


Recommended Comments

Excellent entry, as usual [grin]

So with VC8 you can just define both/either of those names in the project settings for 'debug profile' and it'll work? Straight out of the box?

If so, that's awesome - I'm gonna have to add this to my list of things to try!

Quote:
I could tell you, but then I would have to kill a newbie

I seem to remember announcements against newbie flaming and newbie bashing... is newbie killing a convenient loophole these days?

One last thing - any more entries on cool new things in VC8 would be very interesting!
Cheers,
Jack

Share this comment


Link to comment
Quote:

So with VC8 you can just define both/either of those names in the project settings for 'debug profile' and it'll work? Straight out of the box?

Not exactly, the first one must always be defined if you want to use the second one. The second one mostly affects release mode builds. If you want to enable just debug mode checking, well, the next post will cover that stuff.
Quote:

If so, that's awesome - I'm gonna have to add this to my list of things to try!

It is quite awsome, and fairly intuitive to use as well.
Quote:

Quote:
I could tell you, but then I would have to kill a newbie

I seem to remember announcements against newbie flaming and newbie bashing... is newbie killing a convenient loophole these days?

Well...it's not exactly a loophole, it's just not covered at all!

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!