void test_set1()
{
  set<int> s;
  s.insert(3);
  s.insert(2);
  s.insert(1);
  s.insert(5);
  set<int>::iterator it = s.begin();
  while (it != s.end())
  {
    cout << *it << " ";
    it++;
  }
  cout << endl;
}
//迭代器的价值是什么？
//1.封装底层的实现，不暴露底层的实现细节
//2.提供统一的访问方式，降低使用的成本。（不需要关心set底层的二叉搜索树结构）
// 遍历一棵树不容易，但如果封装了迭代器进行访问那就容易很多了，这就足以降低使用的成本。
// 底层结构形态各异，但访问方式达到了统一

void push_back(const T& x)
{
  //node* newnode = new node(x);//会调用类Node的构造函数
  //node* tail = _head->_prev;
  //tail->_next = newnode;
  //newnode->_prev = tail;
  //newnode->_next = _head;
  //_head->_prev = newnode;
  insert(end(), x);
}
void push_front(const T& x)
{
  insert(begin(), x);
}
void pop_front()
{
  erase(begin());
}
void pop_back()
{
  erase(--end());//调用迭代器对象的operator--运算符重载
}
iterator insert(iterator pos, const T& x)
{
  node* newnode = new node(x);//调用node类的带参构造
  node* cur = pos._pnode;
  //通过迭代器对象pos拿到当前结点的结构体指针，pos所属类是struct，则成员是公有
  node* prev = cur->_prev;
  //拿到前一个和当前位置的node指针
  //prev newnode cur
  prev->_next = newnode;
  newnode->_prev = prev;
  newnode->_next = cur;
  cur->_prev = newnode;
  ++_size;
  return iterator(newnode);//返回插入结点的迭代器对象
}
iterator erase(iterator pos)
{
  //assert(pos != _head);//一个是指针，一个是迭代器类型，这里类型不匹配，选择用end()来进行比较
  assert(pos != iterator(_head));//迭代器位置不能是哨兵卫结点
  //assert(pos != end());//上下两种assert方式都可以
  //拿到当前位置的前一个和后一个位置的结构体指针
  node* prev = pos._pnode->_prev;
  node* next = pos._pnode->_next;
  prev->_next = next;
  next->_prev = prev;
  delete pos._pnode;
  --_size;
  return iterator(next);//返回删除位置的下一个位置的迭代器，这个迭代器现在是一个对象。vector那里是原生指针。
}

