void test_list1()
{
  list<int> lt;
  lt.push_back(1);
  lt.push_back(2);
  lt.push_back(3);
  lt.push_back(4);
  list<int>::iterator it = lt.begin();//迭代器属于类的内嵌类型
  while (it != lt.end())
  {
    cout << *it << " ";
    ++it;
  }
  cout << endl;
  lt.push_front(10);
  lt.push_front(20); 
  lt.push_front(30);
  lt.push_front(40);
  for (int e : lt)
  {
    cout << e << " ";
  }
  cout << endl;
  lt.pop_back();
  lt.pop_back();
  lt.pop_front();
  lt.pop_front();
  for (int e : lt)
  {
    cout << e << " ";
  }
  cout << endl;
}

void test_list2()
{
  list<int> lt;
  lt.push_back(1);
  lt.push_back(2);
  lt.push_back(3);
  lt.push_back(4);
  list<int>::iterator pos = find(lt.begin(), lt.end(), 3);
  if (pos != lt.end())
  {
    lt.insert(pos, 30);//insert之后，pos迭代器肯定不会失效。
  }
  cout << *pos << endl;
  (*pos)++;
  for (int e : lt)
  {
    cout << e << " ";
  }
  cout << endl;
  lt.erase(pos);//erase之后，迭代器会失效，因为节点空间被释放了
  cout << *pos << endl;
  for (int e : lt)
  {
    cout << e << " ";
  }
  cout << endl;
}

//operations操作接口：有用，但用处不大，和我们做的时间规划表一样，想的挺好，但在实际用的时候，并没有那么常用。
void test_list3()
{
  list<int> lt;
  lt.push_back(1);
  lt.push_back(9);
  lt.push_back(5);
  lt.push_back(2);
  lt.push_back(5);
  lt.push_back(2);
  for (int e : lt)
  {
    cout << e << " ";
  }
  cout << endl;
  lt.remove(3);//remove=find+erase
  lt.remove(30);//如果删除的元素不存在，则什么也不会发生
  for (int e : lt)
  {
    cout << e << " ";
  }
  cout << endl;
  lt.sort();//链表单独提供一个排序，没有用算法库里面的
  //sort(lt.begin(), lt.end());//这样进行链表排序是不行的
  //迭代器功能分类：
  //1.单向迭代器 ++ 单链表
  //2.双向迭代器 ++ -- list
  //3.随机迭代器 ++ -- + - vector&&string
  for (int e : lt)
  {
    cout << e << " ";
  }
  cout << endl;
  //必须先排序，再去重
  lt.unique();//去重算法是建立在有序的基础上。去重有点像快慢指针删除数组重复元素，所以如果重复数字不挨着，unique就会出现错误。
  for (int e : lt)
  {
    cout << e << " ";
  }
  cout << endl;
  lt.reverse();逆置
  lt.merge();归并
  lt.splice();拼接转移
}

//1.vector排序和链表排序的性能对比，所以如果你要排序，就不要将数据放到链表里面去，这也正是链表的sort接口不常用的原因。
//2.N个数据需要排序，vector+ 算法sort  list+ sort
void test_op()//优化这部分直接看release版本即可，debug版本对于不同的结构在底层优化达到的效果都不太一样。主要看release即可。
{
  srand(time(NULL));
  const int N = 100000;
  vector<int> v;
  v.reserve(N);
  list<int> lt1;
  list<int> lt2;
  for (int i = 0; i < N; ++i)
  {
    auto e = rand();
    v.push_back(e);
    lt1.push_back(e);
    //lt2.push_back(e);
  }
  // 拷贝到vector排序，排完以后再拷贝回来
  int begin1 = clock();
  //for (auto e : lt1)
  //{
  //  v.push_back(e);
  //}
  sort(v.begin(), v.end());//调用算法库的sort对vector进行排序
  //size_t i = 0;
  //for (auto& e : lt1)
  //{
  //  e = v[i++];
  //}
  int end1 = clock();
  int begin2 = clock();
  lt1.sort();
  int end2 = clock();
  printf("vector sort:%d\n", end1 - begin1);
  printf("list sort:%d\n", end2 - begin2);
}

