Topic : Crash Course on STL
Author : Osvaldo
Page : << Previous 2  
Go to page :

which is actually a function. STL has protocols related to such parameters: Generator, UnaryFunction, BinaryFunction, Predicate, BinaryPredicate, and Adaptable
versions of everything (e.g. AdaptableBinaryFunction) with some metalevel facilities to query types of arguments and results.

Functors can be either plain C functions, or objects that look like functions because they redefine the function invocation operator -- operator() -- like our example. That's how we can do first-class functions, because we have full-blown objects that can do things like memorizing data for the comparision. I can use the functor like this:

SubjectCIt i = find_if(subjects.begin(), subjects.end(),

This will search objects of type Subject (code from real app) in the collection named extent; the search matches the string value in subjName against the names of Subjects obtained by calling the accessor name(). The SubjectCIt is an automatically generated (by macros...) typedef, so I don't have to remember that my Subjects are stored in a vector nor write an horrible templatized expression like:

vector<Subject*>::const_iterator i = ...

If you are a skeptic and think this will generate bloated code, you can do an optimized build (in a good compiler anyway) and check the output Assembly listing, and verify that the code is exactly equivalent to this:

for (Subject const* i = subjects._begin; i != subjects._end; ++i)
    if (!strcmp((*i)->_pvt_name_attr, subjName))

Where is the Functor object? It goes away, it's totally killed by the optimizer. The whole thing translates in compile time to a raw loop in the internal data of the vector and Subject classes. Of course, you may get less optimization with more complex iterators / containers, but this is the typical case by a large margin.

Developers experient in other languages (e.g. Smalltalk or functional languages), or CS-educated (e.g. Lambda calculus), will notice that functors look like closures / first-class methods. In this respect they are just a hacked emulation of these (just like Java inner classes). C++ has no way to attach an environment to a method pointer, which makes impossible the more advanced uses of closures. Functors attempt to go beyond method pointers by allowing you to store in the "method object" copies of (or references to) variables which would not otherwise be accessible from their code (you can do exactly the same with Java's inner classes)... this is not very elegant but it works in most cases, without the overhead of full closures.

A post-final trick in the It Gets Weirder Each Day Dept. Templates can implement entire parse trees, so one can model operations via templates and solve complex expressions statically. You can even do recursion in compile time. Look at this "wonderful" code...

template<int N> class Factorial
    public: enum { value = N * Factorial<N-1>::value };
class Factorial<0> // Specialized template instantiation
    public: enum { value = 1 };
const int x = Factorial<5>::value;
// Calculates 5! during compilation!!
// Generated code is equivalent to: "const int x = 120". :-)

1.Differently from most C/C++ hacked designs, STL is a major, strong and very formal design. The part about performance guarantees makes it cool for realtime apps or any demanding work. I consider it a brilliant piece of work. Check it in the source.
2.Not beautiful and easy as ST, Java or Eiffel, but STL gives major benefits (some of them not available in "superior" languages) with no cost. People like the author of the article presenting the Factorial class above are very concerned with performance.
3.After you climb the learning curve, STL is productive and fun. I have written a parser generator and later entire distributed application servers on the back of STL. Performance is terrific and the code has proved to be easy to work and reuse (for the C++ initiated, of course). Robustness is not a problem either -- STL forces you to use zillions of pointers, but these are more "civilized" pointers, if you follow the rules (read fourty-two times: "learn the thing before writing apps").
4.This thing stresses compiler technology insanely. It took over half a decade for some vendors to catch up. The implementation of STL is so incredibly complex that it forced the ANSI committee do do lots of changes in the language (kinda tail-wagging-the-dog situation). BTW, The ANSI C++ standard adopted templates RADICALLY. Previous libraries have been rewritten, so now string and iostreams are STL Containers, and everything they could templatize (like complex or min/max) was deeply changed in the innards (and sometimes in the interface). That's why some compilers ship with two separate C++ libs (the old-and-compatible, plus the new-and-cool).
5.Existing C pointers, arrays and functions are first class citizens in STL. All legacy code can be mixed with STL code, and new code can resort to plain-old-superfast primitive things whenever necessary. For example,
int[100] arr;
int* found = find(arr, &arr[100]); // that's STL's find<>()!
6.Almost all Containers provide powerful Iterators, and almost all Algorithms require simple Iterators. Then, the Algorithm X Container matching is not 100% but it's very near to that, and you won't usually want the unavailable matches -- e.g. running the QuickSort algorithm on a file (not because you never want to sort a file, but because this algorithm is not suited for files). Some algorithms come in several flavors and you pick the most suited to your Container or to your Things (for example, some sorting algorithms are better when the data is "almost sorted", while others degenerate in the same case).
7.C++ programmers have no real OO, but they work hard to emulate it, and then they can write Quake :-) Curiously, a huge part of the new ANSI library consists in abstract protocol specifications decoupled from real implementation (classes and functions); this is very similar to the Smalltalk ANSI document. Computer Science is sometimes funny.

Page : << Previous 2