24 September 2011 Comments Off

Power up C++ with the Standard Template Library: Part I

By DmitryKorolev

(collected from Topcoder)

Containers
Before we begin
Vector
Pairs
Iterators
Compiling STL Programs
Data manipulation in Vector
String
Set
Map
Notice on Map and Set
More on algorithms
String Streams
Summary

Perhaps you are already using C++ as your main programming language to solve TopCoder problems. This means that you have already used STL in a simple way, because arrays and strings are passed to your function as STL objects. You may have noticed, though, that many coders manage to write their code much more quickly and concisely than you.

Or perhaps you are not a C++ programmer, but want to become one because of the great functionality of this language and its libraries (and, maybe, because of the very short solutions you’ve read in TopCoder practice rooms and competitions).

Regardless of where you’re coming from, this article can help. In it, we will review some of the powerful features of the Standard Template Library (STL) – a great tool that, sometimes, can save you a lot of time in an algorithm competition.

The simplest way to get familiar with STL is to begin from its containers.

Containers
Any time you need to operate with many elements you require some kind of container. In native C (not C++) there was only one type of container: the array.

The problem is not that arrays are limited (though, for example, it’s impossible to determine the size of array at runtime). Instead, the main problem is that many problems require a container with greater functionality.

For example, we may need one or more of the following operations:

  • Add some string to a container.
  • Remove a string from a container.
  • Determine whether a string is present in the container.
  • Return a number of distinct elements in a container.
  • Iterate through a container and get a list of added strings in some order.

Of course, one can implement this functionality in an ordinal array. But the trivial implementation would be very inefficient. You can create the tree- of hash- structure to solve it in a faster way, but think a bit: does the implementation of such a container depend on elements we are going to store? Do we have to re-implement the module to make it functional, for example, for points on a plane but not strings?

If not, we can develop the interface for such a container once, and then use everywhere for data of any type. That, in short, is the idea of STL containers.

Before we begin
When the program is using STL, it should #include the appropriate standard headers. For most containers the title of standard header matches the name of the container, and no extension is required. For example, if you are going to use stack, just add the following line at the beginning of your program:

#include <stack>

Container types (and algorithms, functors and all STL as well) are defined not in global namespace, but in special namespace called “std.” Add the following line after your includes and before the code begin:

using namespace std;

Another important thing to remember is that the type of a container is the template parameter. Template parameters are specified with the ‘<’/’>’ “brackets” in code. For example:

vector<int> N;

When making nested constructions, make sure that the “brackets” are not directly following one another – leave a blank between them.

vector< vector<int> > CorrectDefinition;
vector<vector<int>> WrongDefinition; // Wrong: compiler may be confused by 'operator >>'

Vector
The simplest STL container is vector. Vector is just an array with extended functionality. By the way, vector is the only container that is backward-compatible to native C code – this means that vector actually IS the array, but with some additional features.

 vector<int> v(10);
 for(int i = 0; i < 10; i++) {
      v[i] = (i+1)*(i+1);
 }
 for(int i = 9; i > 0; i--) {
      v[i] -= v[i-1];
 }

[...]

Tags: , ,
7 August 2011 Comments Off

Let’s Learn STL (Rerefences)

The Standard Template Libraries (STL’s) are a set of C++ template classes to provide common programming data structures and functions such as doubly linked lists (list), paired arrays (map), expandable arrays (vector), large string storage and manipulation (rope), etc. The STL library is available from the STL home page. This is also your best detailed reference for all of the STL class functions available.

  • From YoLinux and Wiki
    • Sequences:
      • vector: (this tutorial) Dynamic array of variables, struct or objects. Insert data at the end.
      • deque: Array which supports insertion/removal of elements at beginning or end of array
      • list: (this tutorial) Linked list of variables, struct or objects. Insert/remove anywhere.
    • Associative Containers:
      • set (duplicate data not allowed in set), multiset (duplication allowed): Collection of ordered data in a balanced binary tree structure. Fast search.
      • map (unique keys), multimap (duplicate keys allowed): Associative key-value pair held in balanced binary tree structure.
    • Container adapters:
      • stack LIFO
      • queue FIFO
      • priority_queue returns element with highest priority.
    • String:
      • string: Character strings and manipulation
      • rope: String storage and manipulation
    • bitset: Contains a more intuitive method of storing and manipulating bits.
  • Operations/Utilities:
    • iterator: (examples in this tutorial) STL class to represent position in an STL container. An iterator is declared to be associated with a single container class type.
    • algorithm: Routines to find, count, sort, search, … elements in container classes
    • auto_ptr: Class to manage memory pointers and avoid memory leaks.
Tags: ,
27 February 2011 Comments Off

Power up C++ with the Standard Template Library: Part II: Advanced Uses

Power up C++ with the Standard Template Library: Part II: Advanced Uses

We will love to quote Topcoder’s STL tutorial by DmitryKorolev here:

“Creating Vector from Map
As you already know, map actually contains pairs of element. So you can write it in like this:

 map<string, int> M;
 // ...
 vector< pair<string, int> > V(all(M)); // remember all(c) stands for
 (c).begin(),(c).end()

Now vector will contain the same elements as map. Of course, vector will be sorted, as is map. This feature may be useful if you are not planning to change elements in map any more but want to use indices of elements in a way that is impossible in map.

