容器

容器仆嗦，就是用來存放東西的盒子。

常用的數(shù)據(jù)結(jié)構(gòu)包括：數(shù)組array, 鏈表list先壕， 樹tree瘩扼， 棧stack， 隊列queue启上， 散列表hash table, 集合set邢隧、映射表map 等等。容器便是容納這些數(shù)據(jù)結(jié)構(gòu)的冈在。這些數(shù)據(jù)結(jié)構(gòu)分為序列式與關(guān)聯(lián)式兩種倒慧，容器也分為序列式容器和關(guān)聯(lián)式容器。

STL 標(biāo)準(zhǔn)模板庫包券，核心包括容器纫谅、算法、迭代器溅固。

序列式容器/順序容器

元素排列次序與元素?zé)o關(guān)付秕，由元素添加到容器的順序決定

向量(vector)

連續(xù)存儲的元素

列表 (list)

由節(jié)點組成的雙向鏈表侍郭，每個結(jié)點包含著一個元素

雙端隊列(deque)

連續(xù)存儲的指向不同元素的指針?biāo)M成的數(shù)組

以上三種容器操作基本一樣

基本操作:

#include <vector>
using namespace std;

vector<int> vec_1;
//1個元素
vector<int> vec_2(1);
//6個值為 1 的元素
vector<int> vec_3(6,1);
//使用容器初始化
vector<int> vec_4(vec_3);

//通過下標(biāo)操作元素
int i = vec_3[1];
int j = vec_3.at(1);
//首尾元素
vec_3.front()
vec_3.back()

//插入元素 
//vector不支持 push_front list,deque可以
vec_1.push_back(1);
//刪除元素 vector不支持 pop_front
vec_1.pop_back();

//釋放
//可以單個清除询吴，也可以清除一段區(qū)間里的元素
vec_3.erase(vec_3.begin(),vec_3.end())
//清理容器 即erase所有
vec_3.clear(); 

//容量大小
vec_3.capacity();
//在容器中掠河，其內(nèi)存占用的空間是只增不減的，
//clear釋放元素猛计，卻不能減小vector占用的內(nèi)存
//所以可以對vector 收縮到合適的大小 
vector< int >().swap(vec_3);  

//在vec是全局變量時候
//建立臨時vector temp對象唠摹，swap調(diào)用之后對象vec占用的空間就等于默認(rèn)構(gòu)造的對象的大小
//temp就具有vec的大小，而temp隨即就會被析構(gòu)奉瘤，從而其占用的空間也被釋放勾拉。

迭代器

//獲得指向首元素的迭代器  模板類，不是指針盗温，當(dāng)做指針來使用
vector<int>::iterator it = vec.begin();
//遍歷元素
for (; it < vec.end(); it++)
{
    cout << *it << endl;
}
//begin和end   分別獲得 指向容器第一個元素和最后一個元素下一個位置的迭代器
//rbegin和rend 分別獲得 指向容器最后一個元素和第一個元素前一個位置的迭代器

//注意循環(huán)中操作元素對迭代器的影響
vector<int>::iterator it = vec.begin();
for (; it < vec.end(); )
{
    //刪除值為2的元素 
    if (*it == 2) {
        vec.erase(it);
    }
    else {
        it++;
    }
}

棧(stack)

后進先出的值的排列

stack<int> s;
//入棧
s.push(1);
s.push(2);
//彈棧
s.pop();
//棧頂
cout << s.top() << endl;

隊列(queue)

先進先出的值的排列

queue<int> q;
q.push(1);
q.push(2);
//移除最后一個
q.pop();
//獲得第一個
q.front();
//最后一個元素
cout << q.back() << endl;

優(yōu)先隊列(priority_queue )

元素的次序是由所存儲的數(shù)據(jù)的某個值排列的一種隊列

//最大的在隊首
priority_queue<int>;
//在vector之上實現(xiàn)的
priority_queue<int, vector<int>, less<int> >; 
//vector 承載底層數(shù)據(jù)結(jié)構(gòu)堆的容器
//less 表示數(shù)字大的優(yōu)先級高藕赞，而 greater 表示數(shù)字小的優(yōu)先級高
//less       讓優(yōu)先隊列總是把最大的元素放在隊首
//greater    讓優(yōu)先隊列總是把最小的元素放在隊首

//less和greater都是一個模板結(jié)構(gòu)體 也可以自定義

class Student {
public:
    int grade;
    Student(int grade):grade(grade) {
    }
};
struct cmp {
    bool operator ()(Student* s1, Student* s2) {
        // > 從小到大
        // < 從大到小 
        return s1->grade > s2->grade;
    }
    bool operator ()(Student s1, Student s2) {
        return s1.grade > s2.grade;
    }
};
priority_queue<Student*, vector<Student*>, cmp > q1;
q1.push(new Student(2));
q1.push(new Student(1));
q1.push(new Student(3));
cout << q1.top()->grade << endl;

關(guān)聯(lián)式容器

關(guān)聯(lián)容器和大部分順序容器操作一致

關(guān)聯(lián)容器中的元素是按關(guān)鍵字來保存和訪問的 支持高效的關(guān)鍵字查找與訪問

