分类 Cpp tutorial 下的文章

C++多线程编程——C++11 thread构造函数


构造方式

std::thread默认提供了四种构造方式:

  1. default constructor:构造一个不代表任何执行线程的线程对象。
  2. initialization constructor:构造一个新的、joinable的thread对象,该方式需要一个fn函数作为参数,线程会执行这个函数。构造的完成与fn开始调用同步。
  3. copy constructor:不可用,线程对象不可被拷贝。
  4. move constructor:运用了C++11引入的新特性std::move,需要一个已有线程x通过std::move(x)作为参数。该操作不会影响被移动线程的执行,它只是传递其句柄。之后x不再表示任何执行线程。
    注意:一个线程只有在被销毁前被join或detach才是joinable的。

简单例程

cplusplus.com给出这样一个例程:

// constructing threads
#include <iostream>       // std::cout
#include <atomic>         // std::atomic
#include <thread>         // std::thread
#include <vector>         // std::vector

std::atomic<int> global_counter (0);

void increase_global (int n) { for (int i=0; i<n; ++i) ++global_counter; }

void increase_reference (std::atomic<int>& variable, int n) { for (int i=0; i<n; ++i) ++variable; }

struct C : std::atomic<int> {
  C() : std::atomic<int>(0) {}
  void increase_member (int n) { for (int i=0; i<n; ++i) fetch_add(1); }
};

int main ()
{
  std::vector<std::thread> threads;

  std::cout << "increase global counter with 10 threads...\n";
  for (int i=1; i<=10; ++i)
    threads.push_back(std::thread(increase_global,1000));

  std::cout << "increase counter (foo) with 10 threads using reference...\n";
  std::atomic<int> foo(0);
  for (int i=1; i<=10; ++i)
    threads.push_back(std::thread(increase_reference,std::ref(foo),1000));

  std::cout << "increase counter (bar) with 10 threads using member...\n";
  C bar;
  for (int i=1; i<=10; ++i)
    threads.push_back(std::thread(&C::increase_member,std::ref(bar),1000));

  std::cout << "synchronizing all threads...\n";
  for (auto& th : threads) th.join();

  std::cout << "global_counter: " << global_counter << '\n';
  std::cout << "foo: " << foo << '\n';
  std::cout << "bar: " << bar << '\n';

  return 0;
}

该例输出:

increase global counter using 10 threads...
increase counter (foo) with 10 threads using reference...
increase counter (bar) with 10 threads using member...
synchronizing all threads...
global_counter: 10000
foo: 10000
bar: 10000

该例展示了初始化构造函数使用的三种情形,分别为对全局变量、局部变量和成员变量进行++操作。
再来看看其他构造函数如何使用:

#include <iostream>
#include <utility>
#include <thread>
#include <chrono>
#include <functional>
#include <atomic>

void f1(int n)
{
    for (int i = 0; i < 5; ++i) {
        std::cout << "Thread " << n << " executing\n";
        std::this_thread::sleep_for(std::chrono::milliseconds(10));
    }
}

void f2(int& n)
{
    for (int i = 0; i < 5; ++i) {
        std::cout << "Thread 2 executing\n";
        ++n;
        std::this_thread::sleep_for(std::chrono::milliseconds(10));
    }
}

int main()
{
    int n = 0;
    std::thread t1; // t1 is not a thread
    std::thread t2(f1, n + 1); // pass by value
    std::thread t3(f2, std::ref(n)); // pass by reference
    std::thread t4(std::move(t3)); // t4 is now running f2(). t3 is no longer a thread
    t2.join();
    t4.join();
    std::cout << "Final value of n is " << n << '\n';
}

其可能输出为:

Thread 1Thread 2 executing
 executing
Thread 1 executing
Thread 2 executing
Thread 2 executing
Thread 1 executing
Thread 2 executing
Thread 1Thread 2 executing
 executing
Thread 1 executing
Final value of n is 5

如之前介绍所言,t4通过std::move(t3)构造,并且不影响线程的运行,n的值仍然为5,t3也不再是线程。


Ceres solver简介


Ceres简介

