Abstract Data Types

Data abstraction is important because:

• It allows uns to create data types not otherwise available in a programming language
• It allows us to produce off-the-shelf-software, pieces of software that can be used over and over again in different programs by any programmer

The primary tool for practicing data abstraction is the abstract data type(ADT), a new data type that is not built into the programming language, concentrating only on its logical properties and deferring the details of its implementation.

An abstract data type has both a specification (the what) and an implementation (the how) 

Properties of abstract data types

• Attributes
  
  • Java: fields
  • C++: data members or member variables
  
  
• Oprations
• Java: methods
• C++: member functions

Interaction with (usage of) an abstract data type is made through its interface or public interface

• Public attributes
• Public operations

TIP: public interface should be built around public operations. 

Example of informal specification

TYPE
    IntList
DOMAIN
    Each IntList value is a collection of up to 100 separate integer numbers
OPERATIONS
    Insert an item into the list
    Delete an item from the list
    Return the current length of the list
    Print the list

Notice the complete absense of implementation details


Reference: wikipedia, google books, thefreedictionary

Previous post

Next post

 

Abstraction

To cope with complexity, the human mind engages in abstraction, the act of separating the essential qualities of an idea or object from the details of how it works or is composed. With abstraction, we focus on the what, not the how. Abstraction can be performed from different viewpoints.

Examples:

• Words of a spoken language
• Metaphysical abstractions
• Objects in a classroom
• Mathematical abstractions
• Abstraction in programming

Fig: Abstraction in real life



Abstraction in Programming

Data types: An int-type represents an integer, a float-type represents a floating point number

Functions: absoluteValue

double absoluteValue(double d)
{
    if(d<0)
    {
        return -d;
    }
    else
    {
        return d;
    }
}

#include<cmath>
double absoluteValue(double d)
{
    return abs(d);
}

Both of the given example functions do the same thing. We don't need to know how they are doing. So we are focusing on what, not how.

Types of Abstraction

There are two important abstraction techniques:

• control abstraction
• data abstraction

Control abstraction is the separation of the logical properties of an action from its implementation.

Data abstraction is the separation of a data type's logical properties from its implementation.

Reference: wikipedia, artima, microsoft

Previous post

Next post

Array vs vector

Vectors are intended to replace the C-style arrays, i.e. the static arrays:

• Safe to pass as a parameter or assign to
• Size increases when necessary means no memory management problem
• Comparisons (==, < etc.) works "as it should"

vector has its own dangers, though:

• No forced boundary limit checks in indexing
• Easy to write code that may be inefficient in parameter passing
• Passing arrays to libraries that use C arrays is difficult

Comparisons between C arrays and vector:

operation	array	vector
Creation	int t[10]	vector<int> t(10); or vector<int> t; (empty)
Assignment	in a loop	t1 = t2
Indexing	t[i]	t[i] or t.at(i)
Inserting to the end	not possible	t.push_back(item)
Combining	not possible	t1.insert(t1.end(), t2.begin(), t2.end())
Size	programmer must know	t.size()
Emptying	not possible	t.clear()
Comparison	in a loop	t1 == t2 (likewise <>
Insertion to the middle	not possible	t.insert(iterator, item)
Searching	in a loop	find(t.begin(), t.end(), item)
Exchange of values	in a loop	t1.swap(t2)

vector< type > var;An empty vector
vector< type > var(vector< type >); Initialization with another vector
vector< type > var(int);A vector of the size int with elements of the type
vector< type > var(int, element);A vector with int elements initialized to element

Operations:
vector[int] // Indexing the vector at int.
vector1 = vector2 // Assignment
vector1 == vector2 // Comparison
vector1 != vector2vector1 < vector2vector1 <= vector2vector1 > vector2 vector1 >= vector2

Functions:
swap(vector1, vector2) // swaps the contents

Own functions:

type at( int )	Indexing the vector at int
type front()	The first element
type back()	Last element
vector<type>::size_type size()	number of elements
bool empty()	true if vector is empty
void push_back(element)	Element is added to the end of vector
void pop_back()	Last element is removed, size gets smaller by one
void clear()	Empty the vector completely
iterator being()	An iterator to the beginning
iterator end()	An iterator to the end

#include <algorithm>

Functions:

void sort( array, array+size );
void sort( vector.begin(), vector.end() );
// Sorting the vector or array into an ascending order
bool compare(const item&, const item&);
void sort( array, array+size, compare );
void sort( vector.begin(), vector.end(), compare );
// Sort can be given a comparison function as a third parameter
// Function returns true if the first parameter is smaller than the second.
void operations(const item&);
void for_each( array, array+size, operations );
void for_each( vector.begin(), vector.end(), operation );
// Calls the function operation for each element in the array or vector at a time.


Reference: cplusplus, velocityreviews, devx

Previous post

Next post

Vector

The C++ standard library offers the programmer plenty of generic data structures and algorithms that are ready for use. The programmer can concentrate on the essential and does not need to invent the wheel all over again. Just like string is dynamic and easier to use than static character strings, there is a dynamic data structure corresponding to static arrays. That is vector. vector is a part of the C++ standard library. The problems with arrays in C++:

• They are static, i.e. the amount of elements cannot be changed without compiling the program again
• An array cannot be copied into another away with the = operator
• An array cannot be initialized with an another array
• There is no way of knowing the current amount of actual elements without keeping constant score of the situation

vector makes all of the above possible and has a lot of other useful features. In practice, vector is generic, dynamic array.

In order to be able to use vector the library vector must be taken into use.

Any type of data can be put into a vector. All elements must be of the same type (just like with static arrays). vector is defined with <> notation:

vector< element_type > variable_name;

for example:

vector< int > numbers;
vector< string > names;

The vector is empty at initialization if no initial values are given:

vector< double > temperatures1( 5, 20.1 );
vector< double > temperatures2( 3 );
vector< double > temperatures3( temperatures2 );

now there are five elements in the vector temperatures1 with the value 20.1, all three elements in the vector temperatures2 have been initialized to 0.0 and the temperatures3 has the same contents as temperatures2.

Just like string, vector has its own functions.

vector <int> numbers(2,3);
//The elements in numbers are (3 3)
numbers.clear();
//numbers now empty
numbers.push_back(4);
numbers.push_back(10);
//Now the elements are (4 10)
numbers.push_back( numbers[1] );
//(4 10 10)
numbers.push_back( numbers.at( 0 ) );
//(4 10 10 4)
numbers.pop_back();
//(4 10 10)

// printing the contents
if( !numbers.empty() )
{
    unsigned int i;
    for( i = 0; i < numbers.size(); ++i )
    {
        cout << "numbers are: " << numbers[ i ] << " ";
    }
    cout << endl;
}

A vector can be assigned another vector of the same type with the = operator. Two vectors of the same type can be compared with ==, !=, <, >, <= and >= operators.

vector can be passed both as a value and a reference parameter like any ordinary variable:

vector<type> valueparam
vector<type>& referenceparam

In practice vector should always be passed as a reference parameter due to efficiency issues.

Reference: cplusplus, codesource, cppreference

Previous post

Next post

Using several code files

Sometimes it is very handy to use several code files for a particular program. For example, if the program is very big and difficult to handle then its necessary to split the whole program into several files and combine together to make the program work properly. Sometimes function can be moved into a separate file. Let's take an example on how to move the functions into a separate file from the main function.

In the file plus.hh the function is declared:

#ifndef PLUS_HH #define PLUS_HH int plus( int a, int b ); #endif // PLUS_HH

In the file plus.cc the function is defined:

int plus( int a, int b ) { return a + b; }

In the file main.cc the main function is defined:

#include <iostream> #include <cstdlib> #include "plus.hh" int main( void ) { cout << "3+4 = " << plus( 3, 4 ) << endl; return EXIT_SUCCESS; }

The files work together in that sense that the .hh files (header files) have the declarations of those functions the .cc files (source files) define. The actual code, e.g. the function bodies, is in the .cc files. The .hh files must be added to the program with the #include directive if the functions need to be used in that file.

The command <file> is used when the included file is in some of the systems default directories. The compiler automatically also links these files. "file.hh" means that the header file is in the same directory as the source file. The function definitions need to be included also into the compilation stage to get an executable program. This is done by linking the files together. The compiler also links:

> g++ o plus plus.cc main.cc >./plus 3+4 = 7

If the different stages of compiling and linking ned to be separated, the source files (.cc) can first be compiled into object files (.o) which then are linked into an executable program. For example:

>g++ c plus.cc >g++ c main.cc >g++ o plus plus.o main.o >./plus 3+4 = 7

It makes sense to separate the compiling and linking stages when compiling large programs. It is easy to locate which stage the errors are coming from.

Some important matters:

• Always include only header files
• Write the actual code into the source files
• Since include adds the file as a part of the compiled file, it is possible that some file is included more than once. Overlapping definitions can prevent compilation
• The directives #ifndef, #define and #endif tell the preprocessor to add the file only once into the compiled file no matter how many times it has been included
• The readability of a small program can be increased by moving the main to the beginning of the file and adding the definitions of functions after that. The functions must be declared before the main

Reference: fredosaurus, gamedev, learncpp

Previous post

Next post

typedef

Sometimes there is a need to have types that cannot operate together in the program. For instance, money and weight should not be added even though both can be saved into variables of the type double. In these cases the situation can be made clearer by giving an existing type a new name with the typedef definition. For example:

typedef doube Currency;

typedef does not create a new type. For instance the types double and Currency would be interchangeable.

Type definitions make the code easier to read. They can also be used to writing more portable code. The type int is on some machines only 16 bits long, for instance. If the program when moved to this machine needed to operate with large sums, only the typedefinition needs to be changed. All the gazillion points in the code using the alias would remain intact.

Reference: cprogramming, wikipedia, mmbase

Previous post

Next post

switch statement

The switch statement can be used to implement a multi-alternative selection statement when:

• The tested value can be interpreted as an integer (int, char or enum)
• The alternatives the value is tested are constants that can be interpreted as integers

Note: The switch statement is not as general as the if statement. However, switch is more efficient in some situations.

The general form of the switch statement is:

switch ( tested_expression )
{
    case alternative1:
        statementlist1;
        break;
    .
    .
    .
    case alternativeN:
        statementlistN;
        break;
    default:
        statementlist def;
        break;
}

When the switch statement is executed, the tested expression is evaluated. It is compared to the alternatives one by one. If one of the alternatives matches the tested expression the execution begins in the corresponding statementlist i. The execution continues through the statementlist i until one of the following is reached:

• A break statement
• A return statement
• The end of the switch statement

If the tested expression doesn't match any of the alternatives the statementlist def is executed.

The default clause can be omitted. If the value of the tested expression is not in the alternatives execution "falls through" the switch.

If one of the statementlist i's missing a break the execution continues from the next tested expression, otherwise continues from the statement following the switch.

This can be used in situations where several alternatives have same functionality:

switch( answer )
{
    case 'n':
    case 'N':
        //the actions performed when
        //the user answers n or N
        break;
    ...
}

The break can also be omitted if the entire statement (or actually the function) is exited with return:

switch( month )
{
    case 1:
        return "January";
    case 2:
        return "February";
    etc...
    case 12:
        return "December";
    default:
        return "Error";
}

Reference: msdn, intap, awitness

Previous post

Next post

Enumeration

An enumeration is a datatype with all the valid values defined by the programmer. In C++ an enumeration is declared.

enum TypeName { List_of_values };

that defines a new data type named TypeName whose values are the identifiers in the List of values. Each identifier is associated with an integer constant, i.e. the C++ compiler automatically preforms a identifier-to-integer mapping associating the integer 0 with the first identifier the integer 1 with the second etc.

C++ also allows the programmer to specify explicitly the values given to the identifiers:

enum NumberBase { BINARY = 2, OCTAL = 8, DECIMAL = 10, HEX = 16, HEXADECIMAL = 16 };

The integer associated with an identifier is, by default, one more than the integer associated with the preceding identifier. The integers can be declared:

enum Color { RED = 1, BLUE, GREEN, YELLOW, VIOLET };

Two ro more identifiers can have the same integer value associated with them. The enumerators (the identifiers in the enumeration) can be used wherever int or char values can be used. The enumerator is interpreted as the integer it is associated with. Enumeration and integer data can operate together as they were of the same type.

An integer value cannot be used instead of an enumerator in assignments or as a function parameter without explicit type conversion:

enum Season { SUMMER, FALL, WINTER, SPRING };
void print( Season quarter );

int figure = SUMMER; // figure <--- 0
// equivalent <--- SUMMER
Season equivalent = static_cast (figure);
// print( SUMMER )
print( static_cast (figure) );

Reference: ucalgary, anyexample, codeproject

Previous post

Next post

Streams as parameters

The most important thing to remember when passing a stream to a function as a parameter: the formal parameter needs to be a reference parameter

It makes sense to require that since the function operates with the stream. The state of the stream changes and the change must be passed back to the actual parameter. As a rule the actual parameter needs to be of the same type as the formal parameter of the function, except when:

the type of the formal parameter is	the actual parameter can also be
sitram&	ifstream or istringstream
ostream&	ofstream or ostringstream

In practice that makes writing more general functions possible: the same function can operate with different types of streams.

A small example function:

int readNumber( istrea& stream )
{
    int number;
    stream >> number;
    if( !stream )
    {
        return ERROR;
    }
    else
    {
        return number;
    }
}

Now the same function can be used for reading input from the keyboard:

int number;
number = readNumber( cin );

of from a file:

ifstrea database( "input.txt" );
int number;
number = readNumber( database );

or from a string:

istrinigstream numberstring("12345 67890 101112");
int number;
number = readNumber( numberstring );

Reference: daniweb, bytes, cplusplus

Previous post

Next post

Problems with streams

The following problem situations can occur when using streams:

• An attempt to write data into a outputstream fails (e.g. the disk is full)
• An attempt to read data from an inputstream even though everything has already been read (e.g. the read operation is at the end of file)
• Data of the wrong type is attempted to read from an inputstream (e.g. an integer is expected but the user types characters)

Noticing the problematic situations is easy with the following details:

• All previously introduced stream operations evaluate the stream the operations is directed to ( peek() and get() without parameters are exceptions)
• A stream used as a condition evaluates true only if the operation was successful (initialization included)

The following useful examples can be done based on these:

Connecting an inputstream to a file and reading it a line at a time:

ifstream file( "products.dat" );
if( !file )
{
    cerr << "open failed!" << endl;
    return ERROR; // depends on the situation
}
string line;
while( getline( file, line ) )
{
    ...
    // here work with the read data
    ...
}

noticing input of the incorrect type:

cout << "give number: ";
int number;
while( !(cin >> number) )
{
    cerr << "Invalid input, try again!" << endl;
    cin.clear();
    cin.ignore( 1000, '\n' );
}

The cin's own function clear() has been used to deal with the error situation above. The stream malfunctions every time an error occurs when handling data with it. Not even legal operations work any longer. Sometimes the situation can be fixed with the clear() function. Execution can (sometimes) go on normally afterward. Some errors cannot be fixed with clear() (e.g. the end of file has been met)

How to see the difference between the end of stream error and some other error situation:

while( getline( stream, line ) )
{
    ...
}
if( !stream.eof() )
{
    // Read failed for some other reason than
    // the end of the stream
}

The stream's own function eof() returns true only if an attempt has been made to read from the stream after it has already ended. Also peeking the next character in the stream with the peek() function is sometimes an useful way to deduct whether the input has been read entirely or not.

Last, an example on how to read the following input stream:

tel.number1 name1
tel.number2 name2
...

with the code:

int number;
string name;

while( stream >> number && getline( stream, name ) )
{
    // do stuff with the name and number
}
if( !stream.eof() )
{
    // invalid line in input
}

Reference: daniweb, dreamincode, cplusplus

Previous post

Next post

Operations with inputstreams

cin >> variable

Reads the next word from the stream, interprets it as the same type as the variable and saves the value into the variable. The variable can be of any basic type or string.


cin.get()

Reads and returns the next character in the stream. At the end of input EOF is returned.


cin.get( chr )

Reads the next character into the parameter that must be of the type char.


getline( cin, str )

Reads a line of input from the stream and saves it into a parameter of the type string.


getline( cin, str, chr )

Like above but reads only until meets the first character matching chr.


cin.ignore( how_many, chr )

Reads at most how_many characters from the stream or until meets the first chr. The read characters are "thrown away". How_many is of the type int and chr char.


cin.peek()

Returns the next character in the stream. The character is not read from the stream but the next read operations return it also Returns EOF at the end of input.

Reference: cplusplus, augustcouncil, elcel

Previous post

Next post

Streams in C++

In C++ streams are represented with datatypes implemented in a number of libraries:

#inlcude <iostream>

istream	Inputstreams usually already associated with the keyboard (cin).
ostream	Outputstreams usually already associated with the monitor (cout or cerr)

#inlcude <fstream>

ifstream	Inputstreams the user must associated with a file on the computer disk
ofstream	Outputstreams the user must associated with a file on the computer disk

#inlcude <sstream>

istringstream	inputstreams the user can use to read from a string using the formatting facilities provided by streams
ostringstream	Outputstreams the user can use to write to a string using the formatting facilities provided by streams

A programmer does not need to worry about associating cout, cin and cerr. They can always be used straight after #include<iostream>. Using streams usually consist of three phases (cin, cerr and cout exceptions):

• Initializing (connecting, associating)
• Operating with the stream (read, write etc...)
• Closing

Before handling data with the streams found in fstream and sstream libraries they must be initialized:

ifstream: A variable of the type ifstream is declared and the name of the file to be read is given:

ifstream stream_name( file_name );

ofstream: A variable of the type ofstream is declared and the name of the file to be written into is given:

ofstream stream_name( file_name );

istringstream: A variable of the type istringstream is declared and the string from which the input is read is given:

istringstream stream_name( s_name );

ostringstream: A varible of the type ostringstream is declared.

ostringstream stream_name;

The file_name is not of the type string. It is of an older character string type adopted from the C language. The programmer must give the name of the correct type:

string file_name;
cin >> file_name;
ifstream file( file_name.c_str() );

the c_str() function returns a character string of the c-style string type matching the original string-typed string. The file_name can also be a character string literal:

ifstream file( "inputs.txt" );

After being initialized, different operations can be done with the stream depending on its type and whether it is an input or an output stream (phase 2).

Working with streams can be confusing because of different alternative ways to do things:

operations: cout << "Hello!";
functions: getline( cin, cstring );
own function: cout.put( 'a' );

Operations that can be used with all kinds of outputstreams (e.g. cout):

cout << value << endl;

Prints the value into the stream: the value can be of any basic datatype or string.

cout.put( c );

Prints one character c(char) into the stream

There are no more essential printing operations. Almost everything can be done with << operator.

The stream must be closed when it is not needed any longer (phase 3). If it isn't properly closed it will needlessly keep on using the system's resources. There are two ways to close a stream:

• If the stream is a local variable, C++ automatically closes it when the code block the stream was defined in is exited.
• The stream can also be "manually" closed if needed with the stream's own function close():

ifstream database( "phonenumbers.dat" ); // using the stream
...
database.close();

The stream cannot be used after closing unless it is initialized again.

cin, cout and cerr

cin is used for reading from the keyboard and cout for printing on the screen. cerr has the same functionality as cout but it is meant for printing the error messages of the program. All other output is printed into cout.

Reference: cplusplus, exforsys, msdn

Previous post

Next post

Streams

Most programs have some kind of I/O operations:

• Reading data from a file on the computer's disk into the program
• Saving the results of the program into a file on the disk for future use

There must be a way in a programming language to represent the real world disk files in such a way that a program can understand them. Usually a special data type that offers operations for reading and writing data is used. In C++ a data type called a stream is used for this purpose. In fact, besides file I/O, all input and output operations in C++ are done with streams.

The stream can be thought of as a line of characters following in a specific order in one direction without ever changing their order.

• Only the first character of the stream can be read from the stream ( with the operation get() )
• Writing can only be done after the last character in the stream( with the operation put() )

All other stream operations can be implemented with get and put. Not changing the order of characters in a stream is essential:

• If the user types "abcdef" on a keyboard undoubtedly the program gets the same characters in the same order from the input stream(cin)
• If the program writes characters into a stream connected to a file it is desirable that the characters are saved in the same order they were written into the stream

Streams are sequential in nature: data can only be managed in the same order it is in the stream. A stream is simply a sequence of bytes, that means, if a program is interested in the fifth character in the user's input, the preceding four characters must be read first. The same applies to a stream connected to a file: the file must be read from beginning to end. In reality, disk files can be read and written in an arbitrary order.

A stream is usually connected to a file, the screen or the keyboard. However, streams can also be used to connect two programs to each other. The interesting thing is that streams can always be handled in the same way, regardless of what they happen to be connected to.

Reference: cplusplus, msdn, exforsys

Previous post

Next post

sizeof

The sizeof operator returns the number of bytes required to store a variable or a data (1 byte = 8 bits). The operator can be applied to any type of variable:

sizeof( variable name );
sizeof( data_type_name );

sizeof is a handy tool in finding out the amount of elements in an array:

const int SIZE = sizeof( array ) / sizeof( element_type );
or
const int SIZE = sizeof( array ) / sizeof( array[ 0 ] );

When the value of size is always equal to the actual amount of elements in the array even if the size of the array is changed between complications.

Note that sizeof does not produce a correct answer if they array is a formal parameter of a function.

Reference: cppreference, space, msdn

Previous post

Next post