11.07.2018

What are some fun C++ tricks

This one applies to all languages so far:

a=a+b-(b=a);

A REALLY fast way of swaping a and b.

#include <iostream>
#include <string>

using namespace std;

int main (int argc, char*argv) {
float a; cout << «A:»; cin >> a;
float b; cout << «B:» ; cin >> b;

cout << «———————» << endl;
cout << «A=» << a << «, B=» << b << endl;
a=a+b-(b=a);
cout << «A=» << a << «, B=» << b << endl;
exit(0);
}

void Send(int * to, const int* from, const int count)

{

int n = (count+7) / 8;

switch(count%8)

{

case 0:

do

{

*to++ = *from++;

case 7:

*to++ = *from++;

case 6:

*to++ = *from++;

case 5:

*to++ = *from++;

case 4:

*to++ = *from++;

case 3:

*to++ = *from++;

case 2:

*to++ = *from++;

case 1:

*to++ = *from++;

} while (—n>0);

}

Preprocessor Tricks

The arraysize macro used in Chrome’s source:

template <typename T, size_t N>

char (&ArraySizeHelper(T (&array)[N]))[N];

#define arraysize(array) (sizeof(ArraySizeHelper(array)))

This is better than the ordinary

sizeof(array)/sizeof(array[0])

because it raises compilation errors when the passed in array is just a pointer, or a null pointer whereas the simpler macro silently returns a useless value. For a detailed example, see PVS-Studio vs Chromium.

Predefined Macros:

#define expect(expr) if(!expr) cerr << «Assertion « << #expr \

» failed at « << __FILE__ << «:» << __LINE__ << endl;

#define stringify(x) #x

#define tostring(x) stringify(x)

#define MAGIC_CONSTANT 314159

cout << «Value of MAGIC_CONSTANT=» << tostring(MAGIC_CONSTANT);

The

tostring

macro is a common trick used to expand macro values inside other macros. The Linux kernel uses a lot of macro tricks.

Using iterators for quickly dumping the contents of a container:

#define dbg(v) copy(v.begin(), v.end(), ostream_iterator<typeof(*v.begin())>(cout, » «))

Sadly, this doesn’t work for

pair

types so maps are out of scope.

Template Voodoo

Recursion:You can specialize your class templates for certain cases, so you can write down the base-case of a recursion and then define the generic template as a recursive combination of base cases.
For example, the following code calculates the values of the Choose function at compile time:

template<unsigned n, unsigned r>

struct Choose {

enum {value = (n * Choose<n—1, r—1>::value) / r};

};

template<unsigned n>

struct Choose<n, 0> {

enum {value = 1};

};

int main() {

// Prints 56

cout << Choose<8, 3>::value;

// Compile time values can be used as array sizes

int x[Choose<25, 3>::value];

}

More interesting examples at C++ Programming/Templates/Template Meta-Programming

Mostly Painless Memory Management and RAII

With certain restrictions, you can create templates for «smart» pointers that automatically deallocate resources when they go out of scope or reference count goes to 0. This is basically done by overloading

operator *

and

operator =

. Based on your use case, you can transfer ownership when the

operator =

is used, or update reference counts.
See Smart Pointer Guidelines — The Chromium Projects and http://code.google.com/searchfra…

Argument-dependent name lookup aka Koenig lookup

When a function call cannot be matched to a name in the current namespace, other namespaces can be searched for a matching signature. This is why

std::cout << "Hi";

works even though

operator <<

is defined in the

std

namespace.
See Argument-dependent name lookup

auto keyword
In C++ you can use auto to iterate over map,vector,set,..etc which specifies that the type of the variable that is being declared will be automatically deduced from its initializer or for functions it will the return type or it will be deduced from its return statements
So instead of :

vector<int> vs;

vs.push_back(4),vs.push_back(7),vs.push_back(9),vs.push_back(10);

for (vector<int>::iterator it = vs.begin(); it != vs.end(); ++it)

cout << *it << ‘ ‘;cout<<‘\n’;

just use :

vector<int> vs;

vs.push_back(4),vs.push_back(7),vs.push_back(9),vs.push_back(10);

for (auto it: vs)

cout << it << ‘ ‘;cout<<endl;

//you can also change the values using

vector<int> vs;

vs.push_back(4),vs.push_back(7),vs.push_back(9),vs.push_back(10);

for (auto& it: vs) it*=3;

for (auto it: vs)

cout << it << ‘ ‘;cout<<endl;

Declaring variable

template<class A, class B>

auto mult(A x, B y) -> decltype(x * y){

return x * y;

}

int main(){

auto a = 3 * 2; //the return type is the type of operator (x*y)

cout<<a<<endl;

return 0;

}

The Power of Strings

int n,m;

cin >> n >> m;

int matrix[n+1][m+1];

//This loop

for(int i = 1; i <= n; i++) {

for(int j = 1; j <= m; j++)

cout << matrix[i][j] << » «;

cout << «\n»;

}

// is equivalent to this

for(int i = 1; i <= n; i++)

for(int j = 1; j <= m; j++)

cout << matrix[i][j] << » \n»[j == m];

because

" \n"

is a

char*

,

" \n"[0]

is

' '

and

" \n"[1]

is

'\n'

.

Some Hidden function
__gcd(x, y)
you don’t need to code gcd function.

cout<<__gcd(54,48)<<endl; //return 6

__builtin_ffs(x)
This function returns 1 + least significant 1-bit of x. If x == 0, returns 0. Here x is int, this function with suffix ‘l’ gets a long argument and with suffix ‘ll’ gets a long long argument.
e.g: __builtin_ffs(10) = 2 because 10 is ‘…10 1 0′ in base 2 and first 1-bit from right is at index 1 (0-based) and function returns 1 + index.three)

Pairing tricks

pair<int, int> p;

//This

p = make_pair(1, 2);

//equivalent to this

p = {1, 2};

//So

pair<int, pair<char, long long> > p;

//now easier

p = {1, {‘a’, 2ll}};

Super include
Simply use

#include <bits/stdc++.h>

This library includes many of libraries we do need like algorithm, iostream, vector and many more. Believe me you don’t need to include anything else 😀 !!

Smart Pointers

Using smart pointers, we can make pointers to work in way that we don’t need to explicitly call delete. Smart pointer is a wrapper class over a pointer with operator like * and -> overloaded. The objects of smart pointer class look like pointer, but can do many things that a normal pointer can’t like automatic destruction (yes, we don’t have to explicitly use delete), reference counting and more.
The idea is to make a class with a pointer, destructor and overloaded operators like * and ->. Since destructor is automatically called when an object goes out of scope, the dynamically alloicated memory would automatically deleted (or reference count can be decremented).

You can put URIs in your C++ code and the compiler will not throw any error.

#include <iostream>

int main() {

using namespace std;

http://www.google.com

int x = 5;

cout << x;

}

Explanation: Any identifier followed by a : becomes a (goto) label in C++. Anything followed by // becomes a comment so in the code above, http is a label and //google.com/is a comment. The compiler might throw a warning however, since the label is unutilized.

Don’t Confuse Assign (=) with Test-for-Equality (==).

This one is elementary, although it might have baffled Sherlock Holmes. The following looks innocent and would compile and run just fine if C++ were more like BASIC:

if (a = b)
cout << «a is equal to b.»;

Because this looks so innocent, it creates logic errors requiring hours to track down within a large program unless you’re on the lookout for it. (So when a program requires debugging, this is the first thing I look for.) In C and C++, the following is not a test for equality:

a = b

What this does, of course, is assign the value of b to a and then evaluate to the value assigned.
The problem is that a = b does not generally evaluate to a reasonable true/false condition—with one major exception I’ll mention later. But in C and C++, any numeric value can be used as a condition for “if” or “while.
Assume that a and b are set to 0. The effect of the previously-shown if statement is to place the value of b into a; then the expression a = b evaluates to 0. The value 0 equates to false. Consequently, aand b are equal, but exactly the wrong thing gets printed:

if (a = b) // THIS ENSURES a AND b ARE EQUAL…
cout << «a and b are equal.»;
else
cout << «a and b are not equal.»; // BUT THIS GETS PRINTED!

The solution, of course, is to use test-for-equality when that’s what you want. Note the use of double equal signs (==). This is correct inside a condition.

// CORRECT VERSION:
if (a == b)
cout << «a and b are equal.»;

The most amazing trick i found was a status of someone’s topcoder profile:
Code:
#include <cstdio>
double m[]= {7709179928849219.0, 771};
int main()
{
m[1]—?m[0]*=2,main():printf((char*)m);
}
You will be seriously amazed by the ouput…here it is:
C++Sucks

I tried to analyse the code and came up with a reason but not an exact explanation..so i tried to ask it on stackoverflow..you can go through the explanation here:
Concept behind this 4 lines tricky C++ code
Read it and you will learn something you wouldn’t have even thought of… 😉

Set Bits using a macro compacted lookup table: (Source Bit Twiddling Hacks)

static const unsigned char BitsSetTable256[256] =

{

# define B2(n) n, n+1, n+1, n+2 

# define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2) 

# define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2) 

 B6(0), B6(1), B6(1), B6(2)

};

unsigned int v; // count the number of bits set in 32-bit value v 

unsigned int c; // c is the total bits set in v 

// Option 1: 

c = BitsSetTable256[v & 0xff] +

BitsSetTable256[(v >> 8) & 0xff] +

BitsSetTable256[(v >> 16) & 0xff] +

BitsSetTable256[v >> 24];

// Option 2: 

unsigned char * p = (unsigned char *) &v;

c = BitsSetTable256[p[0]] +

BitsSetTable256[p[1]] +

BitsSetTable256[p[2]] +

BitsSetTable256[p[3]];

// To initially generate the table algorithmically: 

BitsSetTable256[0] = 0;

for (int i = 0; i < 256; i++)

{

BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];

}

Inverse square root approximation: (Source Fast inverse square root)

float Q_rsqrt( float number )

{

long i;

float x2, y;

const float threehalfs = 1.5F;

 x2 = number * 0.5F;

 y = number;

 i = * ( long * ) &y; // evil floating point bit level hacking

 i = 0x5f3759df - ( i >> 1 ); // what the fuck?

 y = * ( float * ) &i;

 y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration

// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed

return y;

}

Iteration:

#define FOR(i,n) for(int (i)=0;(i)<(n);(i)++)

#define FORR(i,a,b) for(int (i)=(a);(i)<(b);(i)++)

//reverse

#define REV(i,n) for(int (i)=(n)-1;(i)>=0;(i)--)

Handy way to use it like this.

typedef long long int int64;

typedef unsigned long long int uint64;

FastIO for +ve integers.

inline void frint(int *a){

register char c=0;while (c<33) c=getchar_unlocked();*a=0;

while (c>33){*a=*a*10+c-'0';c=getchar_unlocked();}

}