list()
{
  empty_initialize();
}
template <class InputIterator>
list(InputIterator first, InputIterator last)//迭代器区间为参数的默认构造
{
  empty_initialize();//如果不调用初始化接口，则被拷贝对象的_head是一个野指针，交换后析构会出问题。
  while (first != last)
  {
    push_back(*first);
    ++first;
  }
}
void swap(list<T>& lt)
{
  std::swap(_head, lt._head);
  std::swap(_size, lt._size);
}
// lt2(lt1)
//list(const list<T>& lt)//传统写法
//{
//  empty_initialize();//初始化被拷贝链表，先搞一个头结点出来。
//  //下面的范围for会傻瓜式的替换为const迭代器
//  for (auto& e : lt)//如果T是自定义类型，则会调用该类的拷贝构造，代价会很大，为了提高效率，这里用引用。
//  //范围for本质就是取容器里面的每一个迭代器，然后解引用迭代器赋值给元素e，如果T是string类型拷贝的字节会很多
//  {
//    //如果已知auto的类型是int，char等，可以不用引用，但如果是泛型或自定义类型，就应该用引用减少拷贝的消耗
//    push_back(e);//e是数据不是结点，解引用迭代器拿到的是数据，然后将数据尾插到链表里
//  }
//}
list(const list<T>& lt)//拷贝构造的现代写法
  //:_head(nullptr)//不能用空指针初始化_head，否则在析构时，进入到clear里面，begin()会访问空指针，造成越界访问
{
  empty_initialize();
  list<T> tmp(lt.begin(), lt.end());//交换两个指向头结点的结构体指针，就完成了链表的交换
  swap(tmp);
}
list<T>& operator=(list<T> lt)//现代写法
{
  swap(lt);
  return *this;//返回list<T>类的对象
}
// lt1=lt2
//list<T>& operator=(const list<T>& lt)//传统写法
//{
//  if (this != &lt)//对象的取地址运算符重载
//  {
//    //将this对象的数据先清掉，但不要清掉哨兵卫的头结点，就算你清了，等会儿还得empty_initialize
//    clear();
//    for (auto& e : lt)//这里也用auto引用
//    {
//      push_back(e);
//    }
//    return *this;
//  }
//}
void clear()//clear不清除头结点
{
  //C语言实现的方式：定义下一个节点的地址cur，删除cur->prev，++cur，cur->prev!=end()；
  //C++可以直接利用迭代器和erase进行删除。迭代器是真牛啊
  iterator it = begin();
  while (it != end())
  {
    it = erase(it);//不更新it，会出现迭代器失效的问题。
    //++it;//再++it的位置就不对了，clear无法完全删除除头之外的节点，erase会自动返回删除位置的下一个位置的迭代器
  }
}
size_t size()const//提供const版本，这样const对象和非const对象都可以调用
{
  //如果搞一个迭代器循环，计数器记录到底有多少个结点，然后返回计数器大小。
  //但如果频繁调用size()的话，则效率就会降下来。所以可以想到以空间换时间，多在list里面加一个成员变量
  return _size;
}
bool empty()const
{
  return _size == 0;//两个条件都可以
  //return _head == _head->_next;
}
~list()//析构函数清除头结点
{
  //如果显示写了析构函数会存在野指针访问的问题，没写则依靠不处理内置类型的默认析构来析构对象。
  //如果内置类型涉及堆空间的资源申请，则调用编译器的默认析构会导致内存泄露的问题，但内存泄露又不会报错，
  //这真是令人害怕的事情！
  clear();
  delete _head;
  _head = nullptr;
}

// const T* p1;
// T* const p2;
//正确的const迭代器类似于p1的行为，解引用迭代器后的内容不能被修改，但迭代器本身可以被修改，因为无论是const还是非const迭代器都要++或--
void print_list(const list<int>& lt)
{
  //普通迭代器前面加个const肯定是不行的，这不符合const迭代器的意义。
  const list<int>::iterator cit = lt.begin();
  //这样写的话，const修饰的是迭代器本身，迭代器不能++或--了，我们要的是const修饰迭代器指向的内容
  list<int>::const_iterator it = lt.begin();
  while (it != lt.end())
  {
    //(*it) += 2;//实现const迭代器之后，这里就不能写了
    cout << *it << " ";
    ++it;
  }
  cout << endl;
}

T& operator*()
{
  return _pnode->_data;//返回变量_data的引用，表示数据可以被读或修改，_data的类型是T
}
//const iterator cit;
//*cit;
//++it;这样的话，可以解引用，但是不能++
const T& operator*()const
{
  return _pnode->_data;
}
__list_iterator<T>& operator++()//++改变的就是成员变量_pnode，所以不能用const修饰此函数
{
  _pnode = _pnode->_next;
  return *this;
}
__list_iterator<T>& operator--()
{
  _pnode = _pnode->_prev;
  return *this;
}

