C++ Programming Code Examples

Algorithm make heap - A heap is a sequence of elements organized like a binary tree make_heap Header <algorithm> template<class RandomAccessIterator> inline void make_heap(RandomAccessIterator first, RandomAccessIterator last) A heap is a sequence of elements organized like a binary tree. Each heap element corresponds to a tree node. The first value in the sequence [first..last) is the root, and is the largest value in the heap. Every element in the heap satisfies the following: Every element is less than or equal to its parent. The largest element is stored in the root, and all children hold progressively smaller values. The make_heap function converts the range [first..last) into a heap. The non-predicate versions of the heap functions use the operator< for comparisons. template<class RandomAccessIterator, class Compare> inline void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare compare) A heap is a sequence of elements organized like a binary tree. Each heap element corresponds to a tree node. The first value in the sequence [first..last) is the root, and is ordered by the predicate. For example, if the predicate is greater, every element in the heap satisfies the following: Every element is greater than or equal to its parent. The smallest element is stored in the root, and all children hold progressively larger values. The make_heap function converts the range [first..last) into a heap. The predicate versions of the heap functions use the compare function for comparisons. Samples Sample for Non-Predicate Version // disable warning C4786: symbol greater than 255 character, // okay to ignore #pragma warning(disable: 4786) #include <iostream> #include <algorithm> #include <functional> #include <vector> using namespace std; void main() { const int VECTOR_SIZE = 8 ; // Define a template class vector of int typedef vector<int > IntVector ; //Define an iterator for template class vector of strings typedef IntVector::iterator IntVectorIt ; IntVector Numbers(VECTOR_SIZE) ; IntVectorIt it ; // Initialize vector Numbers Numbers[0] = 4 ; Numbers[1] = 10; Numbers[2] = 70 ; Numbers[3] = 10 ; Numbers[4] = 30 ; Numbers[5] = 69 ; Numbers[6] = 96 ; Numbers[7] = 100; // print content of Numbers cout << "Numbers { " ; for(it = Numbers.begin(); it != Numbers.end(); it++) cout << *it << " " ; cout << " }\n" << endl ; // convert Numbers into a heap make_heap(Numbers.begin(), Numbers.end()) ; cout << "After calling make_heap\n" << endl ; // print content of Numbers cout << "Numbers { " ; for(it = Numbers.begin(); it != Numbers.end(); it++) cout << *it << " " ; cout << " }\n" << endl ; // sort the heapified sequence Numbers sort_heap(Numbers.begin(), Numbers.end()) ; cout << "After calling sort_heap\n" << endl ; // print content of Numbers cout << "Numbers { " ; for(it = Numbers.begin(); it != Numbers.end(); it++) cout << *it << " " ; cout << " }\n" << endl ; //insert an element in the heap Numbers.push_back(7) ; push_heap(Numbers.begin(), Numbers.end()) ; // you need to call make_heap to re-assert the // heap property make_heap(Numbers.begin(), Numbers.end()) ; cout << "After calling push_heap and make_heap\n" << endl ; // print content of Numbers cout << "Numbers { " ; for(it = Numbers.begin(); it != Numbers.end(); it++) cout << *it << " " ; cout << " }\n" << endl ; // remove the root element from the heap Numbers pop_heap(Numbers.begin(), Numbers.end()) ; cout << "After calling pop_heap\n" << endl ; // print content of Numbers cout << "Numbers { " ; for(it = Numbers.begin(); it != Numbers.end(); it++) cout << *it << " " ; cout << " }\n" << endl ; } Program Output Numbers { 4 10 70 10 30 69 96 100 } After calling make_heap Numbers { 100 30 96 10 4 69 70 10 } After calling sort_heap Numbers { 4 10 10 30 69 70 96 100 } After calling push_heap and make_heap Numbers { 100 69 96 30 4 70 10 10 7 } After calling pop_heap Numbers { 96 69 70 30 4 7 10 10 100 } Sample for Predicate Version // disable warning C4786: symbol greater than 255 character, // okay to ignore #pragma warning(disable: 4786) #include <iostream> #include <algorithm> #include <functional> #include <vector> using namespace std; void main() { const int VECTOR_SIZE = 8 ; // Define a template class vector of int typedef vector<int > IntVector ; //Define an iterator for template class vector of strings typedef IntVector::iterator IntVectorIt ; IntVector Numbers(VECTOR_SIZE) ; IntVectorIt it ; // Initialize vector Numbers Numbers[0] = 4 ; Numbers[1] = 10; Numbers[2] = 70 ; Numbers[3] = 10 ; Numbers[4] = 30 ; Numbers[5] = 69 ; Numbers[6] = 96 ; Numbers[7] = 100; // print content of Numbers cout << "Numbers { " ; for(it = Numbers.begin(); it != Numbers.end(); it++) cout << *it << " " ; cout << " }\n" << endl ; // convert Numbers into a heap make_heap(Numbers.begin(), Numbers.end(), greater<int>()) ; cout << "After calling make_heap\n" << endl ; // print content of Numbers cout << "Numbers { " ; for(it = Numbers.begin(); it != Numbers.end(); it++) cout << *it << " " ; cout << " }\n" << endl ; // sort the heapified sequence Numbers sort_heap(Numbers.begin(), Numbers.end(), greater<int>()) ; cout << "After calling sort_heap\n" << endl ; // print content of Numbers cout << "Numbers { " ; for(it = Numbers.begin(); it != Numbers.end(); it++) cout << *it << " " ; cout << " }\n" << endl ; make_heap(Numbers.begin(), Numbers.end(), greater<int>()) ; //insert an element in the heap Numbers.push_back(7) ; push_heap(Numbers.begin(), Numbers.end(), greater<int>()) ; cout << "After calling push_heap()\n" << endl; // print content of Numbers cout << "Numbers { " ; for(it = Numbers.begin(); it != Numbers.end(); it++) cout << *it << " " ; cout << " }\n" << endl ; //remove the root element from the heap Numbers pop_heap(Numbers.begin(), Numbers.end(), greater<int>()) ; cout << "After calling pop_heap\n" << endl ; // print content of Numbers cout << "Numbers { " ; for(it = Numbers.begin(); it != Numbers.end(); it++) cout << *it << " " ; cout << " }\n" << endl ; } Program Output Numbers { 4 10 70 10 30 69 96 100 } After calling make_heap Numbers { 4 10 69 10 30 70 96 100 } After calling sort_heap Numbers { 100 96 70 69 30 10 10 4 } After calling push_heap() Numbers { 4 7 10 30 100 10 70 96 69 } After calling pop_heap Numbers { 7 30 10 69 100 10 70 96 4 }