Try This….

#include <iostream>
using namespace std;
int main()
{
int a,b,c;
int count = 1;
for (b=c=10;a=»- FIGURE?, UMKC,XYZHello Folks,\
TFy!QJu ROo TNn(ROo)SLq SLq ULo+\
UHs UJq TNn*RPn/QPbEWS_JSWQAIJO^\
NBELPeHBFHT}TnALVlBLOFAkHFOuFETp\
HCStHAUFAgcEAelclcn^r^r\\tZvYxXy\
T|S~Pn SPm SOn TNn ULo0ULo#ULo-W\
Hq!WFs XDt!» [b+++21]; )
for(; a— > 64 ; )
putchar ( ++c==’Z’ ? c = c/ 9:33^b&1);
return 0;
}

I think one of the coolest of all time, is defining an abstract base class in C++, and inheriting from it in python, and passing it back to C++ to call.
It actually works

struct Interface{

int foo()const=0;

virtual ~Interface(){}

};

void call(Interface const& f){

 std::cout<<f.foo()<<std::endl;

}

struct InterfaceWrap final: Interface, boost::python::wrapper<Interface>

{

int foo() const final

{

return this->get_override("foo")();

}

};

BOOST_PYTHON_MODULE(interface){

using namespace boost::python;

 class_<Interface ,boost ::noncopyable,boost::shared_ptr<Interface>>("_InterfaceCpp",no_init)

.def("foo",&Interface::foo)

;

 class_<InterfaceWrap ,bases<Interface>,boost::shared_ptr<InterfaceWrap>>("Interface",init<>())

;

 def("call",&call);

}

and then

import interface as i # C++ code

class impl(i.Interface):#inherit from C++ class

def __init__(self):

 i.Interface.__init__(self)

def foo(self):

return 100

i.call(impl())#call C++ function with Python derived class

This does exactly what you think it should do.

void qsort ( void * base, size_t num, size_t size, int ( * compar ) ( const void *, const void * ) )

base Pointer to the first element of the array to be sorted.

num Number of elements in the array pointed by base. size_t is an unsigned integral type.

size Size in bytes of each element in the array. size_t is an unsigned integral type.

compar Function that compares two elements. This function is called repeatedly by qsorttocomparetwoelements.It shall follow the following prototype:

int compar ( const void * elem1, const void * elem2 );

Taking a pointer to two pointers as arguments (both type-casted to const void*). The function should compare the data pointed by both: if they match in ranking, the function shall return zero; if elem1 goes before elem2, it shall return a negative value; and if it goes after, a positive value.

Eg :

int values[] = { 40, 10, 100, 90, 20, 25 };

int compare (const void * a, const void * b) { return ( *(int*)a — *(int*)b ); }

int main () {
int n;
qsort (values, 6, sizeof(int), compare);
for (n=0; n<6; n++) printf («%d «,values[n]); return 0; }

Partial template specialization

C++11

has this cool function

get<J>

which can be used to access the

first

and

second

member of a

pair

, with a different syntax:

std::pair < std::string, double > pr ( «pi», 3.14 );

std::cout << std::get < 0 > ( pr ); // outputs «pi»

std::cout << std::get < 1 > ( pr ); // outputs 3.14

Note that this is a function and not a function object or a member function.

I do not find it trivial to write a function

with three template types
template < size_t J, class T1, class T2 >

which can get
std::pair < T1, T2 >

as an argument

and outputs
pr.first

if the template value J is 0

and outputs
pr.second

if the template value J is 1.

In particular consider that in

C++

one cannot overload a function based on its return type. So what should the return type of this function be declared as?

T1

or

T2

?

template < size_t J, class T1, class T2>

??? get ( std::pair < T1, T2 > & );

The interesting thing is that one could already write this function in

C++98

using Partial template specialization, which is a really cool trick. The problem is that function templates cannot be partially specialized, but this is easy to solve:

namespace

{

/*!

* helper template to do the work with partial specialization

*/

template < size_t J, class T1, class T2 >

struct Get;

template < class T1, class T2>

struct Get < 0, T1, T2 >

{

typedef typename std::pair < T1, T2 >::first_type result_type;

static result_type & elm ( std::pair < T1, T2 > & pr ) { return pr.first; }

static const result_type & elm ( const std::pair < T1, T2 > & pr ) { return pr.first; }

};

template < class T1, class T2>

struct Get < 1, T1, T2 >

{

typedef typename std::pair < T1, T2 >::second_type result_type;

static result_type & elm ( std::pair < T1, T2 > & pr ) { return pr.second; }

static const result_type & elm ( const std::pair < T1, T2 > & pr ) { return pr.second; }

};

}

template < size_t J, class T1, class T2 >

typename Get< J, T1, T2 >::result_type & get ( std::pair< T1, T2 > & pr )

{

return Get < J, T1, T2 >::elm( pr );

}

template < size_t J, class T1, class T2 >

const typename Get< J, T1, T2 >::result_type & get ( const std::pair< T1, T2 > & pr )

{

return Get < J, T1, T2 >::elm( pr );

}

Define operator<< for STL structures to make it easy to add debug outputs to your code. (This is better than special printing functions because it nests automatically! Printing a map< vector<int>, int> works without any additional effort if you can print any map and any vector.)

Additionally, define a macro that makes nicer debug outputs and makes it easy to turn them off using the standard mechanism (same one that is used for assert). Here’s a short example how to do all of this in C++11:

#include <iostream>
#include <string>
#include <map>
#ifdef NDEBUG
#define DEBUG(var)
#else
#define DEBUG(var) { std::cout << #var << ": " << (var) << std::endl; }
#endif
template<typename T1, typename T2>
std::ostream& operator<< (std::ostream& out, const std::map<T1,T2> &M) {
out << "{ ";
for (auto item:M) out << item.first << "->" << item.second << ", ";
out << "}";
return out;
}
int main() {
std::map<std::string,int> age = { {"Joe",47}, {"Bob",22}, {"Laura",19} };
DEBUG(age);
}

This is a very amazing piece of code:

main(a){printf(a,34,a=»main(a){printf(a,34,a=%c%s%c,34);}»,34);}

It is the shortest C++ code which when executed prints itself. It was discovered by Vlad Taeerov and Rashit Fakhreyev and is only 64 characters in length(Making it the shortest).

To Convert list<T> to vector<T>:

std::vector<T> v(l.begin(), l.end());

Variadic Templates :

They can be useful in places. You can pass any number of parameters .
Example :

#include <iostream>
#include <bitset>
#include <string>
using namespace std;
void print() {
cout<<«Nothing to print :)» ;
}
template<typename T,typename… args>
void print(T x,args… y) {
cout<<x<<endl;
print(y…);
}
int main() {
print(10,14.56,«Quora»,bitset<20>(28));
return 0;
}

Code on ideon : http://ideone.com/b8TNHD

Output :

10
14.56
Quora
00000000000000011100
Nothing to print 🙂

Range based for loops can be used with some STL containers :
eg.

#include <iostream>
#include <list>
#include <vector>
using namespace std;
int main() {
list<int> x;
x.push_back(10);
x.push_back(20);
for(auto i : x)
cout<<i;
return 0;
}

11.07.2018

Old but still C++ Tricks

I see lots of programmers write code like this one:


<span class="pln">pair</span><span class="pun">&lt;</span><span class="kwd">int</span><span class="pun">,</span> <span class="kwd">int</span><span class="pun">&gt;</span><span class="pln"> p</span><span class="pun">;</span><span class="pln">

vector</span><span class="str">&lt;int&gt;</span><span class="pln"> v</span><span class="pun">;</span>

<span class="com">// ...</span><span class="pln">

p </span><span class="pun">=</span><span class="pln"> make_pair</span><span class="pun">(</span><span class="lit">3</span><span class="pun">,</span> <span class="lit">4</span><span class="pun">);</span><span class="pln">

v</span><span class="pun">.</span><span class="pln">push_back</span><span class="pun">(</span><span class="lit">4</span><span class="pun">);</span><span class="pln"> v</span><span class="pun">.</span><span class="pln">push_back</span><span class="pun">(</span><span class="lit">5</span><span class="pun">);</span>

while you can just do this:


<span class="pln">pair</span><span class="pun">&lt;</span><span class="kwd">int</span><span class="pun">,</span> <span class="kwd">int</span><span class="pun">&gt;</span><span class="pln"> p</span><span class="pun">;</span><span class="pln">

vector</span><span class="str">&lt;int&gt;</span><span class="pln"> v</span><span class="pun">;</span>

<span class="com">// ...</span><span class="pln">

p </span><span class="pun">=</span> <span class="pun">{</span><span class="lit">3</span><span class="pun">,</span> <span class="lit">4</span><span class="pun">};</span><span class="pln">

v </span><span class="pun">=</span> <span class="pun">{</span><span class="lit">4</span><span class="pun">,</span> <span class="lit">5</span><span class="pun">};</span>

1. Assign value by a pair of {} to a container

I see lots of programmers write code like this one:


<span class="pln">pair</span><span class="pun">&lt;</span><span class="kwd">int</span><span class="pun">,</span> <span class="kwd">int</span><span class="pun">&gt;</span><span class="pln"> p</span><span class="pun">;</span>

<span class="com">// ...</span><span class="pln">

p </span><span class="pun">=</span><span class="pln"> make_pair</span><span class="pun">(</span><span class="lit">3</span><span class="pun">,</span> <span class="lit">4</span><span class="pun">);</span>

while you can just do this:


<span class="pln">pair</span><span class="pun">&lt;</span><span class="kwd">int</span><span class="pun">,</span> <span class="kwd">int</span><span class="pun">&gt;</span><span class="pln"> p</span><span class="pun">;</span>

<span class="com">// ...</span><span class="pln">

p </span><span class="pun">=</span> <span class="pun">{</span><span class="lit">3</span><span class="pun">,</span> <span class="lit">4</span><span class="pun">};</span>

even a more complex

pair


<span class="pln">pair</span><span class="pun">&lt;</span><span class="kwd">int</span><span class="pun">,</span><span class="pln"> pair</span><span class="pun">&lt;</span><span class="kwd">char</span><span class="pun">,</span> <span class="kwd">long</span> <span class="kwd">long</span><span class="pun">&gt;</span> <span class="pun">&gt;</span><span class="pln"> p</span><span class="pun">;</span>

<span class="com">// ...</span><span class="pln">

p </span><span class="pun">=</span> <span class="pun">{</span><span class="lit">3</span><span class="pun">,</span> <span class="pun">{</span><span class="str">'a'</span><span class="pun">,</span> <span class="lit">8ll</span><span class="pun">}};</span>

What about

vector

deque

set

and other containers?


<span class="pln">vector</span><span class="str">&lt;int&gt;</span><span class="pln"> v</span><span class="pun">;</span><span class="pln">

