CPP基础操作___2023-07-25

目录

• 输入输出
• 格式化
  • 设置输出宽度
  • 前置补0
  • 保留有效位数
  • 设置小数位数
  • 四舍五入
• 特殊值
• 最大最小值
• 数据结构
• 数组
  • 定义
• 链表
  • 单链表
  • 操作
  • 初始化
  • 通过数组创建链表
  • 遍历链表
  • 双链表
• 列表
  • 定义
  • 增删改查
  • 排序
• set
  • unordered_set
  • set
• map
  • unordered_map
  • map
• 栈
• queue
• 比较器
• 定义比较器
• 使用比较器
• 理解
• 排序比较器
• 优先级队列比较器
  • 自定义的比较器
• 计时器
• 计时器
• 细节比较
  • 经典算数 vs 位运算
  • 经典交换 vs 异或交换
  • 直接遍历 vs 先算长度
  • 声明后循环 vs 每次都声明
  • cout输出 vs printf输出
  • == vs !=
  • 直接计算 vs 调用函数
  • 传参赋值 vs 手动赋值
  • 声明数组长度 vs 直接调用size() vs 用auto e:array
  • push_back vs emplace_back
• 注意事项
• pow函数是浮点数
• 算法的抢跑: constexpr 和 const 和 #define
• 工具函数
• 直观打印二叉树

---

输入输出

格式化

格式化要用到头文件 iomanip

设置输出宽度

setw(n)

• 作用: 设置<<后的输出宽度一次, 如果输出宽度大于n则会全部输出
• 注意: 仅生效一次, 所以输出一次要用一次

float six = 123456;
float three = 12.3;
float mini = 0.123123;
cout << setw(4) << setfill('*') << six <<endl 
  << setw(4) << three <<endl
  << setw(4) << mini << endl;

输出如下

123456
12.3
0.1234

前置补0

setfill(“0”)

• 作用: 设置填充的字符
• 注意: 会应用到之后所有
• 备注: 默认是空格

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

int main(){
 int hour = 5;
 int minute = 30;
 int second = 0; 
 cout << setw(2) << setfill('0') << hour <<":" 
   << setw(2) << minute <<":"
   << setw(2) << second << endl;
} 

保留有效位数

setprecision(n)

• 作用: 设置有效位数, 会对之后的输出均产生影响
• 注意: 只针对浮点数生效, 过大的数会用科学计数法表示

float big = 12345;
cout << big <<" after " << setprecision(4) << big << endl;

输出如下

12345 after 1.234e+04

设置小数位数

cout << fixed << setprecision(n);

• 作用: 将后续输出的浮点数全部设定为显示小数点后n位
• 注意: 作用范围是之后的全部的浮点数

cout << fixed << setprecision(4); 
float big = 12345;
cout  << big << endl;// 12345.0000
float middle = 1.2345; 
cout << middle << endl;// 1.2345
float mini = 0.12345;
cout << mini << endl;//0.1235

四舍五入

使用 cmath 中的函数可以调整数字
不使用函数的方法也有很多

float a = 12.3456;
//基本函数调用
cout<<ceil(a)<<endl;   //向上取整
cout<<floor(a)<<endl;   //向下取整
cout<<round(a)<<endl;   //四舍五入
//不使用函数实现
//向下取整
cout<<(int)a<<endl;
//向上取整
cout<<(a>(int)a?(int)a+1:(int)a)<<endl;
//四舍五入
cout<<(int)(a+0.5)<<endl;

特殊值

最大最小值

使用包含头文件 climits

cout<<INT_MAX<<endl;  // int最大值
cout<<INT_MIN<<endl;  // int最小值

数据结构

数组

定义

// 存在栈上
int arr[10] = {1,2,3,4,5,6};
// 存在堆上
int *arr = new int[10] {1,2,3,4,5,6};

栈是一块小区域, 访问快
堆很大, 但是访问慢, 系统自动动态申请空间, 需要手动释放空间

链表

单链表

单链表的定义如下

struct Node {
    int value;
    Node *next;
    Node(int x): val(x), next(nullptr) {};
};

操作

初始化

Node* n0 = new Node(0);
Node* n1 = new Node(1);
n0 -> next = n1;

通过数组创建链表

先创建一个头结点, 然后创建一个数组, 将数组中的元素逐个挂在头结点的后面

Node *head = new Node;
head->value = 0;
head->next = nullptr;
Node *p = head;
int arr[10] = {1,2,3,4,5,6,7,8,9,10};
for(int i = 0; i < 10; i++){
    Node *temp = new Node;
    temp->value = arr[i];
    temp->next = nullptr;
    p->next = temp;
    p = p->next;
}