/* returns the iterator pointing to the past-the-last element of the vector container by vector::end function code example. */ // CPP program to illustrate implementation of begin() function #include <iostream> #include <string> #include <vector> using namespace std; int main() { // declaration of vector container vector<string> myvector{ "This", "is", "HappyCodings" }; // using begin() to print vector for (auto it = myvector.begin(); it != myvector.end(); ++it) cout << ' ' << *it; return 0; }

/* C++ Algorithm pop_heap() function is used to swap the value in the position ?first? and the value in the position ?last-1? and makes the sub range [first, last-1) into a max heap. It has the effect of removing the first (largest) element from the heap defined by the range [first, last). Elements are compared using operator < for the first version or using the given binary comparison function comp for the second version. */ /* Pop element from heap range by pop_heap() function code example */ #include <vector> #include <algorithm> #include <functional> #include <iostream> int main( ) { using namespace std; vector <int> v1; vector <int>::iterator Iter1, Iter2; int i; for ( i = 1 ; i <= 9 ; i++ ) v1.push_back( i ); // Make v1 a heap with default less than ordering random_shuffle( v1.begin( ), v1.end( ) ); make_heap ( v1.begin( ), v1.end( ) ); cout << "The heaped version of vector v1 is ( " ; for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ ) cout << *Iter1 << " "; cout << ")." << endl; // Add an element to the back of the heap v1.push_back( 10 ); push_heap( v1.begin( ), v1.end( ) ); cout << "The reheaped v1 with 10 added is ( " ; for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ ) cout << *Iter1 << " "; cout << ")." << endl; // Remove the largest element from the heap pop_heap( v1.begin( ), v1.end( ) ); cout << "The heap v1 with 10 removed is ( " ; for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ ) cout << *Iter1 << " "; cout << ")." << endl << endl; // Make v1 a heap with greater-than ordering with a 0 element make_heap ( v1.begin( ), v1.end( ), greater<int>( ) ); v1.push_back( 0 ); push_heap( v1.begin( ), v1.end( ), greater<int>( ) ); cout << "The 'greater than' reheaped v1 puts the smallest " << "element first:\n ( " ; for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ ) cout << *Iter1 << " "; cout << ")." << endl; // Application of pop_heap to remove the smallest element pop_heap( v1.begin( ), v1.end( ), greater<int>( ) ); cout << "The 'greater than' heaped v1 with the smallest element\n " << "removed from the heap is: ( " ; for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ ) cout << *Iter1 << " "; cout << ")." << endl; return 0; }