v </span><span class="pun">=</span> <span class="pun">{</span><span class="lit">1</span><span class="pun">,</span> <span class="lit">2</span><span class="pun">,</span> <span class="lit">5</span><span class="pun">,</span> <span class="lit">2</span><span class="pun">};</span>

<span class="kwd">for</span> <span class="pun">(</span><span class="kwd">auto</span><span class="pln"> i</span><span class="pun">:</span><span class="pln"> v</span><span class="pun">)</span><span class="pln">

    cout </span><span class="pun">&lt;&lt;</span><span class="pln"> i </span><span class="pun">&lt;&lt;</span> <span class="str">' '</span><span class="pun">;</span><span class="pln">

cout </span><span class="pun">&lt;&lt;</span> <span class="str">'\n'</span><span class="pun">;</span>

<span class="com">// prints "1 2 5 2"</span><span class="pln">





deque</span><span class="pun">&lt;</span><span class="pln">vector</span><span class="pun">&lt;</span><span class="pln">pair</span><span class="pun">&lt;</span><span class="kwd">int</span><span class="pun">,</span> <span class="kwd">int</span><span class="pun">&gt;&gt;&gt;</span><span class="pln"> d</span><span class="pun">;</span><span class="pln">

d </span><span class="pun">=</span> <span class="pun">{{{</span><span class="lit">3</span><span class="pun">,</span> <span class="lit">4</span><span class="pun">},</span> <span class="pun">{</span><span class="lit">5</span><span class="pun">,</span> <span class="lit">6</span><span class="pun">}},</span> <span class="pun">{{</span><span class="lit">1</span><span class="pun">,</span> <span class="lit">2</span><span class="pun">},</span> <span class="pun">{</span><span class="lit">3</span><span class="pun">,</span> <span class="lit">4</span><span class="pun">}}};</span>

<span class="kwd">for</span> <span class="pun">(</span><span class="kwd">auto</span><span class="pln"> i</span><span class="pun">:</span><span class="pln"> d</span><span class="pun">)</span> <span class="pun">{</span>

    <span class="kwd">for</span> <span class="pun">(</span><span class="kwd">auto</span><span class="pln"> j</span><span class="pun">:</span><span class="pln"> i</span><span class="pun">)</span><span class="pln">

        cout </span><span class="pun">&lt;&lt;</span><span class="pln"> j</span><span class="pun">.</span><span class="pln">first </span><span class="pun">&lt;&lt;</span> <span class="str">' '</span> <span class="pun">&lt;&lt;</span><span class="pln"> j</span><span class="pun">.</span><span class="pln">second </span><span class="pun">&lt;&lt;</span> <span class="str">'\n'</span><span class="pun">;</span><span class="pln">

    cout </span><span class="pun">&lt;&lt;</span> <span class="str">"-\n"</span><span class="pun">;</span>

<span class="pun">}</span>

<span class="com">// prints "3 4</span>

<span class="com">//         5 6</span>

<span class="com">//         -</span>

<span class="com">//       1 2</span>

<span class="com">//       3 4</span>

<span class="com">//       -"</span>





<span class="kwd">set</span><span class="str">&lt;int&gt;</span><span class="pln"> s</span><span class="pun">;</span><span class="pln">

s </span><span class="pun">=</span> <span class="pun">{</span><span class="lit">4</span><span class="pun">,</span> <span class="lit">6</span><span class="pun">,</span> <span class="lit">2</span><span class="pun">,</span> <span class="lit">7</span><span class="pun">,</span> <span class="lit">4</span><span class="pun">};</span>

<span class="kwd">for</span> <span class="pun">(</span><span class="kwd">auto</span><span class="pln"> i</span><span class="pun">:</span><span class="pln"> s</span><span class="pun">)</span><span class="pln">

    cout </span><span class="pun">&lt;&lt;</span><span class="pln"> i </span><span class="pun">&lt;&lt;</span> <span class="str">' '</span><span class="pun">;</span><span class="pln">

cout </span><span class="pun">&lt;&lt;</span> <span class="str">'\n'</span><span class="pun">;</span>

<span class="com">// prints "2 4 6 7"</span><span class="pln">





list</span><span class="str">&lt;int&gt;</span><span class="pln"> l</span><span class="pun">;</span><span class="pln">

l </span><span class="pun">=</span> <span class="pun">{</span><span class="lit">5</span><span class="pun">,</span> <span class="lit">6</span><span class="pun">,</span> <span class="lit">9</span><span class="pun">,</span> <span class="lit">1</span><span class="pun">};</span>

<span class="kwd">for</span> <span class="pun">(</span><span class="kwd">auto</span><span class="pln"> i</span><span class="pun">:</span><span class="pln"> l</span><span class="pun">)</span><span class="pln">

    cout </span><span class="pun">&lt;&lt;</span><span class="pln"> i </span><span class="pun">&lt;&lt;</span> <span class="str">' '</span><span class="pun">;</span><span class="pln">

cout </span><span class="pun">&lt;&lt;</span> <span class="str">'\n'</span><span class="pun">;</span>

<span class="com">// prints "5 6 9 1"</span><span class="pln">





array</span><span class="pun">&lt;</span><span class="kwd">int</span><span class="pun">,</span> <span class="lit">4</span><span class="pun">&gt;</span><span class="pln"> a</span><span class="pun">;</span><span class="pln">

a </span><span class="pun">=</span> <span class="pun">{</span><span class="lit">5</span><span class="pun">,</span> <span class="lit">8</span><span class="pun">,</span> <span class="lit">9</span><span class="pun">,</span> <span class="lit">2</span><span class="pun">};</span>

<span class="kwd">for</span> <span class="pun">(</span><span class="kwd">auto</span><span class="pln"> i</span><span class="pun">:</span><span class="pln"> a</span><span class="pun">)</span><span class="pln">

    cout </span><span class="pun">&lt;&lt;</span><span class="pln"> i </span><span class="pun">&lt;&lt;</span> <span class="str">' '</span><span class="pun">;</span><span class="pln">

cout </span><span class="pun">&lt;&lt;</span> <span class="str">'\n'</span><span class="pun">;</span>

<span class="com">// prints "5 8 9 2"</span><span class="pln">





tuple</span><span class="pun">&lt;</span><span class="kwd">int</span><span class="pun">,</span> <span class="kwd">int</span><span class="pun">,</span> <span class="kwd">char</span><span class="pun">&gt;</span><span class="pln"> t</span><span class="pun">;</span><span class="pln">

t </span><span class="pun">=</span> <span class="pun">{</span><span class="lit">3</span><span class="pun">,</span> <span class="lit">4</span><span class="pun">,</span> <span class="str">'f'</span><span class="pun">};</span><span class="pln">

cout </span><span class="pun">&lt;&lt;</span> <span class="kwd">get</span><span class="pun">&lt;</span><span class="lit">2</span><span class="pun">&gt;(</span><span class="pln">t</span><span class="pun">)</span> <span class="pun">&lt;&lt;</span> <span class="str">'\n'</span><span class="pun">;</span>

Note that it doesn’t work for

stack

and

queue

2. Name of argument in macros

You can use ‘#’ sign to get exact name of an argument passed to a macro:


<span class="com">#define</span><span class="pln"> what_is</span><span class="pun">(</span><span class="pln">x</span><span class="pun">)</span><span class="pln"> cerr </span><span class="pun">&lt;&lt;</span> <span class="com">#x &lt;&lt; " is " &lt;&lt; x &lt;&lt; endl;</span>

<span class="com">// ...</span>

<span class="kwd">int</span><span class="pln"> a_variable </span><span class="pun">=</span> <span class="lit">376</span><span class="pun">;</span><span class="pln">

what_is</span><span class="pun">(</span><span class="pln">a_variable</span><span class="pun">);</span>

<span class="com">// prints "a_variable is 376"</span><span class="pln">

what_is</span><span class="pun">(</span><span class="pln">a_variable </span><span class="pun">*</span> <span class="lit">2</span> <span class="pun">+</span> <span class="lit">1</span><span class="pun">)</span>

<span class="com">// prints "a_variable * 2 + 1 is 753"</span>

3. Get rid of those includes!

Simply use


<span class="com">#include</span> <span class="pun">&lt;</span><span class="pln">bits</span><span class="pun">/</span><span class="pln">stdc</span><span class="pun">++.</span><span class="pln">h</span><span class="pun">&gt;</span>

This library includes many of libraries we do need in contest like

algorithm

iostream

vector

and many more. Believe me you don’t need to include anything else!

4. Hidden function (not really hidden but not used often)

one)


<span class="pln">__gcd</span><span class="pun">(</span><span class="pln">value1</span><span class="pun">,</span><span class="pln"> value2</span><span class="pun">)</span>

You don’t need to code Euclidean Algorithm for a gcd function, from now on we can use. This function returns gcd of two numbers.

e.g. __gcd(18, 27) = 9.

two)


<span class="pln">__builtin_ffs</span><span class="pun">(</span><span class="pln">x</span><span class="pun">)</span>

This function returns 1 + least significant 1-bit of x. If x == 0, returns 0. Here x is

int

, this function with suffix ‘l’ gets a

long

argument and with suffix ‘ll’ gets a

long long

argument.

e.g. __builtin_ffs(10) = 2 because 10 is ‘…10 1 0′ in base 2 and first 1-bit from right is at index 1 (0-based) and function returns 1 + index.

three)


<span class="pln">__builtin_clz</span><span class="pun">(</span><span class="pln">x</span><span class="pun">)</span>

This function returns number of leading 0-bits of x which starts from most significant bit position. x is

unsigned int

and like previous function this function with suffix ‘l gets a

unsigned long

argument and with suffix ‘ll’ gets a

unsigned long long

argument. If x == 0, returns an undefined value.

e.g. __builtin_clz(16) = 27 because 16 is ‘ … 10000′. Number of bits in a

unsigned int

is 32. so function returns 32 — 5 = 27.

four)


<span class="pln">__builtin_ctz</span><span class="pun">(</span><span class="pln">x</span><span class="pun">)</span>

This function returns number of trailing 0-bits of x which starts from least significant bit position. x is

unsigned int

and like previous function this function with suffix ‘l’ gets a

unsigned long

argument and with suffix ‘ll’ gets a

unsigned long long

argument. If x == 0, returns an undefined value.

e.g. __builtin_ctz(16) = 4 because 16 is ‘…1 0000 ‘. Number of trailing 0-bits is 4.

five)


<span class="pln">__builtin_popcount</span><span class="pun">(</span><span class="pln">x</span><span class="pun">)</span>

This function returns number of 1-bits of x. x is

unsigned int

and like previous function this function with suffix ‘l’ gets a

unsigned long

argument and with suffix ‘ll’ gets a

