Archive | C++ RSS feed for this section

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

26 October 2010 Comments Off

90+ Beginners Lab Assignments in C Langauge

  1. A Calculator in C Using Graphics & Mouse Operations
  2. A chat program in C
  3. A program to implement Heap Sort
  4. All types of Linked List Operations
  5. Analog and Digital clock
  6. Begginers of system programming
  7. Bomber Fighter Plane simulation
  8. Bubble Sorting Algorithm
  9. Calendar of Thousands of Years
  10. Calendar Program
  11. Calender Program in C
  12. Calender
  13. Class with constructor ( for bank account )
  14. Convert decimail nos to roman equivalent upto 10,000
  15. Converting Roman letter to number
  16. convertion of number to letters
  17. CPU Scheduling algorithm implementation
  18. Decimal to Binary, Octal and HEX converter
  19. encryption and decryption of files
  20. Finding LCM and GCD
  21. Frequency Based Histogram
  22. Graphical Calculator Design
  23. Guessing Game in C
  24. INTERVIEW QUESTIONS C
  25. Invoke function without main in C Language
  26. Kite flying code in C
  27. Merge sort
  28. No guessing
  29. N-Queen’s Problem
  30. Factorial Function
  31. Prg. to convert upper case to lower case or lower case to upper case
  32. Prg. to correct rudimentary syntax errors
  33. Prg. to count no. of characters,no. of blanks,no. of words & no.
  34. Prg. to sort any no. of numeral i-p in ascending or descending order.
  35. Printint a double pyramid
  36. Program for Binary, Octal, Hexadecimal Conversions
  37. Program for computing Area, Volume and Perimeter of Rrectangle using
  38. Program for finding the prime numbers
  39. Program for finding the sum of digits of a five digit number
  40. Program for Prime Number Generation
  41. Program for rotating circles using maths.(sin,cos,Phase defference,e.t.c)
  42. Program Implementing the rot13 algorithm
  43. Program of Falling Characters
  44. Program to calculate frequency of vowels in a string
  45. Program to Calculate the Pascal triangle
  46. Program to calculate the sum of series

Source: http://www.c.happycodings.com/Beginners_Lab_Assignments/

24 October 2010 Comments Off

STL vector (STL Tutorial -1)

vector: Dynamic array of variables, struct or objects. Insert data at the end. Simple example of storing STL strings in a vector. Bangla (বাংলা) version of this tutorial

This example shows three methods of accessing the data within the vector:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

main()
{
   vector<string> SS;

   SS.push_back("The number is 10");
   SS.push_back("The number is 20");
   SS.push_back("The number is 30");

   cout << "Loop by index:" << endl;

   int ii;
   for(ii=0; ii < SS.size(); ii++)
   {
      cout << SS[ii] << endl;
   }

   cout << endl << "Constant Iterator:" << endl;

   vector<string>::const_iterator cii;
   for(cii=SS.begin(); cii!=SS.end(); cii++)
   {
      cout << *cii << endl;
   }

   cout << endl << "Reverse Iterator:" << endl;

   vector<string>::reverse_iterator rii;
   for(rii=SS.rbegin(); rii!=SS.rend(); ++rii)
   {
      cout << *rii << endl;
   }

   cout << endl << "Sample Output:" << endl;

   cout << SS.size() << endl;
   cout << SS[2] << endl;

   swap(SS[0], SS[2]);
   cout << SS[2] << endl;
}

Compile: g++ exampleVector.cpp
Run: ./a.out
Output:

Loop by index:

The number is 10
The number is 20
The number is 30

Constant Iterator:
The number is 10
The number is 20
The number is 30

Reverse Iterator:
The number is 30
The number is 20
The number is 10

Sample Output:
3
The number is 30
The number is 10

[...]

Tags: ,
16 October 2010 Comments Off

The Standard Template Libraries (STL’s) Tutorials

The Standard Template Libraries (STL’s) Tutorials

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.

STL can be categorized into the following groupings:

  • Container classes:
    • Sequences:
    • 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.

Also see the YoLinux.com GDB tutorial on dereferencing STL containers.

Tags: ,
23 August 2010 2 Comments

C++ Bubble Sort

Bubble sort is a simple and well-known sorting algorithm. It is used in practice once in a blue moon and its main application is to make an introduction to the sorting algorithms. Bubble sort belongs to O(n2) sorting algorithms, which makes it quite inefficient for sorting large data volumes. Bubble sort is stable and adaptive.

Algorithm

  1. Compare each pair of adjacent elements from the beginning of an array and, if they are in reversed order, swap them.
  2. If at least one swap has been done, repeat step 1.

You can imagine that on every step big bubbles float to the surface and stay there. At the step, when no bubble moves, sorting stops. Let us see an example of sorting an array to make the idea of bubble sort clearer.

Complexity analysis

Average and worst case complexity of bubble sort is O(n2). Also, it makes O(n2) swaps in the worst case. Bubble sort is adaptive. It means that for almost sorted array it gives O(n) estimation. Avoid implementations, which don’t check if the array is already sorted on every step (any swaps made). This check is necessary, in order to preserve adaptive property.

One more problem of bubble sort is that its running time badly depends on the initial order of the elements. Big elements (rabbits) go up fast, while small ones (turtles) go down very slow. This problem is solved in the Cocktail sort.

Code

#include<iostream>
using namespace std;

#include<iomanip>
using std::setw;

int main()

{
const int arraysize = 10;
int Bubble[ arraysize ];

cout << "Please enter 10 integers: " << endl;

for ( int i = 0; i < arraysize; i++ )
cin >> Bubble[ i ];

cout <<"unsorted array:\n";

for ( int j = 0; j < arraysize; j++ )
cout << setw( 4 ) << Bubble[ j ];

for(int y=0; y < arraysize; y++)

{

for ( int k =0; k < arraysize -1-y; k++ )

if(Bubble[k]>Bubble[k+1])

{

int temp = Bubble[k+1];

Bubble[k+1] = Bubble[k];

Bubble[k] = temp;

}

}

cout << "\nSorted Bubble array:\n";

for (int l = 0; l < arraysize; l++ )
cout << setw( 4 ) << Bubble[ l ];

cout << endl;
return 0;
}
Tags: ,