嵌入式C++（十一）

forward_list 始于c++11，是一个single linked list管理元素
头文件 #include <forward_list>
namespace std{
  template<typename T,typename Allocator = allocator>
     class forward_list;
};
元素类型：可以为任意类型的T，默认的内存类型是allocator

forward_list是一个行为受限制的list,不能走回头路，凡是list没有的功能，forward_list都不提供
优点：内存用量少，行动略迅速
设计目标：和自己写的c-style linked list比较，没有任何空间和时间上的额外开销
      如果任何方法和这两个要求相违背，就应该放弃该方法（API）

1.只提供前向迭代器，而不是双向迭代器，不支持反向迭代器
2.不提供成员函数size()--->不允许空间时间的浪费
  因为size()被调用，要么直接计算其大小，要么需要提供一个额外的数据栏记录其大小
  只要某个有能力改变其大小的函数被调用，这个数据栏都要去更新检查
  -->解决方案：1.自行追踪 2.使用list
3.forward_list没有指向最末元素的anchor(锚点)，所以不提供给处理最末元素的成员函数
    比如：push_back(),pop_back()都不提供
    -->解决方案：1.提供特殊版本（xx_after）,(before_xx)

1.forward_list不支持随机访问，如果想要访问第n个元素，必须遵循link所形成的串链“航行”前n个元素，因此速度相当满。
2.在任意位置安插和移除，因为没有任何元素需要搬移，只有若干个pointer需要被涂改
3.在这个里面提供特殊成员函数，是一般算法的快速版本。

#include <iostream>
#include <forward_list>
#include <string>
using namespace std;
int main(void)
{
  forward_list<int> f1 = { 1,2,3,4,5,6 };
  f1.emplace_front(7);
  f1.emplace_after(f1.before_begin(), 88);  //第一个参数传入要插入的前一个位置，支持插入一个元素
  for (auto &l : f1)
  {
  cout << l << " ";
  }
  cout << endl;
  /*for (auto it = f1.begin(); it != f1.end(); it++)
  {
  cout << *it << " ";
  }
  cout << endl;*/
  f1.insert_after(f1.before_begin(), {11,22,33});  //允许插入一个区间，一个元素，或者n个相同的元素
  for (auto &l : f1)
  {
  cout << l << " ";
  }
  cout << endl;
  //f1.insert_after(f1.end(), { 44,55,66 });  //如果想要在最后一个位置插入，必须要传入最后一个元素的位置
  forward_list<int> l1 = { 1,2,3,4,5 };
  forward_list<int> l2 = { 97,98,99 };
//接合函数
  //l2.splice_after()
  //void splice_after(const_iterator pos, forward_list& other,const_iterator it);
//将l1内部第一个数值为3的元素搬移到l2内第一个数值为99元素的前方：
  auto pos1 = l1.cbefore_begin();
  for (auto t1 = l1.begin(); t1 != l1.end(); ++t1,++pos1)
  {
  if (*t1 == 3)
  {
    break;  
  }
  }
  //在l2中找99
  auto pos2 = l2.cbefore_begin();
  for (auto t2 = l2.begin(); t2 != l2.end(); ++t2, ++pos2)
  {
  if (*t2 == 99)
  {
    break;
  }
  }
  l2.splice_after(pos2,l1,pos1);
  for (auto &l : l2)
  {
  cout << l << " ";
  }
  cout << endl;
  for (auto &l : l1)
  {
  cout << l << " ";
  }
  cout << endl;
  return 0;
}

//创建两个forward_list list1 list2
forward_list<int> list1 = {1,2,3,4};
forward_list<int> list2 = {77,88,99};
//在list2开始的位置插入6个新元素
//1.在77的前面插入99这个元素
//2.使用头插法插入元素10
//3.在第一个元素的前面插入一个区间【10，11，12，13】
//在list1的开头插入list2中所有的元素
//删除list2中第二个元素和99后面的所有元素（提示：使用find查找算法，可以找到99元素的位置）
                                              //find(beign,end,val);
//给list1排序，并且将其赋值给list2，并且移除所有相邻重复的元素
//合并list1和list2到list1中
//上述所有结果封装成函数进行遍历

