黑马程序员C++提高编程笔记

[toc]

1. STL

1.1 STL

• 标准模版库（Standard Templete Library）

1.2 STL基本概念：

• STL六大组件：

  • 容器：各种数据结构、如vector、list、map、set、deque
  • 算法：各种常见的算法、比如sort、find、copy、for_each
  • 迭代器：扮演了容器和算法之间的粘合剂
  • 仿函数：行为类似函数、可以作为 算法的某种策略
  • 适配器：一种用来修饰容器或者仿函数或迭代器接口的东西
  • 空间配置器：负责空间的配置与管理

• 容器就是用来存放数据的

• STL容器就是将一些运用最广泛的数据结构实现出来

• 常用的数据结构：数组、链表、二叉树、栈、队列、集合、映射表

• 这些容器分为序列式容器和关联式容器

  • 序列式容器强调值的排序，里面每个值都有固定的位置
  • 关联式容器：二叉树结构、各元素之间没有严格的物理上的顺序关系

1.2 容器算法

• 算法
  • 算法就是用有限的步骤，解决数学或者逻辑上的问题
  • 算法分为质变算法和非质变算法
    • 质变算法是指运算过程中会更改区间内的元素，例如拷贝、删除、替换
    • 非质变算法是指运算过程中不会更改区间内的元素。例如查找、计数、遍历、寻找极值等

1.3 迭代器

• 迭代器就是容器和算法之间的粘合剂
  • 提供一种方法，使之能够依序访问容器内的各个元素，而不暴露容器的内部表示方式

//
//  main.cpp
//  迭代器初识
//
//  Created by OnlyBei on 2021/9/24.
//

#include <iostream>
#include <vector>
using namespace std;

void myPrint(int val) {
    cout << val << endl;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    
    vector<int>::iterator pBegin = v.begin();
    vector<int>::iterator pEnd = v.end();
    
    // 第一种遍历方式
    while(pBegin != pEnd) {
        cout << *pBegin << endl;
        pBegin++;
    }
    
    // 第二种
    for(vector<int>::iterator it = v.begin(); it != v.end(); it++) {
        cout << *it << endl;
    }
    
    for_each(v.begin(), v.end(), myPrint);
    
}

1.4 vector存放自定义数组

//
//  main.cpp
//  vector中存放自定义数据类型
//
//  Created by OnlyBei on 2021/9/24.
//

#include <iostream>
#include <vector>
using namespace std;

class Person {
public:
    Person(string name, int age) {
        this->m_Name = name;
        this->m_Age = age;
    }
public:
    string m_Name;
    int m_Age;
};

void test01() {
    vector<Person> v;
    
    Person p1("aaa", 10);
    Person p2("bbb", 20);
    Person p3("ccc", 30);
    Person p4("ddd", 40);
    
    v.push_back(p1);
    v.push_back(p2);
    v.push_back(p3);
    v.push_back(p4);
    
    for(vector<Person>::iterator it = v.begin(); it != v.end(); it++) {
//        cout << "姓名：" << it->m_Name << "年龄：" << it->m_Age << endl;
        cout << "姓名：" << (*it).m_Name << "年龄：" << (*it).m_Age << endl;

    }

}

void test02() {
    vector<Person*> v;
    
    Person p1("aaa", 10);
    Person p2("bbb", 20);
    Person p3("ccc", 30);
    Person p4("ddd", 40);
    
    v.push_back(&p1); // 取地址
    v.push_back(&p2);
    v.push_back(&p3);
    v.push_back(&p4);
    
    for(vector<Person*>::iterator it = v.begin(); it != v.end(); it++) {
      // 双重指针
//        cout << "2姓名：" << (*(*it)).m_Name << "年龄：" << (*(*it)).m_Age << endl;
        cout << "2姓名：" << (*it)->m_Name << "年龄：" << (*it)->m_Age << endl;

    }

}

int main(int argc, const char * argv[]) {
    // insert code here...
//    test01();
    test02();
}

