Month: September 2019

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);

Write XML from a string

There are two ways of writing XML from a string.

  • To an XML file[1]
    • ET.XML()
    • ET.tostring()
    • write()
  • To the memory[2]
    • ET.fromstring()

Take the xml data from [2] as an exmaple.

xmlData = """<?xml version="1.0"?>
        <data>
            <country name="Liechtenstein">
                <rank>1</rank>
                <year>2008</year>
                <gdppc>141100</gdppc>
                <neighbor name="Austria" direction="E"/>
                <neighbor name="Switzerland" direction="W"/>
            </country>
            <country name="Singapore">
                <rank>4</rank>
                <year>2011</year>
                <gdppc>59900</gdppc>
                <neighbor name="Malaysia" direction="N"/>
            </country>
            <country name="Panama">
                <rank>68</rank>
                <year>2011</year>
                <gdppc>13600</gdppc>
                <neighbor name="Costa Rica" direction="W"/>
                <neighbor name="Colombia" direction="E"/>
            </country>
        </data>"""

To an XML file

from xml.etree import ElementTree as ET

root = ET.XML(xmlData)
with open('a.xml', 'w') as f:
    f.write(ET.tostring(root).decode())

Read the xml file:

tree = ET.parse('a.xml')
rootNode = tree.getroot()
for child in rootNode:
    print(child.tag, child.attrib)
    
country {'name': 'Liechtenstein'}
country {'name': 'Singapore'}
country {'name': 'Panama'}

To the memory

root = ET.fromstring(xmlData)

Read the root directly:

for child in root:
    print(child.tag, child.attrib)
    
country {'name': 'Liechtenstein'}
country {'name': 'Singapore'}
country {'name': 'Panama'}

References

[1] https://stackoverflow.com/questions/6440115/how-do-i-parse-a-string-in-python-and-write-it-as-an-xml-to-a-new-xml-file

[2] https://docs.python.org/2/library/xml.etree.elementtree.html

BFS (Breadth-First Search) and DFS (Depth-First Search)

Some essential definitions:

typedef char Element;

struct Node 
{
  Node( Element inputData ) : data( inputData ) { 
    cout << "Construct " << data << endl; 
  }
  
  ~Node() { 
    cout << "Destruct " << data << endl;
    
    if( lchild != NULL ) {
      delete lchild;
      lchild = NULL;
    }
    
    if( rchild != NULL ) {
      delete rchild;
      rchild = NULL;
    }
  }

  Element data;
  Node *lchild;
  Node *rchild;
};

typedef Node* Tree;

BFS: Breadth-First Search

// BFS
void breadthFirstSearch(Tree root)
{
  queue<Node *> nodeQueue;
  nodeQueue.push (root);
  Node *node;
  while (!nodeQueue.empty()) {
   node = nodeQueue.front();
   nodeQueue.pop ();
   cout << node->data;

   if (node->lchild) {
     nodeQueue.push(node->lchild);
   }

   if (node->rchild) {
     nodeQueue.push(node->rchild);
   }
  }
}

DFS: Depth-First Search

// DFS (iterative)
void depthFirstSearch(Tree root)
{
  stack<Node *> nodeStack;
  nodeStack.push (root);
  Node *node;
  while (!nodeStack.empty ()) {
   node = nodeStack.top();
   nodeStack.pop ();
   cout << node->data;

   if (node->rchild) {
     nodeStack.push(node->rchild);
   }

   if (node->lchild) {
     nodeStack.push(node->lchild);
   }
  }
}

// DFS (recursive)
void depthFirstSearchRecursive(Tree root)
{
  if (root) {
    cout << root->data;

    if (root->lchild) {
     depthFirstSearchRecursive(root->lchild);
    }

    if (root->rchild) {
     depthFirstSearchRecursive(root->rchild);
    }
  }
}

Test

Define a class TreeBuilder to build a tree and destroy it.

class TreeBuilder
{
public:
  TreeBuilder( Element data[] ) : index_( 0 ) {
   constructTree( root_, data );  
  }

  ~TreeBuilder() {
   destructTree( root_ );
  }

  Tree tree() const { return root_ ;}
 
private:
  void constructTree(Tree &root, Element data[])
  {
    Element e = data[index_++];
    if (e == '#') {
     root = NULL;
    }
    else {
     root = new Node (e);
     constructTree(root->lchild, data);
     constructTree(root->rchild, data);
    }
  }