/* The C++ algorithm::push_heap function is used to extend the range of max heap by one. Given that the initial range of the heap is [first, last-1), this function extends its range to [first, last) by placing the element at position (last-1) to its corresponding position. */ /* Push element into heap range by algorithm::push_heap function code example */ #include <iostream> #include <algorithm> #include <vector> using namespace std; int main (){ vector<int> vec{10, 5, 55, 22, 27, -10}; vector<int>::iterator it; cout<<"vec contains:"; for(it = vec.begin(); it != vec.end(); ++it) cout<<" "<<*it; //make the vector max heap make_heap(vec.begin(), vec.end()); cout<<"\nAfter make_heap call, vec contains:"; for(it = vec.begin(); it != vec.end(); ++it) cout<<" "<<*it; //add a new element at the end of the vector vec.push_back(50); cout<<"\nAfter adding new element, vec contains:"; for(it = vec.begin(); it != vec.end(); ++it) cout<<" "<<*it; //calling push_heap function which extends //the max heap range by 1 and rearranges //the subrange into max heap push_heap(vec.begin(), vec.end()); cout<<"\nAfter push_heap call, vec contains:"; for(it = vec.begin(); it != vec.end(); ++it) cout<<" "<<*it; return 0; }

/* make_heap() is used to transform a sequence into a heap. A heap is a data structure which points to highest( or lowest) element and making its access in O(1) time. Order of all the other elements depends upon particular implementation, but remains consistent throughout. This function is defined in the header "algorithm". */ /* Make heap from range by make_heap() function code example */ #include <iostream> // std::cout #include <algorithm> // std::make_heap, std::pop_heap, std::push_heap, std::sort_heap #include <vector> // std::vector using namespace std; int main () { int myints[] = {20,10,30,5,13}; vector<int> v(myints,myints+5); make_heap (v.begin(),v.end()); cout << "initial max heap : " << v.front() << '\n'; pop_heap (v.begin(),v.end()); v.pop_back(); cout << "max heap after pop : " << v.front() << '\n'; v.push_back(99); push_heap (v.begin(),v.end()); cout << "max heap after push: " << v.front() << '\n'; sort_heap (v.begin(),v.end()); cout << "final sorted range :"; for (unsigned i=0; i<v.size(); i++) cout << ' ' << v[i]; cout << '\n'; return 0; }

/* function with parameters in C++ language */ // program to print a text #include <iostream> using namespace std; // display a number void displayNum(int n1, float n2) { cout << "The int number is " << n1; cout << "The double number is " << n2; } int main() { int num1 = 5; double num2 = 5.5; // calling the function displayNum(num1, num2); return 0; }

/* Vectors in C++ language */ // C++ program to illustrate the capacity function in vector #include <iostream> #include <vector> using namespace std; int main() { vector<int> myvector; for (int i = 1; i <= 5; i++) myvector.push_back(i); cout << "Size : " << myvector.size(); cout << "\nCapacity : " << myvector.capacity(); cout << "\nMax_Size : " << myvector.max_size(); // resizes the vector size to 4 myvector.resize(4); // prints the vector size after resize() cout << "\nSize : " << myvector.size(); // checks if the vector is empty or not if (myvector.empty() == false) cout << "\nVector is not empty"; else cout << "\nVector is empty"; // Shrinks the vector myvector.shrink_to_fit(); cout << "\nVector elements are: "; for (auto it = myvector.begin(); it != myvector.end(); it++) cout << *it << " "; return 0; }

