fast I/O in C/C++

There many ways to do input/output in C/C++. Some are slow, some are fast and some can be very fast. Here I’ll be discussing some of these methods.

Many a times during competetive programming you come across the warning “Careful – large input/output“. Now what exactly does this means?
This basically means that you have to use an optimized code for your reading/writing to the standard input/output to stay inside the tighter time constraints of the problem. So let’s get going and explore the different methods to optimize your I/O in C/C++.

All the code can be found here: GitHub.

First one is the basic method that you guys must already be using. This is based on cin/cout methods of the iostream library. It is the most basic method and does not require you to specify the type of input you are expecting, but, is extremely slow.

#include <iostream>
#include <string>
#include <sstream>

using namespace std;

int main() {
	/* integer or any integer like */
	int integer;
		cin>>integer;
		cout<<integer<<endl;

	/* character string */
	char charstring[100];
		cin>>charstring;	// stops input after a "space"
		cout<<charstring<<endl;

		cin.getline(charstring, 100);	// stops after 100 character or eof whichever comes first
		cout<<charstring<<endl;

	string strstring;
		cin>>strstring;		// stops input after a "space"
		cout<<strstring<<endl;

		getline(cin, strstring);	// stops after eof or '\n', whichever comes first
		cout<<strstring<<endl;

	/* safest way to get an integer (but very slow) - taken from cpluspls.com */
	int number = 0;
	string input;
	while(true) {
		getline(cin, input);

		stringstream myStream(input);
		if(myStream>>number)
			break;
	}

	/* Safest way to get a single character */
	char singlechar = {0};
	while(true) {
		getline(cin, input);

		if(input.length() == 1){
			singlechar = input[0];
			break;
		}
	}
}

The second method is based on the simple printf/scanf functions of stdio.h library for C. These are much faster than the above method and can be easily used in competetive programming for a decent time limit. These are multi-thread safe as they lock the file before writing.
Detailed description of the stdio.h library you can refer to here.

#include <cstdio>
#include <string>

int main() {
	/* integer I/O */
	int a;
	scanf("%d", &a);
	printf("%d\n", a);

	/*
        Other format specifiers.
        %d, %i = signed integer
        %u = unsigned integer
        %l = prefix for long
        %f = signed floating point
        %e = signed scientific
        %c = single character
	*/

	/* sting I/O */
	char charstring[100];
	scanf("%s", charstring);    // only till the first white space is stored
	printf("%s\n", charstring);

	scanf("%[^\n]s", charstring);   // sets th delimeter to be "new line"
	printf("%s\n", charstring); // thus whole line is read until a \n is observed
								// does not eliminate \n from the input stream

	gets(charstring);
	printf("%s\n", charstring);
}

This method is very fast than the last method and used unlocked versions of the above functions used. I have written the code to scan integer and a string. For others you can easily write your function referring the below code. These are NOT multi-thread safe. Should be used in caution. But, in competetive programming plateforms, one program is already separated from others, so can easilt be used for better I/O in competetive programming which have even tighter time constraints.

#include <cstdio>

inline void fastRead_int(int &x) {
    register int c = getchar_unlocked();
    x = 0;
    int neg = 0;

    for(; ((c<48 || c>57) && c != '-'); c = getchar_unlocked());

    if(c=='-') {
    	neg = 1;
    	c = getchar_unlocked();
    }

    for(; c>47 && c<58 ; c = getchar_unlocked()) {
    	x = (x<<1) + (x<<3) + c - 48;
    }

    if(neg)
    	x = -x;
}

inline void fastRead_string(char *str)
{
    register char c = 0;
    register int i = 0;

    while (c < 33)
        c = getchar_unlocked();

    while (c != '\n') {
        str[i] = c;
        c = getchar_unlocked();
        i = i + 1;
    }

    str[i] = '\0';
}

int main()
{

  int n;
  char s[100];

  fastRead_int(n);
  	printf("%d\n", n);

  fastRead_string(s);
  	printf("%s\n", s);
  return 0;
}

There is another method I came across a solution in one of the problems on codechef. I haven’t tested it’s performance, but, his solution had the lowest timing with the same logic for the actual problem. So, I am assuming this gives a better performance for I/O. You can download the code here.
The solution referrenced is this.

I’ll come up with more updates on the same topic.

Ubuntu (12.04) upstart (at boot) services

