Category: C/C++

Traits and Template Partial Specialisation – 2

template< class InputIterator, class Distance >
void advance( InputIterator &i, Distance n )
{
   if( is_random_access_iterator( I ) ) {
      advance_RAI( i, n );
   } else if( is_bidirectional_iterator( I ) ) {
      advance_BI( i, n );
   } else {
      advance_II( i, n );
   }
}

The disadvantage of this approach is which advance_xx() is going to be used is determined during runtime, not at compile time, and thus the performance is not ideal.

Overloading mechanism can address this problem. 

// Define five tag types
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};

These classes are only used as tags, and no need any members.

Now, the above advance_xx() functions can be written like below:

template< class InputIterator, class Distance >
inline void __advance( InputIterator &i, Distance n, input_iterator_tag )
{
   while( n-- ) ++I;
}

template< class ForwardIterator, class Distance >
inline void __advance( ForwardIterator &i, Distance n, forward_iterator_tag )
{
   advance( i, n, input_iterator_tag() );
}

template< class BidirectionalIterator, class Distance >
inline void __advance( BidirectionalIterator &i, Distance n, bidirectional_iterator_tag )
{
   if( n >= 0 ) {
      while( n-- ) ++i;
   } else {
      while( n++ ) --i;
   }
}

template< class RandomAccessIterator, class Distance >
inline void __advance( RandomAccessIterator &i, Distance n, random_access_iterator_tag )
{
   i += n;
}

The third parameter is only used to invoke overloading mechanism.

Now, the interface advance() is much simpler as below:

template< class InputIterator, class Distance >
void advance( InputIterator &i, Distance n )
{
   __advance( i, n, iterator_traits< InputIterator >::iterator_category() );
}

In addition, to achieve the above feature, traits needs another type:

template< class I >
struct iterator_traits {
   ...
   typedef typename I::iterator_category iterator_category;
};

// Partial specialisation for raw pointer
template< class T >
struct iterator_traits< T* > {
   ...
   // Note, raw pointer is of RandomAccessIterator
   typedef random_access_iterator_tag iterator_category;
};

// Partial specialisation for pointer-to-const
template< class T >
struct iterator_traits< const T* > {
   ...
   // Similarly, pointer-to-const is also of RandomAccessIterator
   typedef random_access_iterator_tag iterator_category;
};

Traits and Template Partial Specialisation – 1

In C++, template argument deduction doesn’t work for function return type. One solution is using nested type like below:

template< class T >
struct MyIter {
   typedef T value_type; // nested type
   T* ptr_;
   MyIter( T* p=nullptr ) : ptr_( p ){}
   T& operator*() const { return *ptr_; }
};


template< class I >
typename I::value_type func( I iter )
{
   return *iter;
}

// ...
MyIter< int > iter( new int(8) );
cout << func( iter ); // Output: 8

A drawback of this approach is not all iters are of class type, e.g. raw pointer. It’s not possible to define nested type for a raw pointer.

Traits and Template partial specialisation can address this.

// Traits
template< class I >
struct iterator_traits
{ 
   typedef typename I::value_type value_type;
}

// Template Partial Specialisation for T*
template< class T >
typename iterator_traits< T* > 
{
   typedef T value_type;
}

// Template Partial Specialisation for const T*
template< class T >
typename iterator_traits< const T* > 
{
   typedef T value_type; // Note, here should be T rather than const T
}

The above func() could be written like below:

template< class I >
typename iterator_traits< I >::value_type func( I iter )
{
   return *iter;
}

Check if a binary tree is a valid BST

Definition for a binary tree node:

struct TreeNode {
   int value;
   TreeNode *left;
   TreeNode *right;
   TreeNode( int x ) : value( x ), left( nullptr ), right( nullptr ) {}
}

A straightforward but incorrect solution:

bool validateBST( TreeNode *root ) {
   if( root == nullptr ) {
     return true;
   }
   
   if( root->left != nullptr && root->left->value > root->value ) {
     return false;
   }
   
   if( root->right != nullptr && root->right->value < root->value ) {
     return false;
   }
   
   if( !validateBST( root->left ) || !validateBST( root->right ) ) {
     return false;
   }
   
   return true;
}

Test it.

#include <iostream>

int main (int argc, char** argv)
{
  {
    TreeNode *root    = new TreeNode( 3 ); 
    root->left        = new TreeNode( 2 ); 
    root->right       = new TreeNode( 5 ); 
    root->left->left  = new TreeNode( 1 ); 
    root->left->right = new TreeNode( 4 ); 

    std::cout<< validateBST( root ) << std::endl;  // Expect 0
  }
  
  {
    TreeNode *root    = new TreeNode( 4 ); 
    root->left        = new TreeNode( 2 ); 
    root->right       = new TreeNode( 5 ); 
    root->left->left  = new TreeNode( 1 ); 
    root->left->right = new TreeNode( 3 ); 

    std::cout<< validateBST( root ) << std::endl;  // Expect 1
  }

  return 0;
}

Build and run it.

g++ main.cpp --std=c++14
./a.out
1
1

A correct solution:

#include <climits>

bool isValidBST( TreeNode *root, int min, int max ) {
  if( root == nullptr ) {
    return true;
  }
  
  if( root->value < min || root->value > max ) {
    return false;
  }
  
  return isValidBST( root->left, min, root->value - 1 ) && 
         isValidBST( root->right, root->value + 1, max );
}

