【C++学习总结1】从C到C++

1. C的超集 C++的语言联邦：C语言 + 类和对象 + 模板 + Lambda

• C语言：面向过程编程
• 类和对象：面向对象编程
• 模板：泛型编程
• Lambda：函数式编程

所以 C++ 可以支持以上 4 种编程范式。不同的编程范式的编程效率不同。

2. 程序对比

#include
using std::cin;
using std::cout;
using std::endl;

int main() {
    int n;
    cin >> n;
    cout << n << endl;
    return 0;
}

#include 

int main() {
    int n;
    scanf("%d", &n);
    printf("%dn", n);
    return 0;
}

C语言中，读入整数是通过格式占位符 %d 实现的，即要明确说明要读入的数据的类型；但是在C++中，无论读入的数据是什么类型都不需要特殊说明，只需要 cin 跟上要读入的数据。
那么 C++是怎么实现放什么变量就读什么类型的数据呢？ 后续会解答。

3. STL 3.1 queue 类说明 3.2 deque（double-ended queue) 类说明 3.3 string类说明 3.4 unordered_map 类说明（C++11标准）

• map : 排序的映射表，底层实现是红黑树；
• unordered_map : 非排序的映射表，底层实现是哈希表。

4. 应用 HZOJ-245.货仓选址

【思路】

找到中位数。

【代码】
v1：本版本是先排序，然后找到中位数。

#include
#include 
#include 
using namespace std;

int main() {
    vector arr;
    int n;
    cin >> n;
    for (int i = 0, a; i < n; i++) cin >> a, arr.push_back(a);
    sort(arr.begin(), arr.end());
    int pos = arr[n / 2], sum = 0;
    for (int i = 0; i < arr.size(); i++) {
        sum += abs(arr[i] - pos);
    }
    cout << sum << endl;
    return 0;
}

但是本题不用对所有的数据进行排序，只需要找到一组数据的中位数即可。STL 中提供了一个部分排序的函数 nth_element，可以在指定位置处放上正确的值，而不用完全排序。

v2：使用 nth_element 函数部分排序

#include 
#include 
#include 
using namespace std;

int main() {
    vector arr;
    int n;
    cin >> n;
    for (int i = 0, a; i < n; i++) cin >> a, arr.push_back(a);
    nth_element(arr.begin(), arr.begin() + arr.size() / 2, arr.end());
    int pos = arr[n / 2], sum = 0;
    for (int i = 0; i < arr.size(); i++) {
        sum += abs(arr[i] - pos);
    }
    cout << sum << endl;
    return 0;
}

HZOJ-166.字符串操作1

【思路】

使用 string 类中提供的方法进行操作。

【代码】

#include
#include 
using namespace std;

int main() {
    string s1, s2;
    int n;
    cin >> s1 >> n >> s2;
    if (s1.size() > 100) cout << 100 << endl;
    else cout << s1.size() << endl;
    //s1中n-1的位置处插入s2字符串
    s1 = s1.insert(n - 1, s2);
    cout << s1 << endl;
	//find:从左往右查找 rfind：从右往左查找,返回值为字符串的正常下标位置
    cout << s1.size() - s1.rfind("x") << endl;

    return 0;
}

HZOJ-216.获取姓名并排序

【思路】

使用 map 存储数据，则数据就是有序的。

【代码】

#include
#include 

HZOJ-287.合并果子

【思路】

每次拿出最小的两个合并到一起，再放到原来的序列中，依次重复之前的操作。就是 哈夫曼编码。

【代码】

//使用优先队列实现
#include
#include 
using namespace std;

struct CMP {
public:
    bool operator()(int a, int b) {
        return a > b; //值越大，优先级越低，使得原序列从大到小排列
    }
};

int main() {
    //底层使用的是用堆实现的，从后往前出队 CMP此处其实就是个可调用对象
    //还可以写成：priority_queue, greater> que; 其中greater就是个模板类
    priority_queue, CMP> que;
    //prority_queue que; //默认是优先级高的先出队，对于整数来说，默认是从小到大排列，先出队的是大的数
    int n;
    cin >> n;
    for (int i = 0, a; i < n; i++) {
        cin >> a;
        que.push(a);
    }
    
    //合并果子
    int sum = 0;
    for (int i = 1; i < n; i++) {
        int a = que.top(); que.pop();
        int b = que.top(); que.pop();
        sum += a + b;
        que.push(a + b);
    }
    cout << sum << endl;
    
    return 0;
}