Creating your own ubuntu upstart service:

  • Create a shell script. (Name it whatever you want. Here I am assuming it to be “autorun.sh”)
    vi autorun.sh
    
  • Copy the shell script to /etc/init.d/
    sudo cp autorun.sh /etc/init.d/autorun.sh
    
  • Make the script executable.
    sudo chmod +x /etc/init.d/autorun.sh
    
  • Update the upstart table of ubuntu by creating symbolic links.
    sudo update-rc.d autorun.sh defaults
    
  • Done.

To boot an already existing script:

  • Update the upstart table of ubuntu by creating symbolic links.
    sudo update-rc.d service_name defaults
    
  • Enable a disabled upstart service
    sudo update-rc.d service_name enable
    

To remove a script from upstart:

  1. (option-1)
    update the table and remove the script(not necessary)
    sudo update-rc.d -f autorun.sh remove
    sudo rm /etc/init.d/autorun.sh (optional)
    
  2. (option-2)
    Disable the service from boot
    sudo update-rc.d -f autorun.sh disable
    
  3. (option-3)
    if there is a configuration file for the script in /etc/init/
    sudo echo 'manual' | /etc/init/scriptname.override
    sudo update-rc.d -f scriptname remove
    

Reference: ubuntu upstart cookbook

Download Facebook Album

Here, I am going to tell you a simple method to download an entire facebook album with just one click.

It is an automated process using a small JavaScript code. All you have to do is:

  • Go to: https://github.com/chirag1992m/facebookAlbumDownloader/blob/master/js/downloader_min.js
  • Select the whole code, and copy it your clipboard.
  • Now, Open the facebook album you want to download.
  • Scroll down so that you can see all the thumbnails of all the photographs present in the album.
  • Copy the js script in the file “js/downloader_min.js”
  • In your browser’s address bar, paste the code and press enter.
  • Voila, all your photos start to download in one click 😉
  • NOTE: You may have to “allow” “this site is trying to download multiple files at once”.

GitHub for beginners (debian/ubuntu/linux)

Just yesterday I was trying to setup my first github repository, but it wasn’t that easy I thought it would be. YES I know, github has a support page, but  it didn’t seemed to work for me.

So here, I’ll give you a little introduction on the initial setup of git on your local machine and setting up of your cloud repository on github. This tutorial is for debian/ubuntu users.

GIT
Git is an extremely fast, efficient, distributed version control system ideal for the collaborative development of software.

GITHUB
GitHub is the best way to collaborate with others. Fork, send pull requests and manage all your public and private git repositories. In simple terms, it is a cloud storage for all your repositories, be it local or distributed.

SETTING UP OF GIT REPOSITORY ON LOCAL MACHINE
NOTE: GIT CAN BE USED WITH/WITHOUT GITHUB. GIT is a subversion control system which can just be used solely on your local machine without using github at all.

First we’ll setup git on the local machine and create a local repository.
Install GIT using the command on your terminal:

sudo apt-get install git

This will install git on your machine. Now you we’ll start by doing a bit of configuration. Every commit you make will have your name and email address to identify the ‘owner’ of the commit, so you should start by giving it those values. To do so, run these commands:

git config --global user.name "your name"
git config --global user.email "your@email.com"

So Git knows who you are now. Let’s work upon the local repository we were talking about,  just imagine you are creating a simple PHP web app. (Of course, the bigger the project, the brighter Git shines, but we’re just learning the tools, right?) We’ve got an empty directory called ‘project’. Add all your project files in the new created empty directory. This is the base directory for your repository. To get started with your very own repository, first change your current working directory to the base repository directory and initialize git. Type:

cd /path/to/project/
touch README.md
git init
git add *
git commit -m "commit message"
git status