#include <iostream>
#include <forward_list>
#include <string>
#include <algorithm>
#include <iterator>
using namespace std;
void printList(const string &s, const forward_list<int> &l1, const forward_list<int> &l2)
{
  cout << s << endl;
  cout << "list1：" << endl;
  copy(l1.begin(),l1.end(), ostream_iterator<int>(cout, " "));  //关联cout,设置分隔符（输出迭代器）
                  //元素拷贝到ostream_iterator所指向的对象cout
  cout << endl;
  cout << "list2：" << endl;
  copy(l2.begin(), l2.end(), ostream_iterator<int>(cout, " "));  //关联cout,设置分隔符（输出迭代器）
                  //元素拷贝到ostream_iterator所指向的对象cout
  cout << endl;
}
int main(void)
{
  //创建两个forward_list list1 list2
  forward_list<int> list1 = { 1,2,3,4 };
  forward_list<int> list2 = { 77,88,99 };
  printList("init list1 list2:",list1,list2);
  //在list2开始的位置插入6个新元素
  //1.在77的前面插入99这个元素
  list2.emplace_after(list2.cbefore_begin(), 99);
  //2.使用头插法插入元素10
  list2.emplace_front(10);
  //3.在第一个元素的前面插入一个区间【10，11，12，13】
  list2.insert_after(list2.before_begin(), {10,11,12,13});
  printList("插入六个元素：", list1, list2);
  //在list1的开头插入list2中所有的元素
  list1.insert_after(list1.before_begin(),list2.begin(),list2.end());
  printList("在list1的开头插入list2中所有的元素：", list1, list2);
  //删除list2中第二个元素和99后面的所有元素（提示：使用find查找算法，可以找到99元素的位置）
              //find(beign,end,val);
  list2.erase_after(list2.begin());
  list2.erase_after(find(list2.begin(), list2.end(), 99), list2.end());
  printList("删除list2中第二个元素和99后面的所有元素：", list1, list2);
  //给list1排序，并且将其赋值给list2，并且移除所有相邻重复的元素
  list1.sort();
  list2 = list1;
  printList("给list1排序,并且将其赋值给list2：", list1, list2);
  list1.unique();
  printList("移除所有相邻重复的元素：", list1, list2);  
  //合并list1和list2到list1中
  list1.merge(list2);
  printList("合并list1和list2到list1中：", list1, list2);
  //上述所有结果封装成函数进行遍历
  return 0;
}

#include <iostream>
#include <forward_list>
#include <string>
#include <algorithm>
#include <iterator>
#include <vector>
using namespace std;
template <typename T1,typename T2>
class MyPair
{
public:
  T1 first;
  T2 second;
};
int main(void)
{
  pair<int, string> p1;
  p1.first = 1;
  p1.second = "hello world";
  MyPair<int, string> p2;
  p2.first = 2;
  p2.second = "nihao nanjing";
  pair<int, string> p3(1,"hello");
  pair<int, string> p4 = make_pair(1, "hello world"); //c++11
  cout << p4.first << endl;
  cout << p4.second << endl;
//编写程序，将每个string和int存入一个pair中，pair保存在一个vector中，遍历输出每个string和int
  string s[10];
  int v[10];
  for (int i = 0; i < 10; i++)
  {
  s[i] = "hello";
  v[i] = i + 1;
  }
  vector<pair<string, int>> data;
  for (int i = 0; i < 10; i++)
  {
  //data.emplace_back(pair<string, int>(s[i], v[i]));
  //data.emplace_back(make_pair(s[i], v[i]));
  data.push_back({s[i],v[i]});
  }
  for (auto &d : data)
  {
  cout << d.first << " " << d.second << endl;
  }
  return 0;
}

tuple<int, string, int> t1(1,"zhangsan",12);
  cout << std::tuple_size<decltype(t1)>::value << endl;
  cout << t1 << endl;
  cout << "id = " << std::get<0>(t1) << endl;
  cout << "name = " << std::get<1>(t1) << endl;
  cout << "age = " << std::get<2>(t1) << endl;
  //tie解包
  int id;
  string name;
  int age;
  std::tie(id, name, age) = t1;
  cout << "id = " << id << endl;
  cout << "name = " << name << endl;
  cout << "age = " << age << endl;