namespace wyn
{
  template<class T>
  struct list_node
  {
    list_node* _next;//指向下一个结点的结构体指针
    list_node* _prev;//指向前一个结点的结构体指针
    T _data;//数据类型是泛型，可能是内置类型，也有可能是自定义类型
    list_node(const T& x)
    //new结点的时候会调用构造函数，但编译器默认生成的无参构造函数无法满足我们的要求
    //所以我们需要自己写一个带参数的构造函数，因为new结点时需要将数据作为参数传递，无参不符合要求。
      :_next(nullptr)
      ,_prev(nullptr)
      ,_data(x)
    {}
  };
  template<class T>
  struct __list_iterator
  {
    typedef list_node<T> node;
    node* _pnode;//迭代器类的成员就是一个结构体指针_pnode
    __list_iterator(node* p)
      :_pnode(p)
    {}
    T& operator*()//返回_data的引用，则解引用迭代器可以修改结点对应的数据
    {
      return _pnode->_data;
    }
    __list_iterator<T>& operator++()
    {
      _pnode = _pnode->_next;
      return *this;
    }
    bool operator!=(const __list_iterator<T>& it)
    //比较两个迭代器是否相等，就是比较结点指针相不相等
    {
      return _pnode != it._pnode;
    }
  };
  template<class T>
  class list
  {
    typedef list_node<T> node;//将实例化后的类模板list_node<T>类型重定义为node
  public:
    typedef __list_iterator<T> iterator;
    //将实例化后的类模板__list_iterator<T>类型重定义为iterator
    iterator begin()
    {
      //iterator it(_head->_next);
      //return it;
      //上下这两种写法是等价的。
      return iterator(_head->_next);
      //返回迭代器类的匿名对象，参数传结构体指针，迭代器类的成员变量只有一个结构体指针。
      //匿名对象可以省下我们自己定义出对象然后再返回，这样比较麻烦。
    }
    iterator end()//迭代器对象出了作用域被析构掉，所以用传值返回，不能用传引用返回
    {
      return iterator(_head);
      //end()返回的是最后一个元素的下一个位置的迭代器，所以我们返回的是哨兵卫结点的迭代器对象。
    }
    void empty_initialize() 
    {
      _head = new node(T());//node实现的构造函数是带参数的，调用T类型的默认构造初始化
      //new一个结点，new会自动调用node类的带参构造函数，我们给构造函数传一个泛型的匿名对象，
      //保证结点存储的数据类型是泛型，既有可能是内置类型也有可能是自定义类型，所以传匿名对象。
      //如果是自定义类型，会调用其类的无参构造函数，如果是内置类型，基本是0或NULL等初始值，
      //我们可以认为内置类型也有构造函数，这样的写法实际是为了支持C++的泛型编程所搞出来的，
      //如果是内置类型，编译器会做特殊处理。
      _head->_next = _head;
      _head->_prev = _head;
    }
    list()
    {
      empty_initialize();
    }
    void push_back(const T& x)
    {
      node* newnode = new node(x);
      //这里所传x的类型是不确定的，他的类型取决于调用方给模板参数所传的值。
      //如果T是自定义类型，那x就是对象，如果T是内置类型，x就是变量。
      node* tail = _head->_prev;
      tail->_next = newnode;
      newnode->_prev = tail;
      newnode->_next = _head;
      _head->_prev = newnode;
      //insert(end(), x);
    }
  private:
    node* _head;
  };
}
  void test_list1()
  {
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    //内嵌类型 -- 迭代器需要能够1.解引用能够取到结点的数据 2.并且可以++或--进行移动
    //string和vector的iterator原生指针能够使用，是因为数组结构正好支持迭代器行为。
    //list如果用原生指针，它的数组结构无法支持迭代器行为，因为list的空间是不连续的。
    //为了支持list的迭代器，我们用类的封装和运算符重载进行支持。
    list<int>::iterator it = lt.begin();
    //由于迭代器对象的拷贝构造没有实现，所以用编译器默认生成的浅拷贝。
    while (it != lt.end())//vector和string可以用<来进行判断，但list这里只能用!=，这里会调用it对应类的运算符重载
    {
      //it.operator*(){} --- 转换为调用自定义类型对应类内的运算符重载函数
      //it.operator++(){}
      cout << *it << " ";//*it是自定义类型iterator的运算符重载，iterator是进行封装的类型
      ++it;//++it也是自定义类型iterator的运算符重载。
      //(*it)++; --- it.operator*()函数的引用返回值进行自增，返回值可能是自定义类型或内置类型。
    }
    cout << endl;
    for (auto e : lt)//范围for就是傻瓜式的替换迭代器的代码，begin()end()，迭代器支持解引用++--等操作，范围for就能用
    {
      cout << e << " ";
    }
    cout << endl;
  }