Generic algorithms

Algorithms are at the core of computing. To be able to write an algorithm once and for all to work with any type of sequence makes your programs both simpler and safer. The ability to customize algorithms at runtime has revolutionalized software development.

The subset of the standard C++ library known as the Standard Template Library (STL) was originally designed around generic algorithms?code that processes sequences of any type of values in a type-safe manner. The goal was to use predefined algorithms for almost every task, instead of hand-coding loops every time you need to process a collection of data.
Stream iterators
Like any good software library, the Standard C++ Library attempts to provide convenient ways to automate common tasks. We mentioned in the beginning of this tutorial that you can use generic algorithms in place of looping constructs. So far, however, our examples have still used an explicit loop to print their output. Since printing output is one of the most common tasks, you would hope for a way to automate that too.

That?s where stream iterators come in. A stream iterator allows you to use a stream as either an input or an output sequence. To eliminate the output loop in the CopyInts2.cpp program, for instance, you can do something like the following.

In this example we?ve replaced the output sequence b in the third argument to remove_copy_if( ) with an output stream iterator, which is an instance of the ostream_iterator class template declared in the header. Output stream iterators overload their copy-assignment operators to write to their stream. This particular instance of ostream_iterator is attached to the output stream cout. Every time remove_copy_if( ) assigns an integer from the sequence a to cout through this iterator, the iterator writes the integer to cout and also automatically writes an instance of the separator string found in its second argument, which in this case contains just the newline character.
It is just as easy to write to a file instead of to cout, of course. All you have to do is provide an output file stream instead of cout:

An input stream iterator allows an algorithm to get its input sequence from an input stream. This is accomplished by having both the constructor and operator++( ) read the next element from the underlying stream and by overloading operator*( ) to yield the value previously read. Since algorithms require two pointers to delimit an input sequence, you can construct an istream_iterator in two ways, as you can see in the program that follows.

The first argument to replace_copy_if( ) in this program attaches an istream_iterator object to the input file stream containing ints. The second argument uses the default constructor of the istream_iterator class. This call constructs a special value of istream_iterator that indicates end-of-file, so that when the first iterator finally encounters the end of the physical file, it compares equal to the value istream_iterator( ), allowing the algorithm to terminate correctly. Note that this example avoids using an explicit array altogether.
Algorithm complexity
Using a software library is a matter of trust. You trust the implementers to not only provide correct functionality, but you also hope that the functions execute as efficiently as possible. It?s better to write your own loops than to use algorithms that degrade performance.

To guarantee quality library implementations, the C++ standard not only specifies what an algorithm should do, but how fast it should do it and sometimes how much space it should use. Any algorithm that does not meet the performance requirements does not conform to the standard. The measure of an algorithm?s operational efficiency is called its complexity.

When possible, the standard specifies the exact number of operation counts an algorithm should use. The count_if( ) algorithm, for example, returns the number of elements in a sequence satisfying a given predicate. The following call to count_if( ), if applied to a sequence of integers similar to the examples earlier in this tutorial, yields the number of integer elements that are greater than 15:

Since count_if( ) must look at every element exactly once, it is specified to make a number of comparisons exactly equal to the number of elements in the sequence. Naturally, the copy( ) algorithm has the same specification.

Other algorithms can be specified to take at most a certain number of operations. The find( ) algorithm searches through a sequence in order until it encounters an element equal to its third argument:

It stops as soon as the element is found and returns a pointer to that first occurrence. If it doesn?t find one, it returns a pointer one position past the end of the sequence (a+SIZE in this example). Therefore, find is said to make at most a number of comparisons equal to the number of elements in the sequence.

Sometimes the number of operations an algorithm takes cannot be measured with such precision. In such cases, the standard specifies the algorithm?s asymptotic complexity, which is a measure of how the algorithm behaves with large sequences compared to well-known formulas. A good example is the sort( ) algorithm, which the standard says takes ?approximately n log n comparisons on average? (n is the number of elements in the sequence) . Such complexity measures give a ?feel? for the cost of an algorithm and at least give a meaningful basis for comparing algorithms. As you?ll see, the find( ) member function for the set container has logarithmic complexity, which means that the cost of searching for an element in a set will, for large sets, be proportional to the logarithm of the number of elements. This is much smaller than the number of elements for large n, so it is always better to search a set by using its find( ) member function rather than by using the generic find( ) algorithm. […]

Arrays in C Programming

What is an Array in C Language?
An array in C Programing Language can be defined as number of memory locations, each of which can store the same data type and which can be references through the same variable name.

An array is a collective name given to a group of similar quantities. These similar quantities could […]

Functions in C Programming

What is a Function?
A function is a block of code that has a name and it has a property that it is reusable i.e. it can be executed from as many different points in a C Program as required.

Function groups a number of program statements into a unit and gives it a name. This unit […]

Input and Output