Copying data between containers
Let’s take a look at the copy(…) algorithm. The prototype is the following:

 copy(from_begin, from_end, to_begin);

This algorithm copies elements from the first interval to the second one. The second interval should have enough space available. See the following code:

 vector<int> v1;
 vector<int> v2; 

 // ... 

 // Now copy v2 to the end of v1
 v1.resize(v1.size() + v2.size());
 // Ensure v1 have enough space
 copy(all(v2), v1.end() - v2.size());
 // Copy v2 elements right after v1 ones

Another good feature to use in conjunction with copy is inserters. I will not describe it here due to limited space but look at the code:

 vector<int> v;
 // ...
 set<int> s;
 // add some elements to set
 copy(all(v), inserter(s));

The last line means:

 tr(v, it) {
// remember traversing macros from Part I
      s.insert(*it);
 }

But why use our own macros (which work only in gcc) when there is a standard function? It’s a good STL practice to use standard algorithms like copy, because it will be easy to others to understand your code.”

Full tutorial here: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=standardTemplateLibrary2

4 January 2011 Comments Off

How Install C/C++ Compiler by Max Berger

Max Berger, who is currently a Software Developer at Amazon EU, has written a nice tutorial about installing C/C++ compiler. Here we quote this tutorial:

“(…)Setting up a compiler

Unfortunately Eclipse only provides the Integrated Development Environment (IDE) but it is missing the actual compiler. To install a compiler, please follow the instructions for your operating system.

Windows compiler

Windows doesn’t come with a build-in compiler. You could try to install Visual Studio, but it is tricky to get that working with Eclipse. Therefore we will install MSYS. MSYS is part of the MinGW suite, which provides free development tools for Windows.

You will have to follow these 4 steps:

  • Download and install MinGW
  • Download and install MSYS
  • Set your path environment variable
  • Restart Eclipse if it was started.

MinGW

First, you need to download MinGW. You can either click through the websites mentioned above or go directly to the MinGW download area. Look for the Package “Automated MinGW Installer”. There, download the file ending in .exe. The file name should be something like “MinGW-5.1.4.exe”. You can also download MinGW Version 5.1.4 from the link given here.

You may also download an older version, and follow the instructions given in the section called “Older Instructions”:

Most of the options in the MinGW 5 installer are pretty straightforward. I will point out some of the more tricky options.

The first one of such options is which “MinGW” package to install. Any of those should work just fine, but I would recommend Current.

Figure 1. MinGW 5 install

MinGW 5 install

MinGW will ask which components to install. Either select All or at least make sure that you have the g++ compiler checked. This is needed for C++ support.

[...]

5 December 2010 Comments Off

Great Collection of C++ Programming Books!

C++ book for download -

http://www.pragsoft.com/download.html#CppBook
C++ Programming is provided as a zip file which includes the chapters (in Word 6 format) and the sample programs (in DOS text format):

Free Online C/C++ Books -

http://www.programmertutorials.com/redirect.php?id=62
A collection of free online C/C++ programming books. Topics range from beginner to advanced level.

Thinking in C++ -

http://www.mindview.net/Books/TICPP/ThinkingInCPP2e.html
A superb resource for learning C++ , perhaps the best online.

C++ How to Program 4/e -

http://www.deitel.com/books/cppHTP4/
C++ How to Program, 4/e introduces the fundamentals of object-oriented programming … Source Code

C++ Books -

http://www.programmershelp.co.uk/c%2B%2Bbooks.php
Some top quality books here for learning or enhancing your C++ skills. Essential C++ and Beginners guide to C++ are highly recommended

C++: A Dialog -

http://www.steveheller.com/cppad/Output/dialogTOC.html
Programming with C++ standard library.
Tags: ,
30 November 2010 Comments Off

Beginning C Programming in Linux

Don’t ask a lot to begin C programming in Linux. Just grab your tools and start small. This time, I just wanna show you how to start C programming in linux. You can use any Linux distro. However, if you are beginner, just follow me using Ubuntu Linux.

1. Install the required packages.
First of all, you have to make sure that you have C compiler to compile your code. In linux, we use “gcc – GNU project C and C++ compiler”.

In Debian, Ubuntu and it’s family distro, all the basic programming tools for C programming can be found in build-essential package. Use this command to install this package:

$ sudo apt-get install build-essential

2. Write your first program
Now, after installing the required package, we can start coding our first program. As usual, you may start with a “Hello World” program.

Create new project directory
Under your home directory, you may start creating your project directory to begin with. In this example, I’m calling it as myhello:

$ mkdir myhello

Then, get into our project directory:

$ cd myhello

Now, create our hello.c file. You may follow this example “hello world” code or be imaginative to modified it as you like. Experiments to see what is possible to modify in this code:

#include <stdio.h>

int main() {

printf("Hello My friend, Let's do C programming\n");
}

3. Compile your program.
To compile your first linux C program, launch your terminal and go to current directory where you put your hello.c code. Then, run this command:

$ gcc hello.c -o hello

After that, you will have an executable file called hello in this directory. Congratulations! you have created your first C program in linux. You can now, execute this program using this command:

$ ./hello

The output will be printed on your screen. You can add more stuff and experiments. Until next time, I hope you enjoy this. Happy coding…

Collected from:://coderstalk.blogspot.com/