1.5 vector的嵌套结构

//
//  main.cpp
//  vector中的嵌套数据类型
//
//  Created by OnlyBei on 2021/9/24.
//

#include <iostream>
#include <vector>
using namespace std;

void test() {
    vector<vector<int> > v;
    
    vector<int> v1;
    vector<int> v2;
    vector<int> v3;
    vector<int> v4;
    
    for(int i = 0; i < 4; i++) {
        v1.push_back(i);
        v2.push_back(i + 4);
        v3.push_back(i + 8);
        v4.push_back(i + 12);
    }
    
    v.push_back(v1);
    v.push_back(v2);
    v.push_back(v3);
    v.push_back(v4);
    
    for(vector<vector<int> >::iterator it = v.begin(); it != v.end(); it++) {
        for(vector<int>::iterator vit = (*it).begin(); vit != (*it).end(); vit++) {
            cout << *vit << " ";
        }
        cout << endl;
    }

}

int main(int argc, const char * argv[]) {
    // insert code here...
    test();
}

2. String容器

2.0 前置知识：

• 在C语言中:

  • char是定义一个字符，存储一个字符，占一个字节。
  • string是定义一个字符串，存储的是一段如“abcd”的数据，而且最后还有一个结束符’\0’。

• 在C++中:

  • string有两种，要区别理解；

  • 第一种是字符串char[ ]，例如’a’是char, “a”是char string，这两者都是普通的字符和字符串，和C语言中没什么不同值得注意的是后者包含两个字符，末尾有一个隐身的’\0’。

  • 第二种是封装好的字符串类，如string str = “a” 是C++ 封装好的string。

  • C++中的char string和string不是一回事。当用到了”string”这个关键词，就不是普通的字符串，而是用到了封装后的类。

  • 在C++中，char仍然是一个primitive type(原始类型)，而string已经经过封装，成为了一个class(类)用到它时，我们需要 #include，它是C++ Standard Library (C++标准库)的一部分。

• c中的char* 定义字符串，不能改变字符串内的字符的内容，但却可以把另外一个字符串赋给它。

2.1 String的基本概念

• string是C++风格的字符串，而string本质是一个类
• string和char *的区别
  • char *是一个指针
  • string是一个类，类内部封装了char * ，管理这个字符串，是一个char * 的容器
• 特点：
  • string内部封装了很多成员方法
  • 例如：find查找、insert插入、delete删除、replace替换、copy拷贝
  • string管理char*的内存，不用担心复制越界和取值越界等，由类内部负责

2.2 String的构造函数

• string(); //创建一个空的字符串，例如string str
• string(const char* s); // 使用字符串s初始化
• string(const string& str); // 使用一个string对象初始化另一个string对象
• string(int n, char c); // 使用n个字符c初始化

2.3 Sring的赋值操作

• string& operator = (const char* s); //char*类型字符串，赋值给当前字符串
• string& operator = (const string &s); //把字符串s赋值给当前字符串
• string& operator = (char c); //把字符赋值给当前字符串
• string& assign(const char* s); //把字符串s赋值给当前字符串
• string& assign(const char* s, int n); //把字符串s的前n位赋值给当前字符串
• string& assign(const stringr &s); //把字符串s赋值给当前字符串
• string& assign(int n, char c); //用n个字符赋值给当前字符串

//
//  main.cpp
//  String的赋值操作
//
//  Created by OnlyBei on 2021/9/24.
//

#include <iostream>
#include <string>
using namespace std;

void test() {
    string s1;
    s1 = "hello,world";
    cout << "s1 = " << s1 << endl;
    
    string s2 = s1;
    cout << "s2 = " << s2 << endl;
    
    string s3;
    s3 = "a";
    cout << "s3 = " << s3 << endl;
    
    string s4;
    s4.assign("hello, c++");
    cout << "s4 = " << s4 << endl;
    
    string s5;
    s5.assign("hello, c++", 5);
    cout << "s5 = " << s5 << endl;
    
    string s6;
    s6.assign(s5);
    cout << "s6 = " << s6 << endl;
    
    string s7;
    s7.assign(15, 'h');
    cout << "s7 = " << s7 << endl;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    test();
}

