C++学习笔记day4

红黑树的特性(了解):
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）如果一个节点是红色的，则它的子节点必须是黑色的。
（4）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。[这里指到叶子节点的路径]

红黑树的优势：平衡查找二叉树
1.失掉了一部分平衡（保证在二倍以内即可）
2.比普通平衡查找二叉树，插入结点时，尽量在3次旋转内，插入到正确的位置，效率高，速度快
插入和删除的时间复杂度：logn

容器类自动申请和释放内存，无需new和delete *** 作。
map 通过关联容器保存数据，以键值对key-value形式存放数据  红黑树

map是存放pair的容器，根据pair中的first进行红黑树的排序。
first在map中又叫key，second又叫value。

Map是键-值对的集合，map中的所有元素都是pair，可以使用键作为下标来获取一个值。
Map中所有元素都会根据元素的键 （key）自动被排序，同时拥有实值value和键值key，
pair的第一元素被视为键值，第二元素被视为实值，同时map不允许两个元素有相同的键值。

声明及其初始化：pair  pair也是一种模板类型。键(key)值(value)对它的数据成员是公有的，分别命名为first和second。

map m;//创建一个名为m的空map对象，其键和值的类型分别为key和value。 
map m(m2);//创建m2的副本m，m与m2必须有相同的键类型和值类型。

**********************************示例1：pair关联容器******************************
#include 
#include 
#include 

************************************示例代码：************************************
#include 
#include 

1.底层原理：红黑树
2.map如何保存元素的？  键值对的方式存储
3.一个键值对是什么？  pair关联容器
4.如何获取 键值对中的值？ key -->p.first  value  --> p.second
5.map容器和pair（键值对）关系？ map中可以存储 很多的键值对
6.关联容器特点：自动排序（默认升序）

7.map容器的特点：
1.键值对方式存储数据，并且按照key自动升序
2.插入的元素，key不可以重复
3.通过key  去查找 value cout<
using namespace std;
#include 

迭代器：一种检查容器内元素并遍历元素的数据类型。C++更趋向于使用迭代器而不是下标 *** 作，因为标准库为每一种标准容器（如vector）定义了一种迭代器类型，而只用少数容器（如vector）支持下标 *** 作访问容器元素。C++中的迭代器是对指针的封装，迭代器提供特定的函数让调用者对指针进行特定的安全的 *** 作

定义和初始化：每种容器都定义了自己的迭代器类型，如vector:
vector::iterator    iter;    //定义一个名为iter的变量

每种容器都定义了一对名为begin和end的函数，用于返回迭代器。
迭代器初始化 *** 作：
vector    ivec;      //将迭代器iter1初始化为指向ivec容器的第一个元素
vector::iterator iter1=ivec.begin();  

vector::iterator   iter2=ivec.end();//初始化指向ivec容器的最后一个元素的下一个位置   

注意：end并不指向容器的任何元素，而是指向容器的最后元素的下一位置，称为超出末端迭代器。
如果vector为空，则begin返回的迭代器和end返回的迭代器相同。
一旦向上面这样定义和初始化，就相当于把该迭代器和容器进行了某种关联，就像把一个指针初始化为指向某一空间地址一样。

示例：使用迭代器输出容器中的元素
 vector::iterator iter;
   //for(int i = 0;  i< 10; i++)
   //begin是容器的头元素 ，end并不是尾元素，而是无效的元素表示容器结束
   for(iter = v.begin(); iter != v.end(); iter++)
   {
       cout<<*iter<<" ";
   }
   cout<

常用 *** 作：
*iter       //对iter进行解引用，返回迭代器iter指向的元素的引用
iter->men //对iter进行解引用，获取指定元素中名为men的成员。等效于(*iter).men
++iter     //给iter加1，使其指向容器的下一个元素
iter++
--iter     //给iter减1，使其指向容器的前一个元素
iter--
iter1==iter2  //比较两个迭代器是否相等，当它们指向同一个容器的同一个元素或者都指向同一个容器	的超出末端的下一个位置时，它们相等 
iter1!=iter2    

#include 
#include //向量容器的头文件
using namespace std;
//参数：容器类型
vector&  fun(vector& v1)//拷贝  同一个
{
    //将容器第一个元素值改成 100
    v1[0] = 100;
    return v1;
}
//迭代器iterator(工具)遍历：对指针的封装
int main ()
{
    vector v;
    for(int i=0;i<10;i++)
    {
        v.push_back(i);//0~9
    }
    fun(v);
    //v容器的迭代器
    //类型                变量名
  //  vector::iterator  iter;
    //遍历  头             不到尾i<10      偏移
    for(vector::iterator  iter=v.begin(); iter != v.end();iter++)
    {
//        if(*iter %2 == 0)
//        {
//            *iter = 0;
//        }
        cout<<*iter< v1;
   for(int i=0;i<10;i++)
        v1.push_back(i);

   vector::iterator iter = v1.begin()+1;
   //v1.erase(iter);
   v1.erase(v1.begin()+1,v1.end()); //移除[begin, end)区间的数据

  for(int i=0;i::iterator iter = find(v.begin(), v.end(), 3);
3）注意：find方法只能删除找到的第一个元素

#include 
#include 
#include 
using namespace std;

int main()
{
    vector v;
    for(int i = 0;i < 10;i++)
    {
        v.push_back(i);
    }
    vector::iterator iter = find(v.begin(), v.end(), 3);
    v.erase(iter);
    
    for(vector::iterator iter = v.begin();iter != v.end();iter++)
    {
        cout<<*iter<
#include 
#include //算法头文件
using namespace std;
class Person
{
    int age;
public:
    Person(int age):age(age){}
    void show(){cout< v;
    //添加元素:3种方式
    Person p(1);
    //1.将对象装进容器
    v.push_back(p);

    Person p1(2);
    v.push_back(p1);

    //2.将匿名对象装进容器
    v.push_back(Person(3));
    //3.利用隐士转换方式 将对象装进容器
    v.push_back(4);
	
    for(int i=0 ; i< v.size(); i++)
        v[i].show();//v[i]-->pesron对象

    //迭代器遍历 调用show方法
    vector::iterator iter;
    for(iter=v.begin(); iter!=v.end(); iter++)
    {
        iter->show();//(*iter).show();
    }
    return 0;
}
*****************************示例：查找迭代器删除自定义类型***************************
#include 
#include 
#include 
using namespace std;

class Person
{
    int age;
public:
    Person(int a):age(a){}
    void show(){cout v;
    Person p(10);
    v.push_back(p);//Person(10)
    v.push_back(Person(20));
    v.push_back(Person(30));
   vector::iterator it = find(v.begin(),v.end(),Person(20));
    if(it != v.end())
    {
        it->show();
    }else
        cout<<"not"<::iterator iter = v.begin();iter != v.end(); iter++)
    {
        (*iter).show();//iter->show();
    }
}