/* It is a function object class for greater-than inequality comparison and binary function object class whose call returns whether the its first argument compares greater than the second (as returned by operator >). */ /* Function object class for greater-than inequality comparison by std::greater code example */ #include <functional> #include <iostream> #include <queue> using namespace std; // Function to print elements of priority_queue void showpq(priority_queue<int, vector<int>, greater<int> > pq) { priority_queue<int, vector<int>, greater<int> > g; g = pq; // While priority_queue is not empty while (!g.empty()) { // Print the top element cout << g.top() << ' '; // Pop the top element g.pop(); } } // Driver Code int main() { // priority_queue use to implement // Max Heap, but using function // greater <int> () it implements // Min Heap priority_queue<int, vector<int>, greater<int> > gquiz; // Inserting Elements gquiz.push(10); gquiz.push(30); gquiz.push(20); gquiz.push(5); gquiz.push(1); // Print elements of priority queue cout << "The priority queue gquiz is : "; showpq(gquiz); return 0; }

/* For Loop Statement in C++ Language */ // C++ program to find the sum of first n natural numbers // positive integers such as 1,2,3,...n are known as natural numbers #include <iostream> using namespace std; int main() { int num, sum; sum = 0; cout << "Enter a positive integer: "; cin >> num; for (int i = 1; i <= num; ++i) { sum += i; } cout << "Sum = " << sum << endl; return 0; }

/* using #include directive in C language */ #include <stdio.h> int main() { /* * C standard library printf function * defined in the stdio.h header file */ printf("I love you Clementine"); printf("I love you so much"); printf("HappyCodings"); return 0; }

/* namespaces in C++ language */ // A C++ code to demonstrate that we can define // methods outside namespace. #include <iostream> using namespace std; // Creating a namespace namespace ns { void display(); class happy { public: void display(); }; } // Defining methods of namespace void ns::happy::display() { cout << "ns::happy::display()\n"; } void ns::display() { cout << "ns::display()\n"; } // Driver code int main() { ns::happy obj; ns::display(); obj.display(); return 0; }

/* simple code example by main() function in C++ */ #include <iostream> using namespace std; int main() { int day = 4; switch (day) { case 1: cout << "Monday"; break; case 2: cout << "Tuesday"; break; case 3: cout << "Wednesday"; break; case 4: cout << "Thursday"; break; case 5: cout << "Friday"; break; case 6: cout << "Saturday"; break; case 7: cout << "Sunday"; break; } return 0; }

/* returns a random access iterator pointing to the first element of the vector by std::vector::begin() function code example. */ // CPP program to illustrate implementation of begin() function #include <iostream> #include <string> #include <vector> using namespace std; int main() { // declaration of vector container vector<string> myvector{ "This", "is", "HappyCodings" }; // using begin() to print vector for (auto it = myvector.begin(); it != myvector.end(); ++it) cout << ' ' << *it; return 0; }

/* If make a function as inline, then the compiler replaces the function calling location with the definition of the inline function at compile time. Any changes made to an inline function will require the inline function to be recompiled again because the compiler would need to replace all the code with a new code; otherwise, it will execute the old functionality. */ #include <iostream> using namespace std; class operation { int a,b,add,sub,mul; float div; public: void get(); void sum(); void difference(); void product(); void division(); }; inline void operation :: get() { cout << "Enter first value:"; cin >> a; cout << "Enter second value:"; cin >> b; } inline void operation :: sum() { add = a+b; cout << "Addition of two numbers: " << a+b << "\n"; } inline void operation :: difference() { sub = a-b; cout << "Difference of two numbers: " << a-b << "\n"; } inline void operation :: product() { mul = a*b; cout << "Product of two numbers: " << a*b << "\n"; } inline void operation ::division() { div=a/b; cout<<"Division of two numbers: "<<a/b<<"\n" ; } int main() { cout << "Program using inline function\n"; operation s; s.get(); s.sum(); s.difference(); s.product(); s.division(); return 0; }

