Algorithms看不见Containers，对其一无所知。所以，它所需要的一切信息都必须从iterators取得，而iterators（由Containers提供）必须能够回答Algorithm的所有提问，才能搭配该Algorithm的所有操作。
1. C++ 标准库提供了五种迭代器类别
- Input Iterator（输入迭代器）
- Output Iterator（输出迭代器）
- Forward Iterator（前向迭代器）
- Bidirectional Iterator（双向迭代器）
- Random Access Iterator（随机访问迭代器）
2.iterator模版
std::iterator 是一个方便的模板，它简化了自定义迭代器的定义。它提供了标准化的方式来定义迭代器的类型信息。它有以下五个模板参数：
iterator_category：迭代器的类别（如input_iterator_tag、output_iterator_tag等）。value_type：迭代器所指向的值的类型。difference_type：两个迭代器之间的距离类型。pointer：指向value_type的指针类型。reference：引用value_type的类型。
3.各种容器的iterators的iterator_category
#include<typeinfo>
void _display_category(input_iterator_tag) {
std::cout << "Input iterator" << std::endl;
}
void _display_category(output_iterator_tag) {
std::cout << "Output iterator" << std::endl;
}
void _display_category(forward_iterator_tag) {
std::cout << "Forward iterator" << std::endl;
}
void _display_category(bidirectional_iterator_tag) {
std::cout << "Bidirectional iterator" << std::endl;
} // √
void _display_category(random_access_iterator_tag) {
std::cout << "Random access iterator" << std::endl;
}
void _display_category(std::input_iterator_tag) {
std::cout << "Input iterator" << std::endl;
} // 输入迭代器
void _display_category(std::output_iterator_tag) {
std::cout << "Output iterator" << std::endl;
} // 输出迭代器
template<typename I>
void display_category(I it)
{
// 提问与回答
typename iterator_traits<I>::iterator_category cagy;
_display_category(cagy);
cout << "typeid(it).name()=" << **typeid**(it).name << endl;
}
display_category(set<int>::iterator());
- 使用了
typeid(it).name()来输出迭代器it的类型信息
display_category(istream_iterator<int>()); // Input iterator
display_category(ostream_iterator<int>(cout, "")); // Output iterator
- 输入迭代器的定义：
template <typename T, typename CharT = char, typename Traits = std::char_traits<CharT>, typename Dist = std::ptrdiff_t>
class istream_iterator{
public:
typedef input_iterator_tag iterator_category; // (1)
typedef T value_type; // (2)
typedef const T* pointer; // (3)
typedef const T& reference; // (4)
typedef Dist difference_type; // (5)
private:
basic_istream<CharT, Traits>* in_stream;
T value;
...
};
4.iterator_category对算法的影响
例如：distance算法求解两个指针之间的距离。
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, catrgory());
}
template<class InputIterator>
inline iterator_traits<InputIterator>::difference_type
__difference(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>::difference_type
__difference(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag)
{
return last - first;
}
inline关键字：建议编译器内联扩展此函数，尽量避免函数调用的开销，具体是否内联由编译器决定。typename iterator_traits<InputIterator>::difference_type：这是函数的返回类型。
random_access_iterator_tag → bidirectional_iterator_tag → farward_iterator_tag → input_iterator_tag
！如果当萃取机问得的答案category是
farward_iterator_tag 或bidirectional_iterator_tag时，要调用input_iterator_tag的实现。
- 算法源码中对iterator_category的“暗示”
- 对于输入迭代器（
input_iterator_tag），使用逐元素遍历计数的方式计算距离。 - 对于随机访问迭代器（
random_access_iterator_tag），使用指针减法直接计算距离。
- 对于输入迭代器（
5.accumulate算法内部剖析
通常有两种版本
第一种，默认版本：
template <class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init)
{
for( ; first != last; ++first)
init = init + *first;
return init;
}
第二种，加了仿函数：
template <class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binary_op)
{
for(;first!=last;++first)
init = binary_op(init, *first);
return init;
}
调用：
int myfunc(int x, int y)
{ return x + 2*y;}
struct myclass
{
int operator()(int x, int y)
{ return x + 3*y;}
} myobj;
void test_accumulate()
{
int init = 100;
int nums[] = {10, 20, 30};
accumulate(nums, nums+3, init); // 160
accumulate(nums, nums+3, init, minus<int>()); // 40
accumulate(nums, nums+3, init, myfunc); // 220 仿函数
accumulate(nums, nums+3, init, myobj); // 280 函数对象
}
6.容器中是否带有全局算法的同名成员函数
count()：
- 带：set/multiset, map/multimap, unordered_set/unordered_multiset, unordered_map/unordered_multimap
- 不带：array, vector, list, forward_list, deque
find()：
- 带：set/multiset, map/multimap, unordered_set/unordered_multiset, unordered_map/unordered_multimap
- 不带：array, vector, list, forward_list, deque
sort()：
- 带：list, forward_list
- 不带：array, vector, deque, set/multiset, map/multimap, unordered_set/unordered_multiset, unordered_map/unordered_multimap
7.仿函数functors的可适配adaptable条件
// using default comparison (operator <):
sort(myvec.begin(), myvec.end());
// 没有融入STL(因为没有继承，无法回答问题)
sort(myvec.begin(), myvec.end(), myfunc);
sort(myvec.begin(), myvec.end(), myobj);
// 融入STL
sort(myvec.begin(), myvec.end(), less<int>());
sort(myvec.begin(), myvec.end(), greater<int>());
int myfunc(int x, int y)
{ return (x < y);}
struct myclass
{
int operator()(int x, int y)
{ return (x < y);}
} myobj;
template<class T>
struct greater : public binary_function<T,T,bool>{
bool operator()(const T& x, const T& y)
{return x > y;}
};
template<class T>
struct less : public binary_function<T,T,bool>{
bool operator()(const T& x, const T& y)
{return x < y;}
};
- 通过继承自
binary_function，less与greayer自动获得了这些类型定义。
typedef int first_argument_type;
typedef int second_argument_type;
typedef bool result_type;
- 一个仿函数要适配STL中的函数适配器（能够回答问题），通常需要满足以下条件：
- 类型定义：提供
first_argument_type、second_argument_type和result_type这些类型定义（对于二元仿函数）。 - 操作符重载：重载函数调用操作符
operator()，实现实际的操作逻辑。
- 类型定义：提供
- STL提供了一些仿函数适配器，用于创建或修改仿函数以满足特定的需求
8.常见适配器
- 容器适配器（内含一个容器）：stack,queue
template <class T, class Sequence=deque<T>>
class stack {
...
public:
typedef typename Sequence::value_type value_type;
typedef typename Sequence::size_type size_type;
typedef typename Sequence::reference reference;
typedef typename Sequence::const_reference const_reference;
protected:
Sequence c; // deque是stack的底层容器
public:
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
reference top() { return c.back(); }
const_reference top() const { return c.back(); }
void push(const value_type& x) { c.push_back(x); }
void pop() { c.pop_back(); )
- 仿函数适配器（将一个函数对象转换成另一个函数对象）：binder2nd
bind2nd 是一个函数适配器，用于将二元函数对象的第二个参数绑定为一个固定值，从而生成一个新的仿函数，使其只接受一个参数。
auto less_than_5 = bind(less<int>(), 5);
-
bind2nd函数模板通过绑定二元函数对象的第二个参数，返回一个binder2nd对象。template <class Operation, class T> inline binder2nd<Operation> bind2nd(const Operation& op, const T& x) { typedef typename Operation::second_argument_type arg2_type; return binder2nd<Operation>(op, arg2_type(x)); } -
binder2nd类模板继承自unary_function，实现将二元函数对象转换为一元函数对象。template <class Operation> class binder2nd : public unary_function<typename Operation::first_argument_type, typename Operation::result_type> { protected: Operation op; // 内部成员，存储二元函数对象 typename Operation::second_argument_type value; // 存储绑定的第二个参数 public: // 构造函数 binder2nd(const Operation& x, const typename Operation::second_argument_type& y) : op(x), value(y) {} // 重载的函数调用操作符 typename Operation::result_type operator()(const typename Operation::first_argument_type& x) const { return op(x, value); // 实际调用存储的二元函数对象，并将value作为第二个参数 } }; -
新型适配器bind
std::bind是一个函数适配器，可以将函数或函数对象的一部分参数绑定到特定的值上，从而生成一个新的函数对象。它可以绑定：- 普通函数
- 函数对象
using namespace std::placeholders; double my_divide(double x, double y) { return x / y;} auto fn_five = bind(my_divide, 10, 2); cout << fn_five() << endl; // 5 auto fn_half = bind(my_divide, _1, 2); // 占位符 cout << fn_five(10) << endl; // 5 auto fn_invert = bind(my_divide, _2, _1); // 占位符 cout << fn_five(10, 2) << endl; // 0.2 auto fn_rounding = bind<int>(my_divide, _1, _2); // 占位符 cout << fn_five(10, 3) << endl; // 3- 成员函数
struct MyPair { double a, b; double multiply() { return a * b; } }; MyPair ten_two {10, 2}; auto bound_memfn = bind(&MyPair::multiply, _1); cout << bound_memfn(ten_two) << endl; // 20- 数据成员
auto bound_memdata = bind(&MyPair::a, ten_two); cout << bound_memdata() << endl; // 绑定a，输出：10 auto bound_memdata2 = bind(&MyPair::b, std::placeholders::_1); cout << bound_memdata2(ten_two) << endl; // 绑定b，输出：2 -
迭代器适配器reverse_iterator
-
使用
reverse_iterator适配器将普通的前向迭代器转换为反向迭代器，使得可以从容器的末尾向前遍历元素。 -
rbegin(): 返回一个指向容器最后一个元素的反向迭代器reverse_iterator rbegin() {return reverse_iterator(end());} -
rend(): 返回一个指向容器第一个元素前一个位置的反向迭代器。reverse_iterator rend() {return reverse_iterator(begin());}
template <class Iterator> class reverse_iterator { protected: Iterator current; // 对应的正向迭代器 public: typedef typename iterator_traits<Iterator>::iterator_category iterator_category; typedef typename iteratot_traits<Iterator>::value_type value_type; typedef typename iteratot_traits<Iterator>::difference_type difference_type; typedef typename iteratot_traits<Iterator>::pointer pointer; typedef typename iteratot_traits<Iterator>::reference reference; typedef Iterator iterator_type; // 代表正向迭代器 typedef reverse_iterator<Iterator> self; // 代表逆向迭代器 public: // 构造函数：将传入的迭代器 x 用于初始化成员变量 current // 该构造函数用于将一个正向迭代器转换为一个反向迭代器 explicit reverse_iterator(iterator_type x): current(x){} //复制一个现有的反向迭代器对象 reverse_iterator(const self& x): current(x.current) {} // 取出对应的正向迭代器 iterator_type base() const { return current;} // 逆向迭代器取值时，对应的正向迭代器向后移一位 reference operator*() const { Iterator tmp = current; return *--tmp;} pointer operator->() const { return &operator*();} self& operator++ { --current; return *this;} self& operator-- { ++current; return *this;} self operator+(difference_type n) { return self(current - n);} self operator-(difference_type n) { return self(current + n);} }; -
-
迭代器适配器inserter
list<int> foo, bar;
for(int i=1; i<5; i++)
{ foo.push_back(i); bar.push_back(i*10);}
list<int>::iterator it = foo.begin();
advance(it, 3);
copy(bar.begin(), bar.end(), inserter(foo,it));
// inserter中的container是指向foo的指针
template <class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result)
{
while(first!=last)
{
*result = *first;
++first;
++result;
}
return result;
}
- 在
*result = *first这一步，输出迭代器需要重载等号操作符是因为对于标准的迭代器（如指针、vector的迭代器等），这些操作符已经默认提供。然而，对于自定义迭代器（如插入迭代器），需要重载这些操作符以实现特定的行为。
template <class Container, class Iterator>
inline insert_iterator<Container> insert(Container& x, Iterator i)
{
typedef typename Container::iterator iter; // 容器的迭代器的类型
// 将传入的迭代器类型转换为容器的迭代器的类型
return insert_iteraor<Container>(x, iter(i));
};
Container& x：这是一个引用，指向将要进行插入操作的容器。Iterator i：这是一个迭代器，指示插入位置。
tempalte <class Container>
class insert_iterator
{
protected:
Container* container; // 底层容器的指针
typename Container::iterator iter;
typedef insert_iterator<Container> self;
public:
typedef output_iterator_tag iterator_category;
// 初始化时，将容器地址赋给container
insert_iterator(Container& x, typename Container::iterator i):container(&x), iter(i) {}
self& operaor=(const typename Container::value_type& value){
iter = container->insert(iter,value); // 使用容器的insert方法插入value
++iter; // 插入后，迭代器前移
return *this;
}
};
-
++iter; 令insert iterator永远随其target贴身移动
举例：
int main(){ vector<int> v = {1, 2, 3}; vector<int>::iterator it = v.begin(); advance(it, 1); insert_iterator<vector<int>> inserter(v, it); *inserter = 10; // 插入10后，inserter迭代器自动更新到10之后 *inserter = 20; // 插入20后，inserter迭代器自动更新到20之后 // 1, 10, 20, 2, 3 -
创建一个插入迭代器
insert_iterator对象有两种方法- 直接调用构造函数：
insert_iterator<vector<int>> inserter(v, it); // 这里 inserter 是一个 insert_iterator<vector<int>> 对象 // 这直接调用了 insert_iterator 的构造函数- 使用辅助函数inserter：
auto inserter_it = inserter(v, it); // 这里 inserter_it 是一个 insert_iterator<vector<int>> 对象 // inserter(v, it) 调用了辅助函数 inserter // 该函数内部调用了 insert_iterator 的构造函数 // 创建并返回一个 insert_iterator 对象
9.输出流迭代器ostream_iterator
- 代码示例
int main(){
vector<int> v;
for(int i=1; i<10; i++)
{
v.push_back(i*10);
}
ostream_iterator<int> out_it(cout, ", ");
copy(v.begin(), v.end(), out_it);
template <class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result)
{
while(first!=last)
{
*result = *first;
++first;
++result;
}
return result;
}
- 因为
iterator中有五个模板参数。而对于ostream_iterator，它是一个输出迭代器，因此只关心iterator_category，而其他类型都不需要（可以设置为void）。
template <class T, class charT=char, class traits=char_traits<charT>>
class ostream_iterator:public iterator<output_iterator_tag, void, void, void, void>
{
protected:
basic_ostream<charT, traits>* out_stream;
const charT* delim;
public:
typedef ostream_iterator<T, charT, traits> self;
typedef basic_ostream<charT, traits> ostream_type;
// ostream_iterator<int> out_it(cout);
ostream_iterator(ostream_type& s):out_stream(&s), delim(0) {}
// ostream_iterator<int> out_it(cout, ", ");
ostream_iterator(ostream_type& s, const charT* delimiter) : out_stream(&s), delim(delimiter) {}
// ostream_iterator<int> out_it(cout, ", ");
// ostream_iterator<int> out_it_copy(out_it);
ostream_iterator(const ostream_iterator<T, charT, traits>& x) : out_stream(x.out_stream), delim(x.delim) {}
~ostream_iterator() {}
self& operator=(const T& value) {
*out_stream << value; // out_stream 指向的输出流对象是cout
if (delim != 0) *out_stream << delim;
return *this;
}
10.输入流迭代器istream_iterator
#include <iostream>
#include <iterator>
int main() {
double value1, value2;
cout << "Please, insert two values: ";
istream_iterator<double> eos; // end-of-stream iterator 表示输入流的结束
istream_iterator<double> iit(cin); // stdin iterator 绑定到标准输入 std::cin
if (iit != eos) value1 = *iit; // 读取第一个值,因为在构造时就已经开始尝试从输入流中读取一个值
++iit; // 移动到下一个输入
if (iit != eos) value2 = *iit; // 读取第二个值
cout << value1 << " * " << value2 << " = " << (value1 * value2) << '\\n';
return 0;
}
template <class T, class charT=char, class traits=char_traits<charT>, class Distance=ptrdiff_t>
class istream_iterator : public iterator<input_iterator_tag, T, Distance, const T*, const T&> {
basic_istream<charT, traits>* in_stream; // 输入流指针
T value; // 存储读取的值
public:
typedef basic_istream<charT, traits> istream_type;
typedef istream_iterator<T, charT, traits, Distance> self;
istream_iterator() : in_stream(0) {} // 作为结束迭代器的标志
istream_iterator(istream_type& s) : in_stream(&s) { ++*this; } // cin就是输入流指针s
istream_iterator(const self& x) : in_stream(x.in_stream), value(x.value) {}
~istream_iterator() {}
const T& operator*() const { return value; }
const T* operator->() const { return &value; }
self& operator++() {
if (in_stream && !(*in_stream >> value)) in_stream = 0;
return *this;
}
self operator++(int) {
istream_iterator<T, charT, traits, Distance> tmp = *this;
++*this;
return tmp;
}
bool operator==(const self& rhs) const {
return in_stream == rhs.in_stream;
}
bool operator!=(const self& rhs) const {
return in_stream != rhs.in_stream;
}
};