遍历链表

通过已知的头结点, 逐个遍历链表

Node *p = head->next;
while(p != nullptr){
    cout << p->value << endl;
    p = p->next;
}

双链表

双链表的定义如下

struct Node {
    int value;
    Node *next;
    Node *pre;
};

列表

定义

vector<int> list = {1,2,3};

增删改查

• 尾部添加: list.push_back(4);
• 尾部删除: list.pop_back();
• 中间插: list.insert(list.begin()+1, 5);
• 中间删: list.erase(list.begin()+1);

填坑机制, 数组长度会缩短

list.end()-list.begin() == list.size()

排序

sort(list.begin(), list.end(), [](int x, int y){return x > y;});

结果是从大到小排序: [3, 2, 1]

set

unordered_set

unordered_set无序存储一些键
注意, unordered_set中的元素不重复

要求包含头文件 unordered_set

其相关语法有:

• 定义: unordered_set<type> myUnorderedSet;
• 增加: myUnorderedSet.insert(key);
• 删除: myUnorderedSet.erase(key);
• 计数: myUnorderedSet.count(key);

一般查找一个元素的时候, 会使用count函数, 如果返回值为0, 则表示不存在, 否则表示存在(因为set中的元素不重复, 所以返回值只有0和1)

注意, 一下操作的返回值是指针, 需要在前加上*才能获取值

• 查找: myUnorderedSet.find(key);
• 开头: myUnorderedSet.begin();
• 结尾: myUnorderedSet.end();

对于unordered_set, 其end()函数返回的是最后一个元素的下一个位置, 所以在遍历的时候, 不能使用!=, 而应该使用<

增删改查的时间复杂度都是O(1)

遍历这个对象可以使用for循环, 也可以使用迭代器

for(auto it = myUnorderedSet.begin(); it != myUnorderedSet.end(); it++){
    cout << *it << endl;
}

set

set有序存储一些键

要求包含头文件 set

其相关语法有:

• 定义: set<type> mySet;

其他性质与unordered_set相同

map

unordered_map

unordered_map无序存储一些键值对

就其本质而言, unordered_map在内部与unordered_set的实现是相同的, 只是在外部表现上, unordered_map是键值对的形式, 而unordered_set是单个键的形式

要求包含头文件 unordered_map

其相关语法有:

• 定义: unordered_map<type1, type2> myUnorderedMap;
• 增加:
• insert方式: myUnorderedMap.insert(pair<type1, type2>(key, value));
• 更常用的方式: myUnorderedMap[key] = value;
• 删除: myUnorderedMap.erase(key);
• 计数: myUnorderedMap.count(key);

insert方法一般写成: myUnorderedMap.insert({key, value});

获取一个key对应的value的方式有两种:

• myUnorderedMap[key];
• myUnorderedMap.at(key);

myUnorderedMap.find(key)方法返回的是一个迭代器，指向key所在的键值对, 需要用到迭代器的 -> 符号来获取值

cout << myUnorderedMap.find(key)->first << " "
<< myUnorderedMap.find(key)->second << endl;

增删改查的时间复杂度都是O(1)

遍历这个对象可以使用for循环, 也可以使用迭代器

for(auto it = myUnorderedMap.begin(); it != myUnorderedMap.end(); it++){
    cout << it->first << " " << it->second << endl;
}

map

map有序存储一些键值对

要求包含头文件 map

其相关语法有:

• 定义: map<type1, type2> myMap;

其他性质与unordered_map相同

栈

需要包含头文件 stack

定义一个栈的语法如下:

stack<int> myStack;

栈的相关操作有:

• 压栈: myStack.push(value);
• 弹栈: myStack.pop();
• 获取栈顶元素: myStack.top();
• 获取栈的大小: myStack.size();
• 判断栈是否为空: myStack.empty();

queue

需要包含头文件 queue

相关操作:

• 尾部插入: myQueue.push(value);
• 头部删除: myQueue.pop();
• 获取头部元素: myQueue.front();
• 获取尾部元素: myQueue.back();
• 获取队列大小: myQueue.size();
• 判断队列是否为空: myQueue.empty();

比较器

定义比较器

struct CMP1{
    bool operator()(Node &a,Node&b) const{
        return a.val < b.val;
    }
};
struct CMP2{
    bool operator()(Node &a,Node&b) const{
        return a.val > b.val;
    }
};

使用比较器

Node A = Node(1);
Node B = Node(2);
Node C = Node(3);
vector<Node> v = {A, B, C};