bool validateBST( TreeNode *root ) {
  return isValidBST( root, INT_MIN, INT_MAX );
}

Use the same “main” to test it.

g++ main.cpp --std=c++14
./a.out
0
1

A better solution:

bool isValidBST( TreeNode *root, TreeNode *left, TreeNode *right ) {
  if( root == nullptr ) {
      return true;
  }

  if( left != nullptr && left->value >= root->value ) {
      return false;
  }

  if( right != nullptr && right->value <= root->value ) {
      return false;
  }

  return isValidBST( root->left, left, root ) && 
         isValidBST( root->right, root, right );
}

bool validateBST( TreeNode *root ) {
  return isValidBST( root, nullptr, nullptr );
}

Ceres Solver: A non-linear optimization library developed by Google

Ceres Solver is an open source C++ library for modeling and solving large, complicated optimization problems. Here is its tutorial about Non-linear Least Squares.

2,9,3 in the following codes represent the dimension of residual, the dimension of camera, the dimension of point.

// Factory to hide the construction of the CostFunction object from
// the client code.
static ceres::CostFunction* Create(const double observed_x,
                                   const double observed_y) {
return (new ceres::AutoDiffCostFunction<SnavelyReprojectionError, 2, 9, 3>(
                 new SnavelyReprojectionError(observed_x, observed_y)));
}

Their definitions can be found in the latest source code (autodiff_cost_function.h).

//   CostFunction* cost_function
//       = new AutoDiffCostFunction<MyScalarCostFunctor, 1, 2, 2>(
//            new MyScalarCostFunctor(1.0));             ^  ^  ^
//                                                       |  |  |
//                            Dimension of residual -----+  |  |
//                            Dimension of x ---------------+  |
//                            Dimension of y ------------------+

The latest code is using variadic template or template parameter pack which was introduced since C++11 to define the number of parameters.

template <typename CostFunctor,
          int kNumResiduals,  // Number of residuals, or ceres::DYNAMIC.
          int... Ns>          // Number of parameters in each parameter block.
class AutoDiffCostFunction : public SizedCostFunction<kNumResiduals, Ns...>

Before that, in the version 1.14.0 released on March 24, 2018, it was using 10 parameters directly.

template <typename CostFunctor,
          int kNumResiduals,  // Number of residuals, or ceres::DYNAMIC.
          int N0,       // Number of parameters in block 0.
          int N1 = 0,   // Number of parameters in block 1.
          int N2 = 0,   // Number of parameters in block 2.
          int N3 = 0,   // Number of parameters in block 3.
          int N4 = 0,   // Number of parameters in block 4.
          int N5 = 0,   // Number of parameters in block 5.
          int N6 = 0,   // Number of parameters in block 6.
          int N7 = 0,   // Number of parameters in block 7.
          int N8 = 0,   // Number of parameters in block 8.
          int N9 = 0>   // Number of parameters in block 9.
class AutoDiffCostFunction : public SizedCostFunction<kNumResiduals,
                                                      N0, N1, N2, N3, N4,
                                                      N5, N6, N7, N8, N9> {

Here are their differences.

boost::combine

boost::combine() packs a group of variables.

#include <vector>
#include <boost/range/combine.hpp>

int main(int argc, char** argv) 
{ 
    // The ranges mush have the same size
    std::vector<int> ids = {1, 2, 3, 4};
    std::vector<std::string> names = { "A", "B", "C", "D" };
    std::vector<float> heights = { 1.71, 1.65, 1.80, 1.75 };    

    for( const auto &zipped : boost::combine(ids, names, heights) ) {
      {
        // tie()
        int id;
        std::string name;
        float height;
        boost::tie(id, name, height) = zipped;

        std::cout << id << "," << name << "," << height << std::endl;
      }
      
      {      
        // get<>()
        int id = boost::get<0>( zipped );
        std::string name = boost::get<1>( zipped );
        float height = boost::get<2>( zipped );

        std::cout << id << "," << name << "," << height << std::endl;
      }    
    }
}

Output:

1,A,1.71
1,A,1.71
2,B,1.65
2,B,1.65
3,C,1.8
3,C,1.8
4,D,1.75
4,D,1.75

Note, the boost version used in this example is 1.71.

boost::endian

Boost introduced a new library endian in version 1.58: Types and conversion functions for correct byte ordering and more regardless of processor endianness.

#include <boost/endian/conversion.hpp>

int32_t x;

... read into x from a file ...

boost::endian::big_to_native_inplace(x);

for (int32_t i = 0; i < 1000000; ++i)
  x += i;

boost::endian::native_to_big_inplace(x);

... write x to a file ...

Use libpng to read and write png file

As for libpng, here is an example about how to use it to read and write a png. But actually the read() method can be simplified as below.

...
png_read_png( png, info, PNG_TRANSFORM_IDENTITY, NULL );
png_bytepp row_pointers = png_get_rows( png, info );

auto width = png_get_image_width( png, info );
auto height = png_get_image_height( png, info );
...

Note, png_read_png() must be called first before calling png_get_rows(), otherwise the return pointer row_pointers would be invalid. Its manual says:

After you have called png_read_png(), you can retrieve the image data with

   row_pointers = png_get_rows(png_ptr, info_ptr);