template<class T>
struct __list_const_iterator//将迭代器进行了封装，以便于解引用，++，--等运算符依旧对迭代器适用
{
  //迭代器的封装完美体现了面向对象封装的思想，以及类和对象强大的力量。一个成员变量仅仅是结构体指针的迭代器对象
  //可以通过运算符重载和类封装的思想，将迭代器的功能实现的滴水不漏，隐藏底层实现的机制。
  typedef list_node<T> node;
  node* _pnode;
  __list_const_iterator(node* p)
    :_pnode(p)
  {}
  const T& operator*()
  {
    return _pnode->_data;//返回变量_data的引用，表示数据可以被读或修改，_data的类型是T
  }
  __list_const_iterator<T>& operator++()//++改变的就是成员变量_pnode，所以不能用const修饰此函数
  {
    _pnode = _pnode->_next;
    return *this;
  }
  __list_const_iterator<T>& operator--()
  {
    _pnode = _pnode->_prev;
    return *this;
  }
  bool operator!=(const __list_const_iterator<T>& it)const//比较两个迭代器是否相等，实际比较的是list_node的地址是否相等
  {
    return _pnode != it._pnode;
  }
};
template<class T>
class list
{
  typedef list_node<T> node;
public:
  typedef __list_iterator<T> iterator;//iterator是类模板的typedef，模板也是类型，只不过还没有实例化
  typedef __list_const_iterator<T> const_iterator;
  const_iterator begin()const//const修饰*this，代表list对象的成员变量不可被修改，用于const的list对象调用。
  {
    return const_iterator(_head->_next);
  }
  const_iterator end()const
  {
    return const_iterator(_head);
  }
  iterator begin()
  {
    return iterator(_head->_next);
  }
  iterator end()
  {
    return iterator(_head);
  }
  ……………………省略
}

// typedef __list_iterator<T, T&> iterator;
// typedef __list_iterator<T, const T&> const_iterator;
template<class T, class Ref>
struct __list_iterator
{
  typedef list_node<T> node;
  typedef __list_iterator<T, Ref> Self;
  node* _pnode;
  __list_iterator(node* p)
    :_pnode(p)
  {}
  Ref operator*()
  {
    return _pnode->_data;//返回的是数据类型，所以用Ref
  }
  Self& operator++()
  {
    _pnode = _pnode->_next;
    return *this;
    //返回的是迭代器对象，所以用该迭代器对应的类的类型，实际就是__list_iterator<T,Ref>
    //只是将__list_iterator<T,Ref> typedef为 Self
  }
  Self& operator--()
  {
    _pnode = _pnode->_prev;
    return *this;
  }
  bool operator!=(const Self& it)
  {
    return _pnode != it._pnode;
  }
};
template<class T>
class list
{
  typedef list_node<T> node;
public:
  typedef __list_iterator<T, T&> iterator;
  //typedef __list_const_iterator<T> const_iterator;
  typedef __list_iterator<T, const T&> const_iterator;
  const_iterator begin() const
  {
    return const_iterator(_head->_next);
  }
  const_iterator end() const
  {
    return const_iterator(_head);
  }
  ……………………省略
}

cout << (*it)._row << ":" << (*it)._col << endl;

cout << it->_row << ":" << it->_col << endl;

cout << it->->_row << ":" << it->->_col << endl;//严格来说应该是这样写的
cout << it->_row << ":" << it->_col << endl;//但编译器为了代码可读性，做了特殊处理，省略掉一个->
cout << it.operator->()->_row << ":" << it.operator->()->_col << endl;

cout << (*it)._row << ':' << (*it)._col << endl;