sort(v.begin(), v.end(), CMP1());

输出为: 1 2 3

sort(v.begin(), v.end(), CMP2());

输出为:3 2 1

理解

按着比较器中的大小关系, 输出结果中从左至右依次放进去两个数, 比较器返回值均为true
也可以记忆为: 大于号, 所以从大开始

排序比较器

对于这样一个数组:

vector<item *> items

在使用sort函数时, 可以使用如下的比较器:

sort(items.begin(), items.end(), [](item *a, item *b) {
        return a->value < b->value;
    });

优先级队列比较器

对于自定义的结构体, 可以使用如下的比较器:

struct Node{
    int cost;
    int profit;
};
struct cmp1{

        bool operator()(Node n1,Node n2) {
            return n1.profit < n2.profit;//大根堆
        }
};
struct cmp2{

        bool operator()(Node n1,Node n2) const{
            return n1.cost > n2.cost;//小根堆
        }
};

定义优先级队列的语法如下:

priority_queue<Node,vector<Node>,cmp2 > min; //小顶堆--cost
priority_queue<Node,vector<Node>,cmp1 > max; //大顶堆----profit

或者, 更常用的:

priority_queue<int,vector<int>,greater<int> > min; //小顶堆 顶上是最小的
priority_queue<int,vector<int>,less<int> > max; //大顶堆 顶上是最大的

理解: 相反记法, 小于号对应大顶堆, 大于号对应小顶堆

自定义的比较器

场景: 有个数组aaa, 和一个优先级队列bbb, 期望实现bbb存储aaa中元素的索引, 且排序方法是按照aaa中元素的大小来排序

vector<int>
    aaa = {1, 2, 7, 9, 3};

auto comp = [&](int a, int b)
{
    return aaa[a] > aaa[b];
};

priority_queue<int, vector<int>, decltype(comp)>
    bbb(comp);

这里用到的decltype非常巧妙, 可以让编译器自动推断出comp的类型
从而作为priority_queue的模板参数

计时器

计时器