unsigned long long

argument. If x == 0, returns an undefined value.

e.g. __builtin_popcount(14) = 3 because 14 is ‘… 111 0′ and has three 1-bits.

Note: There are other

__builtin

functions too, but they are not as useful as these ones.

Note: Other functions are not unknown to bring them here but if you are interested to work with them, I suggest this website.

5. Variadic Functions and Macros

We can have a variadic function. I want to write a sum function which gets a number of ints, and returns sum of them. Look at the code below:


<span class="kwd">int</span><span class="pln"> sum</span><span class="pun">()</span> <span class="pun">{</span> <span class="kwd">return</span> <span class="lit">0</span><span class="pun">;</span> <span class="pun">}</span>



<span class="kwd">template</span><span class="pun">&lt;</span><span class="kwd">typename</span><span class="pun">...</span> <span class="typ">Args</span><span class="pun">&gt;</span>

<span class="kwd">int</span><span class="pln"> sum</span><span class="pun">(</span><span class="kwd">int</span><span class="pln"> a</span><span class="pun">,</span> <span class="typ">Args</span><span class="pun">...</span><span class="pln"> args</span><span class="pun">)</span> <span class="pun">{</span> <span class="kwd">return</span><span class="pln"> a </span><span class="pun">+</span><span class="pln"> sum</span><span class="pun">(</span><span class="pln">args</span><span class="pun">...);</span> <span class="pun">}</span>



<span class="kwd">int</span><span class="pln"> main</span><span class="pun">()</span> <span class="pun">{</span><span class="pln"> cout </span><span class="pun">&lt;&lt;</span><span class="pln"> sum</span><span class="pun">(</span><span class="lit">5</span><span class="pun">,</span> <span class="lit">7</span><span class="pun">,</span> <span class="lit">2</span><span class="pun">,</span> <span class="lit">2</span><span class="pun">)</span> <span class="pun">+</span><span class="pln"> sum</span><span class="pun">(</span><span class="lit">3</span><span class="pun">,</span> <span class="lit">4</span><span class="pun">);</span> <span class="com">/* prints "23" */</span> <span class="pun">}</span>

In the code above I used a template. sum(5, 7, 2, 2) becomes 5 + sum(7, 2, 2) then sum(7, 2, 2), itself, becomes 7 + sum(2, 2) and so on… I also declare another sum function which gets 0 arguments and returns 0.

I can even define a any-type sum function:


<span class="kwd">int</span><span class="pln"> sum</span><span class="pun">()</span> <span class="pun">{</span> <span class="kwd">return</span> <span class="lit">0</span><span class="pun">;</span> <span class="pun">}</span>



<span class="kwd">template</span><span class="pun">&lt;</span><span class="kwd">typename</span><span class="pln"> T</span><span class="pun">,</span> <span class="kwd">typename</span><span class="pun">...</span> <span class="typ">Args</span><span class="pun">&gt;</span><span class="pln">

T sum</span><span class="pun">(</span><span class="pln">T a</span><span class="pun">,</span> <span class="typ">Args</span><span class="pun">...</span><span class="pln"> args</span><span class="pun">)</span> <span class="pun">{</span> <span class="kwd">return</span><span class="pln"> a </span><span class="pun">+</span><span class="pln"> sum</span><span class="pun">(</span><span class="pln">args</span><span class="pun">...);</span> <span class="pun">}</span>



<span class="kwd">int</span><span class="pln"> main</span><span class="pun">()</span> <span class="pun">{</span><span class="pln"> cout </span><span class="pun">&lt;&lt;</span><span class="pln"> sum</span><span class="pun">(</span><span class="lit">5</span><span class="pun">,</span> <span class="lit">7</span><span class="pun">,</span> <span class="lit">2</span><span class="pun">,</span> <span class="lit">2</span><span class="pun">)</span> <span class="pun">+</span><span class="pln"> sum</span><span class="pun">(</span><span class="lit">3.14</span><span class="pun">,</span> <span class="lit">4.89</span><span class="pun">);</span> <span class="com">/* prints "24.03" */</span> <span class="pun">}</span>

Here, I just changed

int

and added

typename T

to my template.

In C++14 you can also use

auto sum(T a, Args... args)

in order to get sum of mixed types. (Thanks to slycelote and Corei13)

We can also use variadic macros:


<span class="com">#define</span><span class="pln"> a_macro</span><span class="pun">(</span><span class="pln">args</span><span class="pun">...)</span><span class="pln"> sum</span><span class="pun">(</span><span class="pln">args</span><span class="pun">...)</span>



<span class="kwd">int</span><span class="pln"> sum</span><span class="pun">()</span> <span class="pun">{</span> <span class="kwd">return</span> <span class="lit">0</span><span class="pun">;</span> <span class="pun">}</span>



<span class="kwd">template</span><span class="pun">&lt;</span><span class="kwd">typename</span><span class="pln"> T</span><span class="pun">,</span> <span class="kwd">typename</span><span class="pun">...</span> <span class="typ">Args</span><span class="pun">&gt;</span>

<span class="kwd">auto</span><span class="pln"> sum</span><span class="pun">(</span><span class="pln">T a</span><span class="pun">,</span> <span class="typ">Args</span><span class="pun">...</span><span class="pln"> args</span><span class="pun">)</span> <span class="pun">{</span> <span class="kwd">return</span><span class="pln"> a </span><span class="pun">+</span><span class="pln"> sum</span><span class="pun">(</span><span class="pln">args</span><span class="pun">...);</span> <span class="pun">}</span>



<span class="kwd">int</span><span class="pln"> main</span><span class="pun">()</span> <span class="pun">{</span><span class="pln"> cout </span><span class="pun">&lt;&lt;</span><span class="pln"> a_macro</span><span class="pun">(</span><span class="lit">5</span><span class="pun">,</span> <span class="lit">7</span><span class="pun">,</span> <span class="lit">2</span><span class="pun">,</span> <span class="lit">2</span><span class="pun">)</span> <span class="pun">+</span><span class="pln"> a_macro</span><span class="pun">(</span><span class="lit">3.14</span><span class="pun">,</span> <span class="lit">4.89</span><span class="pun">);</span> <span class="com">/* prints "24.03" */</span> <span class="pun">}</span>

Using these 2, we can have a great debugging function: (thanks to Igorjan94) — Updated!


<span class="com">#include</span> <span class="pun">&lt;</span><span class="pln">bits</span><span class="pun">/</span><span class="pln">stdc</span><span class="pun">++.</span><span class="pln">h</span><span class="pun">&gt;</span>



<span class="kwd">using</span> <span class="kwd">namespace</span><span class="pln"> std</span><span class="pun">;</span>



<span class="com">#define</span><span class="pln"> error</span><span class="pun">(</span><span class="pln">args</span><span class="pun">...)</span> <span class="pun">{</span> <span class="kwd">string</span><span class="pln"> _s </span><span class="pun">=</span> <span class="com">#args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator&lt;string&gt; _it(_ss); err(_it, args); }</span>



<span class="kwd">void</span><span class="pln"> err</span><span class="pun">(</span><span class="pln">istream_iterator</span><span class="str">&lt;string&gt;</span><span class="pln"> it</span><span class="pun">)</span> <span class="pun">{}</span>

<span class="kwd">template</span><span class="pun">&lt;</span><span class="kwd">typename</span><span class="pln"> T</span><span class="pun">,</span> <span class="kwd">typename</span><span class="pun">...</span> <span class="typ">Args</span><span class="pun">&gt;</span>

<span class="kwd">void</span><span class="pln"> err</span><span class="pun">(</span><span class="pln">istream_iterator</span><span class="str">&lt;string&gt;</span><span class="pln"> it</span><span class="pun">,</span><span class="pln"> T a</span><span class="pun">,</span> <span class="typ">Args</span><span class="pun">...</span><span class="pln"> args</span><span class="pun">)</span> <span class="pun">{</span><span class="pln">

    cerr </span><span class="pun">&lt;&lt;</span> <span class="pun">*</span><span class="pln">it </span><span class="pun">&lt;&lt;</span> <span class="str">" = "</span> <span class="pun">&lt;&lt;</span><span class="pln"> a </span><span class="pun">&lt;&lt;</span><span class="pln"> endl</span><span class="pun">;</span><span class="pln">

    err</span><span class="pun">(++</span><span class="pln">it</span><span class="pun">,</span><span class="pln"> args</span><span class="pun">...);</span>

<span class="pun">}</span>



<span class="kwd">int</span><span class="pln"> main</span><span class="pun">()</span> <span class="pun">{</span>

    <span class="kwd">int</span><span class="pln"> a </span><span class="pun">=</span> <span class="lit">4</span><span class="pun">,</span><span class="pln"> b </span><span class="pun">=</span> <span class="lit">8</span><span class="pun">,</span><span class="pln"> c </span><span class="pun">=</span> <span class="lit">9</span><span class="pun">;</span><span class="pln">

    error</span><span class="pun">(</span><span class="pln">a</span><span class="pun">,</span><span class="pln"> b</span><span class="pun">,</span><span class="pln"> c</span><span class="pun">);</span>

<span class="pun">}</span>

Output:


<span class="pln">a </span><span class="pun">=</span> <span class="lit">4</span><span class="pln">

b </span><span class="pun">=</span> <span class="lit">8</span><span class="pln">

c </span><span class="pun">=</span> <span class="lit">9</span>

This function helps a lot in debugging.

6. Here is C++0x in CF, why still C++?

Variadic functions also belong to C++11 or C++0x, In this section I want to show you some great features of C++11.

one) Range-based For-loop

Here is a piece of an old code:


<span class="kwd">set</span><span class="str">&lt;int&gt;</span><span class="pln"> s </span><span class="pun">=</span> <span class="pun">{</span><span class="lit">8</span><span class="pun">,</span> <span class="lit">2</span><span class="pun">,</span> <span class="lit">3</span><span class="pun">,</span> <span class="lit">1</span><span class="pun">};</span>

<span class="kwd">for</span> <span class="pun">(</span><span class="kwd">set</span><span class="str">&lt;int&gt;</span><span class="pun">::</span><span class="pln">iterator it </span><span class="pun">=</span><span class="pln"> s</span><span class="pun">.</span><span class="kwd">begin</span><span class="pun">();</span><span class="pln"> it </span><span class="pun">!=</span><span class="pln"> s</span><span class="pun">.</span><span class="kwd">end</span><span class="pun">();</span> <span class="pun">++</span><span class="pln">it</span><span class="pun">)</span><span class="pln">

    cout </span><span class="pun">&lt;&lt;</span> <span class="pun">*</span><span class="pln">it </span><span class="pun">&lt;&lt;</span> <span class="str">' '</span><span class="pun">;</span>

<span class="com">// prints "1 2 3 8"</span>

