Coding&Hobbies

Using heap is C++

2018-07-11T16:12:06+09:00

Heap is a very important and widely used in any programing language. Unlike queue and stack, there are no dedicated class for heap in C++. However, there are some functions that let you work with heap in C++. This post will discuss about these functions and how should we use them.

1. make_heap()

template <class RandomAccessIterator, class Compare>
  void make_heap (RandomAccessIterator first, RandomAccessIterator last,
                  Compare comp );

A heap in C++ is a max-heap by default, the default comparator is operator<, if you want a min_heap change the comp arguments to something like std::greater<int>().the element with the highest order is always pointed by first. It can be retrieved by the function front(). the range is [first,last), first and last in must be random access iterators so vector is the best bet. The value type should be valid to the swap function, means it should be move-constructible and move-assignable. This function will take O(N) where N is the number of elements.

2. push_heap()

template <class RandomAccessIterator, class Compare>
  void push_heap (RandomAccessIterator first, RandomAccessIterator last,
                   Compare comp);

Given a heap in the range [first,last-1), this function extends the range considered a heap to [first,last) by placing the value in (last-1) into its corresponding location within it. This function will take O(log(N)).

3. pop_heap()

template <class RandomAccessIterator, class Compare>
  void pop_heap (RandomAccessIterator first, RandomAccessIterator last,
                 Compare comp);

The element with the highest value is moved from first to (last-1) (which now is out of the heap), the other elements are reorganized in such a way that the range [first,last-1) preserves the properties of a heap. If the previous heap is [begin(), end()), after this function its not true any more. So we need a variable to keep track of the end of the heap. The complexity of this function is O(log(N)).

4. sort_heap()

template <class RandomAccessIterator, class Compare>
  void sort_heap (RandomAccessIterator first, RandomAccessIterator last,
                  Compare comp);

Sorts the elements in the heap range [first,last) into ascending order. The range loses its properties as a heap. This is sort heap, and it take N*log(N).

5. is_heap() and is_heap_until()

template< class RandomIt, class Compare >
constexpr bool is_heap( RandomIt first, RandomIt last, Compare comp );

template< class RandomIt, class Compare >
constexpr RandomIt is_heap_until( RandomIt first, RandomIt last, Compare comp );

is_heap check if the range is a heap or not and return a bool value. While is_heap_until return finds the largest range [first, last) beginning at first which is a heap. These to function took O(N).

Discussion

As we can see, techniques to manage a heap are complex and prone to errors since we have to keep track of the heap’s base representation and variables. May be this is because it is inherited from older version of C++. Vector should be used as the base representation and a variable should be define to keep track of the ending of the heap.

Notes on C++ class constructor and destructor

2018-06-20T16:02:06+09:00

In this posts, I will list some notes that I think they worth to be reminded when mentioning about classes’ declaration, constructor, and destructor.

1. In-class member function is inline function

If you define a method member inside the class declaration such as

class People {
	string first_name() {return _fname;}
    string last_name();
}
string People::last_name {return _lname;}

Then first_name() function will be an inline function by default while the function last_name() is not. Remember the good and the bad of an inline function. On the good side, an inline function can remove the overhead of the function calling mechanism, thus, improves the performance. However, it also increases the code size, leads to increasing the percentage of the cache miss and reduce the performance as well. Therefore, only define a function inside its class definition if the function is small.

2. Define constructors that can take a single argument as explicit

By default, a constructor invoked by a single argument acts as an implicit conversion from its argument type to its type. Implicit is usually found in copy assignment and function call.

void my_fnc(Date);

class Date {
	Date (int dd);
}

void f() {
	my_fnc(4); //OK.implicit
    my_fnc(Date(4));//OK.explicit
}

In this case, 4 will be implicitly converted to Date and used in my_fnc. This may be the behavior you expect. Therefore, declare a constructor that can be called with a single argument explicit.

class Date {
	explicit Date (int dd =0, int mm =0, int yy =0);
}

3. Default arguments or in-class initializercan save your time

If you want to set default values for your data members, ease the pain of defining many constructors each with a different number of arguments, there are two ways to do that:

//1. Set default argument for the constructor
class Date {
	Date (int dd =0, int mm =0, int yy =0);
}
//2. In-class initializer
class Date {
	int dd =0;
    int mm =0;
    int yy =0;
	Date (int d, int m, int y);
}

4. Prefer member initialization over assignment in a constructor

Data member of a class can be initialized by:

//Initialization
class Date {
	int dd, mm, yy;
    A aa;
	Date (int d, int m, int y, int a)
    : dd{d}, mm{m}, yy {y}, aa{a} {}
}
//Assignment
class Date {
	int dd, mm, yy;
    A aa;
	Date (int d, int m, int y) {
    	dd = d; mm = m; yy = y;
        aa = A(a);
    }
}

They look the same, but there are reasons you should prefer the initialization over the assignment.

If your data member is const. You have to use initialization since you cannot assign a value to a const variable.
If your data member is of a class does not have a default constructor. The first method is the only way to go.
Reference data member. If your data member is a reference. You cannot define it then assign a value to it later. So, the first method is the only one will work.
If you inherit a Base class, it can make sure the Base class is properly initialized before your class. Otherwise, your base class will be initialized by the default constructor.
Performance boost. In the assignment method, if your member is a class, it actually is initialized by the default constructor first. Then you assign another value to it. This, of course, does excessive works.

5. If a method does not need to modify data, declare it as const function

