狭路相逢勇者胜: STL

Showing posts with label STL. Show all posts

Tuesday, March 11, 2008

Introduction to STL

a C++ library of container classes, algorithms, and iterators

STL is a generic library, meaning that its components are heavily parameterized: almost every component in the STL is a template.

STL includes container classes: classes whose purpose is to contain other objects. The STL includes the classes vector, list, deque, set, multiset, map, multimap, hash_set, hash_multiset, hash_map, and hash_multimap. Each of these classes is a template, and can be instantiated to contain any type of object.

STL also includes collection of algorithms that manipulate the data stored in containers. algorithms are decoupled from the STL container classes.

iterators are a generalization of pointers. Iterators are the mechanism that makes it possible to decouple algorithms from containers: algorithms are templates, and are parameterized by the type of iterator, so they are not restricted to a single type of container.

Concepts and Modeling
One very important question to ask about any template function is what the set of types is that may correctly be substituted for the formal template parameters. These requirements are sufficiently important that we give them a name: we call such a set of type requirements a concept, and we call this particular concept Input Iterator. We say that a type conforms to a concept, or that it is a model of a concept, if it satisfies all of those requirements. We say that int* is a model of Input Iterator because int* provides all of the operations that are specified by the Input Iterator requirements.

Refinement
Refinement of concepts is very much like inheritance of C++ classes; the main reason we use a different word, instead of just calling it "inheritance", is to emphasize that refinement applies to concepts rather than to actual types. The main purpose is to impose additional requirements.

Other parts of STL

the STL includes several utilities: very basic concepts and functions that are used in many different parts of the library. The concept Assignable, for example, describes types that have assignment operators and copy constructors; almost all STL classes are models of Assignable, and almost all STL algorithms require their arguments to be models of Assignable.

Some low-level mechanisms for allocating and deallocating memory: Allocator

the STL includes a large collection of function objects, also known as functors. Just as iterators are a generalization of pointers, function objects are a generalization of functions: a function object is anything that you can call using the ordinary function call syntax. Function objects are an important part of generic programming because they allow abstraction not only over the types of objects, but also over the operations that are being performed.

Reference:

http://www.sgi.com/tech/stl/stl_introduction.html

Sunday, March 9, 2008

Associative Container - MAP

http://www.cprogramming.com/tutorial/stl/stlmap.html

STL Maps -- Associative Arrays
Suppose that you're working with some data that has values associated with strings -- for instance, you might have student usernames and you want to assign them grades. How would you go about storing this in C++? One option would be to write your own hash table. This will require writing a hash function and handling collisions, and lots of testing to make sure you got it right. On the other hand, the standard template library (STL) includes a templated class to handle just this sort of situation: the STL map class, which conceptually you can think of as an "associative array" -- key names are associated with particular values (e.g., you might use a student name as a key, and the student's grade as the data).

In fact, the STL's map class allows you to store data by any type of key instead of simply by a numerical key, the way you must access an array or vector. So instead of having to compute a hash function and then access an array, you can just let the map class do it for you.

To use the map class, you will need to include and maps are part of the std namespace. Maps require two, and possibly three, types for the template:

std::map

Notice that the comparison function is in brackets, indicating that it is optional so long as your key_type has the less-than operator, <, defined -- so you don't need to specify a comparision function for so-called primitive types such as int, char, or even for the string class. Moreover, if you overloaded the < char=""> grade_list;

Now, to actually store or access data in the map, all you need to do is treat it like a normal array and use brackets. The only difference is that you no longer use integers for the index -- you use whatever data type was used for the key.

For instance, following the previous example, if we wanted to assign a grade of 'B' to a student named "John", we could do the following:

grade_list["John"] = 'B';

If we later decided that John's grades had improved, we could change his grade in the same fashion:

grade_list["John"] = 'B';
// John's grade improves
grade_list["John"] = 'A';

So adding keys to a map can be done without doing anything special -- we just need to use the key and it will be added automatically along with the corresponding data item. On the other hand, getting rid of an element requires calling the function erase, which is a member of the map class:

erase(key_type key_value);

For instance, to erase "John" from our map, we could do the following:

grade_list.erase("John");

If we're curious, we could also check to see how many values the map contains by using the size function, which is also a member of the map class and other containers:

int size();

For instance, to find the size of our hypothetical class, we could call the size function on the grade list:

std::cout<<"The class is size "<< grade_list;
grade_list["John"] = 'A';
if(grade_list.find("Tim") == grade_list.end())
{
std::cout<<"Tim is not in the map!"<::iterator iterator_name;

where parameters are the parameters used for the container class this iterator will be used for. This iterator can be used to iterate in sequence over the keys in the container. Ah, you ask, but how do I know the key stored in the container? Or, even better, what exactly does it mean to dereference an iterator over the map container? The answer is that when you dereference an iterator over the map class, you get a "pair", which essentially has two members, first and second. First corresponds to the key, second to the value. Note that because an iterator is treated like a pointer, to access the member variables, you need to use the arrow operator, ->, to "dereference" the iterator.

For instance, the following sample shows the use of an iterator (pointing to the beginning of a map) to access the key and value.

std::map grade_list;
grade_list["John"] = 'A';
// Should be John
std::cout<first<<second<

Finally, you might wonder what the cost of using a map is. One issue to keep in mind is that insertion of a new key (and associated value) in a map, or lookup of the data associated with a key in a map, can take up to O(log(n)) time, where n is the size of the current map. This is potentially a bit slower than some hash tables with a good hashing function, and is due to the fact that the map keys are stored in sorted order for use by iterators.

Summary

The Good

* Maps provide a way of using "associative arrays" that allow you to store data indexed by keys of any type you desire, instead of just integers as with arrays.
* Maps can be accessed using iterators that are essentially pointers to templated objects of base type pair, which has two members, first and second. First corresponds to the key, second to the value associated with the key.
* Maps are fast, guaranteeing O(log(n)) insertion and lookup time.

The Gotchas

* Checking for whether an element is in a map requires using the find function and comparing the returned iterator with the iterator associated with the end of the map.
* Since maps associate a key with only one value, you need to use a multimap (or make the type of the data a container) if you must associate multiple pieces of data with one key.

Saturday, March 8, 2008

hash_map

using hash_map in g++:

#include <.ext/hash_map.>

using namespace __gnu_cxx;

Sunday, October 28, 2007

Standard Templates

1. Stack

#include <. stack.>

stack <.T.> s;

s. push(t);
s.pop();
s.top();
s.empty();
s.size();

狭路相逢勇者胜