集合(set)

由節(jié)點組成的紅黑樹，每個節(jié)點都包含著一個元素,元素不可重復(fù)

set<string> a;  
set<string> a1={"fengxin","666"};
a.insert("fengxin");  // 插入一個元素
a.erase("123"); //刪除

鍵值對(map)

由{鍵卖局，值}對組成的集合

map<int, string> m;
map<int, string> m1 = { { 1,"Lance" },{ 2,"David" } };
//插入元素
m1.insert({ 3,"Jett" });
//pair=鍵值對
pair<int, string> p(4, "dongnao");
m1.insert(p);
//insetrt 返回 map<int, string>::iterator : bool 鍵值對
//如果 插入已經(jīng)存在的 key斧蜕，則會插入失敗   
//multimap：允許重復(fù)key
//使用m1[3] = "xx" 能夠覆蓋


//通過【key】操作元素
m1[5] = "yihan";
cout << m1[5].c_str() << endl; 
//通過key查找元素
map<int, string>::iterator it = m1.find(3);
cout << (*it).second.c_str()<< endl;
// 刪除 
m1.erase(5);
//遍歷
for (it = m1.begin(); it != m1.end(); it++)
{
    pair<int, string> item = *it;
    cout << item.first << ":" << item.second.c_str() << endl;
}

//其他map================================

unordered_map c++11取代hash_map（哈希表實現(xiàn)，無序）

哈希表實現(xiàn)查找速度會比RB樹實現(xiàn)快,但rb整體更節(jié)省內(nèi)存

需要無序容器吼驶，高頻快速查找刪除惩激，數(shù)據(jù)量較大用unordered_map店煞；

需要有序容器蟹演，查找刪除頻率穩(wěn)定，在意內(nèi)存時用map顷蟀。

紅黑樹

二叉樹

二叉樹.png

二分查找：

查找 2 ：

1酒请、查看根節(jié)點為10

2、由于2小于10鸣个，因此查找左孩子羞反，節(jié)點為5

3、同時2小與5囤萤，繼續(xù)查看左邊昼窗，找到2節(jié)點

查找最大次數(shù)為樹的高度

如果有下面的二叉查找樹，插入7涛舍、6澄惊、5......

這樣幾乎成為線性，查找性能大幅下降

二叉樹插入

)

為了解決這種不平衡富雅，紅黑樹就誕生了掸驱。

https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91

紅黑樹(Red Black Tree)又稱為 RB樹,是一種相對平衡二叉樹 。

1.節(jié)點是紅色或黑色没佑。

2.根節(jié)點是黑色毕贼。

3.每個葉子節(jié)點(空節(jié)點)都是黑色的。

4 每個紅色節(jié)點的兩個子節(jié)點都是黑色蛤奢。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點)

5.從任一節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點鬼癣。

插入7.png

1. 插入新節(jié)點總是紅色節(jié)點
2. 如果插入節(jié)點的父節(jié)點是黑色, 能維持性質(zhì)
3. 如果插入節(jié)點的父節(jié)點是紅色, 破壞了性質(zhì)陶贼。插入算法就是通過重新著色或旋轉(zhuǎn), 來維持性質(zhì)

插入 7 后,破壞了規(guī)則，那么需要根據(jù)不同的狀況進行不同的策略使其平衡并符合規(guī)則待秃。

7的父節(jié)點8 與叔父節(jié)點 12 都是紅色骇窍，則我們可以將8、12兩個重繪為黑色并重繪祖父節(jié)點9為紅色锥余。

這里9是根節(jié)點腹纳，為了滿足規(guī)則1，又把它重繪為黑色 .

經(jīng)過調(diào)整：

插入7_over.png

現(xiàn)在滿足5個規(guī)則驱犹，因此7插入完成嘲恍。

接下來插入 6

插入6.png

現(xiàn)在新節(jié)點 6 是 父節(jié)點 7的左節(jié)點，而6的叔父節(jié)點 缺少雄驹，父節(jié)點 7 又是祖父節(jié)點8的左子節(jié)點 佃牛，

這種情形下，我們進行針對6節(jié)點的祖父節(jié)點8的一次右旋轉(zhuǎn)

右旋轉(zhuǎn)：

順時針旋轉(zhuǎn)紅黑樹的兩個節(jié)點医舆，使得父節(jié)點被自己的左孩子取代俘侠，而自己成為自己的右孩子。

左旋轉(zhuǎn)則倒過來

插入6右旋.png

再切換 7 和 8 的顏色

插入6旋轉(zhuǎn)切換顏色.png

再插入5蔬将，5和6都是紅色爷速，將 父節(jié)點 6 和叔父節(jié)點 8 繪為黑色，祖父7設(shè)為紅色霞怀，最終

最終插入5.png

類型轉(zhuǎn)換

除了能使用c語言的強制類型轉(zhuǎn)換外,還有：轉(zhuǎn)換操作符 （新式轉(zhuǎn)換）

const_cast

修改類型的const或volatile屬性

const char *a;
char *b = const_cast<char*>(a);
    
char *a;
const char *b = const_cast<const char*>(a);

static_cast