//typedef __list_iterator<T,T&,T*> iterator
//typedef __list_iterator<T,const T&,const T*> const_iterator;
template<class T,class Ref,class Ptr>
struct __list_iterator//将迭代器进行了封装，以便于解引用，++，--等运算符依旧对迭代器适用
{
  //迭代器的封装完美体现了面向对象封装的思想，以及类和对象强大的力量。一个成员变量仅仅是结构体指针的迭代器对象
  //可以通过运算符重载和类封装的思想，将迭代器的功能实现的滴水不漏，隐藏底层实现的机制。
  typedef list_node<T> node;
  typedef __list_iterator<T, Ref, Ptr> Self;//Self代表整个类模板实例化的类型，这就是typedef的价值。
  node* _pnode;
  __list_iterator(node*p)
    :_pnode(p)
  {}
  //T* operator->()
  //{
  //  return &_pnode->_data;//返回list_node的_data的地址，这个地址是对象的地址，可以用于对象的成员选择。
  //}
  Ptr operator->()
  {
    return &_pnode->_data;//返回list_node的_data的地址，这个地址是对象的地址，可以用于对象的成员选择。
  }
}
struct Pos
{
  //friend ostream& operator<<(ostream& out, Pos& p);实际这里不用用友元，因为struct默认是public
  Pos(int row = 0, int col = 0)//全缺省的构造既能当默认构造用，又能当传具体参数的构造用。
    :_row(row)
    , _col(col)
  {}
  int _row;
  int _col;
};
ostream& operator<<(ostream& out, Pos& p)
{
  out << p._row << ":" << p._col;
  return out;
}
void test_list5()
{
  list<Pos> lt;
  Pos p1(1, 1);
  lt.push_back(p1);
  lt.push_back(p1);
  lt.push_back(p1);
  lt.push_back(Pos(2, 2));//用匿名对象来push_back，省下自己初始化创建一个对象了。
  lt.push_back(Pos(3, 3));
  // int* p  -> *p
  // pos* p  -> p->
  // 解引用的三种方式：1.数组的[] 2.普通指针的解引用 3.结构体指针的成员选择，分为.和->两种成员选择的方式
  //
  list<Pos>::iterator it = lt.begin();
  while (it != lt.end())
  {
    //cout << *it << endl;
    //cout << (&(*it))->_row << ':' << (&(*(&(*it))))->_col << endl;//堪称迂腐。
    cout << it->_row << ":" << it->_col << endl;//这里编译器省略了一个箭头，对于老手很喜欢
    //编译器会把上面这行代码转换成下面这行代码
    //cout << it.operator->()->_row << ":" << it.operator->()->_col << endl;//也还可以，比较照顾新手。
    //':'":"一个是字符串，一个是字符，打印出来的结果看起来一样是因为\0是标识字符不显示。
    //operator->()返回Pos对象的地址，因为_data是push_back到list的对象。
    //  应该再加一层->才能正常得到结构体Pos里面的成员变量的值。
    //  所以本来的面貌是cout << it->->_row << it->->_col << endl;
    //编译器为了可读性，做了特殊处理，省略了一个->
    //但使用时不可以多加一个->，因为这会干扰编译器的识别。
    //*it拿到的是Pos对象，因为我们push_back的是一个类实例化的对象，而不再是某一个内置类型的变量
    //Pos这个类并没有支持流插入运算符重载，所以无法直接打印出Pos的对象的值。
    //1.我们可以重载Pos的流插入运算符2.或者直接访问*it所属类的成员变量
    //C++搞流插入运算符重载，是为了支持自定义类型更好的输出。这就是和printf的区别
    it++;
  }
  //map<string, string>dict;
  //这个数据结构的迭代器很常用->，我们上面的list迭代器一般还是*解引用用的比较多。
  cout << endl;
  print_list(lt);
}

template<class T,class Ref,class Ptr>
struct __list_iterator//将迭代器进行了封装，以便于解引用，++，--等运算符依旧对迭代器适用
{
  //迭代器的封装完美体现了面向对象封装的思想，以及类和对象强大的力量。一个成员变量仅仅是结构体指针的迭代器对象
  //可以通过运算符重载和类封装的思想，将迭代器的功能实现的滴水不漏，隐藏底层实现的机制。
  typedef list_node<T> node;
  typedef __list_iterator<T, Ref, Ptr> Self;//Self代表整个类模板实例化的类型，这就是typedef的价值。
  node* _pnode;
  __list_iterator(node*p)
    :_pnode(p)
  {}
  Ptr operator->()//当迭代器指向内容是结构体时，我们倾向于这样的访问方式。
  {
    return &_pnode->_data;//返回迭代器所指向的结构体的地址。
  }
}
template<class T>
  class list
  {
    typedef list_node<T> node;
  public:
    typedef __list_iterator<T,T&,T*> iterator;//iterator是类模板的typedef，模板也是类型，只不过还没有实例化
    //typedef __list_const_iterator<T> const_iterator;
    typedef __list_iterator<T,const T&,const T*> const_iterator;
    ………………省略
  }