// 计时器
clock_t startTime, endTime;
startTime = clock();
// 程序代码
for(int i=0; i<10e8; ++i){
    ;
}
// 计时结束
endTime = clock();
cout << "Totle Time : " << (double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;

细节比较

注: 一下时间结果均以10e8次操作所得

经典算数 vs 位运算

就a = 2*2;和a = 2<<1;而言, 真没差多少
诸如此类的还有: a = ~b + 2; 和 a = !b;
但是要对2取模的话, a = 987 & 1; 确实会比 a = 987 % 2; 快一点

经典交换 vs 异或交换

// 1 经典交换
int t = b;
    b = a;
    a = t;

// 2 异或交换
a = a ^ b;
b = a ^ b;
a = a ^ b;

虽然后者更屌而且用了位运算…
但事实证明: 前者更快! (比较明显)

直接遍历 vs 先算长度

一直在想, 每次遍历都要用.size()获取数组长度, 会不会变慢?

// 1 直接遍历
for (int i = 0; i < aaa.size();i++){
    aaa[i] = i;
}

// 2 先算长度
int len = aaa.size();
for (int i = 0; i < len;i++){
    aaa[i] = i;
}

结果是: 前者的耗时是后者两倍! 所以先算好数组长度再遍历更好!

结果可能会因为数组的长度发生变化(我这里开的是20的长度)
由此在Leecode上刷, 从1方案改成2方案反而耗时增加了, 当时就很困惑
也有可能不同编译器之间有区别吧…

声明后循环 vs 每次都声明

一般对于temp临时工作变量, 我们都会在循环中直接遍历

// 1 每次都声明
for (int i = 0; i < 20; i++)
{
    int temp = b;
    b = a;
    a = temp;
}

// 2 声明后循环
int temp = 0;
for (int i = 0; i < 20; i++)
{
    temp = b;
    b = a;
    a = temp;
}

实验证明: 后者小快
但区别不大, 而且对于前者, 不会导致变量对环境的污染, 后者会有这个隐患
结论是”无伤大雅”

cout输出 vs printf输出

printf确实牛逼!
打印10e3次整数和布尔值
cout结果是$6.706s$, printf结果是$4.642s$
还是多用printf吧

== vs !=

因为非黑即白的条件判断就这两种, 所以就会想有无快慢之分
结果表明基本一致, 哪个顺手用哪个呗

直接计算 vs 调用函数

很多时候会写一些工具函数, 即便函数内容非常简单, 也会出于函数名帮助理解的原因去使用工具函数
那么调用函数的时间如何?

//    auto add = [](int a, int b) -> int
//    { return a<<1 + b<<1; };

int t = a*2 + b*2;
int t = add(a, b);

结果表明: 调用函数耗时2.5倍!
争分夺秒的竞赛中还是别用工具函数了///-_-

传参赋值 vs 手动赋值

一个标准的node结构体一般会这么定义:

struct node
{
    int val;
    explicit node() = default;
    explicit node(int x) { this->val = x; }
};

那么直接利用结构体中传参赋值更快? 还是自己先定义一个空的再手动为其赋值更快?

// 1 传参赋值
node *t = new node(1);
delete t;

// 2 手动赋值
node *t = new node();
t->val = 1;
delete t;

实验表明: 后者小快 (也尝试了更多成员变量, 结果仍旧小快)
考虑到传参会导致一行代码很长, 手动赋值形式上更直观也更无脑, 因此推荐手动赋值

声明数组长度 vs 直接调用size() vs 用auto e:array

一般算法题会给出一个数组, 由于后面可能会多次用到这个长度信息, 直觉上先声明一个变量存储长度信息会更快
单纯遍历数组的话, 还有一种更简便的写法: for(auto e:arr), 将三者的耗时做个对比

vector<int> nums(100'000'000);

// 1 声明数组长度
void test1(vector<int> &nums)
{
    int len = nums.size();
    for (int i = 0; i < len; i++)
        ;
}

// 2 直接调用size()
void test2(vector<int> &nums)
{
    for (int i = 0; i < nums.size(); i++)
        ;
}

// 3 用auto e:array
void test3(vector<int> &nums)
{
    for (int &num : nums)
        ;
}

实验表明: 1 优于 2 优于 3, 而且差异巨大!

Test1 Runtime = 5.97800 s
Test2 Runtime = 19.00300 s
Test3 Runtime = 64.07700 s

不过好像LeetCode上2比1快一点…

push_back vs emplace_back

push_back是将一个新元素拷贝到容器中, 而emplace_back是将新元素直接构造到容器中, 因此前者会多一次拷贝的过程
但是因为前者只需要一个拷贝操作, 而后者需要一个构造函数和一个析构函数, 所以前者的时间消耗更低

void test1(vector<pair<int,int>> &nums)
{
    vector<pair<int,int>> n;
    for (auto e : nums)
    {
        n.push_back(e);
    }
}

void test2(vector<pair<int,int>> &nums)
{
    vector<pair<int,int>> n;
    for (auto e : nums)
    {
        n.emplace_back(e);
    }
}

实验表明: 只有在处理上述这种非基础类型的数据的情况下, emplace_back才稍有优势
基本上, push_back比emplace_back快一小截

Test1 Runtime = 3.61700 s
Test2 Runtime = 3.60600 s

其他不变的情况下, 在LeetCode上测试, push_back比emplace_back甚至快一倍

推荐使用push_back!

注意事项

pow函数是浮点数

打印pow(10, 2), 得到的结果是100
但是!, 打印(int)(pow(10, 2))是99!
这是因为浮点数不精确, 答案是99.999999之类的浮点小数, 在强制转换类型时, 会直接舍去小数部分, 所以得到的结果是99

正确做法是(int)round(pow(10, 2)), 得到正确结果是100

算法的抢跑: constexpr 和 const 和 #define

产生效果的时点分别是:
| | 时点 | 效果 |
| :——-: | :————–: | :——————: |
| #define | 预编译, 编译之前 | 单纯的文本替换 |
| constexpr | 编译时 | 编译时计算, 生成常量 |
| const | 运行时 | 运行时确定 |

因此前两个可以视作”抢跑”, 不被记录在运行时间中
而constexpr可以类型检查, 较为推荐

工具函数

直观打印二叉树

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    explicit TreeNode()
    {
        this->val = 0;
        this->left = nullptr;
        this->right = nullptr;
    };
    explicit TreeNode(int x)
    {
        this->val = x;
        this->left = nullptr;
        this->right = nullptr;
    };
};
class PrintBS
{
    int getPos(int h) { return h != 0 ? 3 * pow(2, h - 1) : 1; }
    void printSpace(int t = 1)
    {
        while (t-- > 0)
        {
            printf(" ");
        }
    }
    void printLine() { printf("_"); }
    void print3SpaceNum(int x)
    {
        if (x / 100 > 0)
        {
            printf("%d", x);
        }
        else if (x / 10 > 0)
        {
            printf("%d ", x);
        }
        else
        {
            printf(" %d ", x);
        }
    }
    int dfs(vector<TreeNode *> &node, TreeNode *root, int x)
    {
        node[x] = root;
        int leftHeight = root->left == nullptr ? -1 : dfs(node, root->left, 1 + x * 2);
        int rightHeight = root->right == nullptr ? -1 : dfs(node, root->right, 2 + x * 2);
        return 1 + max(leftHeight, rightHeight);
    }

public:
    void print(TreeNode *root)
    {
        vector<TreeNode *> node(10e6);
        int rootHeight = dfs(node, root, 0);
        TreeNode *cur = root;
        // 遍历每一层, 分别打印这一层所有的值和延长线, 以及一行"/"和"\"
        for (int curHeight = rootHeight; curHeight > 1; curHeight--)
        {
            // 打印值, 这些值最左侧的序号先要确定, 值的个数也要确定, 都基于curHeight
            int indexOffset = pow(2, rootHeight - curHeight) - 1; // 这一层最左侧的元素序号
            // x代表现在在打印这一层的第几个
            for (int x = 0; x < pow(2, rootHeight - curHeight); x++)
            {
                cur = node[indexOffset + x];
                if (cur == nullptr)
                {
                    for (int i = 0; i < getPos(curHeight); i++)
                        printSpace();
                }
                if (cur->left == nullptr)
                {
                    for (int i = 0; i < getPos(curHeight) - 2; i++)
                        printSpace();
                }
                else
                {
                    for (int i = 0; i < getPos(curHeight - 1) + 1; i++)
                        printSpace();
                    for (int i = getPos(curHeight - 1) + 1; i < getPos(curHeight) - 2; i++)
                        printLine();
                }
                print3SpaceNum(cur->val);
                if (cur->right == nullptr)
                {
                    for (int i = 0; i < getPos(curHeight) - 1; i++)
                        printSpace();
                }
                else
                {
                    for (int i = getPos(curHeight - 1) + 1; i < getPos(curHeight) - 2; i++)
                        printLine();
                    for (int i = 0; i < getPos(curHeight - 1) + 2; i++)
                        printSpace();
                }
            }
            printf("\n");
            // 这里处理下一行的"/"和"\"
            for (int x = 0; x < pow(2, rootHeight - curHeight); x++)
            {
                cur = node[indexOffset + x];
                if (cur == nullptr)
                {
                    for (int i = 0; i < getPos(curHeight); i++)
                        printSpace();
                }
                if (cur->left == nullptr)
                {
                    for (int i = 0; i < getPos(curHeight); i++)
                        printSpace();
                }
                else
                {
                    for (int i = 0; i < getPos(curHeight - 1); i++)
                        printSpace();
                    printf("/");
                    for (int i = 0; i < getPos(curHeight - 1) - 1; i++)
                        printSpace();
                }
                if (cur->right == nullptr)
                {
                    for (int i = 0; i < getPos(curHeight); i++)
                        printSpace();
                }
                else
                {
                    for (int i = 0; i < getPos(curHeight - 1) - 2; i++)
                        printSpace();
                    printf("\\");
                    for (int i = 0; i < getPos(curHeight - 1) + 1; i++)
                        printSpace();
                }
            }
            printf("\n");
        }
        // 处理倒数第二层
        int indexOffset = pow(2, rootHeight - 1) - 1; // 这一层最左侧的元素序号
        for (int x = 0; x < indexOffset + 1; x++)
        {
            if ((cur = node[indexOffset + x]) == nullptr)
            {
                printSpace(6);
            }
            else
            {
                printSpace(1);
                print3SpaceNum(cur->val);
                printSpace(2);
            }
        }
        printf("\n");
        for (int x = 0; x < indexOffset + 1; x++)
        {
            if ((cur = node[indexOffset + x]) == nullptr)
            {
                printSpace(6);
            }
            else
            {
                if (cur->left == nullptr)
                    printSpace(3);
                else
                {
                    printSpace();
                    printf("/");
                    printSpace();
                }
                if (cur->right == nullptr)
                    printSpace(3);
                else
                {
                    printf("\\");
                    printSpace(2);
                }
            }
        }
        printf("\n");
        // 处理最后一层的叶节点
        indexOffset = pow(2, rootHeight) - 1; // 这一层最左侧的元素序号
        for (int x = 0; x < pow(2, rootHeight); x++)
        {
            if ((cur = node[indexOffset + x]) == nullptr)
            {
                printSpace(3);
            }
            else
            {
                if (x & 1)
                {
                    printf("%-3d", cur->val);
                }
                else
                {
                    print3SpaceNum(cur->val);
                }
            }
        }
        printf("\n");
    }
};