Trust me, that’s a lot of code for that, just use this:


<span class="kwd">set</span><span class="str">&lt;int&gt;</span><span class="pln"> s </span><span class="pun">=</span> <span class="pun">{</span><span class="lit">8</span><span class="pun">,</span> <span class="lit">2</span><span class="pun">,</span> <span class="lit">3</span><span class="pun">,</span> <span class="lit">1</span><span class="pun">};</span>

<span class="kwd">for</span> <span class="pun">(</span><span class="kwd">auto</span><span class="pln"> it</span><span class="pun">:</span><span class="pln"> s</span><span class="pun">)</span><span class="pln">

    cout </span><span class="pun">&lt;&lt;</span><span class="pln"> it </span><span class="pun">&lt;&lt;</span> <span class="str">' '</span><span class="pun">;</span>

<span class="com">// prints "1 2 3 8"</span>

We can also change the values just change

auto

with

auto &


<span class="pln">vector</span><span class="str">&lt;int&gt;</span><span class="pln"> v </span><span class="pun">=</span> <span class="pun">{</span><span class="lit">8</span><span class="pun">,</span> <span class="lit">2</span><span class="pun">,</span> <span class="lit">3</span><span class="pun">,</span> <span class="lit">1</span><span class="pun">};</span>

<span class="kwd">for</span> <span class="pun">(</span><span class="kwd">auto</span> <span class="pun">&amp;</span><span class="pln">it</span><span class="pun">:</span><span class="pln"> v</span><span class="pun">)</span><span class="pln">

    it </span><span class="pun">*=</span> <span class="lit">2</span><span class="pun">;</span>

<span class="kwd">for</span> <span class="pun">(</span><span class="kwd">auto</span><span class="pln"> it</span><span class="pun">:</span><span class="pln"> v</span><span class="pun">)</span><span class="pln">

    cout </span><span class="pun">&lt;&lt;</span><span class="pln"> it </span><span class="pun">&lt;&lt;</span> <span class="str">' '</span><span class="pun">;</span>

<span class="com">// prints "16 4 6 2"</span>

two) The Power of

auto

You don’t need to name the type you want to use, C++11 can infer it for you. If you need to loop over iterators of a set<pair<int, pair<int, int> > > from begin to end, you need to type

set<pair<int, pair<int, int> > >::iterator

for me it’s so suffering! just use auto it = s.begin()

also x.begin() and x.end() now are accessible using begin(x) and end(x).

There are more things. I think I said useful features. Maybe I add somethings else to post. If you know anything useful please share with Codeforces community 🙂

From Ximera‘s comment:

this code:


<span class="kwd">for</span><span class="pun">(</span><span class="pln">i </span><span class="pun">=</span> <span class="lit">1</span><span class="pun">;</span><span class="pln"> i </span><span class="pun">&lt;=</span><span class="pln"> n</span><span class="pun">;</span><span class="pln"> i</span><span class="pun">++)</span> <span class="pun">{</span>

    <span class="kwd">for</span><span class="pun">(</span><span class="pln">j </span><span class="pun">=</span> <span class="lit">1</span><span class="pun">;</span><span class="pln"> j </span><span class="pun">&lt;=</span><span class="pln"> m</span><span class="pun">;</span><span class="pln"> j</span><span class="pun">++)</span><span class="pln">

        cout </span><span class="pun">&lt;&lt;</span><span class="pln"> a</span><span class="pun">[</span><span class="pln">i</span><span class="pun">][</span><span class="pln">j</span><span class="pun">]</span> <span class="pun">&lt;&lt;</span> <span class="str">" "</span><span class="pun">;</span><span class="pln">

    cout </span><span class="pun">&lt;&lt;</span> <span class="str">"\n"</span><span class="pun">;</span>

<span class="pun">}</span>

is equivalent to this:


<span class="kwd">for</span><span class="pun">(</span><span class="pln">i </span><span class="pun">=</span> <span class="lit">1</span><span class="pun">;</span><span class="pln"> i </span><span class="pun">&lt;=</span><span class="pln"> n</span><span class="pun">;</span><span class="pln"> i</span><span class="pun">++)</span>

    <span class="kwd">for</span><span class="pun">(</span><span class="pln">j </span><span class="pun">=</span> <span class="lit">1</span><span class="pun">;</span><span class="pln"> j </span><span class="pun">&lt;=</span><span class="pln"> m</span><span class="pun">;</span><span class="pln"> j</span><span class="pun">++)</span><span class="pln">

        cout </span><span class="pun">&lt;&lt;</span><span class="pln"> a</span><span class="pun">[</span><span class="pln">i</span><span class="pun">][</span><span class="pln">j</span><span class="pun">]</span> <span class="pun">&lt;&lt;</span> <span class="str">" \n"</span><span class="pun">[</span><span class="pln">j </span><span class="pun">==</span><span class="pln"> m</span><span class="pun">];</span>

And here is the reason:

" \n"

is a

char*

" \n"[0]

' '

and

" \n"[1]

'\n'

From technetium28‘s comment:

Usage of

tie

and

emplace_back


<span class="com">#define</span><span class="pln"> mt make_tuple

</span><span class="com">#define</span><span class="pln"> eb emplace_back

</span><span class="kwd">typedef</span><span class="pln"> tuple</span><span class="pun">&lt;</span><span class="kwd">int</span><span class="pun">,</span><span class="kwd">int</span><span class="pun">,</span><span class="kwd">int</span><span class="pun">&gt;</span> <span class="typ">State</span><span class="pun">;</span> <span class="com">// operator&lt; defined</span>



<span class="kwd">int</span><span class="pln"> main</span><span class="pun">(){</span>

  <span class="kwd">int</span><span class="pln"> a</span><span class="pun">,</span><span class="pln">b</span><span class="pun">,</span><span class="pln">c</span><span class="pun">;</span><span class="pln">

  tie</span><span class="pun">(</span><span class="pln">a</span><span class="pun">,</span><span class="pln">b</span><span class="pun">,</span><span class="pln">c</span><span class="pun">)</span> <span class="pun">=</span><span class="pln"> mt</span><span class="pun">(</span><span class="lit">1</span><span class="pun">,</span><span class="lit">2</span><span class="pun">,</span><span class="lit">3</span><span class="pun">);</span> <span class="com">// assign</span><span class="pln">

  tie</span><span class="pun">(</span><span class="pln">a</span><span class="pun">,</span><span class="pln">b</span><span class="pun">)</span> <span class="pun">=</span><span class="pln"> mt</span><span class="pun">(</span><span class="pln">b</span><span class="pun">,</span><span class="pln">a</span><span class="pun">);</span> <span class="com">// swap(a,b)</span><span class="pln">



  vector</span><span class="pun">&lt;</span><span class="pln">pair</span><span class="pun">&lt;</span><span class="kwd">int</span><span class="pun">,</span><span class="kwd">int</span><span class="pun">&gt;&gt;</span><span class="pln"> v</span><span class="pun">;</span><span class="pln">

  v</span><span class="pun">.</span><span class="pln">eb</span><span class="pun">(</span><span class="pln">a</span><span class="pun">,</span><span class="pln">b</span><span class="pun">);</span> <span class="com">// shorter and faster than pb(mp(a,b))</span>



  <span class="com">// Dijkstra</span><span class="pln">

  priority_queue</span><span class="pun">&lt;</span><span class="typ">State</span><span class="pun">&gt;</span><span class="pln"> q</span><span class="pun">;</span><span class="pln">

  q</span><span class="pun">.</span><span class="pln">emplace</span><span class="pun">(</span><span class="lit">0</span><span class="pun">,</span><span class="pln">src</span><span class="pun">,-</span><span class="lit">1</span><span class="pun">);</span>

  <span class="kwd">while</span><span class="pun">(</span><span class="pln">q</span><span class="pun">.</span><span class="pln">size</span><span class="pun">()){</span>

    <span class="kwd">int</span><span class="pln"> dist</span><span class="pun">,</span><span class="pln"> node</span><span class="pun">,</span><span class="pln"> prev</span><span class="pun">;</span><span class="pln">

    tie</span><span class="pun">(</span><span class="pln">dist</span><span class="pun">,</span><span class="pln"> ode</span><span class="pun">,</span><span class="pln"> prev</span><span class="pun">)</span> <span class="pun">=</span><span class="pln"> q</span><span class="pun">.</span><span class="pln">top</span><span class="pun">();</span><span class="pln"> q</span><span class="pun">.</span><span class="pln">pop</span><span class="pun">();</span><span class="pln">

    dist </span><span class="pun">=</span> <span class="pun">-</span><span class="pln">dist</span><span class="pun">;</span>

    <span class="com">// ~~ find next state ~~</span><span class="pln">

    q</span><span class="pun">.</span><span class="pln">emplace</span><span class="pun">(-</span><span class="pln">new_dist</span><span class="pun">,</span><span class="pln"> new_node</span><span class="pun">,</span><span class="pln"> node</span><span class="pun">);</span>

  <span class="pun">}</span>

<span class="pun">}</span>

And that’s why

emplace_back

faster:

emplace_back

is faster than

push_back

’cause it just construct value at the end of vector but

push_back

construct it somewhere else and then move it to the vector.

Also in the code above you can see how

tie(args...)

works. You can also use

ignore

keyword in

tie

to ignore a value:


<span class="pln">tuple</span><span class="pun">&lt;</span><span class="kwd">int</span><span class="pun">,</span> <span class="kwd">int</span><span class="pun">,</span> <span class="kwd">int</span><span class="pun">,</span> <span class="kwd">char</span><span class="pun">&gt;</span><span class="pln"> t </span><span class="pun">(</span><span class="lit">3</span><span class="pun">,</span> <span class="lit">4</span><span class="pun">,</span> <span class="lit">5</span><span class="pun">,</span> <span class="str">'g'</span><span class="pun">);</span>

<span class="kwd">int</span><span class="pln"> a</span><span class="pun">,</span><span class="pln"> b</span><span class="pun">;</span><span class="pln">

tie</span><span class="pun">(</span><span class="pln">b</span><span class="pun">,</span><span class="pln"> ignore</span><span class="pun">,</span><span class="pln"> a</span><span class="pun">,</span><span class="pln"> ignore</span><span class="pun">)</span> <span class="pun">=</span><span class="pln"> t</span><span class="pun">;</span><span class="pln">

cout </span><span class="pun">&lt;&lt;</span><span class="pln"> a </span><span class="pun">&lt;&lt;</span> <span class="str">' '</span> <span class="pun">&lt;&lt;</span><span class="pln"> b </span><span class="pun">&lt;&lt;</span> <span class="str">'\n'</span><span class="pun">;</span>

Output:

5 3

I use this macro and I love it:


<span class="com">#define</span><span class="pln"> rep</span><span class="pun">(</span><span class="pln">i</span><span class="pun">,</span> <span class="kwd">begin</span><span class="pun">,</span> <span class="kwd">end</span><span class="pun">)</span> <span class="kwd">for</span> <span class="pun">(</span><span class="pln">__typeof</span><span class="pun">(</span><span class="kwd">end</span><span class="pun">)</span><span class="pln"> i </span><span class="pun">=</span> <span class="pun">(</span><span class="kwd">begin</span><span class="pun">)</span> <span class="pun">-</span> <span class="pun">((</span><span class="kwd">begin</span><span class="pun">)</span> <span class="pun">&gt;</span> <span class="pun">(</span><span class="kwd">end</span><span class="pun">));</span><span class="pln"> i </span><span class="pun">!=</span> <span class="pun">(</span><span class="kwd">end</span><span class="pun">)</span> <span class="pun">-</span> <span class="pun">((</span><span class="kwd">begin</span><span class="pun">)</span> <span class="pun">&gt;</span> <span class="pun">(</span><span class="kwd">end</span><span class="pun">));</span><span class="pln"> i </span><span class="pun">+=</span> <span class="lit">1</span> <span class="pun">-</span> <span class="lit">2</span> <span class="pun">*</span> <span class="pun">((</span><span class="kwd">begin</span><span class="pun">)</span> <span class="pun">&gt;</span> <span class="pun">(</span><span class="kwd">end</span><span class="pun">)))</span>

First of all, you don’t need to name the type you want to use. Second of all it goes forwards and backwards based on (begin > end) condition. e.g.

rep(i, 1, 10)

is 1, 2, …, 8, 9 and

rep(i, 10, 1)

is 9, 8, …, 2, 1

It works well with different types e.g.


<span class="pln">vector</span><span class="str">&lt;int&gt;</span><span class="pln"> v </span><span class="pun">=</span> <span class="pun">{</span><span class="lit">4</span><span class="pun">,</span> <span class="lit">5</span><span class="pun">,</span> <span class="lit">6</span><span class="pun">,</span> <span class="lit">4</span><span class="pun">,</span> <span class="lit">8</span><span class="pun">};</span><span class="pln">

rep</span><span class="pun">(</span><span class="pln">it</span><span class="pun">,</span> <span class="kwd">end</span><span class="pun">(</span><span class="pln">v</span><span class="pun">),</span> <span class="kwd">begin</span><span class="pun">(</span><span class="pln">v</span><span class="pun">))</span><span class="pln">

    cout </span><span class="pun">&lt;&lt;</span> <span class="pun">*</span><span class="pln">it </span><span class="pun">&lt;&lt;</span> <span class="str">' '</span><span class="pun">;</span>

<span class="com">// prints "8 4 6 5 4"</span>

Also there is another great feature of C++11, lambda functions!

Lambdas are like other languages’ closure. It defines like this:


<span class="pun">[</span><span class="pln">capture list</span><span class="pun">](</span><span class="pln">parameters</span><span class="pun">)</span> <span class="pun">-&gt;</span> <span class="kwd">return</span><span class="pln"> value </span><span class="pun">{</span><span class="pln"> body </span><span class="pun">}</span>

one) Capture List: simple! We don’t need it here, so just put

[]

two) parameters: simple! e.g. int x, string s

three) return value: simple again! e.g. pair<int, int> which can be omitted most of the times (thanks to Jacob)

four) body: contains function bodies, and returns return value.

e.g.


<span class="kwd">auto</span><span class="pln"> f </span><span class="pun">=</span> <span class="pun">[]</span> <span class="pun">(</span><span class="kwd">int</span><span class="pln"> a</span><span class="pun">,</span> <span class="kwd">int</span><span class="pln"> b</span><span class="pun">)</span> <span class="pun">-&gt;</span> <span class="kwd">int</span> <span class="pun">{</span> <span class="kwd">return</span><span class="pln"> a </span><span class="pun">+</span><span class="pln"> b</span><span class="pun">;</span> <span class="pun">};</span><span class="pln">

cout </span><span class="pun">&lt;&lt;</span><span class="pln"> f</span><span class="pun">(</span><span class="lit">1</span><span class="pun">,</span> <span class="lit">2</span><span class="pun">);</span> <span class="com">// prints "3"</span>

You can use lambdas in

for_each

sort

and many more STL functions:


<span class="pln">vector</span><span class="str">&lt;int&gt;</span><span class="pln"> v </span><span class="pun">=</span> <span class="pun">{</span><span class="lit">3</span><span class="pun">,</span> <span class="lit">1</span><span class="pun">,</span> <span class="lit">2</span><span class="pun">,</span> <span class="lit">1</span><span class="pun">,</span> <span class="lit">8</span><span class="pun">};</span><span class="pln">

sort</span><span class="pun">(</span><span class="kwd">begin</span><span class="pun">(</span><span class="pln">v</span><span class="pun">),</span> <span class="kwd">end</span><span class="pun">(</span><span class="pln">v</span><span class="pun">),</span> <span class="pun">[]</span> <span class="pun">(</span><span class="kwd">int</span><span class="pln"> a</span><span class="pun">,</span> <span class="kwd">int</span><span class="pln"> b</span><span class="pun">)</span> <span class="pun">{</span> <span class="kwd">return</span><span class="pln"> a </span><span class="pun">&gt;</span><span class="pln"> b</span><span class="pun">;</span> <span class="pun">});</span>

<span class="kwd">for</span> <span class="pun">(</span><span class="kwd">auto</span><span class="pln"> i</span><span class="pun">:</span><span class="pln"> v</span><span class="pun">)</span><span class="pln"> cout </span><span class="pun">&lt;&lt;</span><span class="pln"> i </span><span class="pun">&lt;&lt;</span> <span class="str">' '</span><span class="pun">;</span>

Output:


<span class="lit">8</span> <span class="lit">3</span> <span class="lit">2</span> <span class="lit">1</span> <span class="lit">1</span>

From Igorjan94‘s comment:

Usage of

move

When you work with STL containers like

vector

, you can use

move

function to just move container, not to copy it all.


<span class="pln">vector</span><span class="str">&lt;int&gt;</span><span class="pln"> v </span><span class="pun">=</span> <span class="pun">{</span><span class="lit">1</span><span class="pun">,</span> <span class="lit">2</span><span class="pun">,</span> <span class="lit">3</span><span class="pun">,</span> <span class="lit">4</span><span class="pun">};</span><span class="pln">

vector</span><span class="str">&lt;int&gt;</span><span class="pln"> w </span><span class="pun">=</span><span class="pln"> move</span><span class="pun">(</span><span class="pln">v</span><span class="pun">);</span><span class="pln">



cout </span><span class="pun">&lt;&lt;</span> <span class="str">"v: "</span><span class="pun">;</span>

<span class="kwd">for</span> <span class="pun">(</span><span class="kwd">auto</span><span class="pln"> i</span><span class="pun">:</span><span class="pln"> v</span><span class="pun">)</span><span class="pln">

    cout </span><span class="pun">&lt;&lt;</span><span class="pln"> i </span><span class="pun">&lt;&lt;</span> <span class="str">' '</span><span class="pun">;</span><span class="pln">



cout </span><span class="pun">&lt;&lt;</span> <span class="str">"\nw: "</span><span class="pun">;</span>

<span class="kwd">for</span> <span class="pun">(</span><span class="kwd">auto</span><span class="pln"> i</span><span class="pun">:</span><span class="pln"> w</span><span class="pun">)</span><span class="pln">

    cout </span><span class="pun">&lt;&lt;</span><span class="pln"> i </span><span class="pun">&lt;&lt;</span> <span class="str">' '</span><span class="pun">;</span>

Output:


<span class="pln">v</span><span class="pun">:</span><span class="pln"> 

w</span><span class="pun">:</span> <span class="lit">1</span> <span class="lit">2</span> <span class="lit">3</span> <span class="lit">4</span>

As you can see

moved to

and not copied.

7. C++0x Strings

one) Raw Strings (From IvayloS‘s comment)

You can have UTF-8 strings, Raw strings and more. Here I want to show raw strings. We define a raw string as below:


<span class="kwd">string</span><span class="pln"> s </span><span class="pun">=</span><span class="pln"> R</span><span class="str">"(Hello, World!)"</span><span class="pun">;</span> <span class="com">// Stored: "Hello, World!"</span>

A raw string skips all escape characters like

. e.g.


<span class="kwd">string</span><span class="pln"> str </span><span class="pun">=</span> <span class="str">"Hello\tWorld\n"</span><span class="pun">;</span>

<span class="kwd">string</span><span class="pln"> r_str </span><span class="pun">=</span><span class="pln"> R</span><span class="str">"(Hello\tWorld\n)"</span><span class="pun">;</span><span class="pln">

cout </span><span class="pun">&lt;&lt;</span><span class="pln"> str </span><span class="pun">&lt;&lt;</span><span class="pln"> r_str</span><span class="pun">;</span>

Output:


<span class="typ">Hello</span>  <span class="typ">World</span>

<span class="typ">Hello</span><span class="pln">\t</span><span class="typ">World</span><span class="pln">\n</span>

You can also have multiple line raw string:


<span class="kwd">string</span><span class="pln"> r_str </span><span class="pun">=</span><span class="pln">

R</span><span class="str">"(Dear Programmers,

I'm using C++11

Regards, Swift!)"</span><span class="pun">;</span><span class="pln">

cout </span><span class="pun">&lt;&lt;</span><span class="pln"> r_str</span><span class="pun">;</span>

Output:


<span class="typ">Dear</span> <span class="typ">Programmer</span><span class="pun">,</span><span class="pln">

I</span><span class="str">'m using C++11

Regards, Swift!</span>

two) Regular Expressions (regex)

Regular expressions are useful tools in programming, we can define a regular expression by

regex

e.g.

regex r = "[a-z]+";

. We will use raw string for them because sometimes they have

and other characters. Look at the example:


<span class="pln">regex email_pattern</span><span class="pun">(</span><span class="pln">R</span><span class="str">"(^[a-zA-Z0-9_.+-]+@[a-zA-Z0-9-]+\.[a-zA-Z0-9-.]+$)"</span><span class="pun">);</span> <span class="com">// This email pattern is not totally correct! It's correct for most emails.</span>



<span class="kwd">string</span><span class="pln">

valid_email</span><span class="pun">(</span><span class="str">"swift@codeforces.com"</span><span class="pun">),</span><span class="pln">

invalid_email</span><span class="pun">(</span><span class="str">"hello world"</span><span class="pun">);</span>



<span class="kwd">if</span> <span class="pun">(</span><span class="pln">regex_match</span><span class="pun">(</span><span class="pln">valid_email</span><span class="pun">,</span><span class="pln"> email_pattern</span><span class="pun">))</span><span class="pln">

    cout </span><span class="pun">&lt;&lt;</span><span class="pln"> valid_email </span><span class="pun">&lt;&lt;</span> <span class="str">" is valid\n"</span><span class="pun">;</span>