#include <iostream>
#include <forward_list>
#include <string>
#include <algorithm>
#include <set>
using namespace std;
class Student
{
  friend ostream& operator<<(ostream &out, const Student &t);
public:
  Student(int i,string n)
  {
  cout << "student" << endl;
  id = i;
  name = n;
  }
  ~Student()
  {
  cout << "~student" << endl;
  }
  bool operator<(const Student &s) const
  {
  return this->id < s.id;
  }
  bool operator>(const Student &s) const
  {
  return this->id > s.id;
  }
private:
  int id;
  string name;
};
ostream& operator<<(ostream &out, const Student &t)
{
  out << "id = " << t.id << " name = " << t.name << endl;
  return out;
}
template <typename T,typename U = std::less<T>>
void printSet(const set<T,U> &s)
{
  for (auto &s1 : s)
  {
  cout << s1 << " ";
  }
  cout << endl;
}
int main(void)
{
  Student s1(3, "aa");
  Student s2(4, "bb");
  Student s3(8, "cc");
  Student s4(9, "dd");
  Student s5(1, "ee");
  Student s6(6, "ff");
  Student s7(7, "gg");
  //set<Student> s;
  set<Student, greater<Student>> s;
  s.insert(s1);
  s.insert(s2);
  s.insert(s3);
  s.insert(s4);
  s.insert(s5);
  s.insert(s6);
  s.emplace(s7);
  s.emplace(10, "hh");
  s.emplace(Student(11,"oo"));
  printSet<Student>(s);
  cout << "集合大小：" << s.size() << endl;
  s.erase(s.begin());
  printSet(s);
  cout << "set区间删除" << endl;
  s.erase(--s.end(), s.end());
  printSet(s);
  cout << "删除具体的元素" << endl;
  s.erase(s1); //按照id查找并删除
  printSet(s);
  cout << "set的查找" << endl;
  auto it = s.find(s2);
  if (it == s.end())
  {
  cout << "对象不存在" << endl;
  }
  else
  {
  cout << *it << endl;
  }
  cout << "set的统计" << endl;
  cout << s.count(s6) << endl;
  Student ss(0, "bb");
//如果lower_bound和upper_bound返回的是相等的迭代器，说明元素不存在
  cout << "lower_bound" << endl;
  it = s.lower_bound(ss);  //返回元素ss的第一个可安插的位置，也就是元素值>=ss的第一个元素的位置
  if (it == s.end())
  {
  cout << "不存在" << endl;
  }
  else
  {
  cout << *it << endl;
  }
  cout << "upper_bound" << endl;
  it = s.upper_bound(ss);  //返回元素ss的最后一个可安插的位置，也就是元素值>=ss的第一个元素的位置
  if (it == s.end())
  {
  cout << "不存在" << endl;
  }
  else
  {
  cout << *it << endl;
  }
  /************************************************************************/
  /* equal_range:接受一个关键词，返回一个pair对组
  若关键词存在，第一个迭代器指向第一个与关键词匹配的元素，第二个指向最后一个匹配元素之后的位置
  若未找到匹配，则两个迭代器相等，都指向关键词可插入的位置。
  */
  /************************************************************************/
  cout << "equal_range" << endl;
  pair<set<Student>::iterator, set<Student>::iterator> p;
  p = s.equal_range(ss);
  /*cout << *p.first << endl;
  cout << *p.second << endl;*/
  return 0;
}

#include <iostream>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
template<typename T1,typename T2>
void printMap(const map<T1, T2> &m)
{
  for (auto &m1 : m)
    {
      cout << "key: " << m1.first << " value: " << m1.second << endl;
    }
}
int main(void)
{
    map<int, string> m; //key是int型，value是string类型
    m.insert(pair<int,string>(3,"aa"));
    m.insert(pair<int, string>(4, "bb"));
    m.insert(make_pair(5,"cc"));
    m.insert(make_pair(6, "dd")); //make_pair组合一组数据插入
    m.insert(map<int, string>::value_type(7,"ee"));
    m.insert(map<int, string>::value_type(8, "ff")); //通过map内部的静态成员函数插
    入
    m[9] = "ww"; //map重载了【】运算符
    m[10] = "qq";
    m.emplace(11,"tt");
    m.emplace_hint(m.begin(), 19, "aa");
    printMap(m);
    pair<map<int,string>::iterator,bool> p = m.insert(make_pair(5, "ll")); //返回一个pair
    if (p.second == false)
    {
        cout << "插入失败" << endl;
        cout << "key: " <<p.first->first<< " value: " << p.first->second <<
        endl;
    }
    else
    {
     cout << "插入成功" << endl;
    }
    m[3] = "ww";
    printMap(m);
    //map删除指定位置
    //map删除具体元素（根据KEY值删除）
    cout << "map删除具体元素（根据KEY值删除）" << endl;
    m.erase(4);
    printMap(m);
    return 0;
}