还可以写成模板类的样子，就和 priority_queue, greater> que; 是一样的：

#include
#include 
using namespace std;

template 
struct CMP {
public:
    bool operator()(T a, T b) {
        return a > b; //值越大，优先级越低，使得原序列从大到小排列
    }
};

int main() {
    //底层使用的是用堆实现的，从后往前出队
    priority_queue, CMP> que;
    //prority_queue que; //默认是从大到小进行排列
    int n;
    cin >> n;
    for (int i = 0, a; i < n; i++) {
        cin >> a;
        que.push(a);
    }
    
    //合并果子
    int sum = 0;
    for (int i = 1; i < n; i++) {
        int a = que.top(); que.pop();
        int b = que.top(); que.pop();
        sum += a + b;
        que.push(a + b);
    }
    cout << sum << endl;
    
    return 0;
}

HZOJ-256.国王游戏

【思路】

目标：获得最多金币的大臣获得的金币最少。

算法思想：微扰。

符号定义：

• a i a_i ai​ : 第 i i i 个人左手上的数字
• b i b_i bi​ : 第 i i i 个人右手上的数字
• A i A_i Ai​ : a a a 序列前 i i i 项的累乘
• C i C_i Ci​ : 第 i i i 个人获得的金币数量 C i = A i − 1 b i C_i = frac{A_{i - 1}}{b_i} Ci​=bi​Ai−1​​

假设某种排列下，第 i i i 个人获得金币的数量 C i C_i Ci​ 最多（即 C i − 1 < C i , C i + 1 < C i ) C_{i - 1} < C_i, C_{i+ 1} < C_i) Ci−1​
引入“微扰”：调换第 i i i 个人和第 i − 1 i - 1 i−1个人的位置，假设调换以后，第 i i i 个人能获得的金币数量是 C i ′ C_i' Ci′​，第 i − 1 i - 1 i−1个人能获得的金币数量是 C i − 1 ′ C_{i-1}' Ci−1′​ ，在第二个序列中，只有第 i i i 个人和第 i − 1 i - 1 i−1个人手中金币数量发生了变化，而其他人的金币数量和原来相同。

意味着在新的排列中，只要保证 C i ′ < C i C_i' lt C_i Ci′​
讨论什么情况下 C i ′ < C i C_i' lt C_i Ci′​

C i = A i − 1 b i C_i=frac{A_{i-1}}{b_i} Ci​=bi​Ai−1​​， C i ′ = A i − 2 b i C_i' = frac{A_{i -2}}{b_i} Ci′​=bi​Ai−2​​，所以 C i ′ < C i C_i' lt C_i Ci′​
C i − 1 ′ = A i − 2 ∗ a i b i − 1 C_{i-1}' = frac{A_{i-2}*a_i}{b_{i-1}} Ci−1′​=bi−1​Ai−2​∗ai​​，令 C i − 1 ′ < C i C_{i-1}' lt C_i Ci−1′​
至此，得到了排序依据：两个手上的数字乘积越小的人越往前排。

本题的解法也就出来了，对两个手上的数字乘积进行排序，乘积越小的人越往前排。

注意：本题中的累乘，因为 n n n 值很大，甚至会超出 long long 表示范围，所以本题要采用高精度。

【代码】

• v1版：只能通过80%数据，错误原因是使用了不合适的数据类型。不是算法错误，是数据结构的错误。

#include
#include 
#include 
using namespace std;

typedef pair PII;

int main() {
    vector arr;
    int n;
    cin >> n;
    for (int i = 0, a, b; i <= n; i++) {
        cin >> a >> b;
        arr.push_back(PII(a, b));
    }
    sort(arr.begin() + 1, arr.end(), [](PII &x, PII &y) { return x.first * x.second < y.first * y.second; });
    int p = arr[0].first, ans = 0;
    for (int i = 1; i <= n; i++) {
        int temp = p / arr[i].second;
        ans = max(ans, temp);
        p *= arr[i].first;
    }
    cout << ans << endl;
    return 0;
}

• v2版：使用大整数类

#include
#include 
#include 
using namespace std;

typedef pair PII;

class BigInt : public vector {
public:
    BigInt(int x);
    void operator*=(int x);
    void operator/=(int x);
    BigInt operator/(int x);
    bool operator<(const BigInt &a) const;
    bool operator>(const BigInt &a) const;
private:
    void process_digit();
};

BigInt::BigInt(int x) {
    push_back(x);
    process_digit();
}