Ceres Solver是谷歌的一个开源C++库,用于解决非线性优化问题,包括具有边界约束的非线性最小二乘问题和一般的无约束优化问题。在SLAM项目中Ceres用的非常多,港科大的VINS、谷歌的开源激光雷达SLAM项目Cartographer都有用到Ceres。Ceres的官方文档还是非常详细的,它的docs明确列举了这个库的features,这里就不一一赘述。

简单教程

非线性最小二乘问题

这里我简单搬运一下官方的tutorial。在很多领域,我们都会遇到如下形式的非线性最小二乘问题。
$$\begin{split}\min_{\mathbf{x}} &\quad \frac{1}{2}\sum_{i} \rho_i\left(\left\|f_i\left(x_{i_1}, ... ,x_{i_k}\right)\right\|^2\right) \\
\text{s.t.} &\quad l_j \le x_j \le u_j\end{split} \tag{1}$$
该类问题很常见,如统计学中的拟合曲线、基于图像的三维重建,三维重建的第一步Structure From Motion中的Bundle adjustment实际上就是个非线性最小二乘问题。
公式中的$\rho_i\left(\left\|f_i\left(x_{i_1},...,x_{i_k}\right)\right\|^2\right)$称作ResidualBlock,而$f_i(\cdot)$是关于参数向量$\left[x_{i_1},... , x_{i_k}\right]$的CostFunction 。$\rho_i$是LossFunction,它是一组标量,用于减少outliers对非线性最小二乘解的影响。

一个官方demo

考虑求函数$\frac{1}{2}(10 -x)^2$的最小值。很明显它在$x = 10$处有最小值。
Ceres第一步要求定义代价函数$f(x) = 10 - x$的functor,其代码如下:

struct CostFunctor {
   template <typename T>
   bool operator()(const T* const x, T* residual) const {
     residual[0] = T(10.0) - x[0];
     return true;
   }
};

方法operator()已经模板化了,这使得Ceres可以调用CostFunctor::operator<T>(),当需要残差的值时,T的类型为double,当需要Jacobians时,T的类型为Jet
之后使用代价函数$f(x)$,也就是上面的CostFunctor构建待求解的优化问题。

CostFunction* cost_function = 
      new AutoDiffCostFunction<CostFunctor, 1, 1>(new CostFunctor);

再配置求解器,设置如何求解、是否输出求解过程等参数,调用Solve方法即可得到结果。

int main(int argc, char** argv) {
  google::InitGoogleLogging(argv[0]);

  // The variable to solve for with its initial value.
  double initial_x = 0.5;
  double x = initial_x;

  // Build the problem.
  Problem problem;

  // Set up the only cost function (also known as residual). This uses
  // auto-differentiation to obtain the derivative (jacobian).
  CostFunction* cost_function =
      new AutoDiffCostFunction<CostFunctor, 1, 1>(new CostFunctor);
  problem.AddResidualBlock(cost_function, NULL, &x);

  // Run the solver!
  Solver::Options options;
  options.linear_solver_type = ceres::DENSE_QR;
  options.minimizer_progress_to_stdout = true;
  Solver::Summary summary;
  Solve(options, &problem, &summary);

  std::cout << summary.BriefReport() << "\n";
  std::cout << "x : " << initial_x
            << " -> " << x << "\n";
  return 0;
}

该例的输出为:

iter      cost      cost_change  |gradient|   |step|    tr_ratio  tr_radius  ls_iter  iter_time  total_time
   0  4.512500e+01    0.00e+00    9.50e+00   0.00e+00   0.00e+00  1.00e+04       0    5.33e-04    3.46e-03
   1  4.511598e-07    4.51e+01    9.50e-04   9.50e+00   1.00e+00  3.00e+04       1    5.00e-04    4.05e-03
   2  5.012552e-16    4.51e-07    3.17e-08   9.50e-04   1.00e+00  9.00e+04       1    1.60e-05    4.09e-03
Ceres Solver Report: Iterations: 2, Initial cost: 4.512500e+01, Final cost: 5.012552e-16, Termination: CONVERGENCE
x : 0.5 -> 10

这里发现官方文档有个问题,示例代码examples/helloworld.cc给出的迭代的初始值为$x=0.5$,而文档给定的初值为$x=5$,提供的结果却是$x=0.5$的,小问题还望大家注意。

