STL Series

Lately, I am interested in C++ template. I would make a my kernel with c++ and template. so I am reading the books about template, design pattern and O/S. Today, In stl series, 1st

The concept of the STL is based on a separation of data and operations.

In a way, the STL concept contradicts the original idea of object-oriented programming: The STL separates data and algorithms rather than combining them. However, the reason for doing so is very important. In principle, you can combine every kind of container with every kind of algorithm, so the result is a very flexible but still rather small framework.

Containers

1. Sequence containers are ordered collections in which every element has a certain position. This position depends on the time and place of the insertion, but it is independent of the value of the element. For example, if you put six elements into a collection by appending each element at the end of the actual collection, these elements are in the exact order in which you put them. The STL contains three predefined sequence container classes: vector, deque, and list.
2. Associative containers are sorted collections in which the actual position of an element depends on its value due to a certain sorting criterion. If you put six elements into a collection, their order depends only on their value. The order of insertion doesn't matter. The STL contains four predefined associative container classes: set, multiset, map, and multimap.

In associative container, you can always use a binary search, which results in logarithmic complexity rather than linear complexity.

Vectors
A vector manages its elements in a dynamic array. It enables random access, which means you can access each element directly with the corresponding index. Appending and removing elements at the end of the array is very fast. However, inserting an element in the middle or at the beginning of the array takes time because all the following elements have to be moved to make room for it while maintaining the order.

To write generic code that is as independent of the container type as possible, you should not use special operations for random access iterators. For example, the following loop works with any container: for (pos = coll.begin(); pos != coll.end(); ++pos) { ... }
However, the following does not work with all containers: for (pos = coll.begin() ; pos < coll.end(); ++pos) { ... }
The only difference is the use of operator < instead of operator != in the condition of the loop. Operator < is only provided for random access iterators, so this loop does not work with lists, sets, and maps. To write generic code for arbitrary containers, you should use operator != rather than operator <.
Every algorithm processes half-open ranges. Thus, a range is defined so that it includes the position used as the beginning of the range but excludes the position used as the end. This concept is often described by using the traditional mathematical notations for half-open ranges:
[begin,end)
or
[begin,end[





Expression
Kind of Inserter
back_inserter (container)
Appends in the same order by using push_back()
front_inserter (container)
Inserts at the front in reverse order by using push_front()
inserter (container ,pos)
Inserts at pos (in the same order) by using insert()


If you really want to remove elements in one statement, you can call the following statement: coll.erase (remove(coll.begin(),coll.end(), 3), coll.end());
Why don't algorithms call erase() by themselves? Well, this question highlights the price of the flexibility of the STL. The STL separates data structures and algorithms by using iterators as the interface. However, iterators are an abstraction to represent a position in a container. In general, iterators do not know their containers. Thus, the algorithms, which use the iterators to access the elements of the container, can't call any member function for it.
Manipulation algorithms (those that remove elements as well as those that reorder or modify elements) have another problem when you try to use them with associative containers: Associative containers can't be used as a destination. The reason for this is simple: If modifying algorithms would work for associative containers, they could change the value or position of elements so that they are not sorted anymore. This would break the general rule that elements in associative containers are always sorted automatically according to their sorting criterion. So, not to compromise the sorting, every iterator for an associative container is declared as an iterator for a constant value (or key). Thus, manipulating elements of or in associative containers results in a failure at compile time.