Master STL in thirty minutes This is a villain's book. The original name is "using stl", I don't know who wrote it. But I found it very interesting, so I translated it for two nights. I have not checked the translated content. If you can't feel rewarded within thirty minutes, throw it away. I omitted a lot of things in the article. I feel sorry for that, wasting my two nights. Translator: kary contact:karymay@ STL Overview An important feature of STL is the separation of data structures and algorithms. Although this is a simple concept, this separation does make STL very versatile. For example, since STL's sort() function is completely universal, you can use it to manipulate almost any data collection, including linked lists, containers, and arrays. Key points: The STL algorithm is provided as a template function. In order to distinguish it from other components, in this book, the STL algorithm is represented by a pair of parentheses, such as sort(). Another important feature of STL is that it is not object-oriented. In order to be sufficiently universal, STL mainly relies on templates rather than encapsulation, inheritance and virtual functions (polymorphism)—the three elements of OOP. You can't find any obvious class inheritance relationship in STL. This seems to be a backwards, but it happens to be the underlying feature that makes STL's components have broad versatility. In addition, since STL is based on templates, the use of inline functions makes the generated code short and efficient. Tip: Make sure that at least -O optimization should be used to ensure inline expansion when compiling programs that use STL. STL provides a large number of template classes and functions that can be used in OOP and regular programming. All STL's approximately 50 algorithms are completely general and do not depend on any specific data type. The following sections illustrate three basic STL components: 1) The iterator provides a way to access objects in the container. For example, a pair of iterators can be used to specify a range of objects in a list or vector. An iterator is like a pointer. In fact, C++ pointers are also an iterator. However, iterators can also be class objects that define operator*() and other operator local methods similar to pointers. 2) Containers are data structures such as list, vector, and deques, provided in template class methods. To access the data in the container, an iterator output by the container class can be used. 3) Algorithms are template functions used to manipulate data in containers. For example, STL uses sort() to sort the data in a vector, and uses find() to search for objects in a list. Functions themselves have nothing to do with the structure and type of the data they operate on, so they can be used on any data structure from simple arrays to highly complex containers. Header files In order to avoid conflicts with other header files, STL's header files no longer use regular .h extensions. To include standard string classes, iterators and algorithms, use the following indicator: #include <string> #include <iterator> #include <algorithm> If you look at the header file of STL, you can see header files like stl_iterator.h. Since these names may vary between various STL implementations, you should avoid using these names to reference these header files. To ensure portability, use the corresponding file name without the .h suffix. Table 1 lists the header files for the various container classes that are most commonly used. This table is not complete, and for other header files, I will introduce it in this chapter and the next two chapters. Table 1. STL header file and container class #include Container Class <deque> deque <list> list <map> map, multimap <queue> queue, priority_queue <set> set, multiset <stack> stack <vector> vector, vector<bool> namespace Your compiler may not recognize the namespace. The namespace is like an envelope that encapsulates the logo in another name. The symbols only exist in the namespace, thus avoiding conflicts with other symbols. For example, there may be other libraries and program modules that define the sort() function. In order to avoid conflicts with the STL sort() algorithm, STL sort() and other logos are encapsulated in the namespace std. STL's sort() algorithm is compiled to std::sort(), thus avoiding name conflicts. Although your compiler may not implement namespace, you can still use them. To use STL, the following indicator can be inserted into your source code file, typically after all #include indicators: using namespace std; Iterator Iterator provides access to objects in a container and defines the scope of objects in the container. An iterator is like a pointer. In fact, C++ pointers are also an iterator. However, iterators are more than just pointers, so you can't think they must have address values. For example, an array index can also be considered an iterator. There are various ways to create iterators. The program may create an iterator as a variable. An STL container class may create an iterator in order to use a specific type of data. As a pointer, you must be able to use the * operator class to get data. You can also use other mathematical operators such as ++. Typically, the ++ operator is used to increment the iterator to access the next object in the container. If the iterator reaches the last element in the container, the iterator becomes the past-the-end value. It is illegal to use a past-the-end worth pointer to access an object, just like using NULL or an initialized pointer. Tip: STL does not guarantee that one iterator can be reached from another iterator. For example, when sorting objects in a collection, if you specify two iterators in different structures, the second iterator cannot arrive from the first iterator, and the program is doomed to fail. This is a price for STL flexibility. STL does not guarantee detection of unreasonable errors. Types of iterators For STL data structures and algorithms, you can use five iterators. The following briefly illustrates these five types: · � Output iterators Provide write-only access to data · Forward iterators provide read and write operations and can advance iterators forward. Bidirectional iterators provide read and write operations and can operate forward and backward. Random access iterators provide read and write operations and can move randomly in the data. Although the details of different STL implementations vary, the above iterator can still be imagined as a class inheritance relationship. In this sense, the following iterator inherits from the above iterator. Because of this inheritance relationship, you can use a Forward iterator as an output or input iterator. Similarly, if an algorithm requires that iterator is a bidirectional iterator, then only this type and random access iterator can be used. Pointer Iterator As shown in the following mini program, a pointer is also an iterator. The program also shows a major feature of STL - it can be used not only for its own class type, but also for any C or C++ type. Listing 1, , shows how to use pointers as iterators for STL’s find() algorithm to search for ordinary arrays. Table 1.
#include <>
#include <algorithm>
using namespace std;
#define SIZE 100
int iarray[SIZE];
int main()
{
iarray[20] = 50;
int* ip = find(iarray, iarray + SIZE, 50);
if (ip == iarray + SIZE)
cout << "50 not found in array" << endl;
else
cout << *ip << " found in array" << endl;
return 0;
}
After referenced the I/O stream library and STL algorithm header file (note that there is no .h suffix), the program tells the compiler to use the std namespace. This line using the std namespace is optional, because deleting the line will not cause name conflicts for such a small program. A global array with a size of SIZE is defined in the program. Since it is a global variable, the array is automatically initialized to zero during runtime. The following statement sets the element at index 20 to 50, and uses the find() algorithm to search for the value 50:
iarray[20] = 50;
int* ip = find(iarray, iarray + SIZE, 50);
The find() function accepts three parameters. The first two define the scope of the search. Since C and C++ arrays are equivalent to pointers, the expression iarray points to the first element of the array. The second parameter iarray + SIZE is equivalent to the past-the-end value, which is the position after the last element in the array. The third parameter is the value to be located, which is 50. The find() function returns an iterator of the same type as the first two parameters, here is an ip pointer to an integer. Tip: You must remember to use templates for STL. Therefore, STL functions are automatically constructed based on the data type they use. In order to determine whether find() is successful, in the example, test whether the values of ip and past-the-end are equal:
if (ip == iarray + SIZE) ...
If the expression is true, it means that there is no specified value within the range of the search. Otherwise, it is a pointer to a legal object. At this time, it can be displayed using the following statement::
cout << *ip << " found in array" << endl;
It is incorrect to test whether the return value of the function and NULL are equal. Don't use it like this:
int* ip = find(iarray, iarray + SIZE, 50);
if (ip != NULL) ... // ??? incorrect
When using STL functions, you can only test whether the values of ip and past-the-end are equal. Although in this case ip is a C++ pointer, its usage must also comply with the rules of the STL iterator. Container Iterator Although C++ pointers are also iterators, they use more container iterators. The usage of container iterators is the same, but unlike declaring an iterator as a pointer variable, you can use the container class method to get the iterator object. Two typical container class methods are begin() and end(). They represent the entire container scope in most containers. Some other containers also provide reverse iterators using the rbegin() and rend() methods to specify the scope of objects in reverse order. The following program creates a vector container (an object equivalent to an array) and searches it using an iterator. This program is the same as the one in the previous chapter. Listing 2.
#include <>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> intVector(100);
void main()
{
intVector[20] = 50;
vector<int>::iterator intIter =
find((), (), 50);
if (intIter != ())
cout << "Vector contains value " << *intIter << endl;
else
cout << "Vector does not contain 50" << endl;
}
Pay attention to using the following method to display the searched data:
cout << "Vector contains value " << *intIter << endl;
Constant iterators are the same as pointers, you can assign values to an iterator. For example, first declare an iterator:
vector<int>::iterator first;
This statement creates an iterator of the vector<int> class. The following statement sets the iterator to the first object of intVector and sets the object value it points to to 123::
first = ();
*first = 123;
This assignment is allowed for most container classes, except for read-only variables. To prevent incorrect assignment, it can be stated that the iterator is:
const vector<int>::iterator result;
result = find((), (), value);
if (result != ())
*result = 123; // ???
Warning Another way to prevent data from being changed is to declare the container as const type. "ah! There is an error in testing in VC. The correct meaning is that result becomes a constant instead of the object it points to, not allowing change, just like int *const p; it seems that the author himself doesn't understand. Using iterator programming You have seen some examples of iterators, and now we will focus on how each specific iterator is used. Since using iterators requires knowledge about STL container classes and algorithms, you may need to review the content of this chapter after reading the next two chapters. Input Iterator Input iterator is the most common type. The input iterator can at least use == and != to test whether it is equal; use * to access data; use ++ operations to recursively push the iterator to the next element or reach the past-the-end value. In order to understand how iterators and STL functions use them, let’s take a look at the definition of the find() template function:
template <class InputIterator, class T>
InputIterator find(
InputIterator first, InputIterator last, const T& value) {
while (first != last && *first != value) ++first;
return first;
}
Note: In the find() algorithm, note that if first and last point to different containers, the algorithm may fall into a dead loop. Output Iterator The output iterator is written only by default and is usually used to copy data from one location to another. Since the output iterator cannot read the object, you won't use it in any searches and other algorithms. To read a copy of the value, another input iterator (or its inherited iterator) must be used. Listing 3.
#include <>
#include <algorithm> // Need copy()
#include <vector> // Need vector
using namespace std;
double darray[10] =
{1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9};
vector<double> vdouble(10);
int main()
{
vector<double>::iterator outputIterator = ();
copy(darray, darray + 10, outputIterator);
while (outputIterator != ()) {
cout << *outputIterator << endl;
outputIterator++;
}
return 0;
}
Note: When using the copy() algorithm, you must make sure that the target container has enough space, or that the container itself is automatically expanded. The forward push iterator The forward push iterator can read and write data values and can push forward to the next value. But it cannot be reduced. The replace() algorithm shows how to use the forward push iterator.
template <class ForwardIterator, class T>
void replace (ForwardIterator first,
ForwardIterator last,
const T& old_value,
const T& new_value);
Use replace() to replace all objects with old_value in the range [first, last] with new_value. :
replace((), (), 1.5, 3.14159);
Bidirectional Iterator Bidirectional iterator requires that it can be increased or decreased. For example, the reverse() algorithm requires two bidirectional iterators as parameters:
template <class BidirectionalIterator>
void reverse (BidirectionalIterator first,
BidirectionalIterator last);
Use the reverse() function to reverse sort the container:
reverse((), ());
Random access iterator Random access iterator can access data in any order and can be used to read and write data (the C++ pointer that is not a const is also a random access iterator). The sorting and search functions of STL use a random access iterator. Random access iterators can be compared using relational operators. The random_shuffle() function randomly disrupts the original order. The statement is:
template <class RandomAccessIterator>
void random_shuffle (RandomAccessIterator first,
RandomAccessIterator last);
How to use:
random_shuffle((), ());
Iterator technology To learn how to use iterators, containers and algorithms, you need to learn the following new technologies. Streams and Iterators Many example programs in this book use I/O streaming statements to read and write data. For example:
int value;
cout << "Enter value: ";
cin >> value;
cout << "You entered " << value << endl;
For iterators, there is another way to use streams and standard functions. The key point to understand is to view the input/output stream as a container. Therefore, any algorithm that accepts iterator parameters can work with the stream. Listing 4.
#include <>
#include <> // Need random(), srandom()
#include <> // Need time()
#include <algorithm> // Need sort(), copy()
#include <vector> // Need vector
using namespace std;
void Display(vector<int>& v, const char* s);
int main()
{
// Seed the random number generator
srandom( time(NULL) );
// Construct vector and fill with random integer values
vector<int> collection(10);
for (int i = 0; i < 10; i++)
collection[i] = random() % 10000;;
// Display, sort, and redisplay
Display(collection, "Before sorting");
sort((), ());
Display(collection, "After sorting");
return 0;
}
// Display label s and contents of integer vector v
void Display(vector<int>& v, const char* s)
{
cout << endl << s << endl;
copy((), (),
ostream_iterator<int>(cout, "\t"));
cout << endl;
}
The function Display() shows how to use an output stream iterator. The following statement transfers the value in the container to the cout output stream object:
copy((), (),
ostream_iterator<int>(cout, "\t"));
The third parameter instantiates the ostream_iterator<int> type and uses it as the output target iterator object of the copy() function. The "\t" string is used as a separator. Operation results:
$ g++
$ ./
Before sorting
677 722 686 238 964 397 251 118 11 312
After sorting
11 118 238 251 312 397 677 686 722 964
This is the magical side of STL. To define the output stream iterator, STL provides the template class ostream_iterator. The constructor of this class has two parameters: an ostream object and a string value. Therefore, it is possible to simply create an iterator object like the following:
ostream_iterator<int>(cout, "\n")
This iterative can be used with any function that accepts an output iterator. Insert iterator The Insert iterator is used to insert values into containers. They are also called adapters because they adapt or convert containers into an iterator and are used in algorithms like copy(). For example, a program defines a linked list and a vector container:
list<double> dList;
vector<double> dVector;
By using the front_inserter iterator object, you can use a single copy() statement to insert objects in a vector to the front end of the linked list:
copy((), (), front_inserter(dList));
The three types of insertion iterators are as follows: · Front inserters Insert objects into front of the dataset—for example, the linked list header. Back inserters Insert objects into the tail of the collection—for example, the tail of a vector, causing the vector container to expand. Using insertion iterators may cause other objects in the container to move positions, thus making existing iterators illegal. For example, inserting an object into a vector container will cause other values to move positions to make room. In general, inserting into structures like linked lists is more effective because they do not cause other objects to move. Listing 5.
#include <>
#include <algorithm>
#include <list>
using namespace std;
int iArray[5] = { 1, 2, 3, 4, 5 };
void Display(list<int>& v, const char* s);
int main()
{
list<int> iList;
// Copy iArray backwards into iList
copy(iArray, iArray + 5, front_inserter(iList));
Display(iList, "Before find and copy");
// Locate value 3 in iList
list<int>::iterator p =
find((), (), 3);
// Copy first two iArray values to iList ahead of p
copy(iArray, iArray + 2, inserter(iList, p));
Display(iList, "After find and copy");
return 0;
}
void Display(list<int>& a, const char* s)
{
cout << s << endl;
copy((), (),
ostream_iterator<int>(cout, " "));
cout << endl;
}
The operation results are as follows:
$ g++
$ ./
Before find and copy
5 4 3 2 1
After find and copy
5 4 1 2 3 2 1
You can try replacing front_inserter with back_inserter. If you use find() to find the value that does not exist in the list, for example, 99. Since p is set to the past-the-end value at this time. The final copy() function appends the value of iArray to the back of the linked list. Mixed iterator functions. In operations involving containers and algorithms, there are two iterator functions that are very useful: advance(). Increase or decrease iterators by the specified number. distance() Returns the number of (incremental) operations required to reach an iterator. For example:
list<int> iList;
list<int>::iterator p =
find((), (), 2);
cout << "before: p == " << *p << endl;
advance(p, 2); // same as p = p + 2;
cout << "after : p == " << *p << endl;
int k = 0;
distance(p, (), k);
cout << "k == " << k << endl;
The advance() function accepts two parameters. The second parameter is the number of forward advances. For forward iterators, the value must be positive, while for bidirectional iterators and random access iterators, the value can be negative.
Use the distance() function to return the steps required to reach another iterator.
Note that the distance() function is iterative, that is, it increments the third parameter. Therefore, you have to initialize the parameter. Not initializing this parameter is almost doomed to fail. Functions and Function Objects In STL, functions are called algorithms, which means that they are more general than standard C library functions. The STL algorithm is implemented as a template class or template function by overloading the operator() function. These classes are used to create function objects that perform various operations on the data in the container. The following sections explain how to use functions and function objects. Functions and assertions often require user-defined operations on the data in the container. For example, you might want an STL algorithm that traverses all objects in a container to call back its own functions. For example
#include <>
#include <> // Need random(), srandom()
#include <> // Need time()
#include <vector> // Need vector
#include <algorithm> // Need for_each()
#define VSIZE 24 // Size of vector
vector<long> v(VSIZE); // Vector object
// Function prototypes
void initialize(long &ri);
void show(const long &ri);
bool isMinus(const long &ri); // Predicate function
int main()
{
srandom( time(NULL) ); // Seed random generator
for_each((), (), initialize);//Call the normal function
cout << "Vector of signed long integers" << endl;
for_each((), (), show);
cout << endl;
// Use predicate function to count negative values
//
int count = 0;
vector<long>::iterator p;
p = find_if((), (), isMinus);//Calling the assertion function
while (p != ()) {
count++;
p = find_if(p + 1, (), isMinus);
}
cout << "Number of values: " << VSIZE << endl;
cout << "Negative values : " << count << endl;
return 0;
}
// Set ri to a signed integer value
void initialize(long &ri)
{
ri = ( random() - (RAND_MAX / 2) );
// ri = random();
}
// Display value of ri
void show(const long &ri)
{
cout << ri << " ";
}
// Returns true if ri is less than 0
bool isMinus(const long &ri)
{
return (ri < 0);
}
The so-called assertion function is a function that returns the value of bool. Function Object In addition to passing a callback function to the STL algorithm, you may also need to pass a class object to perform more complex operations. Such an object is called a function object. In fact, a function object is a class, but it can be called back like a callback function. For example, statistics can be retained each time a function object is called by the for_each() or find_if() function. Function objects are implemented by overloading operator()(). If TanyClass defines operator()(), then it can be used like this:
TAnyClass object; // Construct object
object(); // Calls TAnyClass::operator()() function
for_each((), (), object);
STL defines several function objects. Since they are templates, they can be used for any type, including data types inherent in C/C++, such as long. Some function objects can be seen from their names, such as plus() and multiples(). Similar greater() and less-equal() are used to compare two values. Note that some versions of ANSI C++ define times() function object, while GNU C++ named it multiples(). The header file <functional> must be included when using it. A useful application of function objects is the accumulation() algorithm. This function calculates the sum of all values in the container. Remember that such values are not necessarily simple types, they can also be class objects by overloading operator+(). Listing 8.
#include <>
#include <numeric> // Need accumulate()
#include <vector> // Need vector
#include <functional> // Need multiplies() (or times())
#define MAX 10
vector<long> v(MAX); // Vector object
int main()
{
// Fill vector using conventional loop
//
for (int i = 0; i < MAX; i++)
v[i] = i + 1;
// Accumulate the sum of contained values
//
long sum =
accumulate((), (), 0);
cout << "Sum of values == " << sum << endl;
// Accumulate the product of contained values
//
long product =
accumulate((), (), 1, multiplies<long>());// Pay attention to this line
cout << "Product of values == " << product << endl;
return 0;
}
The compilation output is as follows:
$ g++
$ ./
Sum of values == 55
Product of values == 3628800
"Note the usage of accumulated() using function object. accumulate() internally uses the object and the third parameter in each container as parameters of the multiplies function object, and multiplies(1,v) calculates the product. The source codes of these templates in VC are as follows: ION accumulate WITH BINOP template<class _II, class _Ty, class _Bop> inline _Ty accumulate(_II _F, _II _L, _Ty _V, _Bop _B) {for (; _F != _L; ++_F) _V = _B(_V, *_F); return (_V); } // TEMPLATE STRUCT binar y_function template<class _A1, class _A2, class _R> struct binary_function { typedef _A1 first_argument_type; typedef _A2 second_argument_type; typedef _R result_type; }; // TEMPLATE STRUCT multiplies tem plate<class _Ty> struct multiplies : binary_function<_Ty, _Ty, _Ty> { _Ty operator()(const _Ty& _X, const _Ty& _Y) const � So there is no need to buy books like "STL Source Code Analysis", as those books may waste time. 'Generator function object There is a useful class of function objects that are "generators". This type of function has its own memory, which means it can remember a value from the previous call. For example, a random number generator function. Ordinary C programmers use static or global variables to "memorize" the result of the last call. But the disadvantage of doing this is that the function cannot be separated from its data. Another disadvantage is that it requires TLS to be thread-safe. Obviously, using classes to encapsulate a piece: "memory" is safer and more reliable. Let’s take a look at the example first: Listing 9.
#include <>
#include <> // Need random(), srandom()
#include <> // Need time()
#include <algorithm> // Need random_shuffle()
#include <vector> // Need vector
#include <functional> // Need ptr_fun()
using namespace std;
// Data to randomize
int iarray[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
vector<int> v(iarray, iarray + 10);
// Function prototypes
void Display(vector<int>& vr, const char *s);
unsigned int RandInt(const unsigned int n);
int main()
{
srandom( time(NULL) ); // Seed random generator
Display(v, "Before shuffle:");
pointer_to_unary_function<unsigned int, unsigned int>
ptr_RandInt = ptr_fun(RandInt); // Pointer to RandInt()// Pay attention to this line
random_shuffle((), (), ptr_RandInt);
Display(v, "After shuffle:");
return 0;
}
// Display contents of vector vr
void Display(vector<int>& vr, const char *s)
{
cout << endl << s << endl;
copy((), (), ostream_iterator<int>(cout, " "));
cout << endl;
}
// Return next random value in sequence modulo n
unsigned int RandInt(const unsigned int n)
{
return random() % n;
}
The compilation and operation results are as follows:
$ g++
$ ./
Before shuffle:
1 2 3 4 5 6 7 8 9 10
After shuffle:
6 7 2 8 3 5 10 1 9 4
First, use the following statement to declare an object:
pointer_to_unary_function<unsigned int, unsigned int>
ptr_RandInt = ptr_fun(RandInt);
Here, we use the monocular function template of STL to define a variable ptr_RandInt and initialize the address to our function RandInt(). The monolog function takes a parameter and returns a value. Now random_shuffle() can be called as follows:
random_shuffle((), (), ptr_RandInt);
In this example, the generator simply calls the rand() function.
A little trouble about constant references (not translated, remove the const in the example under VC) Generator function class object The following example illustrates the use of generator function class object. Listing 10.
#include <>
#include <algorithm> // Need random_shuffle()
#include <vector> // Need vector
#include <functional> // Need unary_function
using namespace std;
// Data to randomize
int iarray[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
vector<int> v(iarray, iarray + 10);
// Function prototype
void Display(vector<int>& vr, const char *s);
// The FiboRand template function-object class
template <class Arg>
class FiboRand : public unary_function<Arg, Arg> {
int i, j;
Arg sequence[18];
public:
FiboRand();
Arg operator()(const Arg& arg);
};
void main()
{
FiboRand<int> fibogen; // Construct generator object
cout << "Fibonacci random number generator" << endl;
cout << "using random_shuffle and a function object" << endl;
Display(v, "Before shuffle:");
random_shuffle((), (), fibogen);
Display(v, "After shuffle:");
}
// Display contents of vector vr
void Display(vector<int>& vr, const char *s)
{
cout << endl << s << endl;
copy((), (),
ostream_iterator<int>(cout, " "));
cout << endl;
}
// FiboRand class constructor
template<class Arg>
FiboRand<Arg>::FiboRand()
{
sequence[17] = 1;
sequence[16] = 2;
for (int n = 15; n > 0; n—)
sequence[n] = sequence[n + 1] + sequence[n + 2];
i = 17;
j = 5;
}
// FiboRand class function operator
template<class Arg>
Arg FiboRand<Arg>::operator()(const Arg& arg)
{
Arg k = sequence[i] + sequence[j];
sequence[i] = k;
i--;
j--;
if (i == 0) i = 17;
if (j == 0) j = 17;
return k % arg;
}
The compilation and running output is as follows:
$ g++
$ ./
Fibonacci random number generator
using random_shuffle and a function object
Before shuffle:
1 2 3 4 5 6 7 8 9 10
After shuffle:
6 8 5 4 3 7 10 1 9
This program uses rand_shuffle in a completely unusable way. The Fibonacci generator is encapsulated in a class that can remember the run results from previous "use". In this case, the class FiboRand maintains an array and two index variables I and j. FiboRand class inherits from unary_function() template:
template <class Arg>
class FiboRand : public unary_function<Arg, Arg> {...
Arg is a user-defined data type. The class also has two member functions, one is the constructor and the other is the operator()() function. This operator allows the random_shuffle() algorithm to "call" a FiboRand object like a function. Binder Function Object One binder creates a function object using another function object f() and parameter value V. The bound function object must be a binocular function, that is, there are two parameters, A and B. The fixer in STL is: · bind1st() Create a function object that takes the value V as the first parameter A. bind2nd() creates a function object that takes the value V as the second parameter B. As shown below: Listing 11.
#include <>
#include <algorithm>
#include <functional>
#include <list>
using namespace std;
// Data
int iarray[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
list<int> aList(iarray, iarray + 10);
int main()
{
int k = 0;
count_if((), (),
bind1st(greater<int>(), 8), k);
cout << "Number elements < 8 == " << k << endl;
return 0;
}
Algorithm count_if() calculates the number of elements that meet certain conditions. This is achieved by bundling a function object and a parameter into an object and using that object as the third parameter of the algorithm. Pay attention to this expression:
bind1st(greater<int>(), 8)
This expression bundles greater<int>() with a parameter value of 8 into a function object. Since bind1st() is used, this function is equivalent to calculating the following expression:
8 > q
The q in the expression is an object in the container. Therefore, the complete expression
count_if((), (),
bind1st(greater<int>(), 8), k);
Calculates the number of all objects less than or equal to 8. Negator function object The so-called negator function object is created from another function object. If the original function returns true, the negative function object returns false. There are two negative function objects: not1() and not2(). not1() accepts a monocular function object, not2() accepts a binocular function object. Negative function objects are usually used with the simulator. For example, in the previous section, bind1nd is used to search for the value of q<=8:
count_if((), (),
bind1st(greater<int>(), 8), k);
If you want to search for an object with q>8, use bind2st. And now you can write this:
start = find_if((), (), not1(bind1nd(greater<int>(), 6)));
You have to use not1 because bind1nd returns the monolog function. Summary: Using Standard Template Library (STL) Although many programmers are still using standard C functions, it is like riding a donkey to look for Mercedes. Of course you will eventually reach your goal, but you have wasted a lot of time. Although sometimes using standard C functions is really convenient (such as using sprintf() for formatting output). However, C functions do not use exception mechanisms to report errors, and are not suitable for handling new data types. Moreover, standard C functions often use memory allocation technology, and inexperienced programmers can easily write bugs. . The C++ standard library provides a safer and more flexible dataset processing method. STL was originally developed by Alexander Stepanov and Meng Lee from HP Labs. Recently, the C++ Standards Committee adopted STL, although there are still differences in detail between implementations. The two main features of STL: the separation of data structures and algorithms, and the non-object-oriented nature. Access objects are implemented through an iterator like a pointer; a container is a data structure like a linked list, a vector, and is provided in a template; an algorithm is a function template, used to operate data in the container. Since STL is template-based, it can be used for any data type and structure.
#include <>
#include <algorithm>
using namespace std;
#define SIZE 100
int iarray[SIZE];
int main()
{
iarray[20] = 50;
int* ip = find(iarray, iarray + SIZE, 50);
if (ip == iarray + SIZE)
cout << "50 not found in array" << endl;
else
cout << *ip << " found in array" << endl;
return 0;
}
After referenced the I/O stream library and STL algorithm header file (note that there is no .h suffix), the program tells the compiler to use the std namespace. This line using the std namespace is optional, because deleting the line will not cause name conflicts for such a small program. A global array with a size of SIZE is defined in the program. Since it is a global variable, the array is automatically initialized to zero during runtime. The following statement sets the element at index 20 to 50, and uses the find() algorithm to search for the value 50:
iarray[20] = 50;
int* ip = find(iarray, iarray + SIZE, 50);
The find() function accepts three parameters. The first two define the scope of the search. Since C and C++ arrays are equivalent to pointers, the expression iarray points to the first element of the array. The second parameter iarray + SIZE is equivalent to the past-the-end value, which is the position after the last element in the array. The third parameter is the value to be located, which is 50. The find() function returns an iterator of the same type as the first two parameters, here is an ip pointer to an integer. Tip: You must remember to use templates for STL. Therefore, STL functions are automatically constructed based on the data type they use. In order to determine whether find() is successful, in the example, test whether the values of ip and past-the-end are equal:
if (ip == iarray + SIZE) ...
If the expression is true, it means that there is no specified value within the range of the search. Otherwise, it is a pointer to a legal object. At this time, it can be displayed using the following statement::
cout << *ip << " found in array" << endl;
It is incorrect to test whether the return value of the function and NULL are equal. Don't use it like this:
int* ip = find(iarray, iarray + SIZE, 50);
if (ip != NULL) ... // ??? incorrect
When using STL functions, you can only test whether the values of ip and past-the-end are equal. Although in this case ip is a C++ pointer, its usage must also comply with the rules of the STL iterator. Container Iterator Although C++ pointers are also iterators, they use more container iterators. The usage of container iterators is the same, but unlike declaring an iterator as a pointer variable, you can use the container class method to get the iterator object. Two typical container class methods are begin() and end(). They represent the entire container scope in most containers. Some other containers also provide reverse iterators using the rbegin() and rend() methods to specify the scope of objects in reverse order. The following program creates a vector container (an object equivalent to an array) and searches it using an iterator. This program is the same as the one in the previous chapter. Listing 2.
#include <>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> intVector(100);
void main()
{
intVector[20] = 50;
vector<int>::iterator intIter =
find((), (), 50);
if (intIter != ())
cout << "Vector contains value " << *intIter << endl;
else
cout << "Vector does not contain 50" << endl;
}
Pay attention to using the following method to display the searched data:
cout << "Vector contains value " << *intIter << endl;
Constant iterators are the same as pointers, you can assign values to an iterator. For example, first declare an iterator:
vector<int>::iterator first;
This statement creates an iterator of the vector<int> class. The following statement sets the iterator to the first object of intVector and sets the object value it points to to 123::
first = ();
*first = 123;
This assignment is allowed for most container classes, except for read-only variables. To prevent incorrect assignment, it can be stated that the iterator is:
const vector<int>::iterator result;
result = find((), (), value);
if (result != ())
*result = 123; // ???
Warning Another way to prevent data from being changed is to declare the container as const type. "ah! There is an error in testing in VC. The correct meaning is that result becomes a constant instead of the object it points to, not allowing change, just like int *const p; it seems that the author himself doesn't understand. Using iterator programming You have seen some examples of iterators, and now we will focus on how each specific iterator is used. Since using iterators requires knowledge about STL container classes and algorithms, you may need to review the content of this chapter after reading the next two chapters. Input Iterator Input iterator is the most common type. The input iterator can at least use == and != to test whether it is equal; use * to access data; use ++ operations to recursively push the iterator to the next element or reach the past-the-end value. In order to understand how iterators and STL functions use them, let’s take a look at the definition of the find() template function:
template <class InputIterator, class T>
InputIterator find(
InputIterator first, InputIterator last, const T& value) {
while (first != last && *first != value) ++first;
return first;
}
Note: In the find() algorithm, note that if first and last point to different containers, the algorithm may fall into a dead loop. Output Iterator The output iterator is written only by default and is usually used to copy data from one location to another. Since the output iterator cannot read the object, you won't use it in any searches and other algorithms. To read a copy of the value, another input iterator (or its inherited iterator) must be used. Listing 3.
#include <>
#include <algorithm> // Need copy()
#include <vector> // Need vector
using namespace std;
double darray[10] =
{1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9};
vector<double> vdouble(10);
int main()
{
vector<double>::iterator outputIterator = ();
copy(darray, darray + 10, outputIterator);
while (outputIterator != ()) {
cout << *outputIterator << endl;
outputIterator++;
}
return 0;
}
Note: When using the copy() algorithm, you must make sure that the target container has enough space, or that the container itself is automatically expanded. The forward push iterator The forward push iterator can read and write data values and can push forward to the next value. But it cannot be reduced. The replace() algorithm shows how to use the forward push iterator.
template <class ForwardIterator, class T>
void replace (ForwardIterator first,
ForwardIterator last,
const T& old_value,
const T& new_value);
Use replace() to replace all objects with old_value in the range [first, last] with new_value. :
replace((), (), 1.5, 3.14159);
Bidirectional Iterator Bidirectional iterator requires that it can be increased or decreased. For example, the reverse() algorithm requires two bidirectional iterators as parameters:
template <class BidirectionalIterator>
void reverse (BidirectionalIterator first,
BidirectionalIterator last);
Use the reverse() function to reverse sort the container:
reverse((), ());
Random access iterator Random access iterator can access data in any order and can be used to read and write data (the C++ pointer that is not a const is also a random access iterator). The sorting and search functions of STL use a random access iterator. Random access iterators can be compared using relational operators. The random_shuffle() function randomly disrupts the original order. The statement is:
template <class RandomAccessIterator>
void random_shuffle (RandomAccessIterator first,
RandomAccessIterator last);
How to use:
random_shuffle((), ());
Iterator technology To learn how to use iterators, containers and algorithms, you need to learn the following new technologies. Streams and Iterators Many example programs in this book use I/O streaming statements to read and write data. For example:
int value;
cout << "Enter value: ";
cin >> value;
cout << "You entered " << value << endl;
For iterators, there is another way to use streams and standard functions. The key point to understand is to view the input/output stream as a container. Therefore, any algorithm that accepts iterator parameters can work with the stream. Listing 4.
#include <>
#include <> // Need random(), srandom()
#include <> // Need time()
#include <algorithm> // Need sort(), copy()
#include <vector> // Need vector
using namespace std;
void Display(vector<int>& v, const char* s);
int main()
{
// Seed the random number generator
srandom( time(NULL) );
// Construct vector and fill with random integer values
vector<int> collection(10);
for (int i = 0; i < 10; i++)
collection[i] = random() % 10000;;
// Display, sort, and redisplay
Display(collection, "Before sorting");
sort((), ());
Display(collection, "After sorting");
return 0;
}
// Display label s and contents of integer vector v
void Display(vector<int>& v, const char* s)
{
cout << endl << s << endl;
copy((), (),
ostream_iterator<int>(cout, "\t"));
cout << endl;
}
The function Display() shows how to use an output stream iterator. The following statement transfers the value in the container to the cout output stream object:
copy((), (),
ostream_iterator<int>(cout, "\t"));
The third parameter instantiates the ostream_iterator<int> type and uses it as the output target iterator object of the copy() function. The "\t" string is used as a separator. Operation results:
$ g++
$ ./
Before sorting
677 722 686 238 964 397 251 118 11 312
After sorting
11 118 238 251 312 397 677 686 722 964
This is the magical side of STL. To define the output stream iterator, STL provides the template class ostream_iterator. The constructor of this class has two parameters: an ostream object and a string value. Therefore, it is possible to simply create an iterator object like the following:
ostream_iterator<int>(cout, "\n")
This iterative can be used with any function that accepts an output iterator. Insert iterator The Insert iterator is used to insert values into containers. They are also called adapters because they adapt or convert containers into an iterator and are used in algorithms like copy(). For example, a program defines a linked list and a vector container:
list<double> dList;
vector<double> dVector;
By using the front_inserter iterator object, you can use a single copy() statement to insert objects in a vector to the front end of the linked list:
copy((), (), front_inserter(dList));
The three types of insertion iterators are as follows: · Front inserters Insert objects into front of the dataset—for example, the linked list header. Back inserters Insert objects into the tail of the collection—for example, the tail of a vector, causing the vector container to expand. Using insertion iterators may cause other objects in the container to move positions, thus making existing iterators illegal. For example, inserting an object into a vector container will cause other values to move positions to make room. In general, inserting into structures like linked lists is more effective because they do not cause other objects to move. Listing 5.
#include <>
#include <algorithm>
#include <list>
using namespace std;
int iArray[5] = { 1, 2, 3, 4, 5 };
void Display(list<int>& v, const char* s);
int main()
{
list<int> iList;
// Copy iArray backwards into iList
copy(iArray, iArray + 5, front_inserter(iList));
Display(iList, "Before find and copy");
// Locate value 3 in iList
list<int>::iterator p =
find((), (), 3);
// Copy first two iArray values to iList ahead of p
copy(iArray, iArray + 2, inserter(iList, p));
Display(iList, "After find and copy");
return 0;
}
void Display(list<int>& a, const char* s)
{
cout << s << endl;
copy((), (),
ostream_iterator<int>(cout, " "));
cout << endl;
}
The operation results are as follows:
$ g++
$ ./
Before find and copy
5 4 3 2 1
After find and copy
5 4 1 2 3 2 1
You can try replacing front_inserter with back_inserter. If you use find() to find the value that does not exist in the list, for example, 99. Since p is set to the past-the-end value at this time. The final copy() function appends the value of iArray to the back of the linked list. Mixed iterator functions. In operations involving containers and algorithms, there are two iterator functions that are very useful: advance(). Increase or decrease iterators by the specified number. distance() Returns the number of (incremental) operations required to reach an iterator. For example:
list<int> iList;
list<int>::iterator p =
find((), (), 2);
cout << "before: p == " << *p << endl;
advance(p, 2); // same as p = p + 2;
cout << "after : p == " << *p << endl;
int k = 0;
distance(p, (), k);
cout << "k == " << k << endl;
The advance() function accepts two parameters. The second parameter is the number of forward advances. For forward iterators, the value must be positive, while for bidirectional iterators and random access iterators, the value can be negative.
Use the distance() function to return the steps required to reach another iterator.
Note that the distance() function is iterative, that is, it increments the third parameter. Therefore, you have to initialize the parameter. Not initializing this parameter is almost doomed to fail. Functions and Function Objects In STL, functions are called algorithms, which means that they are more general than standard C library functions. The STL algorithm is implemented as a template class or template function by overloading the operator() function. These classes are used to create function objects that perform various operations on the data in the container. The following sections explain how to use functions and function objects. Functions and assertions often require user-defined operations on the data in the container. For example, you might want an STL algorithm that traverses all objects in a container to call back its own functions. For example
#include <>
#include <> // Need random(), srandom()
#include <> // Need time()
#include <vector> // Need vector
#include <algorithm> // Need for_each()
#define VSIZE 24 // Size of vector
vector<long> v(VSIZE); // Vector object
// Function prototypes
void initialize(long &ri);
void show(const long &ri);
bool isMinus(const long &ri); // Predicate function
int main()
{
srandom( time(NULL) ); // Seed random generator
for_each((), (), initialize);//Call the normal function
cout << "Vector of signed long integers" << endl;
for_each((), (), show);
cout << endl;
// Use predicate function to count negative values
//
int count = 0;
vector<long>::iterator p;
p = find_if((), (), isMinus);//Calling the assertion function
while (p != ()) {
count++;
p = find_if(p + 1, (), isMinus);
}
cout << "Number of values: " << VSIZE << endl;
cout << "Negative values : " << count << endl;
return 0;
}
// Set ri to a signed integer value
void initialize(long &ri)
{
ri = ( random() - (RAND_MAX / 2) );
// ri = random();
}
// Display value of ri
void show(const long &ri)
{
cout << ri << " ";
}
// Returns true if ri is less than 0
bool isMinus(const long &ri)
{
return (ri < 0);
}
The so-called assertion function is a function that returns the value of bool. Function Object In addition to passing a callback function to the STL algorithm, you may also need to pass a class object to perform more complex operations. Such an object is called a function object. In fact, a function object is a class, but it can be called back like a callback function. For example, statistics can be retained each time a function object is called by the for_each() or find_if() function. Function objects are implemented by overloading operator()(). If TanyClass defines operator()(), then it can be used like this:
TAnyClass object; // Construct object
object(); // Calls TAnyClass::operator()() function
for_each((), (), object);
STL defines several function objects. Since they are templates, they can be used for any type, including data types inherent in C/C++, such as long. Some function objects can be seen from their names, such as plus() and multiples(). Similar greater() and less-equal() are used to compare two values. Note that some versions of ANSI C++ define times() function object, while GNU C++ named it multiples(). The header file <functional> must be included when using it. A useful application of function objects is the accumulation() algorithm. This function calculates the sum of all values in the container. Remember that such values are not necessarily simple types, they can also be class objects by overloading operator+(). Listing 8.
#include <>
#include <numeric> // Need accumulate()
#include <vector> // Need vector
#include <functional> // Need multiplies() (or times())
#define MAX 10
vector<long> v(MAX); // Vector object
int main()
{
// Fill vector using conventional loop
//
for (int i = 0; i < MAX; i++)
v[i] = i + 1;
// Accumulate the sum of contained values
//
long sum =
accumulate((), (), 0);
cout << "Sum of values == " << sum << endl;
// Accumulate the product of contained values
//
long product =
accumulate((), (), 1, multiplies<long>());// Pay attention to this line
cout << "Product of values == " << product << endl;
return 0;
}
The compilation output is as follows:
$ g++
$ ./
Sum of values == 55
Product of values == 3628800
"Note the usage of accumulated() using function object. accumulate() internally uses the object and the third parameter in each container as parameters of the multiplies function object, and multiplies(1,v) calculates the product. The source codes of these templates in VC are as follows: ION accumulate WITH BINOP template<class _II, class _Ty, class _Bop> inline _Ty accumulate(_II _F, _II _L, _Ty _V, _Bop _B) {for (; _F != _L; ++_F) _V = _B(_V, *_F); return (_V); } // TEMPLATE STRUCT binar y_function template<class _A1, class _A2, class _R> struct binary_function { typedef _A1 first_argument_type; typedef _A2 second_argument_type; typedef _R result_type; }; // TEMPLATE STRUCT multiplies tem plate<class _Ty> struct multiplies : binary_function<_Ty, _Ty, _Ty> { _Ty operator()(const _Ty& _X, const _Ty& _Y) const � So there is no need to buy books like "STL Source Code Analysis", as those books may waste time. 'Generator function object There is a useful class of function objects that are "generators". This type of function has its own memory, which means it can remember a value from the previous call. For example, a random number generator function. Ordinary C programmers use static or global variables to "memorize" the result of the last call. But the disadvantage of doing this is that the function cannot be separated from its data. Another disadvantage is that it requires TLS to be thread-safe. Obviously, using classes to encapsulate a piece: "memory" is safer and more reliable. Let’s take a look at the example first: Listing 9.
#include <>
#include <> // Need random(), srandom()
#include <> // Need time()
#include <algorithm> // Need random_shuffle()
#include <vector> // Need vector
#include <functional> // Need ptr_fun()
using namespace std;
// Data to randomize
int iarray[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
vector<int> v(iarray, iarray + 10);
// Function prototypes
void Display(vector<int>& vr, const char *s);
unsigned int RandInt(const unsigned int n);
int main()
{
srandom( time(NULL) ); // Seed random generator
Display(v, "Before shuffle:");
pointer_to_unary_function<unsigned int, unsigned int>
ptr_RandInt = ptr_fun(RandInt); // Pointer to RandInt()// Pay attention to this line
random_shuffle((), (), ptr_RandInt);
Display(v, "After shuffle:");
return 0;
}
// Display contents of vector vr
void Display(vector<int>& vr, const char *s)
{
cout << endl << s << endl;
copy((), (), ostream_iterator<int>(cout, " "));
cout << endl;
}
// Return next random value in sequence modulo n
unsigned int RandInt(const unsigned int n)
{
return random() % n;
}
The compilation and operation results are as follows:
$ g++
$ ./
Before shuffle:
1 2 3 4 5 6 7 8 9 10
After shuffle:
6 7 2 8 3 5 10 1 9 4
First, use the following statement to declare an object:
pointer_to_unary_function<unsigned int, unsigned int>
ptr_RandInt = ptr_fun(RandInt);
Here, we use the monocular function template of STL to define a variable ptr_RandInt and initialize the address to our function RandInt(). The monolog function takes a parameter and returns a value. Now random_shuffle() can be called as follows:
random_shuffle((), (), ptr_RandInt);
In this example, the generator simply calls the rand() function.
A little trouble about constant references (not translated, remove the const in the example under VC) Generator function class object The following example illustrates the use of generator function class object. Listing 10.
#include <>
#include <algorithm> // Need random_shuffle()
#include <vector> // Need vector
#include <functional> // Need unary_function
using namespace std;
// Data to randomize
int iarray[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
vector<int> v(iarray, iarray + 10);
// Function prototype
void Display(vector<int>& vr, const char *s);
// The FiboRand template function-object class
template <class Arg>
class FiboRand : public unary_function<Arg, Arg> {
int i, j;
Arg sequence[18];
public:
FiboRand();
Arg operator()(const Arg& arg);
};
void main()
{
FiboRand<int> fibogen; // Construct generator object
cout << "Fibonacci random number generator" << endl;
cout << "using random_shuffle and a function object" << endl;
Display(v, "Before shuffle:");
random_shuffle((), (), fibogen);
Display(v, "After shuffle:");
}
// Display contents of vector vr
void Display(vector<int>& vr, const char *s)
{
cout << endl << s << endl;
copy((), (),
ostream_iterator<int>(cout, " "));
cout << endl;
}
// FiboRand class constructor
template<class Arg>
FiboRand<Arg>::FiboRand()
{
sequence[17] = 1;
sequence[16] = 2;
for (int n = 15; n > 0; n—)
sequence[n] = sequence[n + 1] + sequence[n + 2];
i = 17;
j = 5;
}
// FiboRand class function operator
template<class Arg>
Arg FiboRand<Arg>::operator()(const Arg& arg)
{
Arg k = sequence[i] + sequence[j];
sequence[i] = k;
i--;
j--;
if (i == 0) i = 17;
if (j == 0) j = 17;
return k % arg;
}
The compilation and running output is as follows:
$ g++
$ ./
Fibonacci random number generator
using random_shuffle and a function object
Before shuffle:
1 2 3 4 5 6 7 8 9 10
After shuffle:
6 8 5 4 3 7 10 1 9
This program uses rand_shuffle in a completely unusable way. The Fibonacci generator is encapsulated in a class that can remember the run results from previous "use". In this case, the class FiboRand maintains an array and two index variables I and j. FiboRand class inherits from unary_function() template:
template <class Arg>
class FiboRand : public unary_function<Arg, Arg> {...
Arg is a user-defined data type. The class also has two member functions, one is the constructor and the other is the operator()() function. This operator allows the random_shuffle() algorithm to "call" a FiboRand object like a function. Binder Function Object One binder creates a function object using another function object f() and parameter value V. The bound function object must be a binocular function, that is, there are two parameters, A and B. The fixer in STL is: · bind1st() Create a function object that takes the value V as the first parameter A. bind2nd() creates a function object that takes the value V as the second parameter B. As shown below: Listing 11.
#include <>
#include <algorithm>
#include <functional>
#include <list>
using namespace std;
// Data
int iarray[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
list<int> aList(iarray, iarray + 10);
int main()
{
int k = 0;
count_if((), (),
bind1st(greater<int>(), 8), k);
cout << "Number elements < 8 == " << k << endl;
return 0;
}
Algorithm count_if() calculates the number of elements that meet certain conditions. This is achieved by bundling a function object and a parameter into an object and using that object as the third parameter of the algorithm. Pay attention to this expression:
bind1st(greater<int>(), 8)
This expression bundles greater<int>() with a parameter value of 8 into a function object. Since bind1st() is used, this function is equivalent to calculating the following expression:
8 > q
The q in the expression is an object in the container. Therefore, the complete expression
count_if((), (),
bind1st(greater<int>(), 8), k);
Calculates the number of all objects less than or equal to 8. Negator function object The so-called negator function object is created from another function object. If the original function returns true, the negative function object returns false. There are two negative function objects: not1() and not2(). not1() accepts a monocular function object, not2() accepts a binocular function object. Negative function objects are usually used with the simulator. For example, in the previous section, bind1nd is used to search for the value of q<=8:
count_if((), (),
bind1st(greater<int>(), 8), k);
If you want to search for an object with q>8, use bind2st. And now you can write this:
start = find_if((), (), not1(bind1nd(greater<int>(), 6)));
You have to use not1 because bind1nd returns the monolog function. Summary: Using Standard Template Library (STL) Although many programmers are still using standard C functions, it is like riding a donkey to look for Mercedes. Of course you will eventually reach your goal, but you have wasted a lot of time. Although sometimes using standard C functions is really convenient (such as using sprintf() for formatting output). However, C functions do not use exception mechanisms to report errors, and are not suitable for handling new data types. Moreover, standard C functions often use memory allocation technology, and inexperienced programmers can easily write bugs. . The C++ standard library provides a safer and more flexible dataset processing method. STL was originally developed by Alexander Stepanov and Meng Lee from HP Labs. Recently, the C++ Standards Committee adopted STL, although there are still differences in detail between implementations. The two main features of STL: the separation of data structures and algorithms, and the non-object-oriented nature. Access objects are implemented through an iterator like a pointer; a container is a data structure like a linked list, a vector, and is provided in a template; an algorithm is a function template, used to operate data in the container. Since STL is template-based, it can be used for any data type and structure.