PS

在编辑公式的时候发现一些坑,在此记录。我博客的公式是由MathJax在客户端上渲染出来的,然而Markdown会把LaTex的符号\当作转义符,造成公式显示错误。解决方法是公式中所有的\都写成\\,方法来自这篇文章。其实我测试的结果是并不是所有的\都要写两次,如果公式中有\begin\text这种符号前端就无法正确解析,需要将\写两次。对于Tex和Markdown之间的关系,我不甚了解,所以无法给出引起这个问题的结论。不过似乎\begin\text等是Tex独占的语法,Markdown原生并不支持,当然这只是我个人猜想而已,以后再去细究。


C++多线程编程——C++11 thread初探


引言

由于项目需要,尝试在代码中引入多线程操作。看了一些博客介绍多线程,但普遍为入门级别的教程;尝试在项目中使用,性能又不忍直视,遂决定在博客中记录C++多线程的学习过程。
std::thread是C++11引入的新特性,在此之前只能使用Windows api或Linux的Pthread编写多线程程序,增加了代码跨平台移植的难度。C++11后,我们可以在编程语言层面使用多线程。本系列文章主要探讨C++标准库的多线程。

简单例程

std::thread类声明在头文件<thread>中。下面给出一个最基本的使用例程

// thread example
#include <iostream>       // std::cout
#include <thread>         // std::thread
 
void foo() 
{
  // do stuff...
}

void bar(int x)
{
  // do stuff...
}

int main() 
{
  std::thread first (foo);     // spawn new thread that calls foo()
  std::thread second (bar,0);  // spawn new thread that calls bar(0)

  std::cout << "main, foo and bar now execute concurrently...\n";

  // synchronize threads:
  first.join();                // pauses until first finishes
  second.join();               // pauses until second finishes

  std::cout << "foo and bar completed.\n";

  return 0;
}

该例输出为:

main, foo and bar now execute concurrently...
foo and bar completed.

该段代码首先声明了两个线程并在构造期间传入相应的函数和参数,之后线程就调用相应函数,该函数的参数即由线程构造函数中的参数给出。在线程执行完之前,主线程main等待子线程的执行完成(join)。

小结

本文仅仅示例了std::thread最简单的用法,它只是后续内容的一个引子。希望自己多学习多思考多记录多交流,做出一些微小的贡献。


从中序与后序遍历序列构造二叉树


问题
  根据一棵树的中序遍历与后序遍历构造二叉树。可以假设数中没有重复元素。
  例如,给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

  返回以下的二叉树

分析
  首先明确两点:
  1. 后序遍历输出的数组,最后一个元素为树根。
  2. 中序遍历输出的数组,树根左边的元素构成左子树,树根右边的元素构成右子树。
  基于这两点,可以先从后序遍历中找到整个树的树根,再在中序遍历的结果中找到该树根,树根左边的元素即为左子树,右边的元素即为右子树。至此,该问题形成一个递归问题--左子树和右子树在后序遍历中也分别对应一个数组集合,对左子树和右子树分别递归即可还原原来的二叉树。

代码

/**
* Definition for a binary tree node.
* struct TreeNode {
*   int val;
*   TreeNode *left;
*   TreeNode *right;
*   TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/

class Solution {
public:
  TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    if(inorder.size()!=postorder.size())
      return NULL;
    if(inorder.size()==0 || postorder.size()==0)
      return NULL;

    int length=inorder.size();
    TreeNode* root=new TreeNode(postorder[length-1]);
    int root_inorder_index=-1;
    vector inorder_l,inorder_r,postorder_l,postorder_r;
    for(int i=0;i<length;i++)
      if(inorder[i]==postorder[length-1]){
        root_inorder_index=i;
        break;
      }

    for(int i=0;i<root_inorder_index;i++){
      inorder_l.push_back(inorder[i]);
      postorder_l.push_back(postorder[i]);
    }

    for(int i=root_inorder_index+1;i<inorder.size();i++){ 
      inorder_r.push_back(inorder[i]); 
      postorder_r.push_back(postorder[i-1]); 
    } 

    root->left=buildTree(inorder_l,postorder_l);
    root->right=buildTree(inorder_r,postorder_r);
    return root;
  }
};