资料：
stl-iterators
[The C++ Standard Library: Tutorial & Reference]
迭代器分类
from [here](http://www.cplusplus.com/reference/iterator/)
from C++STL Tutorial & Ref.
深入学习之前，我对下面这几个问题感到迷茫：
- ++i vs. i++
- 迭代器的合法增长方向
- 迭代器的失效
- 迭代器 vs. 下标运算符
Phase_1 系统地过一遍
- 原理
其实上面那个图已经很清楚地显示了不同分类（categories）的迭代器之间的关系和其合法操作了.
(根据上面的一系列定义定义的5个级别的迭代器，每种都有自己支持的操作)
- Input Iterator
- Output Iterator
- Forward Iterator
- Bidirectional Iterator
- Random Access Iterator
- 实现
上面那些只是一些定义，C++使用所谓的trait class来实现区分这几种迭代器的.(effective c++ RULE no. 47),一种泛型上的概念，即类型的信息.
简单地说，你可以自己实现自己的类的Iterator(随便取你的迭代器名字)，然后在你的迭代器定义中显式地加入一些typedef, 比如value_type、iterator_catagory;这几种别名是std里约定好了，在std里的一些算法将根据这些别名做不同的处理，比如你想说明自己的Iterator是个随机Acess的iterator，则在你的iterator中加入一个typedef std::random_access_iterator_tag iterator_category;到了STL的算法内部会根据你的Iterator中的这些typedef来指定不同的算法实现.
利用tag-dispatching的原因有个比较重要的就是，在编译阶段利用函数的重载机制决定采用哪个do_algorthm来实现.
这里可能会有点晕，附2的目标就是把附1实现的Iterator变成STL-portable的.(可能有点丑，但可以说明问题)
STL如何实现tag-dispatching的，在另一篇里细细来讲(其实也没啥好讲的一但理解了，就很简单).这里有些资料：
-
how-do-traits-classes-work - NO MAGIC!!!
--------------------废话的分割线--------------------
经过一整晚的潜心研究，我终于大致搞懂了iterator的原理和相关的实现(雾)。
上面的描述顶多只能算概念上的描述，实际的实现灵活并奇怪得多.
附1中的Iterator顶多只能算个base_Iterator, 为了让它能够与STL的算法库兼容（如find， distance， copy等），还需要一个wapper-like的模板类包装一下(使这个Iterator实现所谓的tag-dispatching)，其原理实际上就是编译期间绑定，明天继续！明天将参考STLPort实现来进行wrap并使其能支持STL算法库.
（关键词：effective c++_42/46, typedef, overloading, iterator_traits）
--------------Will be Updated SOON---------------实际上几乎拖了一周才更新
--------------------废话的分割线--------------------
Phase_2 回过头来解决最初的问题
- ++i vs. i++
++iis better.
make sure you create a habit of using pre-increment with iterators in loops. i.e. use ++it and not it++. The pre-increment will not create unnecessary temporaries.
- 我认为其实根本原因还是 operator重载中，
a@将调用a.operator(0),而@a将调用a.operator@()，前者将增加一个临时对象, 因此效率会比较低.
(附1.)
<下面3个问题应该是属于使用方面的问题，在另一篇专门来研究如何使用>
迭代器的（合法）增长方向
迭代器的失效
迭代器 vs. 下标运算符
附1. 实现了一个带迭代器的字符串类
#include <cstdio>
#include <cstring>
#include <cassert>
#include <iostream>
class MyString{
public:
MyString() : data_(NULL), size_(0){ }
MyString(const char* s);
MyString(const MyString &b) : size_(b.size_), data_(NULL){
//deep copy
if(size_){
data_ = new char [BufSize(size_)];
memcpy(data_, b.data_, BufSize(size_));
}
}
~MyString(){
if(data_){
delete [] data_;
}
}
MyString& operator=(const MyString &);
bool operator!=(const MyString &);
bool operator==(const MyString &);
MyString operator+(const MyString &);
MyString& operator+=(const MyString &);
char& operator[](const int);
class Iterator{
public:
Iterator() : ptr(NULL){ }
Iterator& operator++(){
ptr++;
return *this;
}
Iterator& operator--(){
ptr--;
return *this;
}
Iterator& operator+(int x){
ptr += x;
return *this;
}
Iterator& operator-(int x){
ptr -= x;
return *this;
}
bool operator!=(const Iterator &s){
return s.ptr != ptr;
}
char& operator*(){
return *ptr;
}
private:
friend MyString;
Iterator(char *s) : ptr(s){ }
char* ptr;
};
Iterator begin(){
return Iterator(data_);
}
Iterator end(){
return Iterator(data_ + size_);
}
int size(){ return size_; }
private:
char* data_;//end with '\0'
int size_;
int BufSize(const int s) const{ return s + 1; }
char* ReSizeBuf(int s){
// std::cout << "[DBG]\n";
// std::cout << s << size_ << std::endl;
if(s > size_){
if(data_){ delete [] data_; }
data_ = new char [BufSize(s)];
}
size_ = s;
return data_;
}
friend std::ostream & operator<<(std::ostream &out, const MyString& s);
};
MyString::MyString(const char* s)
: size_(strlen(s)),
data_(NULL)
{
if(size_){
data_ = new char [BufSize(size_)];
memcpy(data_, s, BufSize(size_));
}
}
MyString& MyString::operator=(const MyString &b)
{
//deep copy
//origin data is overwrote
if(&b != this){
ReSizeBuf(b.size_);
memcpy(data_, b.data_, BufSize(size_));
}
return *this;
}
bool MyString::operator!=(const MyString & b)
{
return !(*this == b);
}
bool MyString::operator==(const MyString & b)
{
if(b.size_ == size_){
return memcmp(b.data_, data_, size_) == 0;
}
return false;
}
//It's not good to do this because it will do 2 alloc.s & dealloc.s(temp. var in c++)
MyString MyString::operator+(const MyString &b)//will concat the two string.
{
MyString tmp;
memcpy(tmp.ReSizeBuf(size_ + b.size_), data_, size_);
memcpy(tmp.data_ + size_, b.data_, BufSize(b.size_));
return tmp;
}
MyString& MyString::operator+=(const MyString &b)
{
char* tmp = BufSize(size_) < BufSize(size_ + b.size_) ?
new char [BufSize(size_ + b.size_)] : data_ ;
if(tmp != data_){
memcpy(tmp, data_, size_);
}
memcpy(tmp + size_, b.data_, BufSize(b.size_));
if(tmp != data_){
delete [] data_;
}
data_ = tmp;
size_ = size_ + b.size_;
return *this;
}
char& MyString::operator[](const int idx)
{
assert(idx < size_);
return *(data_ + idx);
}
std::ostream & operator<<(std::ostream &out, const MyString& s)
{
return s.data_ ? out << s.data_ : out << "";
}
void test1(){
std::string ss = "12345";
std::string::iterator itr;
for(itr = ss.begin(); itr != ss.end(); itr++)
{
printf("%c ", *itr);
}
printf("\n");
}
void test_MyString()
{
MyString s1;
MyString s2("Hello");
MyString s3 = "1234";
MyString s4(s3);
std::cout << s1 << s2 << s3 << s4 << std::endl;
}
void test_operator()
{
MyString s1 = "Hello";
MyString s2 = "Hi";
MyString s3 = ", there";
MyString s4, s5("fff");
std::cout << s4 << " " << s4.size() << ";" << s5 << " " << s5.size() <<std::endl;
s4 = s5 = s1;
std::cout << s4 << " " << s4.size() << ";" << s5 << " " << s5.size()<<std::endl;
std::cout << (s2 == s1 ? "yes" : "no") << std::endl;
s2 = s1;
std::cout << (s2 != s1 ? "no" : "yes") << std::endl;
std::cout << s2 + s3 << std::endl;
s2 += s3;
std::cout << s2 << " " << s2.size() << std::endl;
s2[0] = 'K';
std::cout << s2 << std::endl;
}
void test_iterator()
{
MyString ssx = "Hi, My name is...";
/*
the post-increment ==> itr++ ==> will call MyString::Iterator::operator++(0)
pre-increment.cc:195:6: error: no ‘operator++(int)’ declared for postfix ‘++’ [-fpermissive]
itr++){
^
for(MyString::Iterator itr = ssx.begin();
itr != ssx.end();
itr++){
std::cout << *itr << " " << std::endl;
}
*/
for(MyString::Iterator itr = ssx.begin();
itr != ssx.end();
++itr){
std::cout << *itr << " ";
}
std::cout << std::endl;
}
int main()
{
// char s[4] = {'1','2','4','3'};
// std::cout << s << std::endl;
test_iterator();
return 0;
}
附2. 令附1的代码能支持std::copy()，std::distance()等
代码丑陋 有待优化，但主要目的，令自己写的Iterator可以支持STL的algorithm的目的已经达到了.
#include <cstdio>
#include <cstring>
#include <cassert>
#include <iostream>
#include <iterator>//for the tags
#include <algorithm>//we need to support, for exmaple: std::find() std::copy()
class MyString{
public:
MyString() : data_(NULL), size_(0){ }
MyString(const char* s);
MyString(const MyString &b) : size_(b.size_), data_(NULL){
//deep copy
if(size_){
data_ = new char [BufSize(size_)];
memcpy(data_, b.data_, BufSize(size_));
}
}
~MyString(){
if(data_){
delete [] data_;
}
}
MyString& operator=(const MyString &);
bool operator!=(const MyString &);
bool operator==(const MyString &);
MyString operator+(const MyString &);
MyString& operator+=(const MyString &);
char& operator[](const int);
class Iterator{
public:
typedef typename std::random_access_iterator_tag iterator_category;
typedef char value_type;
typedef int difference_type;
typedef char* pointer;
typedef char& reference;
Iterator() : ptr(NULL){ printf("[DBG] Iterator() is called\n"); }
Iterator& operator++(){
ptr++;
return *this;
}
Iterator& operator--(){
ptr--;
return *this;
}
Iterator& operator+(int x){
ptr += x;
return *this;
}
Iterator& operator-(int x){
ptr -= x;
return *this;
}
//error: no match for ‘operator-’ (operand types are ‘MyString::Iterator’ and ‘MyString::Iterator’)
//we have to impl the operator-(Iterator)
difference_type operator-(const Iterator& rhs){
return ptr - rhs.ptr;
}
bool operator!=(const Iterator &s){
return s.ptr != ptr;
}
bool operator==(const Iterator &s){
return !(*this != s);
}
//std::find() will use this operator
bool operator==(value_type c){
return *ptr == c;
}
char& operator*(){
return *ptr;
}
private:
friend MyString;
Iterator(char *s) : ptr(s){
// printf("[DBG] Iterator(char*) is called\n");
}
protected:
char* ptr;
};
class OuputIterator : public Iterator{
public:
char& operator*(){
if(ptr == mptr_->end().ptr){
int offset = mptr_->size_;
mptr_->ReSizeCopyBuf((mptr_->size_ + 1) * 2);
ptr = mptr_->data_ + offset;
}
return *ptr;
}
void print(){
printf("[DBG] %p\n", ptr);
}
private:
friend MyString;//friend is not inherited
MyString* mptr_;
OuputIterator(MyString* me) : mptr_(me){ }
OuputIterator(char *s) : Iterator(s) { /*printf("[DBG] OuputIterator(char*) is called\n"); */}
};
Iterator begin(){
return Iterator(data_);
}
Iterator end(){
return Iterator(data_ + size_);
}
OuputIterator obegin(){
return OuputIterator(data_);
}
OuputIterator oend(){
return OuputIterator(data_ + size_);
}
int size(){ return size_; }
private:
char* data_;//end with '\0'
int size_;
int BufSize(const int s) const{ return s + 1; }
char* ReSizeBuf(int s){
// std::cout << "[DBG]\n";
// std::cout << s << size_ << std::endl;
if(s > size_){
if(data_){ delete [] data_; }
data_ = new char [BufSize(s)];
}
size_ = s;
return data_;
}
char* ReSizeCopyBuf(int s){
if(s > size_){
char* new_data_ = new char [BufSize(s)];
if(data_){
memcpy(new_data_, data_, BufSize(size_));
delete [] data_;
}
data_ = new_data_;
}
size_ = s;
return data_;
}
friend OuputIterator;
friend std::ostream & operator<<(std::ostream &out, const MyString& s);
};
MyString::MyString(const char* s)
: size_(strlen(s)),
data_(NULL)
{
if(size_){
data_ = new char [BufSize(size_)];
memcpy(data_, s, BufSize(size_));
}
}
MyString& MyString::operator=(const MyString &b)
{
//deep copy
//origin data is overwrote
if(&b != this){
ReSizeBuf(b.size_);
memcpy(data_, b.data_, BufSize(size_));
}
return *this;
}
bool MyString::operator!=(const MyString & b)
{
return !(*this == b);
}
bool MyString::operator==(const MyString & b)
{
if(b.size_ == size_){
return memcmp(b.data_, data_, size_) == 0;
}
return false;
}
//It's not good to do this because it will do 2 alloc.s & dealloc.s(temp. var in c++)
MyString MyString::operator+(const MyString &b)//will concat the two string.
{
MyString tmp;
memcpy(tmp.ReSizeBuf(size_ + b.size_), data_, size_);
memcpy(tmp.data_ + size_, b.data_, BufSize(b.size_));
return tmp;
}
MyString& MyString::operator+=(const MyString &b)
{
char* tmp = BufSize(size_) < BufSize(size_ + b.size_) ?
new char [BufSize(size_ + b.size_)] : data_ ;
if(tmp != data_){
memcpy(tmp, data_, size_);
}
memcpy(tmp + size_, b.data_, BufSize(b.size_));
if(tmp != data_){
delete [] data_;
}
data_ = tmp;
size_ = size_ + b.size_;
return *this;
}
char& MyString::operator[](const int idx)
{
assert(idx < size_);
return *(data_ + idx);
}
std::ostream & operator<<(std::ostream &out, const MyString& s)
{
return s.data_ ? out << s.data_ : out << "";
}
void test1(){
std::string ss = "12345";
std::string::iterator itr;
for(itr = ss.begin(); itr != ss.end(); itr++)
{
printf("%c ", *itr);
}
printf("\n");
}
void test_MyString()
{
MyString s1;
MyString s2("Hello");
MyString s3 = "1234";
MyString s4(s3);
std::cout << s1 << s2 << s3 << s4 << std::endl;
}
void test_operator()
{
MyString s1 = "Hello";
MyString s2 = "Hi";
MyString s3 = ", there";
MyString s4, s5("fff");
std::cout << s4 << " " << s4.size() << ";" << s5 << " " << s5.size() <<std::endl;
s4 = s5 = s1;
std::cout << s4 << " " << s4.size() << ";" << s5 << " " << s5.size()<<std::endl;
std::cout << (s2 == s1 ? "yes" : "no") << std::endl;
s2 = s1;
std::cout << (s2 != s1 ? "no" : "yes") << std::endl;
std::cout << s2 + s3 << std::endl;
s2 += s3;
std::cout << s2 << " " << s2.size() << std::endl;
s2[0] = 'K';
std::cout << s2 << std::endl;
}
void test_iterator()
{
MyString ssx = "Hi, My name is...";
/*
the post-increment ==> itr++ ==> will call MyString::Iterator::operator++(0)
pre-increment.cc:195:6: error: no ‘operator++(int)’ declared for postfix ‘++’ [-fpermissive]
itr++){
^
for(MyString::Iterator itr = ssx.begin();
itr != ssx.end();
itr++){
std::cout << *itr << " " << std::endl;
}
*/
for(MyString::Iterator itr = ssx.begin();
itr != ssx.end();
++itr){
std::cout << *itr << " ";
}
std::cout << std::endl;
}
void test_STL_algor()
{
MyString testss = "Hi, My Name is REM.";
std::cout << std::distance(testss.begin(), testss.end()) <<std::endl;
//std::distance() is actually included at the <iterator>
std::cout << std::find<MyString::Iterator, char>(testss.begin(), testss.end(), 'R') - testss.begin() << std::endl;
//std::find() is included at algorithm
MyString dst;
std::copy<MyString::Iterator, MyString::OuputIterator>(testss.begin(), testss.end(), dst.obegin());
std::cout<< dst << std::endl;
//... you can test other function of STL-algorithm
}
void testobegin()
{
MyString testss = "Hi, I am Rem.Nice to meet you.";
MyString::OuputIterator oitr = testss.obegin();
oitr.print();
}
int main()
{
test_STL_algor();
return 0;
}
TODO
- 3个遗留问题
- 附2优化
- 实现一个模拟STL的tag-dispatching.