2.4 String字符串拼接

• string& operator += (const char* str); // 重载+=操作符
• string& operator += (const char c); // 重载+=操作符
• string& operator += (const string& str); // 重载+=操作符
• string& append(const char *s); // 把字符串s连接到当前字符串的结尾
• string& append(const char *s,int n); // 把字符串s的前n位连接到当前字符串的结尾
• string& append(const string &s); //同string& operator += (const char* str)
• string& append(const string &s, int pos, int n); // 字符串s从pos开始的n个字符拼接到当前字符串的尾部

2.5 String字符串的查找

• 功能描述
  • 查找：查找指定字符串是否存在
  • 替换：在指定的位置替换字符串
• 函数原型：
  • int find(const string& str, int pos = 0) const; // 查找str第一次出现的位置，从pos开始查找
  • Int find(cosnt char* s, int pos = 0) const; // 查找s第一次出现的位置，从pos开始查找
  • int find(const char* s, int pos, int n) const; //从pos位置查找s的前n个字符第一次位置
  • int find(const char c, int pos = 0) const; // 查找字符c第一次出现位置
  • int rfind(const string& str, int pos = npos) const; // 查找str最后一次位置，从pos开始查找
  • int find(const char* s, int pos = npos) const; // 查找s最后一次出现位置，从pos开始查找
  • int rfind(const char* s, int pos, int n) const; //从pos查找s的前n个字符最后一次出现位置
  • int rfind(const char s, int pos = 0) const; //查找字符c最后一次出现位置
  • string& replace(int pos, int n , const string& str); //替换从pos开始n个字符位字符串str
  • string& replace(int pos, int n, const char* s); //替换从pos开始的n个字符为字符串

2.6 String字符串比较

• 功能描述：

  • 字符串之间的比较

• 比较方式：

  • 字符串比较是按字符的ASCII码进行对比
  • = 的话返回 0
  • >的话返回 1
  • <的话返回 -1

• 函数原型：

  • int compare(const string &s) const; //与字符串s进行比较
  • int compare(const char *s) const; //与字符串s进行比较

2.7 String字符串的存取

• string中单个字符的存取有两种方式
• char& operator[] (int n); //通过[]方式取字符
• Char& at(int n); //通过at方式取字符

修改的话直接，str[i] = “”; 或者 str.at(n) = “”;

2.8 String插入和删除

• 功能描述：
  • 对string字符串进行插入和删除操作
• 函数原型：
  • string& insert(int pos, const char* s); //插入字符串
  • string& insert(int pos, const string& s); //插入字符串
  • string& insert(int pos, int n, char c); //在指定位置插入n个字符串c
  • string& erase(int pos, int n = npos); //删除从pos开始的n个字符

2.9 String字符串子串

• 功能描述：
  • 从字符串中获取想要的子串
• 函数原型：
  • string substr(int pos = 0, int n = npos) const; // 返回从pos开始由n个字符组成的字符串

3. Vector容器

3.1 Vector基本概念

• 功能：
  • vector数据结构和数组非常相似，也称为单端数组
• vector与普通数组的区别
  • vector可以动态扩展
• 动态扩展：
  • 并不是在原有空间之后拼接新空间，而是找更大的内存空间，然后将数据拷贝到新空间，释放原空间
• vector容器迭代器是支持随机访问的一个迭代器

3.2 Vector容量和大小

• 功能描述：
  • 对vector的容器的容量和大小进行操作
• 函数原型
  • empty(); //判断容器是否为空
  • capacity(); //容器的容量
  • size(); //返回容器中元素的个数
  • resize(int num); //重新指定容器的大小为num，若容器变长，则以默认值填充新位置，若变短，则末尾超出容器元素被删除
  • resize(int num, in elem);//重新指定容器的大小为num，若容器变长，则以elem值填充新位置，若变短，则末尾超出容器元素被删除