<span class="kwd">else</span><span class="pln">

    cout </span><span class="pun">&lt;&lt;</span><span class="pln"> valid_email </span><span class="pun">&lt;&lt;</span> <span class="str">" is invalid\n"</span><span class="pun">;</span>



<span class="kwd">if</span> <span class="pun">(</span><span class="pln">regex_match</span><span class="pun">(</span><span class="pln">invalid_email</span><span class="pun">,</span><span class="pln"> email_pattern</span><span class="pun">))</span><span class="pln">

    cout </span><span class="pun">&lt;&lt;</span><span class="pln"> invalid_email </span><span class="pun">&lt;&lt;</span> <span class="str">" is valid\n"</span><span class="pun">;</span>

<span class="kwd">else</span><span class="pln">

    cout </span><span class="pun">&lt;&lt;</span><span class="pln"> invalid_email </span><span class="pun">&lt;&lt;</span> <span class="str">" is invalid\n"</span><span class="pun">;</span>

Output:


<span class="pln">swift@codeforces</span><span class="pun">.</span><span class="pln">com </span><span class="kwd">is</span><span class="pln"> valid

hello world </span><span class="kwd">is</span><span class="pln"> invalid</span>

Note: You can learn Regex in this website.

three) User-defined literals

You already know literals from C++ like:

0xA

1000ll

3.14f

and so on…

Now you can have your own custom literals! Sounds great 🙂 So let’s see an example:


<span class="kwd">long</span> <span class="kwd">long</span> <span class="kwd">operator</span> <span class="str">""</span><span class="pln"> _m</span><span class="pun">(</span><span class="kwd">unsigned</span> <span class="kwd">long</span> <span class="kwd">long</span><span class="pln"> literal</span><span class="pun">)</span> <span class="pun">{</span>

    <span class="kwd">return</span><span class="pln"> literal</span><span class="pun">;</span>

<span class="pun">}</span>



<span class="kwd">long</span> <span class="kwd">double</span> <span class="kwd">operator</span> <span class="str">""</span><span class="pln"> _cm</span><span class="pun">(</span><span class="kwd">unsigned</span> <span class="kwd">long</span> <span class="kwd">long</span><span class="pln"> literal</span><span class="pun">)</span> <span class="pun">{</span>

    <span class="kwd">return</span><span class="pln"> literal </span><span class="pun">/</span> <span class="lit">100.0</span><span class="pun">;</span>

<span class="pun">}</span>



<span class="kwd">long</span> <span class="kwd">long</span> <span class="kwd">operator</span> <span class="str">""</span><span class="pln"> _km</span><span class="pun">(</span><span class="kwd">unsigned</span> <span class="kwd">long</span> <span class="kwd">long</span><span class="pln"> literal</span><span class="pun">)</span> <span class="pun">{</span>

    <span class="kwd">return</span><span class="pln"> literal </span><span class="pun">*</span> <span class="lit">1000</span><span class="pun">;</span>

<span class="pun">}</span>



<span class="kwd">int</span><span class="pln"> main</span><span class="pun">()</span> <span class="pun">{</span>

    <span class="com">// See results in meter:</span><span class="pln">

    cout </span><span class="pun">&lt;&lt;</span> <span class="lit">250</span><span class="pln">_m </span><span class="pun">&lt;&lt;</span> <span class="str">" meters \n"</span><span class="pun">;</span> <span class="com">// Prints 250 meters</span><span class="pln">

    cout </span><span class="pun">&lt;&lt;</span> <span class="lit">12</span><span class="pln">_km </span><span class="pun">&lt;&lt;</span> <span class="str">" meters \n"</span><span class="pun">;</span> <span class="com">// Prints 12000 meters</span><span class="pln">

    cout </span><span class="pun">&lt;&lt;</span> <span class="lit">421</span><span class="pln">_cm </span><span class="pun">&lt;&lt;</span> <span class="str">" meters \n"</span><span class="pun">;</span> <span class="com">// Prints 4.21 meters</span>

<span class="pun">}</span>

Note that a literal should start with an underscore (

). We declare a new literal by this pattern:


<span class="pun">[</span><span class="pln">returnType</span><span class="pun">]</span> <span class="kwd">operator</span> <span class="str">""</span><span class="pln"> _</span><span class="pun">[</span><span class="pln">name</span><span class="pun">]([</span><span class="pln">parameters</span><span class="pun">])</span> <span class="pun">{</span> <span class="pun">[</span><span class="pln">body</span><span class="pun">]</span> <span class="pun">}</span>

note that parameters only can be one of these:

(const char *)

(unsigned long long int)

(long double)

(char)

(wchar_t)

(char16_t)

(char32_t)

(const char *, size_t)

(const wchar_t *, size_t)

(const char16_t *, size_t)

(const char32_t *, size_t)

Literals also can used with templates.

11.07.2018

Build a blockchain with C++

So, you might have heard a lot about something called a blockchain lately and wondered what all the fuss is about. A blockchain is a ledger which has been written in such a way that updating the data contained within it becomes very difficult, some say the blockchain is immutable and to all intents and purposes they’re right but immutability suggests permanence and nothing on a hard drive could ever be considered permanent. Anyway, we’ll leave the philosophical debate to the non-techies; you’re looking for someone to show you how to write a blockchain in C++, so that’s exactly what I’m going to do.

Before I go any further, I have a couple of disclaimers:

This tutorial is based on one written by Savjee using NodeJS; and
It’s been a while since I wrote any C++ code, so I might be a little rusty.

The first thing you’ll want to do is open a new C++ project, I’m using CLion from JetBrains but any C++ IDE or even a text editor will do. For the interests of this tutorial we’ll call the project TestChain, so go ahead and create the project and we’ll get started.

If you’re using CLion you’ll see that the main.cpp file will have already been created and opened for you; we’ll leave this to one side for the time being.

Create a file called Block.h in the main project folder, you should be able to do this by right-clicking on the TestChain directory in the Project Tool Window and selecting: New > C/C++ Header File.