First of all we need to learn about streams in C Programming. All C Programming input and output is done with streams, no matter where input is coming from or where output is going to. This is the standard way of handling all input and output and has definite advantages for the programmer. A library package has been evolved which is known as known as the ?Standard I/O Library? which is used in any C program by using stdio.h header. Of course, now that we know its importance, it is essential that we understand what streams are and how they work. First, however, we need to understand exactly what the terms input and output mean in context of C.
The C programming language provides input and output support using library functions, which gives an advantage to system designers to tailor their input and output on their own.
What Exactly Is Program Input/Output?
A C program keeps data in random access memory (RAM) while executing. This data is in the form of variables, structures, and arrays that have been declared by the program. The question is where did this data come from, and what can the program do with it?

Data can come from some location external to the program. Data moved from an external location into RAM, where the program can access it, is called input. The keyboard and disk files are the most common sources of program input.
Data can also be sent to a location external to the program; this is called output. The most common destinations for output are the screen, a printer, and disk files.

Input sources and output destinations are collectively referred to as devices. The keyboard is a device; the screen is a device, and so on. Some devices (the keyboard) are for input only, others (the screen) are for output only, and still others (disk files) are for both input and output. Whatever the device, and whether it’s performing input or output, C carries out all input and output operations by means of streams.
What is a Stream?
A stream is a sequence of characters. More exactly, it is a sequence of bytes of data. A sequence of bytes flowing into a program is an input stream; a sequence of bytes flowing out of a program is an output stream. By focusing on streams, we don’t have to worry as much about where they’re going or where they originated.

The major advantage of streams, therefore, is that input/output programming is device independent. Programmers don’t need to write special input/output functions for each device (keyboard, disk, and so on). The program sees input/output as a continuous stream of bytes no matter where the input is coming from or going to.

Every C stream is connected to a file. In this context, the term file doesn’t refer to a disk file. Rather, it is an intermediate step between the stream that the program deals with and the actual physical device being used for input or output. For the most part, the beginning C programmer doesn’t need to be concerned with these files, because the details of interactions between streams, files, and devices are taken care of automatically by the C library functions and the operating system.
Modes of Streams in C Language
C streams can be divided into two modes: text and binary.
Text Stream
A text stream consists only of characters, such as text data being sent to the screen. Text streams are organized into lines, which can be up to 255 characters long and are terminated by an end-of-line, or newline, character. Certain characters in a text stream are recognized as having special meaning, such as the newline character.
Binary Stream
A binary stream can handle any sort of data, including, but not limited to, text data. Bytes of data in a binary stream aren’t translated or interpreted in any special way; they are read and written exactly as-is. Binary streams are used primarily with disk files.
Predefined Streams
ANSI C has three predefined streams, also referred to as the standard input/output files. If you’re programming for an IBM-compatible PC running DOS, two additional standard streams are available to you. These streams are automatically opened when a C program starts executing and are closed when the program terminates. The programmer doesn’t need to take any special action to make these streams available. Table lists the standard streams and the devices they normally are connected with. All five of the standard streams are text-mode streams.

The five standard streams.

NAME
STREAM
DEVICE

stdin
Standard Input
Keyboard

stdout
Standard Output
Screen

stderr
Standard Error
Screen

stdprn*
Standard Printer
Printer (LPT1)

stdaux*
Standard Auxiliary
Serial Port (COM1)

(*) Supported only under DOS

Whenever we have to use the printf() or puts() functions to display text on-screen, we use the stdout stream. Likewise, when we use gets() or scanf() to read keyboard input, we use the stdin stream. The standard streams are opened automatically, but other streams, such as those used to manipulate information stored on disk, must be opened explicitly.

Loops and Decision – if else, for and while

C language programes are executed in a sequence, but we can control the execution of C program by using any control mechanism by which we can compare things and come to a decision. This involves using some operations called Relational Operators, conditional statements called if-else and loops. We have fundamental operators to compare two […]

Microsoft Direct-X Programming

Before the release of Windows 95, most games were developed and released for
the Microsoft Disk Operating System (DOS) platform, usually using something
like DOS4GW or some other 32-bit DOS extender to obtain access to 32-bit protected
mode. Windows 95, however, seemed to signal the beginning of the end of the
DOS prompt. Game developers began to wonder how […]

By |Tutorials|0 Comments

C# Programming Tutorials

In June 2000, Microsoft announced both the .NET platform and a new programming
language called C#. C# is a simple, modern, object oriented, and type-safe programming
language derived from C and C++. C# (pronounced “C sharp”) is firmly
planted in the C and C++ family tree of languages, and will immediately be familiar
to C and C++ programmers. C# […]

By |Tutorials|0 Comments

C Programming Tutorials

The C programming language is a general programming language. It can be used to program anything, like computers, embedded systems, operating systems and computer applications. It is a structured and procedural programming language. In the beginning it was developed for UNIX, for system development but due to its ease of use […]

By |Tutorials|0 Comments