void BigInt::process_digit() {
    for (int i = 0; i < size(); i++) {
        if (at(i) < 10) continue;
        if (i + 1 == size())  push_back(0);//最高位产生进位，给最高位头部添加0
        at(i + 1) += at(i) / 10;
        at(i) %= 10;
    }   
    //去掉前导0
    while (size() > 1 && at(size() - 1) == 0) pop_back();
    return ;
}

void BigInt::operator*=(int x) {
    for (int i = 0; i < size(); i++) {
        at(i) *= x;
    }
    process_digit();
    return ;
}

void BigInt::operator/=(int x) {
    int y = 0;
    for (int i = size() - 1; i >= 0; i--) {
        y = y * 10 + at(i);
        at(i) = y / x;
        y %= x;
    }
    process_digit();
    return ;
}

BigInt BigInt::operator/(int x) {
    BigInt ret(*this);
    ret /= x;
    return ret;
}

//重载左移运算符，使得cout可以输出大整数
ostream &operator<<(ostream &out, const BigInt &a) {
    for (int i = a.size() - 1; i >= 0; i--) 
        out << a[i];
    return out;
}

bool BigInt::operator<(const BigInt &a) const {
    //大整数大小比较
    //比较位数
    if (size() - a.size()) return size() < a.size();
    //比较第 i 位
    for (int i = size() - 1; i >= 0; i--) {
        if (at(i) - a[i]) return  at(i) < a[i];
    }
    return false;
}

bool BigInt::operator>(const BigInt &a) const {
    return a < (*this);
}

int main() {
    vector arr;
    int n;
    cin >> n;
    for (int i = 0, a, b; i <= n; i++) {
        cin >> a >> b;
        arr.push_back(PII(a, b));
    }
    sort(arr.begin() + 1, arr.end(), [](const PII &x, const PII &y) { return x.first * x.second < y.first * y.second; });
    BigInt p = arr[0].first, ans = 0;
    for (int i = 1; i <= n; i++) {
        BigInt temp = p / arr[i].second;
        ans = max(ans, temp);
        p *= arr[i].first;
    }
    cout << ans << endl;
    return 0;
}

5. 引申 5.1 nth_element 函数的用法及技巧

nth_element函数定义于头文件。

【常用函数的原型】

//(c++20前)
void nth_element( RandomIt first, RandomIt nth, RandomIt last ); 
void nth_element( RandomIt first, RandomIt nth, RandomIt last,Compare comp);

nth_element 函数是部分排序算法，默认是求[first, last)区间的第k小。

【参数】

• first，last：定义待排序范围的随机访问迭代器，如vector
• nth：定义排序划分点的随机访问迭代器，也就是想找的元素所在的位置

【示例】

#include
#include 
#include 
//#include 

int main() {
    std::vector v{5, 6, 4, 3, 2, 6, 7, 9, 3};

    std::cout << "Initial array: ";
    for (int i = 0; i < v.size(); i++) {
        std::cout << v[i] << " ";
    }
    std::cout << std::endl;

    std::nth_element(v.begin(), v.begin() + v.size() / 2, v.end());
    std::cout << "The median is " << v[v.size() / 2] << std::endl;
    std::cout << "1.After nth_element: ";
    for (int i = 0; i < v.size(); i++) {
        std::cout << v[i] << " ";
    }
    std::cout << std::endl;

    std::nth_element(v.begin(), v.begin() + 1, v.end());
    std::cout << "The second largest element is " << v[1] << std::endl;
    std::cout << "2.After nth_element: ";
    for (int i = 0; i < v.size(); i++) {
        std::cout << v[i] << " ";
    }
    return 0;
}

【运行结果】

Initial array: 5 6 4 3 2 6 7 9 3
The median is 5
1.After nth_element: 3 2 3 4 5 6 7 9 6
The second largest element is 3
2.After nth_element: 2 3 3 4 5 6 7 9 6

【总结】

• 每次调用nth_element函数只会将nth位置处的元素正确归位，如果想得到另一个位置的元素，则需要重新调用该函数并传入对应的位置。
• 默认的部分排序顺序是升序；也可用comp自定义比较方法。
• 只是进行了部分排序，而非完全排序

当确切地知道想找到数组中排在第 K 小的数时，可使用nth_element，不用对数组进行完全排序。

5.2 string 的几种基本操作的使用方法 5.2.1 find

【常用函数原型】

//c++11前
size_type find( const basic_string& str, size_type pos = 0 ) const;
size_type find( CharT ch, size_type pos = 0 ) const;