Let me explain each command I typed:

  • cd /path/to/project/: This just changes your current working directory to the project directory for setting up of repository.
  • touch README.md: README.md is a file used by github as a default readme file. So we create an empty file. This step is not necessary, but it surely makes you ready for uploading your repository on github.
  • git init: this initializes your git repository by making a “.git” directory as a sub-directory to your project directory. This is the magic black box used by git where all the different branches, logs and commits are kept.
  • git add *: This adds all the files to be committed to a staging area. The staging area is a spot to hold files for your next commit; maybe you don’t want to commit all your current changes, so you put some in the staging area. “*” is used to add all the files. You can be specific in adding files. Just use ‘*.js’ to only add javascript files.
    you can remove files from the staging area and subsequently from your commit using the command: git rm file_name
  • git commit -m “commit message”: It finally commits the staged files and logs the given commit message for you to recognize your commit later on when you want to rollback or branch.
    For skipping the staging area and updating all the already committed files use:

    git commit -am "commit updated"
  • git status: The git status command allows you to see the current state of your code. We’ve just done a commit, so git status will show us that there’s nothing new. If you continue working on your imaginary project, you’ll see that the status changes. If you have any new files, it will show you the files under “untracked files.” or if you have made changes to the files already committed, it will show you the files under “changed but not updated”. Again running the add and commit commands will add these new/changed files to a new commit.

You can checkout all the available commands/features on git here: http://git-scm.com/book/commands

you can similarly setup more repositories on your local machine. 🙂

SETTING UP GITHUB REPOSITORY

Git is a great way to share code with others and work on projects together. There are a number of Git repository hosting sites. We’ll just look at one.
First I expect you to make an account on GitHub here: https://github.com/

When you’re done with it, create a cloud repository. Instructions are given here: https://help.github.com/articles/creating-a-new-repository

So when your’re done with all this, you can go further and start committing your code on the cloud. For committing your code online, you will need a SSH public key, so let’s create that right now! Open your terminal and type:

cd ~
ssh-keygen -t rsa -C "your@email.com"

This creates a SSH public key to be used in connecting to GitHub. The t option assigns a type, and the C option adds a comment, traditionally your email address. You’ll then be asked where to save the key; just hitting enter will do (that saves the file to the default location). Then, just hit enter again twice when it asks you for a pass-phrase (pass-phrase is just a headache. If you type one, you will have to type one everytime you connect to github).

The key is stored in the default directory which is ~/.ssh/
Copy the contents of the public key. Here’s how you can do it from the terminal:

sudo apt-get install xclip

cd ~/.ssh/
cat id_rsa.pub | xclip

This copies the content of your public key to your clipboard. If you directly copy it using a text editor, remember not to add any newlines or white-space.
Now go to your GitHub account. Go to account settings. Click on SSH keys tab and finally click on add SSH key. Copy the contents of the clipboard in the key section. You can give any title you want. Now try connecting to the github server using SSH. Just type in your terminal:

ssh -vT git@github.com

You should be able to connect to the github server. If not, and getting an agent forwarding error you may have to unset SSH_AUTH_SOCK. You can read more about ssh and public keys and agent forwarding here:
http://www.unixwiz.net/techtips/openssh.html
http://www.unixwiz.net/techtips/ssh-agent-forwarding.html

To unset the environment variable:

unset SSH_AUTH_SOCK

Try and connect to the github server once again. If still not able to connect, use the github help: https://help.github.com/articles/

Once you are able to contact the github server, you can start uploading your commits to your cloud repository. Here’s how you can do that:

cd /path/to/project/
git remote add origin git@github.com:username/cloud_repository_name.git
git push origin master

This pushes the master branch to the origin remote. Now you’re project is available to the world! Head back to your project page and see your project. If you are getting an error in uploading the, again try connecting to the github server using ssh and debug the connection.

You might be on the other end of a project: you’re a contributor instead of the owner. When the owner pushes a new commit to the repository, you can use git pull to get the updates. Git pull is actually a combo tool: it runs git fetch (getting the changes) and git merge (merging them with your current copy).

git pull

C++: incomplete type and cannot be defined

A very confusing error just now:
error: aggregate ‘std::ofstream out’ has incomplete type and cannot be defined

from simple code:
std::ofstream out;

And the similar one:
error: variable ‘std::ofstream out’ has initialiser but incomplete type

from this code:
std::ofstream out(fname.c_str(),std::ios_base::app);

Using this didn’t help:
#include <iostream>

Using this also didn’t help:
#include <ofstream>

That was confusing me most, but now I see I’ve been getting “error: ofstream: No such file or directory” and I was missing it in the noise of other warnings and errors.

The solution was simple:
#include <fstream>
Yes, a very simple solution, but google wasn’t helping. If it had been saying “ofstream is not a member of std” I’d have known I was missing a header file; a strange error message has you looking in other places. (I guess another std header file is doing a forward declaration for ofstream, which is why we get “incomplete type”.)