A const function cannot modify any data in the class, so this is a basic rule to ensure your method does not do anything unexpected. It is important if you work in a large team.

6. If a class has a virtual function, it needs a virtual destructor

This code ensures the case when a Derived class’ object is referred by a pointer of its Base class, the destructor of the Derived class will be called. Without the virtual declaration, it may only call the destructor of Base class and the resources may be leaked.

7. If you have an initializer-List Constructor, remember when it will be called

If you define a container, you should have a constructor that accepts initializer_list. That way you can initialize your class with a list of value just like a vector:

vector<int> v(3);//vector with one 3 zero elements
vector<int> v(); // empty vector
vector<int> v{}; // empty vector
vector<int> v{3};//initializer-list called. vector with one element
vector<int> v{3,4,5};//initializer-list called. vector with 3 elements 3, 4 and 5

However, if you have one, make sure you remember when it will be called:

If either a default constructor (no argument) or an initializer-list constructor could be invoked, prefer the default constructor.
If both an initializer-list constructor and an ‘ordinary constructor’ could be invoked, prefer the initializer-list constructor. This rule is necessary to avoid different resolutions based on different numbers of elements.

8. Remember to copy the Bases when defining copy/move constructor/assignment

In these cases, consider the base class as a member of your class, remember to initialize it. Otherwise, it will be initialized by the default constructor.

//B1 and B2 is base classes of D
D(const D& a) :B1{a}, B2{a}, m1{a.m1}, m2{a.m2} {}

9. Consider before you make a default constructor for your class

The default constructor is necessary in many cases, such as, when objects of your class will be used as elements of a container… But not every time, defining a default constructor is a good idea. If a class inherit your class, users of your class may forget to properly initialize it as the case above.

10. Remember when you have default operations

Default operations include constructor, destructor, copy and move assignment can be autogenerated for your class. The suppression of these operations will happen when:

If the programmer declares any constructor for a class, the default constructor is not generated for that class.
If the programmer declares a copy operation, a move operation, or a destructor for a class, no copy operation, move operation, or destructor is generated for that class.

Otherwise, you can control the suppression behavior by:

class A {
	//Suppress the default behavior
    A()= delete;
	//Explicit default
    A(const A&) = default;
}

By default, the default constructor is a member-wise constructor, it will call the default constructor of all data members. Therefore, it will fail if a data member doesn’t have its default constructor. The default copy operator is the shallow copy, so be careful if it is the behavior that you expect.

Jekyll custom plugins in Github page

2018-06-18T14:42:06+09:00

Github page, which uses Jekyll as it static site generator, is a very convenient way to host a personal website. However, Github only supports some official plugins they listed, to use other plugins, you have to build the site yourself. In this post, I would like to discuss their difficulties and how to overcome them.

Problems

The first problem is, of course, Github does not support custom plugins and they have a valid point to do so - security. Allowing arbitrary code to run on their server is somewhat vulnerable and they don’t want to do so. Hence, I do not expect them to change that anytime soon. However, some plugins are really helpful, in my case, I need plugins to generate category, month archive and tag archive file automatically instead of the painful official way to generate each of them manually as guided when you add any tag or category.

To overcome this, the only way is to build the website your own and upload the static site to Github. I move all of my site source code to a src/ folder and build the static site to the main directory. However, the second problem comes in when you cannot set the destination folder including the source folder. Because of these tricky things, I have to use a quite complex solution as bellowing.

My solution

Step 1.

To keep the code clean, I don’t want my development code and generated one to be mixed and also I don’t want my commit history to be full of built logs, I create a branch named develop and set it to the default branch, this branch will how the source code. The master branch will hold the static site. So, now I have two branches like this:

branches:
-develop (default branch)
-master (hold static site)

Step 2.

In the develop branch, I add a couple of files, the dirrectory look like this:

-src/  (to hold website jekyll code)
-build_Site.sh (to build the webiste for development)
-clean.sh (clean the built site)
-.gitignore (ignore the built files) 

In .gitignore, I would like to exclude all files generated in the build process:

#ignore temporary files
_site
.sass-cache
src/*.gem
src/*.sublime-project
src/*.sublime-workspace
src/.bundle
src/.DS_Store
src/.jekyll-metadata
src/.sass-cache
src/_asset_bundler_cache
src/_site
src/codekit-config.json
src/Gemfile.lock
src/node_modules
src/npm-debug.log*

In clean.sh, all ignored files is deleted.

#!/bin/sh
git clean -fdX

In build_Site.sh, I build the jekyll site to verify in the development process:

#!/bin/sh
./clean.sh
cd src
bundle exec jekyll build --destination ../_site
cd ../_site
jekyll serve

Note that, the built site is in _site directory so you should run jekyll serve there.

Step 3.

In the master branch, my home directory looks like this:

-src/ (will be updated from develop branch)
- build_Site.sh
- .gitignore (ignore the src folder)
- .nojekyll (avoid jekyll to build this directory)
- _config.yml (if .nojekyll does not work, exclude src folder from being built)
- files generated by Jekyll

my build_Site.sh is as bellowing. Other files are as simple as they are described.

#!/bin/sh
rm -r src
git checkout develop src/
cd src
bundle exec jekyll build --destination ../_site

cd ..
rsync -av --delete --exclude _site/ --exclude src/ --exclude .git/ --exclude .gitignore --exclude .nojekyll --exclude _config.yml --exclude build_Site.sh _site/ ./
rm -r _site

All my code can be viewed in the source code of this website. If you have any better solution to work around with this, please leave me a comment.