Loading...
墨滴

果冻

2021/10/09  阅读:23  主题:自定义主题1

C++代码简化之道(二):三目运算符和swap消除非必要的指针

作为C++程序员,肯定免不了和指针打交道了。一般我们使用指针都是为了避免不必要的拷贝,但有时候其实可以简化掉它。

活用三目运算符

先看一段例子,假设我们有一段老代码:

  ...
  const string s = "1234567";

  ...
  foo(s); // foo(const string&)
  bar(s); // bar(const string&)
  ...

在某个函数中我们有一个常量s,参与后续计算逻辑。某一天逻辑调整,我们通过某种计算(比如解析配置)获得了一个 vector 类型的变量 v,如果v里面有元素就取第一个元素赋值给s,否则还沿用默认值"1234567"。那么初学者可能这样改:

  string s = "1234567";
  if (v.size() > 0) {
      s = v[0];
  }
  ...
  foo(s);
  bar(s);
  ...

或者:

  string s;
  if (v.size() > 0) {
      s = v[0];
  } else {
      s = "1234567";
  }
  ...
  foo(s);
  bar(s);
  ...

但是无论哪种都存在string的operato=() 的调用。一开始的初始化可能会变得无意义,因为紧接着就会被覆盖。 稍有经验的程序员会这样写:

  const string def_s = "123467";
  const string* sp = &def_s;
  if (v.size() > 0) {
      sp = &v[0];
  }
  const auto& s = *sp;
  ...
  foo(s);
  bar(s);
  ...

使用指针就能避免这次operato=()的开销。 但其实利用三目运算符会更简洁:

  const auto& s = v.size() > 0 ? v[0]: "1234567";
  
  ...
  foo(s);
  bar(s);
  ...

如果有更多的条件和判断,那么三目运算符嵌套就会影响可读性了,所以不建议盲目使用三目运算符,不要生搬硬套。

通过leetcode题目来看swap

leetcode 102. 二叉树的层序遍历:
给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。

class Solution {
public:
   vector<vector<int>> levelOrder(TreeNode* root) {
   }
};

题目不难,就是二叉树的BFS遍历,一般实现BFS我们通常都借助队列 queue来实现。比如:

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (!root) {
            return {};
        }
        vector<vector<int>> ans;

        queue<TreeNode*>* q = new queue<TreeNode*>;
        q->push(root);
        while (!q->empty()) {
            queue<TreeNode*>* tmp_q = new queue<TreeNode*>;
            vector<int> v;
            while (!q->empty()) {
                
                TreeNode* node = q->front();
                if (node) {
                    v.push_back(node->val);
                    tmp_q->push(node->left);
                    tmp_q->push(node->right);
                }
                q->pop();
            }
  
            // 调整q的指向
            q = tmp_q;
            if (!v.empty()) {
                ans.push_back(move(v));
            }
        }

        return ans;
    }
};

上面代码中,之所以qtmp_q都使用指针,是因为最外层的while循环判断条件是一直判断 q是否为空,然而每一层遍历的q 其实是不同的。使用指针目的是在单层遍历完成后,直接修改q指针的指向,使其指向下一层的队列tmp_q。

另外请忽略代码中只有new,而没有delete,因为leetcode刷题一般都不考虑内存泄漏

如果不想让q 变成指针呢?那么很多人会这样写:

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (!root) {
            return {};
        }
        vector<vector<int>> ans;

        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            vector<TreeNode*> tmp_v;
            vector<int> v;
            while (!q.empty()) {
                
                TreeNode* node = q.front();
                if (node) {
                    v.push_back(node->val);
                    tmp_v.push_back(node->left);
                    tmp_v.push_back(node->right);
                }
                q.pop();
            }
            // 遍历,入队
            for (TreeNode* node: tmp_v) {
                q.push(node);
            }
            if (!v.empty()) {
                ans.push_back(move(v));
            }
        }

        return ans;
    }
};

借助一个临时的vector来处理,在每一层遍历完成后,再从vector里把下一层的节点push到已经变成空的队列q中。 很明显这里的问题就是会多一些遍历和push的操作。

能不能即不把q弄成指针,又不需要做额外的push呢? 答案是借助swap:

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (!root) {
            return {};
        }
        vector<vector<int>> ans;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            queue<TreeNode*> tmp_q;
            vector<int> v;
            while (!q.empty()) {
                
                TreeNode* node = q.front();
                if (node) {
                    v.push_back(node->val);
                    tmp_q.push(node->left);
                    tmp_q.push(node->right);
                }
                q.pop();
            }
           // 交换q和tmp_q的内部存储
            q.swap(tmp_q);
            if (!v.empty()) {
                ans.push_back(move(v));
            }
        }
        return ans;
    }
};

不止queue,像vector、map、stack等STL容器都有swap成员函数。请放心swap的开销是常数时间。

STL容器会占用栈存储和堆存储,比如vector,即使你使用的局部变量的vector,它内部也会把具体的数据存储用堆来存储,在类内部使用一个指针指向这块内存而已。

这个指针本身是栈存储,它指向的位置是堆存储区。所谓的swap,只不过是交换两个容器内部指向数据的指针。

往期推荐

C++代码简化之道(一)
C++代码简化之道(一)
叫板面试官:请不要再问我海量数据题!
叫板面试官:请不要再问我海量数据题!
C++之我见:重剑无锋,大巧不工
C++之我见:重剑无锋,大巧不工
bthread源码剖析:工作窃取与run_main_task()
bthread源码剖析:工作窃取与run_main_task()
bthread源码剖析: bthread上下文的创建
bthread源码剖析: bthread上下文的创建

果冻

2021/10/09  阅读:23  主题:自定义主题1

作者介绍

果冻