okia reports that STL support has been one of the most requested features among Symbian developers. This is no surprise. In 2006, using C++ without STL is like driving a car without wheels. Recently, Penrillian released uSTL, a free, low-memory footprint version of STL for Symbian OS. Is uSTL a dream come true or is it a far cry from the real thing?

ISO STL?Essential but Elusive
Programmers using the Standard Library aren’t always aware of the complex inner-workings that make it work so smoothly. A typical STL implementation consists of hundreds of functions and class templates that interact with each other through sophisticated iterators, type traits, and function objects. Additionally, STL relies on advanced template features that push state-of-the-art compilers and linkers to their limits. Since mobile operating systems?including the latest versions of Symbian and Windows Mobile?support neither dynamic linking nor virtual memory management, porting ISO STL to these platforms is quite a challenge, to say the least. Developers have had to come to terms with this tough reality. Instead of using vector, string, and popular STL algorithms, they have to settle for makeshift container classes and watered down “algorithms” that try hard to impersonate those of STL. This state of affairs imposes significant limitations on the design of mobile applications. Yet considering the rigid limitations of mobile devices on the one hand, and the complex mesh of class templates, allocators, and algorithms that are needed for implementing STL, is there any hope for seeing something at least close to STL on contemporary mobile operating systems?

Enter uSTL
Mile Sharov decided to bite the bullet. By analyzing carefully the ISO C++ standard, he spotted out the impasses hindering the implementation of STL on mobile platforms. He acknowledged that full ISO compliance wouldn’t be feasible. But he also realized that for the average C++ programmer, the low-level implementation details rarely matter. What users are looking for is the familiar interface of STL containers, algorithms, and iterators. He decided to implement an STL clone called uSTL (the “u” stands for the Greek letter mu, meaning “micro”). uSTL is a partial implementation of STL that replaces template-based memory management classes with a classic 1990’s object-oriented design. Thus, instead of creating dozens of specializations from each template class, uSTL uses a simple inheritance model and virtual function overriding. The result is an odd beast: you immediately recognize the common look and feel of STL, but the underlying machinery is completely different.

The First String
Much of the complexity of the STL stems from the requirements imposed by ISO, which include support for two character types: char and wchar_t, and locales. To qualify as ISO compliant, a Standard Library implementation must support no less than eight console I/O objects: the famous cout and cin, as well as cerr and clog (frankly, who uses this one anyway?). If that’s not enough, each of these four fabs has wchar_t counterpart: wcout, wcin, wcerr, and wclog. Sharov eliminated much of this bloat. The result is a compact and manageable library, at the expense of ISO compliance. Take strings for example. In ISO STL, std::string is actually a typedef that stands for:

basic_string, allocator > 

If you want to use a wchar_t string, you need another specialization (i.e., class) called std::wstring. However, uSTL has only one string class called ustl::string. It’s similar to std::string but not identical.

ustl::string assumes all your strings are UTF8-encoded, and provides some additional functionality:

• The format() member function formats strings much like sprintf().
• An implicit const char * conversion operator.

Double Standards
Being able to compile the following code is every mobile developer’s dream:

int main (){    vector v;    v.resize (40);    for (size_t i = 0; i < v.size(); ++ i)	v[i] = i;    v.push_back (87);    v.insert (v.begin() + 20, 555);    v.erase (v.begin() + 3);}

With uSTL, this dream becomes reality. All it takes is a tiny macro that switches between "standard STL" so to speak, and uSTL:

#if USING_USTL #include  using namespace ustl;#else #include  using namespace std;#endif

There should be no observable difference between the uSTL and ISO STL versions of this program except size: the former uses less code under the hood, so for each vector specialization used, you save about 1 kilobyte of memory. 1 kilobyte doesn't seem like much, but notice that you get it for every specialization: vector, vector, and so on. More importantly, when using uSTL, you don't need to link your app against the bloated shared libraries/CRTs of ISO STL. Just to give you a clue: libstdc++ loads 918,502 bytes to the main memory while libustl loads only 196,784. That's about 80 percent less!

uSTL supports other STL containers such as list, stack, queue, map, multimap, multiset, and even some TR1 features, e.g., tuple. Another noteworthy feature is the ustl::matrix class which doesn't exist in ISO STL.

Island in the Streams
ustl::cin, ustl::cout, and ustl::cerr work mostly the same as their standard counterparts. For example:

#include using namespace ustl;cout << "Hello world!" << endl;cout << 456 << ios::hex << 0x1234 << endl;cerr.format("object address: 0x%08X
", &o);//format() is a uSTL extension

That's pretty much it for console I/O in uSTL. classes are not implemented yet. To perform file I/O, you create a string buffer, call read_file(), and then attach a stream to it. It's ugly but gets the job done.

The major difference between ISO STL and uSTL is that the former uses a distinct allocator per specialization, whereas the latter keeps all the memory management logic in a single base class. When ISO STL containers reallocate storage, they call new[] to create more storage and then copy the elements to the new destination. This technique incurs size and speed penalties. uSTL uses a different approach. It manages memory as an opaque, typeless block, and then uses the container templates to cast it to an appropriate pointer type. I know what you're thinking: bitwise copying of objects is a no-no, and you're right. However, uSTL doesn't copy elements; it merely moves them.

What's Still Missing
I've given you the impression that uSTL is a compact, smart and clutter free version of ISO STL. This is true in most part but there are a few caveats you should take note of if you plan to port existing apps to a mobile platform. The most noticeable deviation from ISO STL is the absence of standard function objects such as greater, less, etc. Sharov's rationale for this deliberate omission doesn't sound convincing. Indeed, some of STL's abstruse features don't have a place in a tightly packed implementation but function objects and predicates are too important to be completely dismissed. Additional unimplemented features include:

• File stream classes. This could cause porting difficulties but you can get by with read_file().
• deque and priority_queue.
• Heap algorithms such as push_heap(), make_heap(), etc.
• TR1 hashed containers (now officially called "unordered containers"), like unordered_map. This isn't a major issue since many existing ISO STL implementations don't offer these yet.
• wchar_t-oriented stream and string classes

Overall, uSTL 0.8 is much closer to ISO STL than I anticipated, in spite of its peculiar design. Although it contains a subset of ISO STL, it will suit the needs of the average C++ programmer who simply needs reliable and familiar building blocks such as vector, list, sort(), remove() and cout. Considering the shoddy classes and proprietary APIs that Symbian developers use as alternatives to containers and algorithms, uSTL is light years ahead. uSTL gets a major thumbs up!