/* Returns a reference to the element at specified location pos. No bounds checking is performed. Unlike std::map::operator[], this operator never inserts a new element into the container. Accessing a nonexistent element through this operator is undefined behavior. */ /* Access element from a vector by vector::operator[] code example */ #include <iostream> #include <vector> int main () { std::vector<int> myvector (10); // 10 zero-initialized elements std::vector<int>::size_type sz = myvector.size(); // assign some values: for (unsigned i=0; i<sz; i++) myvector[i]=i; // reverse vector using operator[]: for (unsigned i=0; i<sz/2; i++) { int temp; temp = myvector[sz-1-i]; myvector[sz-1-i]=myvector[i]; myvector[i]=temp; } std::cout << "myvector contains:"; for (unsigned i=0; i<sz; i++) std::cout << ' ' << myvector[i]; std::cout << '\n'; return 0; }

/* C++ Algorithm sort_heap() function is used to converts a heap [first, last) into a sorted range in ascending order. Elements are compared using operator< for the first version or using the given binary comparison function comp for the second version. */ /* Sort elements of heap by sort_heap() function code example */ #include <iostream> #include <algorithm> #include <vector> using namespace std; int main (){ vector<int> vec{10, 5, 55, 22, 27, -10}; vector<int>::iterator it; cout<<"vec contains:"; for(it = vec.begin(); it != vec.end(); ++it) cout<<" "<<*it; //make the vector max heap make_heap(vec.begin(), vec.end()); cout<<"\nAfter make_heap call, vec contains:"; for(it = vec.begin(); it != vec.end(); ++it) cout<<" "<<*it; //sort the max heap sort_heap(vec.begin(), vec.end()); cout<<"\nAfter sort_heap call, vec contains:"; for(it = vec.begin(); it != vec.end(); ++it) cout<<" "<<*it; return 0; }

/* vector::push_back() is a library function of "vector" header, it is used to insert/add an element at the end of the vector, it accepts an element of the same type and adds the given element at the end of the vector and increases the size of the vector. */ //C++ STL program code example to demonstrate example of vector::push_back() function #include <iostream> #include <vector> using namespace std; int main() { //vector declaration vector<int> v1; //inserting elements and printing size cout << "size of v1: " << v1.size() << endl; v1.push_back(10); cout << "size of v1: " << v1.size() << endl; v1.push_back(20); v1.push_back(30); v1.push_back(40); v1.push_back(50); cout << "size of v1: " << v1.size() << endl; //printing all elements cout << "elements of vector v1..." << endl; for (int x : v1) cout << x << " "; cout << endl; return 0; }

/* function templates in C++ language */ /* adding two numbers using function templates */ #include <iostream> using namespace std; template <typename T> T add(T num1, T num2) { return (num1 + num2); } int main() { int result1; double result2; // calling with int parameters result1 = add<int>(2, 3); cout << "2 + 3 = " << result1 << endl; // calling with double parameters result2 = add<double>(2.2, 3.3); cout << "2.2 + 3.3 = " << result2 << endl; return 0; }

/* Iterators in C++ language */ // C++ code to demonstrate the working of next() and prev() #include<iostream> #include<iterator> // for iterators #include<vector> // for vectors using namespace std; int main() { vector<int> ar = { 1, 2, 3, 4, 5 }; // Declaring iterators to a vector vector<int>::iterator ptr = ar.begin(); vector<int>::iterator ftr = ar.end(); // Using next() to return new iterator // points to 4 auto it = next(ptr, 3); // Using prev() to return new iterator // points to 3 auto it1 = prev(ftr, 3); // Displaying iterator position cout << "The position of new iterator using next() is : "; cout << *it << " "; cout << endl; // Displaying iterator position cout << "The position of new iterator using prev() is : "; cout << *it1 << " "; cout << endl; return 0; }

/* Templates are the foundation of generic programming, which involves writing code in a way that is independent of any particular type. A template is a blueprint or formula for creating a generic class or a function. */ #include <iostream> using namespace std; template <typename T> class Array { private: T *ptr; int size; public: Array(T arr[], int s); void print(); }; template <typename T> Array<T>::Array(T arr[], int s) { ptr = new T[s]; size = s; for(int i = 0; i < size; i++) ptr[i] = arr[i]; } template <typename T> void Array<T>::print() { for (int i = 0; i < size; i++) cout<<" "<<*(ptr + i); cout<<endl; } int main() { int arr[5] = {1, 2, 3, 4, 5}; Array<int> a(arr, 5); a.print(); return 0; }