ustl.h

   1 // This file is part of the ustl library, an STL implementation.
   2 //
   3 // Copyright (C) 2005 by Mike Sharov <msharov@users.sourceforge.net>
   4 // This file is free software, distributed under the MIT License.
   5 //
   6 // ustl.h
   7 //
   8 /// \mainpage
   9 ///
  10 /// \section intro Introduction
  11 ///
  12 /// uSTL is a partial implementation of the STL specification intended to
  13 /// reduce code size of the derivative programs. Usually, the STL containers
  14 /// manage their own storage with new[] and delete[] operators, which create
  15 /// strongly typed storage. That is the standard way of allocating C++ object
  16 /// vectors, allowing appropriate constructors and destructors to be called on
  17 /// the allocated storage and ensuring that objects are copied via their copy
  18 /// operators. Although type safety is a good thing, placing memory management
  19 /// code into a template necessitates its reinstantiation for every template
  20 /// instance used by the derivative program. This produces substantial code
  21 /// bloat, that is frequently derided by C developers and used by them as
  22 /// an argument that C is better than C++. The uSTL implementation solves
  23 /// this problem by factoring memory management code into a non-template base
  24 /// class, ustl::memblock, which performs unstructured memory allocation. STL
  25 /// containers are then implemented as template wrappers for memblock to
  26 /// provide a measure of type safety. The result is that each template
  27 /// instantiation contains less code, and although it does not completely
  28 /// "disappear", due to the requirement for calling placement constructors
  29 /// on the allocated memory, most of it does, being replaced by calls to
  30 /// memblock methods. The base classes for unstructured storage management
  31 /// (cmemlink - link to constant memory, memlink - link to mutable memory,
  32 /// and memblock - owner of mutable memory) are, of course, also available
  33 /// for use as data buffers wherever those are needed, and streams that
  34 /// efficiently read and write binary data into them are also available.
  35 //
  36 /// \defgroup Containers Containers
  37 /// Here you'll find all the containers for your objects and data.
  38 //
  39 ///     \defgroup MemoryManagement Memory Management
  40 ///     \ingroup Containers
  41 ///     Classes that implement low-level memory management and form the base for
  42 ///     all containers in the library. Almost all functionality in the containers
  43 ///     is reduced to calls to these base classes through a great deal of inline
  44 ///     crunching by the compiler, and thus you end up storing all your data in
  45 ///     ustl::memblock objects with the container templates as mere syntactic sugar.
  46 //
  47 ///     \defgroup Sequences Sequence Containers
  48 ///     \ingroup Containers
  49 ///     Containers containing sequences of objects.
  50 //
  51 ///     \defgroup AssociativeContainers Associative Containers
  52 ///     \ingroup Containers
  53 ///     Containers containing associations of objects.
  54 //
  55 /// \defgroup Streams Streams
  56 /// Streams convert objects into flat data.
  57 //
  58 ///     \defgroup BinaryStreams Binary Streams
  59 ///     \ingroup Streams
  60 ///     Unlike the C++ standard library,
  61 ///     the default behaviour is very strongly biased toward binary streams. I
  62 ///     believe that text formats should be used very sparingly due to numerous
  63 ///     problems they cause, such as total lack of structure, buffer overflows,
  64 ///     the great multitude of formats and encodings for even the most
  65 ///     trivial of things like integers, and the utter lack of readability
  66 ///     despite ardent claims to the contrary. Binary formats are well-structured,
  67 ///     are simpler to define exhaustively, are aggregates of basic types which
  68 ///     are universal to all architectures (with the exception of two types of
  69 ///     byte ordering, which I hope to be an issue that will go away soon), and
  70 ///     are much more readable (through an appropriate formatting tool equipped
  71 ///     to read binary format specifications).
  72 //
  73 ///             \defgroup BinaryStreamIterators Binary Stream Iterators
  74 ///             \ingroup BinaryStreams
  75 ///             \ingroup Iterators
  76 ///             Iterators for using STL algorithms with binary streams.
  77 //
  78 ///     \defgroup TextStreams TextStreams
  79 ///     \ingroup Streams
  80 ///     Streams converting objects into streams of text.
  81 //
  82 ///             \defgroup DeviceStreams Device Streams
  83 ///             \ingroup Streams
  84 ///             Standard cout, cerr, and cin implementations for reading
  85 ///             and writing text through standard file descriptors.
  86 //
  87 /// \defgroup Iterators Iterators
  88 /// Generalizations of the pointer concept, allowing algorithms to treat
  89 /// all containers in a unified fashion.
  90 //
  91 ///     \defgroup IteratorAdaptors Iterator Adaptors
  92 ///     \ingroup Iterators
  93 ///     Iterators made out of other iterators.
  94 //
  95 /// \defgroup Algorithms Algorithms
  96 /// STL algorithms are the heart of generic programming. The idea is to
  97 /// separate algorithms from containers to take advantage of the fact that
  98 /// there are fewer distinct algorithms than typed containers. This is
  99 /// diametrically opposed to object oriented programming, where each object
 100 /// must contain all functionality related to its internal data. You will
 101 /// find, I think, that in practice, generic programming is not terribly
 102 /// convenient because it prevents you from encapsulating all your data.
 103 /// The best approach is to compromise and have raw data classes that will
 104 /// be manipulated by algorithms and to treat the rest of the objects as
 105 /// stateful data transformers.
 106 //
 107 ///     \defgroup MutatingAlgorithms Mutating Algorithms
 108 ///     \ingroup Algorithms
 109 ///     Algorithms for modifying your data in some way.
 110 //
 111 ///             \defgroup SortingAlgorithms Sorting Algorithms
 112 ///             \ingroup MutatingAlgorithms
 113 ///             Algorithms for sorting containers.
 114 //
 115 ///             \defgroup GeneratorAlgorithms Generator Algorithms
 116 ///             \ingroup MutatingAlgorithms
 117 ///             Algorithms for generating data.
 118 //
 119 ///             \defgroup NumericAlgorithms Numeric Algorithms
 120 ///             \ingroup MutatingAlgorithms
 121 ///             Algorithms generalizing mathematical operations.
 122 //
 123 ///             \defgroup SetAlgorithms Set Algorithms
 124 ///             \ingroup MutatingAlgorithms
 125 ///             Algorithms for working with sorted sets.
 126 //
 127 ///             \defgroup HeapAlgorithms Heap Algorithms
 128 ///             \ingroup MutatingAlgorithms
 129 ///             Algorithms for generating and manipulating heaps.
 130 //
 131 ///             \defgroup SwapAlgorithms Swap Algorithms
 132 ///             \ingroup MutatingAlgorithms
 133 ///             Algorithms for swapping elements.
 134 //
 135 ///             \defgroup RawStorageAlgorithms Raw Storage Algorithms
 136 ///             \ingroup MutatingAlgorithms
 137 ///             Algorithms for manipulating unstructured memory.
 138 //
 139 ///     \defgroup ConditionAlgorithms Condition Algorithms
 140 ///     \ingroup Algorithms
 141 ///     Algorithms for obtaining information about data.
 142 //
 143 ///             \defgroup SearchingAlgorithms Searching Algorithms
 144 ///             \ingroup ConditionAlgorithms
 145 ///             Algorithms for searching through containers.
 146 //
 147 ///     \defgroup PredicateAlgorithms Predicate Algorithms
 148 ///     \ingroup Algorithms
 149 ///     Algorithms that take a functor object. Avoid these if you can,
 150 ///     and carefully check the generated assembly if you can't. These
 151 ///     algorithms can and will generate prodigious amounts of bloat
 152 ///     if you are not very very careful about writing your functors.
 153 //
 154 /// \defgroup Functors Functors
 155 /// Functors are inteded to be passed as arguments to \link PredicateAlgorithms
 156 /// predicate algorithms\endlink. Ivory tower academics make much of this capability,
 157 /// no doubt happy that C++ can now be made to look just like their precious lisp.
 158 /// In practice, however, functors and predicate algorithms are mostly useless.
 159 /// An iterative solution using \ref foreach is usually far simpler to write
 160 /// and to maintain. Furthermore, functional programming in C++ often
 161 /// generates much bloat and slowness, which is difficult to avoid with any
 162 /// but the most primitive functors. Try them if you wish, now and then, but
 163 /// compare with an iterative solution to see if the compiler really can see
 164 /// through all your functional trickery.
 165 //
 166 ///     \defgroup FunctorObjects Functor Objects
 167 ///     \ingroup Functors
 168 ///     Objects that wrap other functors to provide new functionality.
 169 //
 170 ///     \defgroup FunctorAccessors Functor Object Accessors
 171 ///     \ingroup Functors
 172 ///     Because C++ is so very unsuited to functional programming, trying
 173 ///     to do so may require a lot of typing. These accessor functions
 174 ///     are somewhat helpful in making functional constructs more readable.
 175 //
 176
 177 #ifndef USTL_H_6A5A10410D2CD7FC2D78FE470F045EB7
 178 #define USTL_H_6A5A10410D2CD7FC2D78FE470F045EB7
 179
 180 #include "ustl/uspecial.h"
 181 #include "ustl/umap.h"
 182 #include "ustl/umultimap.h"
 183 #include "ustl/ustack.h"
 184 #include "ustl/uqueue.h"
 185 #include "ustl/ofstream.h"
 186 #include "ustl/unumeric.h"
 187 #include "ustl/ulist.h"
 188 #include "ustl/uheap.h"
 189 #include "ustl/ustdxept.h"
 190
 191 #endif
 192