3.3 Vector容器的插入和删除

• push_back(); //尾插法
• pop_back(); // 删除尾部的元素
• clear(); //删除容器中所有元素
• front(); // 返回容器中第一个元素
• back(); // 返回容器中最后一个元素
• swap(); //实现两个容器进行互换操作，实现内存收缩的效果
  • 用swap可以玩很多花样
  • 一篇关于swap写的很好的博客
• reverse(int len); //容器预留len个元素长度，预留位置不初始化，元素不可访问

4. deque容器

3.1 deque容器基本概念

• 功能
  • 双端数组，可以对头端进行插入删除
• deque的区别
  • vector对于头部的插入删除效率低、数据量越大、效率越低
  • deque相对而言，在头部进行数据插入删除的效率比vector高
  • vector访问元素的速度比deque快，这是由两者的内部实现有关

5. List容器

5.1 list基本概念

• 功能
  • 将数据进行链式存储
  • 链表（list）是一种物理存储非连续的物理结构，数据元素的逻辑顺序是通过指针链接实现的
  • STL中的链表是一个双向循环链表

6.Set容器

• set简介
  • 所有元素在插入时会自动排序
• 本质
  • set/multiset属于关联式容器，底层用二叉树实现
• set不允许用重复元素
• multiset允许重复元素

7.Map容器

• 简介：

  • map中所有元素都是pair（对组）
  • pair中第一个元素为key（键值），起到索引作用，第二个元素为value（元素）
  • 所有元素都会按照key值进行排序

• 本质

  • map/multimap属于关联式容器，底层用二叉树实现

• 优点：

  • 可以根据key值快速找到value值

• 区别：

  • map不允许用重复元素
  • multimap允许重复元素

8. 谓词

8.1 谓词概念

• 概念：
  • 返回布尔类型的仿函数称为谓词
  • 如果operator（）接受一个参数，那么叫做一元谓词
  • 如果operator（）接受两个参数，那么叫做二元谓词

//
//  main.cpp
//  谓词
//
//  Created by OnlyBei on 2021/9/25.
//

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class getFive{
public:
    bool operator()(int val) { // 仿函数为什么这样写呢，可以看下面一段代码的源码
        return val > 5;
    }
};

void test() {
    vector<int> v;
    for(int i = 0; i < 10; i++) {
        v.push_back(i);
    }
    
    // getFive()是一个仿函数
    vector<int>::iterator it =  find_if(v.begin(), v.end(), getFive());
    
    if(it != v.end()) {
        cout << "找到了 " << *it << endl;
    }else {
        cout << "未找到" << endl;
    }
    
}

int main(int argc, const char * argv[]) {
    // insert code here...
    test();
}

find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
{
    for (; __first != __last; ++__first)
        if (__pred(*__first)) // 如果这个为真，则跳出循环，放回一个迭代器
            break;
    return __first; 
}

• 二元谓词

  //
  //  main.cpp
  //  谓词
  //
  //  Created by OnlyBei on 2021/9/25.
  //
  
  #include <iostream>
  #include <vector>
  #include <algorithm>
  using namespace std;
  
  class FuncSort {
  public:
      bool operator() (int a, int b) {
          return a > b;
      }
  };
  
  void test02() {
      vector<int> v1;
      v1.push_back(10);
      v1.push_back(30);
      v1.push_back(80);
      v1.push_back(50);
      v1.push_back(20);
      
  //    sort(v1.begin(), v1.end()); // 默认从小打大
      sort(v1.begin(), v1.end(), FuncSort());
      
      for(vector<int>::iterator it = v1.begin(); it != v1.end(); it++) {
          cout << *it << " ";
      }
      cout << endl;
  
  }
  
  int main(int argc, const char * argv[]) {
      test02();
  }