1. 基礎(chǔ)類型之間互轉(zhuǎn)惫东。如：float轉(zhuǎn)成int、int轉(zhuǎn)成unsigned int等
2. 指針與void之間互轉(zhuǎn)毙石。如：float*轉(zhuǎn)成void*廉沮、Bean*轉(zhuǎn)成void*、函數(shù)指針轉(zhuǎn)成void*等
3. 子類指針/引用與 父類指針/引用 轉(zhuǎn)換徐矩。

class Parent {
public:
    void test() {
        cout << "p" << endl;
    }
};
class Child :public Parent{
public:
     void test() {
        cout << "c" << endl;
    }
};
Parent  *p = new Parent;
Child  *c = static_cast<Child*>(p);
//輸出c
c->test();

//Parent test加上 virtual 輸出 p

dynamic_cast

主要 將基類指針滞时、引用 安全地轉(zhuǎn)為派生類.

在運行期對可疑的轉(zhuǎn)型操作進行安全檢查，僅對多態(tài)有效

//基類至少有一個虛函數(shù)
//對指針轉(zhuǎn)換失敗的得到NULL滤灯，對引用失敗  拋出bad_cast異常 
Parent  *p = new Parent;
Child  *c = dynamic_cast<Child*>(p);
if (!c) {
    cout << "轉(zhuǎn)換失敗" << endl;
}


Parent  *p = new Child;
Child  *c = dynamic_cast<Child*>(p);
if (c) {
    cout << "轉(zhuǎn)換成功" << endl;
}

reinterpret_cast

對指針坪稽、引用進行原始轉(zhuǎn)換

float i = 10;

//&i float指針，指向一個地址力喷，轉(zhuǎn)換為int類型刽漂，j就是這個地址
int j = reinterpret_cast<int>(&i);
cout  << hex << &i << endl;
cout  << hex  << j << endl;

cout<<hex<<i<<endl; //輸出十六進制數(shù)
cout<<oct<<i<<endl; //輸出八進制數(shù)
cout<<dec<<i<<endl; //輸出十進制數(shù)

char*與int轉(zhuǎn)換

//char* 轉(zhuǎn)int float
int i = atoi("1");
float f = atof("1.1f");
cout << i << endl;
cout << f << endl;
    
//int 轉(zhuǎn) char*
char c[10];
//10進制
itoa(100, c,10);
cout << c << endl;

//int 轉(zhuǎn) char*
char c1[10];
sprintf(c1, "%d", 100);
cout << c1 << endl;

異常

void test1()
{
    throw "測試!";
}

void test2()
{
    throw exception("測試");
}

try {
    test1();
}
catch (const char *m) {
    cout << m << endl;
}
try {
    test2();
}
catch (exception  &e) {
    cout << e.what() << endl;
}

//自定義
class MyException : public exception
{
public:
   virtual char const* what() const
    {
        return "myexception";
    }
};

//隨便拋出一個對象都可以

文件與流操作

C 語言的文件讀寫操作

頭文件:stdio.h

函數(shù)原型：FILE * fopen(const char * path, const char * mode);

path: 操作的文件路徑

mode:模式

//========================================================================
FILE *f = fopen("xxxx\\t.txt","w");
//寫入單個字符
fputc('a', f);
fclose(f);


FILE *f = fopen("xxxx\\t.txt","w");
char *txt = "123456";
//寫入以 null 結(jié)尾的字符數(shù)組
fputs(txt, f);
//格式化并輸出
fprintf(f,"%s",txt);
fclose(f);

//========================================================================
fgetc(f); //讀取一個字符

char buff[255];
FILE *f = fopen("xxxx\\t.txt", "r");
//讀取 遇到第一個空格字符停止
fscanf(f, "%s", buff);
printf("1: %s\n", buff);

//最大讀取 255-1 個字符
fgets(buff, 255, f);
printf("2: %s\n", buff);
fclose(f);

//二進制 I/O 函數(shù)
size_t fread(void *ptr, size_t size_of_elements, 
             size_t number_of_elements, FILE *a_file);       
size_t fwrite(const void *ptr, size_t size_of_elements, 
             size_t number_of_elements, FILE *a_file);
//1洼专、寫入/讀取數(shù)據(jù)緩存區(qū)
//2棒掠、每個數(shù)據(jù)項的大小
//3、多少個數(shù)據(jù)項
//4屁商、流
//如：圖片烟很、視頻等以二進制操作:
//寫入buffer 有 1024個字節(jié)
fwrite(buffer,1024,1,f);

C++ 文件讀寫操作

<iostream> 和 <fstream>

char data[100];
// 以寫模式打開文件
ofstream outfile;
outfile.open("XXX\\f.txt");
cout << "輸入你的名字: ";
//cin 接收終端的輸入
cin >> data;
// 向文件寫入用戶輸入的數(shù)據(jù)
outfile << data << endl;
// 關(guān)閉打開的文件
outfile.close();

// 以讀模式打開文件
ifstream infile;
infile.open("XXX\\f.txt");

cout << "讀取文件" << endl;
infile >> data;
cout << data << endl;

// 關(guān)閉
infile.close();