【函数功能】

​ 从原字符串的pos位置开始，从左往右查找首个等于给定字符序列的子串

【参数：】

• str：要搜索的字符序列

• pos：开始搜索的位置，默认是0

• ch：要搜索的字符

【返回值：】

​ 找到的子串的首字符位置，或若找不到这种子串则为 npos 。

【示例】

#include
using namespace std;

int main() {
    string s1 = "This is a string!";
    string s2 = "is";
    //从s1的0位置处开始查找字符串"is"
    int res = s1.find("is");
    cout << "find s1 from 0: " << res << endl; //2

    //从s1的5位置处开始查找字符串"is"
    res = s1.find("is", 5);
    cout << "find s2 from 5: " << res << endl; //5

    return 0;
}

5.2.2 insert

【函数原型】

• 插入字符串的函数

//(C++20 前)，在index处插入s指向的以''结尾的字符串
basic_string& insert( size_type index, const CharT* s );
//(C++20 前)，在index处插入[s, s+count)范围的字符串
basic_string& insert( size_type index, const CharT* s, size_type count );
//(C++20 前)，在index处插入string str
basic_string& insert( size_type index, const basic_string& str );
//（C++14前），在index处插入由str.substr(index_str, count) 获得的字符串
basic_string& insert( size_type index, const basic_string& str,
                      size_type index_str, size_type count );

• 插入字符的函数

//（C++20前），在index处插入count个字符ch
basic_string& insert( size_type index, size_type count, CharT ch );
//(C++11前)，在pos指向的字符前插入字符ch
iterator insert( iterator pos, CharT ch );
//(C++11前)，在pos指向的字符前插入count个字符ch
void insert( iterator pos, size_type count, CharT ch );

【参数】

参数	意义
index	在index位置处插入内容
pos	在pos位置前插入内容
ch	要插入的字符
count	要插入的字符数
s	指向要插入的字符串的指针
str	要插入的string
index_str	string str中要插入的首字符的位置

【使用示例】

#include 
#include 
using namespace std;

int main() {

    string s = "xmplr";

    //insert(size_type index, size_type count, char ch)
    s.insert(0, 1, 'E');
    assert("Exmplr" == s);

    //insert(size_type index, const char *s)
    s.insert(2, "e");
    assert("Exemplr" == s);

    //insert(size_type index, string const& str)
    s.insert(6, "a");
    assert("Exemplar" == s);

    //insert(size_type index, string const& str, size_type index_str, size_type count);
    s.insert(8, " is an example string.", 0, 14);
    assert("Exemplar is an example" == s);

    //insert(const_iterator pos, char ch)
    s.insert(s.cbegin() + s.find_first_of('n') + 1, ':');
    assert("Exemplar is an: example" == s);

    //insert(const_iterator pos, size_type count, char ch)
    s.insert(s.cbegin() + s.find_first_of(':') + 1, 2, '=');
    assert("Exemplar is an:== example" == s);

    return 0;
}

5.2.3 substr

【函数原型】

basic_string substr( size_type pos = 0, size_type count = npos ) const;

【功能】