Inside the file, add the following code (if you’re using CLion place all code between the lines that read #define TESTCHAIN_BLOCK_H and #endif):

1 2	#include <cstdint> #include <iostream>

These lines above tell the compiler to include the cstdint, and iostream libraries.

Add this line below it:

1	using namespace std;

This essentially creates a shortcut to the std namespace, which means that we don’t need to refer to declarations inside the stdnamespace by their full names e.g. std::string, but instead use their shortened names e.g. string.

So far, so good; let’s start fleshing things out a little more.

A blockchain is made up of a series of blocks which contain data and each block contains a cryptographic representation of the previous block, which means that it becomes very hard to change the contents of any block without then needing to change every subsequent one; hence where the blockchain essentially gets its immutable properties.

So let’s create our block class, add the following lines to the Block.h header file:

class Block {

public:

string sPrevHash;

Block(uint32_t nIndexIn, const string &sDataIn);

string GetHash();

void MineBlock(uint32_t nDifficulty);

private:

uint32_t _nIndex;

int64_t _nNonce;

string _sData;

string _sHash;

time_t _tTime;

string _CalculateHash() const;

};

Unsurprisingly, we’re calling our class Block (line 1) followed by the public modifier (line 2) and public variable sPrevHash(remember each block is linked to the previous block) (line 3). The constructor signature (line 5) takes three parameters for nIndexIn, and sDataIn; note that the const keyword is used along with the reference modifier (&) so that the parameters are passed by reference but cannot be changed, this is done to improve efficiency and save memory. The GetHash method signature is specified next (line 7) followed by the MineBlock method signature (line 9), which takes a parameter nDifficulty. We specify the private modifier (line 11) followed by the private variables _nIndex, _nNonce, _sData, _sHash, and _tTime (lines 12–16). The signature for _CalculateHash (line 18) also has the const keyword, this is to ensure the output from the method cannot be changed which is very useful when dealing with a blockchain.

Now it’s time to create our Blockchain.h header file in the main project folder.

Let’s start by adding these lines (if you’re using CLion place all code between the lines that read #define TESTCHAIN_BLOCKCHAIN_H and #endif):

#include <cstdint>

#include <vector>

#include «Block.h»

using namespace std;

They tell the compiler to include the cstdint, and vector libraries, as well as the Block.h header file we have just created, and creates a shortcut to the std namespace.

Now let’s create our blockchain class, add the following lines to the Blockchain.h header file:

class Blockchain {

public:

Blockchain();

void AddBlock(Block bNew);

private:

uint32_t _nDifficulty;

vector<Block> _vChain;

Block _GetLastBlock() const;

};

As with our block class, we’re keeping things simple and calling our blockchain class Blockchain (line 1) followed by the publicmodifier (line 2) and the constructor signature (line 3). The AddBlock signature (line 5) takes a parameter bNew which must be an object of the Block class we created earlier. We then specify the private modifier (line 7) followed by the private variables for _nDifficulty, and _vChain (lines 8–9) as well as the method signature for _GetLastBlock (line 11) which is also followed by the const keyword to denote that the output of the method cannot be changed.

Ain't nobody got time for that! Since blockchains use cryptography, now would be a good time to get some cryptographic functionality in our blockchain. We’re going to be using the SHA256 hashing technique to create hashes of our blocks, we could write our own but really – in this day and age of open source software – why bother?

To make my life that much easier, I copied and pasted the text for the sha256.h, sha256.cpp and LICENSE.txt files shown on the C++ sha256 function from Zedwood and saved them in the project folder.

Right, let’s keep going.

Create a source file for our block and save it as Block.cpp in the main project folder; you should be able to do this by right-clicking on the TestChain directory in the Project Tool Window and selecting: New > C/C++ Source File.

Start by adding these lines, which tell the compiler to include the Block.h and sha256.h files we added earlier.

1 2	#include «Block.h» #include «sha256.h»

Follow these with the implementation of our block constructor:

Block::Block(uint32_t nIndexIn, const string &sDataIn) : _nIndex(nIndexIn), _sData(sDataIn) {

_nNonce = —1;

_tTime = time(nullptr);

}

The constructor starts off by repeating the signature we specified in the Block.h header file (line 1) but we also add code to copy the contents of the parameters into the the variables _nIndex, and _sData. The _nNonce variable is set to -1 (line 2) and the _tTime variable is set to the current time (line 3).

Let’s add an accessor for the block’s hash:

string Block::GetHash() {

return _sHash;

}

We specify the signature for GetHash (line 1) and then add a return for the private variable _sHash (line 2).

As you might have read, blockchain technology was made popular when it was devised for the Bitcoin digital currency, as the ledger is both immutable and public; which means that, as one user transfers Bitcoin to another user, a transaction for the transfer is written into a block on the blockchain by nodes on the Bitcoin network. A node is another computer which is running the Bitcoin software and, since the network is peer-to-peer, it could be anyone around the world; this process is called ‘mining’ as the owner of the node is rewarded with Bitcoin each time they successfully create a valid block on the blockchain.

To successfully create a valid block, and therefore be rewarded, a miner must create a cryptographic hash of the block they want to add to the blockchain that matches the requirements for a valid hash at that time; this is achieved by counting the number of zeros at the beginning of the hash, if the number of zeros is equal to or greater than the difficulty level set by the network that block is valid. If the hash is not valid a variable called a nonce is incremented and the hash created again; this process, called Proof of Work (PoW), is repeated until a hash is produced that is valid.

So, with that being said, let’s add the MineBlock method; here’s where the magic happens!

void Block::MineBlock(uint32_t nDifficulty) {

char cstr[nDifficulty + 1];

for (uint32_t i = 0; i < nDifficulty; ++i) {

cstr[i] = ‘0’;

}

cstr[nDifficulty] = ‘\0’;

string str(cstr);

do {

_nNonce++;

_sHash = _CalculateHash();

} while (_sHash.substr(0, nDifficulty) != str);

cout << «Block mined: « << _sHash << endl;

}

We start with the signature for the MineBlock method, which we specified in the Block.h header file (line 1), and create an array of characters with a length one greater that the value specified for nDifficulty (line 2). A for loop is used to fill the array with zeros, followed by the final array item being given the string terminator character (\0), (lines 3–6) then the character array or c-string is turned into a standard string (line 8). A do…while loop is then used (lines 10–13) to increment the _nNonce and _sHashis assigned with the output of _CalculateHash, the front portion of the hash is then compared the string of zeros we’ve just created; if no match is found the loop is repeated until a match is found. Once a match is found a message is sent to the output buffer to say that the block has been successfully mined (line 15).

We’ve seen it mentioned a few times before, so let’s now add the _CalculateHash method:

inline string Block::_CalculateHash() const {

stringstream ss;

ss << _nIndex << _tTime << _sData << _nNonce << sPrevHash;

return sha256(ss.str());

}

We kick off with the signature for the _CalculateHash method (line 1), which we specified in the Block.h header file, but we include the inline keyword which makes the code more efficient as the compiler places the method’s instructions inline wherever the method is called; this cuts down on separate method calls. A string stream is then created (line 2), followed by appending the values for _nIndex, _tTime, _sData, _nNonce, and sPrevHash to the stream (line 3). We finish off by returning the output of the sha256 method (from the sha256 files we added earlier) using the string output from the string stream (line 5).

Right, let’s finish off our blockchain implementation! Same as before, create a source file for our blockchain and save it as Blockchain.cpp in the main project folder.

Add these lines, which tell the compiler to include the Blockchain.h file we added earlier.

1	#include «Blockchain.h»

Follow these with the implementation of our blockchain constructor:

Blockchain::Blockchain() {

_vChain.emplace_back(Block(0, «Genesis Block»));

_nDifficulty = 6;

}

We start off with the signature for the blockchain constructor we specified in Blockchain.h (line 1). As a blocks are added to the blockchain they need to reference the previous block using its hash, but as the blockchain must start somewhere we have to create a block for the next block to reference, we call this a genesis block. A genesis block is created and placed onto the _vChain vector (line 2). We then set the _nDifficulty level (line 3) depending on how hard we want to make the PoW process.

Now it’s time to add the code for adding a block to the blockchain, add the following lines:

void Blockchain::AddBlock(Block bNew) {

bNew.sPrevHash = _GetLastBlock().GetHash();

bNew.MineBlock(_nDifficulty);

_vChain.push_back(bNew);

}

The signature we specified in Blockchain.h for AddBlock is added (line 1) followed by setting the sPrevHash variable for the new block from the hash of the last block on the blockchain which we get using _GetLastBlock and its GetHash method (line 2). The block is then mined using the MineBlock method (line 3) followed by the block being added to the _vChain vector (line 4), thus completing the process of adding a block to the blockchain.

Let’s finish this file off by adding the last method:

Block Blockchain::_GetLastBlock() const {

return _vChain.back();

}

We add the signature for _GetLastBlock from Blockchain.h (line 1) followed by returning the last block found in the _vChainvector using its back method (line 2).

Right, that’s almost it, let’s test it out!

Remember the main.cpp file? Now’s the time to update it, open it up and replace the contents with the following lines:

1	#include «Blockchain.h»

This tells the compiler to include the Blockchain.h file we created earlier.

Then add the following lines:

int main() {

Blockchain bChain = Blockchain();

cout << «Mining block 1…» << endl;

bChain.AddBlock(Block(1, «Block 1 Data»));

cout << «Mining block 2…» << endl;

bChain.AddBlock(Block(2, «Block 2 Data»));

cout << «Mining block 3…» << endl;

bChain.AddBlock(Block(3, «Block 3 Data»));

return 0;

}

As with most C/C++ programs, everything is kicked off by calling the main method, this one creates a new blockchain (line 2) and informs the user that a block is being mined by printing to the output buffer (line 4) then creates a new block and adds it to the chain (line 5); the process for mining that block will then kick off until a valid hash is found. Once the block is mined the process is repeated for two more blocks.

Time to run it! If you are using CLion simply hit the ‘Run TestChain’ button in the top right hand corner of the window. If you’re old skool, you can compile and run the program using the following commands from the command line:

gcc —lstdc++ \

—o TestChain \

—std=c++11 \

—stdlib=libc++ \

—x c++ \

main.cpp Block.cpp Blockchain.cpp sha256.cpp

./TestChain

If all goes well you should see an output like this:

Mining block 1…

Block mined: 000000c1b50cb30fd8d9a0f2e16e38681cfcf9caead098cea726854925ab3772

Mining block 2…

Block mined: 0000005081063c8c854d11560cfea4fe734bde515a08565c26aa05448eea184e

Mining block 3…

Block mined: 000000ea61810fa85ff636440eb803263daf06b306c607aced9a1f996a421042

Congratulations, you have just written a blockchain from scratch in C++, in case you got lost I’ve put all the files into a Github repo. Since the original code for Bitcoin was also written in C++, why not take a look at its code and see what improvements you can make to what we’ve started off today?

Orig post

11.07.2018

Bypassing CSP using polyglot JPEGs

James challenged me to see if it was possible to create a polyglot JavaScript/JPEG. Doing so would allow me to bypass CSP on almost any website that hosts user-uploaded images on the same domain. I gleefully took up the challenge and begun dissecting the format. The first four bytes are a valid non-ASCII JavaScript variable 0xFF 0xD8 0xFF 0xE0. Then the next two bytes specify the length of the JPEG header. If we make that length of the header 0x2F2A using the bytes 0x2F 0x2A as you might guess we have a non-ASCII variable followed by a multi-line JavaScript comment. We then have to pad out the JPEG header to the length of 0x2F2A with nulls. Here’s what it looks like:

FF D8 FF E0 2F 2A 4A 46 49 46 00 01 01 01 00 48 00 48 00 00 00 00 00 00 00 00 00 00....

Inside a JPEG comment we can close the JavaScript comment and create an assignment for our non-ASCII JavaScript variable followed by our payload, then create another multi-line comment at the end of the JPEG comment.

FF FE 00 1C 2A 2F 3D 61 6C 65 72 74 28 22 42 75 72 70 20 72 6F 63 6B 73 2E 22 29 3B 2F 2A

0xFF 0xFE is the comment header 0x00 0x1C specifies the length of the comment then the rest is our JavaScript payload which is of course */=alert(«Burp rocks.»)/*

Next we need to close the JavaScript comment, I edited the last four bytes of the image data before the end of image marker. Here’s what the end of the file looks like:

2A 2F 2F 2F FF D9

0xFF 0xD9 is the end of image marker. Great so there is our polyglot JPEG, well not quite yet. It works great if you don’t specify a charset but on Firefox when using a UTF-8 character set for the document it corrupts our polyglot when included as an script! On MDN it doesn’t state that the script supports the charset attribute but it does. So to get the script to work you need to specify the ISO-8859-1 charset on the script tag and it executes fine.

It’s worth noting that the polyglot JPEG works on Safari, Firefox, Edge and IE11. Chrome sensibly does not execute the image as JavaScript.

Here is the polyglot JPEG:

Polyglot JPEG

The code to execute the image as JavaScript is as follows:

File size restrictions

I attempted to upload this graphic as a phpBB profile picture but it has restrictions in place. There is a 6k file size limit and maximum dimensions of 90×90. I reduced the size of the logo by cropping and thought about how I could reduce the JPEG data. In the JPEG header I use /* which in hex is 0x2F and 0x2A, combined 0x2F2A which results in a length of 12074 which is a lot of padding and will result in a graphic far too big to fit as a profile picture. Looking at the ASCII table I tried to find a combination of characters that would be valid JavaScript and reduce the amount of padding required in the JPEG header whilst still being recognised as a valid JPEG file.

The smallest starting byte I could find was 0x9 (a tab character) followed by 0x3A (a colon) which results in a combined hex value of 0x093A (2362) that shaves a lot of bytes from our file and creates a valid non-ASCII JavaScript label statement, followed by a variable using the JFIF identifier. Then I place a forward slash 0x2F instead of the NULL character at the end of the JFIF identifier and an asterisk as the version number. Here’s what the hex looks like:

FF D8 FF E0 09 3A 4A 46 49 46 2F 2A

Now we continue the rest of the JPEG header then pad with NULLs and inject our JavaScript payload:

FF D8 FF E0 09 3A 4A 46 49 46 2F 2A 01 01 00 48 00 48 00 00 00 00 00 00 00 ... (padding more nulls) 2A 2F 3D 61 6C 65 72 74 28 22 42 75 72 70 20 72 6F 63 6B 73 2E 22 29 3B 2F 2A

Here is the smaller graphic:

Polyglot JPEG smaller

Impact

If you allow users to upload JPEGs, these uploads are on the same domain as your app, and your CSP allows script from «self», you can bypass the CSP using a polyglot JPEG by injecting a script and pointing it to that image.

Conclusion

In conclusion if you allow JPEG uploads on your site or indeed any type of file, it’s worth placing these assets on a separate domain. When validating a JPEG, you should rewrite the JPEG header to ensure no code is sneaked in there and remove all JPEG comments. Obviously it’s also essential that your CSP does not whitelist your image assets domain for script.

This post wouldn’t be possible without the excellent work of Ange Albertini. I used his JPEG format graphicextensively to create the polygot JPEG. Jasvir Nagra also inspired me with his blog post about polyglot GIFs.

PoC

Gareth Heyes @garethheyes

Июль 2018
Пн	Вт	Ср	Чт	Пт	Сб	Вс
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31