C++ Standard Template Library

• A standard, well thought out set of C++ templates for collections and algorythms.
• Recommended by John Schlag during the design review.
• The Standard Template Library is a new C++ library that provides a set of easily composable C++ container classes and generic algorithms (template functions).
  • The container classes include vectors, lists, deques, sets, multisets, maps, multimaps, stacks, queues and priority queues.
  • The generic algorithms include a broad range of fundamental algorithms for the most common kinds of data manipulations, such as searching, sorting, merging, copying, and transforming.
• The Standard Template Library: http://www.cs.rpi.edu/~musser/stl.html
• STL Generic Algorithm Reference: http://www.cs.rpi.edu/projects/STL/htdocs/stl.html
• STL Container Classes: http://www.cs.rpi.edu/~musser/container.html
• STL Iterator Classes: http://www.cs.rpi.edu/~musser/iterator.html
• ObjectSpace STL<ToolKit> Examples: http://www.xraylith.wisc.edu/~khan/software/stl/os_examples/examples.html
• The Standard Template Library Site: http://www.csc.calpoly.edu/~yyu/classes/stl.htm
• The Standard Template Library Page: http://ugweb.cs.ualberta.ca/~nelson/stl/stl.html
• STL FAQ: ftp://butler.hpl.hp.com/stl/stl.faq
• Mumit's STL Newbie guide: http://www.xraylith.wisc.edu/~khan/software/stl/STL.newbie.html
• Views - a C++ Standard Template Library Extension: http://www.zeta.org.au/~jon/STL/views/doc/views.html
  • A view is an abstract container whose contents are determined by applying a filtering transformation to an encapsulated domain of elements. In the most general case, a view is defined in terms of the encapsulated domain, a filtering predicate and a transformation function.
  • A view's encapsulated domain is an entity that behaves like an abstract container. In particular it defines an iterator class that conforms to the interface of an STL bidirectional iterator and two member functions (begin, end) that generate appropriately initialised iterators. Any instance of an STL container that supports use of a bidirectional iterator conforms to the specification of a domain used here. Although a domain is usually implemented by a physical container, it need not be. The header file domain.h contains an example of a domain (scalar_domain) built from a non-container.
  • An important specialisation of a view is a class known as a subdomain. A subdomain is a view whose transformation function is implemented by the identity function. In other words, a subdomain is the subset of the encapsulated domain that complies with the subdomain's predicate.
  • It should be noted that an important property of a view is that it is not formed by copying the encapsulated domain. Instead a view is implemented by defining new iterator classes that adapt to iterators of the encapsulated domain. The end result is that the user uses a view that behaves to all and intents and purposes like a normal STL container.
• There is really only one con in using the STL: Code bloat.
  • Templates are known to cause enormous bloating in the sizes of executables. Suddenly your tiny 100k app is now 500k. Alhough the STL is efficient (an understatement), to achieve this efficacy, in-lining of code is used often which often enlarges code size. Proper design and reuse of code helps you avoid instantating 10 instances of differing types.
  • STL does adds bit more complexity to your existing C++ code, with the use of operator overloading and templates: stuff that should be used in your existing code anyhow. It does requires you to conform to its set of rules so that the generic algoritms like sort or search can access data properly and perform as expected.
  • i.e Every container class must have certain operators defined for it, ++, *, --, etc.
• A solution to the polymorphic class problem in STL: http://www.cpsc.ucalgary.ca/~kremer/STL/ref2.html
  • A serious complaint about STL attacks the very paradigm on which STL is based. One of STL's central tenants is that containers directly contain there objects, and this is the root of many of its efficiency claims. But in doing this, STL runs contrary to one of the very important tenants in object oriented programming: polymorphic references. An alternative solution is to change the behavior of pointers rather than containers. One could make a new reference template class who's destructor would take care of destructing its referent. One of problems with this solution is that it defeats a lot of the efficiency of the STL.The STL goes to great lengths to efficiently store its objects in blocks (separating memory allocation/deallocation and construction/destruction). The Ref2 class blatantly allocates and deallocates its referents one at a time! Run time efficiency is also compromised by the extra level of indirection. It is not clear that there any possible way around the extra-level-of-indirection problem for containers of polymorphic classes.