Overview of U++ containers - NTL
NTL is a library of container and algorithm templates. It is designed to solve some problems we see in current C++ standard library STL.
Each single NTL container template that can store more than one element has random access. This random access is as fast as access using iterators so for iterating elements you can use indices rather than iterators and we recommend this approach.
An important feature of NTL are requirements for stored elements. Unlike STL, which has single copy-constructible and assignable requirement for whole library, NTL makes requirements on per container and even per method basis. This way NTL allows direct storing of any type of elements. NTL provides two or even three flavors for each basic ADT kind of container relative to requirements for elements.
Vector flavor of containers requires types to be moveable and have either deep copy constructor and operator, pick constructor and operator or default constructor. Containers of this flavor have word Vector in their their names, with the exception of Index which is also of this flavor. This flavor has the best runtime characteristics.
Array flavor of containers has no common requirements for elements, but is less efficient. You can use it to store even polymorphic types. Type of stored elements does not even have to be defined at the point of instantiation, so you can use Array flavor to create recursive data structures. Another feature of this flavor is that references to elements are never invalidated. Containers of this flavor have Array in their name.
Containers as return values
NTL allows containers to be used as return values, in single constant time operation. It is allowed by defining specific transfer semantics.
Basic random access containers
This kind of containers allows adding/removing elements at the end of the sequence in amortized constant time. As these containers are basic building blocks for NTL, their names are the same as names for all three flavors. Vector flavor allows direct access to underlying C vector of elements. Vector and Array flavors allow removing and inserting of elements at any position (with complexity based on number of elements moved).
This kind of containers allows adding/removing elements to/from both beginning and end of sequence in constant amortized time. It is well suited for FIFO operations. BiVector and BiArray are two flavors of bidirectional containers.
Basically, this kind of container provides random access sequence that allows adding elements at the end of sequence in constant amortized time (much like basic random access containers) with one unique feature: it allows fast retrieval of position of element with specific value. Hashing is used for this operation. Indexes represent ideal building-blocks for any associative operations. Index and ArrayIndex are two flavors of indexes.
As both index flavors are built on top of according basic random access containers, they provide read-only access or even pick operations to this container. That means you can supply elements to Index by picking Vector in Index constructor or get Vector of elements of Index in low constant time pick operation. Same is true for Array and ArrayIndex.
Also, as most of functionality added to basic random access containers is same for both Index and ArrayIndex, most of operations are shared in common template class AIndex, which represents index container without concrete flavor. Index and ArrayIndex are derived from this AIndex, adding few operations specific for their flavors.
Basically, maps are just simple compositions of Index and basic random access container to store values, thus getting classical map design. In find operation, position of key in Index is retrieved and value from basic access container at the same position is returned. This design also allows accessing both keys and values using indices.
In case of maps, keys are always stored in Index, that means that flavor is relative only to type of values (and keys must be moveable). VectorMap, ArrayMap and SegtorMap are flavors of maps. As with Index, the common operations of this flavor are implemented in template base class AMap. Also, picking operations for any part of maps are available.
InVector, Sorted maps
NTL provides random access containers with fast insertion at arbitrary position, which scale well to milions of items. These containers then provide basis for 'sorted maps' that are using binary search. Sorted maps are useful when range-search is required.
One is a container that can hold one or none elements of the specified type or a type derived from it. Its functionally rather close to standard library auto_ptr but with improvements in direction of NTL, like transfer semantics, moveable concept (yes, you can have Vector< One<T> >) and others. Also it is important from conceptual view, because it is it is treated like a container rather than a pointer.
Any is a container that can store none or single element of any type. Container provides Is<T> method to determine the type of stored element and Create<T> method to create the element in container.
Buffer is a simple random access container without growing properties.