C++標準庫的算法,是什么東西?
從語言層面講
- 容器Container是個class template
- 算法Algorithm是個function template
- 迭代器Iterator是個class template
- 仿函數(shù)Functor是個class template
- 適配器Adapter是個class template
- 分配器Allocator是個class template
template <typename Iterator>
Algorithm(Iterator itr1, Iterator itr2)
{
...
}
template <typename Iterator, typename Cmp>
Algorithm(Iterator itr1, Iterator itr2, Cmp comp)
{
...
}
Algorithms 看不見Containers, 對其一無所知; 所以, 它所需要的一切信息都必須從Iterators取得, 而Iterator(由Container供應)必須能夠回答Algorithm的所有提問, 才能搭配該Algorithm的所有操作.
各種容器的iterators有五種不同的iterator_category
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public input_iterator_tag {};
struct random_access_iterator_tag : public input_iterator_tag {};
如何打印iterator_category?
一個簡單的打印函數(shù):
void _display_category(input_iterator_tag)
{ cout << "input_iterator" << endl; }
void _display_category(output_iterator_tag)
{ cout << "output_iterator" << endl; }
void _display_category(forward_iterator_tag)
{ cout << "forward_iterator" << endl; }
void _display_category(bidirectional_iterator_tag)
{ cout << "bidirectional_iterator" << endl; }
void _display_category(random_access_iterator_tag)
{ cout << "random_access_iterator" << endl; }
template <typename I>
void display_category(I itr)
{
typename iterator_traits<I>::iterator_category cagy;
_display_category(cagy);
}
使用該打印函數(shù)的例子:
cout << "\ntest_iterator_category()..........\n";
display_category(array<int, 10>::iterator());
display_category(vector<int>::iterator());
display_category(list<int>::iterator());
display_category(forward<int>::iterator());
display_category(deque<int>::iterator());
各種容器的iterators的iterator_category的typeid
template <typename I>
void display_category(I itr)
{
// The output depends on library implementation.
// The particular representation pointed by
// returned value is implementation defined,
// and may or may not be different for different types.
cout << "typeid(itr).names=" << typeid(itr).name() << endl;
}
關于運行時類型識別RTTI (摘自C++ Primer):
Run-time type identification (RTTI) is provided through two operators: 1. The typeid operator, which returns the type of a given expression; 2. The dynamic_cast operator, which safely converts a pointer or reference to a base type into a pointer or reference to a derived type. When applied to pointers or references to types that have virtual functions, these operators use the dynamic type of the object to which the pointer or reference is bound.
These operators are useful when we have a derived operation that we want to perform through a pointer or reference to a base-class object and it is not possible to make that operation a virtual function. Ordinarily, we should use virtual functions if we can. When the operation is virtual, the compiler automatically selects the right function according to the dynamic type of the object.
However, it is not always possible to define a virtual. If we cannot use a virtual, we can use one of the RTTI operators. On the other hand, using these operators is more error-prone than using virtual member functions: The programmer must know to which type the object should be cast and must check that the cast was performed successfully.
iterator_category對算法的影響
第一個例子 distance算法:
template <class InputIterator>
inline iterator_traits<InputIterator>::difference_type
__distance(InputIterator first, InputIterator last, input_iterator_tag) {
iterator_traits<InputIterator>::difference_type n = 0;
while (first != last) {
++first; ++n;
}
return n;
}
template <class RandomAccessIterator>
inline iterator_traits<RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag> {
return last - first;
}
// ----------------------------------------------------------------------
template <class InputIterator>
inline iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last) {
typedef typename
iterator_traits<InputIterator>::iterator_category category;
return __distance(first, last, category());
}
評論: 在算法distance中, category()將會創(chuàng)建一個臨時的對象. 如該對象為input_iterator_tag / forward_iterator_tag / bidirectional_iterator_tag, distance調用第一個__distance; 如該對象為random_access_iterator_tag, 則distance調用第二個__distance.
第二個例子 advance算法:
template <class InputIterator, class Distance>
inline void __advance(InputIterator &i, Distance n, input_iterator_tag) {
while (n--) ++i;
}
template <class BidirectionalIterator, class Distance>
inline void __advance(BidirectionalIterator &i, Distance n, bidirectional_iterator_tag) {
if (n >= 0) while (n--) ++i;
else while (n++) --i;
}
template <class RandomAccessIterator, class Distance>
inline void __advance(RandomAccessIterator &i, Distance n, random_access_iterator_tag) {
i += n;
}
// -------------------------------------------------------------------------
template <class Iterator>
inline typename iterator_traits<Iterator>::iterator_category
iterator_category(const Iterator&) {
typedef typename iterator_traits<Iterator>::iterator_category category;
return category(); // 此函數(shù)協(xié)助取出iterator的category,
// 并以此創(chuàng)建一個臨時對象.
}
template <class InputIterator, class Distance>
inline void advance(InputIterator &i, Distance n) {
__advance(i, n, iterator_category(i));
}
評論: 在算法advance中, iterator_category(i)將會創(chuàng)建一個臨時的對象. 如該對象為input_iterator_tag, advance調用第一個__advance; 如該對象為forward_iterator_tag / bidirectional_iterator_tag, advance調用第二個__advance; 如該對象為random_access_iterator_tag, 則advance調用第三個__advance.
仿函數(shù)
在C++中杯拐，有些算法是通過仿函數(shù)來實現(xiàn)的，這些仿函數(shù)基本都會繼承某個類的歪今，例如binary_function<T,T,T> 或者unarg_function<T,T>. 這是因為這些仿函數(shù)并不是單獨存在的，他們可能只是算法的一部分颜矿，需要其他算法進行調用寄猩，才能發(fā)揮作用, 但是如果是的自己可以被其他函數(shù)調用，就需要告知調用者 自己的返回值或衡，參數(shù)等特性. 這一點跟容器的traits非常類似焦影，把需要告知算法的信息進行統(tǒng)一的封裝.
template <class Arg, class Result>
struct unarg_function{
typedef Arg argument_type;
typedef Result result_type;
};
template <class Arg1, class Arg2, class Result>
struct binarg_function {
typedef Arg1 first_argument_type;
typedef Arg2 second_argument_type;
typedef Result result_type;
};
Reverse Iterator
摘自C++ Primer:
A reverse iterator is an iterator that traverses a container backward, from the last element toward the first. A reverse iterator inverts the meaning of increment (and decrement). Incrementing (++it) a reverse iterator moves the iterator to the previous element; derementing (--it) moves the iterator to the next element.
The containers, aside from forward_list, all have reverse iterators. We obtain a reverse iterator by calling the rbegin, rend, crbegin, and crend members. These members return reverse iterators to the last element in the container and one “past” (i.e., one before) the beginning of the container. As with ordinary iterators, there are both const and nonconst reverse iterators.
The following picture illustrates the relationship between these four iterators on a hypothetical vector named vec.
Comparing begin/cend and rbegin/crend Iterators
Insert Iterators
摘自C++ Primer:
An inserter is an iterator adaptor that takes a container and yields an iterator that adds elements to the specified container. When we assign a value through an insert iterator, the iterator calls a container operation to add an element at a specified position in the given container.
There are three kinds of inserters. Each differs from the others as to where elements are inserted:
- back_inserter creates an iterator that uses push_back.
- front_inserter creates an iterator that uses push_front.
- inserter creates an iterator that uses insert. This function takes a second argument, which must be an iterator into the given container. Elements are inserted ahead of the element denoted by the given iterator.
- 使用inserter的返回值是什么? (摘自C++ Primer)
It is important to understand that when we call
inserter(c, iter), we get an iterator that, when used successively, inserts elements ahead of the element originally denoted by iter. That is, if it is an iterator generated by inserter, then an assignment such as*it=val;behaves as the following code:
it = c.insert(it, val); // it points to the newly added element
++it; // increment it so that it denotes the same element as before
X適配器: istream_iterator 和 ostream_iterator
基本概念(摘自C++ Primer):
Even though the iostream types are not containers, there are iterators that can be used with objects of the IO types. An istream_iterator reads an input stream, and an ostream_iterator writes an output stream. These iterators treat their corresponding stream as a sequence of elements of a specified type. Using a stream iterator, we can use the generic algorithms to read data from or write data to stream objects.
istream_iterator的使用(摘自C++ Primer):
When we create a stream iterator, we must specify the type of objects that the iterator will read or write. An istream_iterator uses >> to read a stream. Therefore, the type that an istream_iterator reads must have an input operator defined. When we create an istream_iterator, we can bind it to a stream. Alternatively, we can default initialize the iterator, which creates an iterator that we can use as the off-the-end value.
ostream_iterator的使用(摘自C++ Primer):
An ostream_iterator can be defined for any type that has an output operator (the << operator). When we create an ostream_iterator, we may (optionally) provide a second argument that specifies a character string to print following each element. That string must be a C-style character string (i.e., a string literal or a pointer to a null-terminated array). We must bind an ostream_iterator to a specific stream. There is no empty or off-the-end ostream_iterator.