  void destructTree(Tree root) {
    if( root != NULL ) {
      delete root;
      root = NULL;
    }
  }

private:
  int index_;
  Tree root_;
};

Test BFS and DFS.

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

...

int main(int argc, char** argv) 
{
  Element data[15] = { 'A', 'B', 'D', '#', '#', 'E', '#', '#', 'C', 'F','#', '#', 'G', '#', '#' };	
  
  TreeBuilder builder( data );
  
  auto tree = builder.tree();

  cout << endl;

  cout << "BFS result：";
  breadthFirstSearch(tree);

  cout << endl;
  
  cout << "DFS (iterative) result：";
  depthFirstSearch(tree);

  cout << endl;

  cout << "DFS (recursive) result：";
  depthFirstSearchRecursive(tree);

  cout << endl;
  
  return 0;
}

Build and run it.

g++ main.cpp --std=c++14
./a.out
Construct A
Construct B
Construct D
Construct E
Construct C
Construct F
Construct G

BFS result：ABCDEFG
DFS (iterative) result：ABDECFG
DFS (recursive) result：ABDECFG
Destruct A
Destruct B
Destruct D
Destruct E
Destruct C
Destruct F
Destruct G

Use valgrind to check if there is any memory leak.

valgrind --leak-check=yes ./a.out
...
==30852== HEAP SUMMARY:
==30852==     in use at exit: 0 bytes in 0 blocks
==30852==   total heap usage: 12 allocs, 12 frees, 74,024 bytes allocated
==30852== 
==30852== All heap blocks were freed -- no leaks are possible
==30852== 
==30852== For counts of detected and suppressed errors, rerun with: -v
==30852== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Use gdb to find where to throw a C++ exception

Here is a simple example about how to find where to throw a C++ exception.

#include <iostream>
#include <stdexcept>

using namespace std;

void computeIntegral() {
  throw std::runtime_error( "Input data is not valid" );  
}

int main(int argc, char** argv) {
  try {
    computeIntegral();
  } catch( std::runtime_error &e ) {
    cout << "Caught an exception: " << e.what() << endl;
  }
  
  return 0;
}

Build and run it.

g++ testException.cpp --std=c++14
./a.out
Caught an exception: Input data is not valid

Now use gdb to debug it.

gdb --args ./a.out
(gdb) catch throw
Catchpoint 1 (throw)
(gdb) r
...
(gdb) bt
#0  __cxxabiv1::__cxa_throw (obj=0x614ca0, 
    tinfo=0x6020c0 <_ZTISt13runtime_error@@GLIBCXX_3.4>, 
    dest=0x400a40 <_ZNSt13runtime_errorD1Ev@plt>)
    at ../../../../gcc-8.3.0/libstdc++-v3/libsupc++/eh_throw.cc:80
#1  0x0000000000400bd5 in computeIntegral() ()
#2  0x0000000000400c00 in main ()

Achieve polymorphism using pointer or reference

It is very common to use pointer to achieve polymorphism. For example,

#include <iostream>
 
using namespace std;

// Base class
class A {
public:
  virtual void output() = 0;
};

// Derived class B
class B : public A {
public:
  void output() override {
    cout << "From derived class B" << endl;
  }
};

// Derived class C
class C : public A {
public:
  void output() override {
    cout << "From derived class C" << endl;
  }
};

// Client code
int main(int argc, char** argv) 
{
  A *b = new B;
  A *c = new C;
  
  int flag = 0;
  cin >> flag;
  
  auto t = flag == 0 ? b : c;
  t->output();
  
  delete b;
  delete c;
  
  return 0;
}

Build the above code, and test it.

g++ -o testrefer main.cpp  --std=c++14

./testrefer
0
From the derived class B

./testrefer
1
From the derived class C

What if there are two objects of derived classes instead of two pointers of them in the client code? The answer is using reference.

// Client code
int main(int argc, char** argv) 
{
  B b;
  C c;
 
  int flag = 0;
  cin >> flag;
  
  auto& t = flag == 0 ? static_cast< A& >( b ) : static_cast< A& >( c );
  
  t.output();
  
  return 0;
}

Build and test it, and get the same output.

g++ -o testrefer main.cpp  --std=c++14

./testrefer
0
From the derived class B

./testrefer
1
From the derived class C