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); // 160accumulate(nums, nums+3, init, minus<int>()); // 40accumulate(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; // 5auto fn_half = bind(my_divide, _1, 2); // 占位符 cout << fn_five(10) << endl; // 5auto fn_invert = bind(my_divide, _2, _1); // 占位符 cout << fn_five(10, 2) << endl; // 0.2auto 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,输出:10auto 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;// 初始化时,将容器地址赋给containerinsert_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 指向的输出流对象是coutif (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::cinif (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就是输入流指针sistream_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;}
};