返回子串[pos, pos + count），如果想要得到的子串超过了原字符串的结尾，则返回的子串为[pos, size())。

【参数】

参数	意义
pos	想获取的子串的首字符的位置
count	子串的长度

【返回值】

​ 含子串[pos, pos + count) 的 string

【使用示例】

#include 
#include 
using namespace std;

int main() {
    string s = "Hello World！";
    s = s.substr(6, 5);
    assert("World" == s);
    return 0;
}

5.2.4 replace

【函数原型】

//用字符串string str替换[pos, pos + count)/[first,last)的部分
basic_string& replace( size_type pos, size_type count,
                       const basic_string& str );
basic_string& replace( const_iterator first, const_iterator last,
                       const basic_string& str );

//用字符串str的子串[pos2, pos2 + count)替换原字符串的[pos, pos + count)部分
basic_string& replace( size_type pos, size_type count,
                       const basic_string& str,
                       size_type pos2, size_type count2 );

//用cstr的[cstr, cstr + count2)的字符替换原字符串的[pos, pos + count)/[first,last)部分
basic_string& replace( size_type pos, size_type count,
                       const CharT* cstr, size_type count2 );
basic_string& replace( const_iterator first, const_iterator last,
                       const CharT* cstr, size_type count2 );

//用cstr字符串替换原字符串的[pos, pos + count)/[first,last)部分
basic_string& replace( size_type pos, size_type count,
                       const CharT* cstr );
basic_string& replace( const_iterator first, const_iterator last,
                       const CharT* cstr );

//用count2个字符ch替换原字符串的[pos, pos + count)/[first,last)部分
basic_string& replace( size_type pos, size_type count,
                       size_type count2, CharT ch );
basic_string& replace( const_iterator first, const_iterator last,
                       size_type count2, CharT ch );

【函数功能】

用新的字符串替换[pos, pos+count)或[first, last)的string部分。

【参数】

参数	意义
pos	将被替换的子串的起始位置
count	将被替换的子串长度
first，last	将被替换的字符范围
str	用于替换的string
pos	用于替换的子串起始位置
count2	用于替换的字符数
cstr	指向用于替换的字符串的指针
ch	用于替换的字符

【示例】

#include
#include 
#include 
using namespace std;

int main() {
    string str = "The quick brown fox jumps over the lazy dog.";

    str.replace(10, 5, "red");
    assert("The quick red fox jumps over the lazy dog." == str);

    str.replace(str.begin(), str.begin() + 3, 1, 'A');
    assert("A quick red fox jumps over the lazy dog." == str);

    return 0;
}

5.2.5 assign

【函数原型】

//用count个ch替换字符串内容
basic_string& assign( size_type count, CharT ch );
//用string str替换字符串内容
basic_string& assign( const basic_string& str );
//用str的子串[pos，pos+count)替换字符串的内容
basic_string& assign( const basic_string& str,
                      size_type pos, size_type count );
//用[s, s+count)中的字符替换字符串的内容
basic_string& assign( const CharT* s, size_type count );
//用s指向的以'‘结尾的字符串替换原字符串的内容
basic_string& assign( const CharT* s );

【参数】

参数	意义
count	产生的string大小
str	用来初始化字符串的string
pos	用来替换字符串的str的子串的首字符下标
s	指向用来初始化string字符串的指针

【示例】

#include 
#include 
#include 
using namespace std;

int main() {
    string s;
    s.assign(4, '=');
    assert("====" == s);

    const string c = "Example";
    s.assign(c);
    assert("Example" == s);

    s.assign(c, 0, c.length() - 1);
    assert("Exampl" == s);

    s.assign("C-style string", 7);
    assert("C-style" == s);

    s.assign("C-stylestring");
    assert("C-style" == s);

    return 0;
}

assign的替换更准确来说是赋值，将整个字符串重新进行赋值；而replace则可以选择要替换的子串范围。

5.2.6 stoi、stol、stoll

【函数原型】

int stoi( const std::string& str, std::size_t* pos = 0, int base = 10 );
long stol( const std::string& str, std::size_t* pos = 0, int base = 10 );
long long stoll( const std::string& str, std::size_t* pos = 0, int base = 10 );

【函数功能】

将字符型整数转换为有符号整数值。

【参数】

参数	意义
str	要转换的字符串
pos	存储已处理字符数的整数的地址
base	数的底

【返回值】

str内容中的整数值

【示例】

#include
#include 
#include 
using namespace std;


int main() {

    string s1 = "45";
    int int1 = stoi(s1);
    assert(45 == int1);

    s1 = "Hello World 99!";
    int int2 = stoi(s1);
    assert(99 == int2);

    s1 = "3.1415926";
    int int3 = stoi(s1);
    assert(3 == int3);

    s1 = "words and 2";
    //运行错误：'std::invalid_argument',不能进行转换
    //int int4 = stoi(s1);
    //assert(2 == int4);
    return 0;
}

5.3 讨论HZOJ-287.合并果子题目和Huffman编码的关系

L = ∑ l i ∗ p i L = sum{l_i}*{p_i} L=∑li​∗pi​， l i l_i li​是第 i i i 个字符的编码长度， p i p_i pi​是第 i i i 个字符的出现概率，为了使得 L L L 的值最小，所以出现了Huffman编码，Huffman编码本质就是解决最小编码问题；

C = ∑ l i ∗ c i C = sum{l_i}*{c_i} C=∑li​∗ci​， l i l_i li​为第 i i i 堆果子被合并的次数， c i c_i ci​为第 i i i 堆果子的数量，合并果子问题就是使得 C C C 的值最小。

两个公式本质上都是一样的，所以可以使用Huffman编码的算法流程解决合并果子问题，因为Huffman编码就是解决形如这类公式的和值最小化问题。