TheDeveloperBlog.com

Home | Contact Us

C-Sharp | Java | Python | Swift | GO | WPF | Ruby | Scala | F# | JavaScript | SQL | PHP | Angular | HTML

C++ algorithm inplace_merge() function

C++ algorithm inplace_merge() function with c++ tutorial for beginners and professionals with examples on adjacent_find(),any_of(), copy(), copy_if(), count(), count_if(), equal(), find(), find_end(), find_first_of(), find_if(), find_if_not(), for_each() etc.

<< Back to CPP

C++ Algorithm inplace_merge()

C++ Algorithm inplace_merge() function is used to merge two consecutive sorted ranges [first, last) and [middle, last) into one sorted range [first, last).

Elements are compared using operator < for the first version or using the given binary comparison function comp for the second version.

Syntax

default (1)    template <class BidirectionalIterator>
                       void inplace_merge (BidirectionalIterator first, BidirectionalIterator middle,
                                                        BidirectionalIterator last);

custom (2)   template <class BidirectionalIterator, class Compare>
                     void inplace_merge (BidirectionalIterator first, BidirectionalIterator middle,
                                                     BidirectionalIterator last, Compare comp);

Parameter

first: A bidirectional iterator pointing to the first element in the first of two consecutive sorted ranges to be merged and sorted into single range.

last: A bidirectional iterator pointing to the past last element in the second of two consecutive sorted ranges to be merged and sorted into single range.

middle: A bidirectional iterator pointing to the position of the first element in the second of two consecutive sorted ranges to be merged and sorted into a single range.

comp: A user-defined binary predicate function that accepts two arguments and returns true if the two arguments are in order otherwise false. It follows the strict weak ordering to order the elements.

Return value

None

Complexity

If enough extra memory is available, then the complexity is linear in the distance between first and last: performs N-1 comparisons and up to twice that many elements moves.

Otherwise, complexity is linearithmic: performs up to N*log(N) element comparisons where N = last -first and up to that many elements swaps.

Data races

The object in the range [first, last) are modified.

Exceptions

This function throws an exception if any of element comparison, the element swaps (or moves) or an operation on iterator throws an exception.

Note: The invalid parameters cause an undefined behavior.

Example 1

Let's see the simple example to demonstrate the use of inplace_merge():

#include <iostream>    
#include <algorithm>   
#include <vector>       
using namespace std;
 
void printVector(vector<int>& v)
{
    for (vector<int>::iterator it = v.begin(); it != v.end(); ++it)
        cout << ' ' << *it;
    cout << '\n';
}
 
int main () {
    vector<int> v1 = {5,10,15,20,25}, v2 = {50,40,30,20,10}, v3(10);
    vector<int>::iterator it;
 
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    it = copy(v1.begin(), v1.end(), v3.begin());
    copy(v2.begin(), v2.end(), it);
    inplace_merge(v3.begin(), it, v3.end());
 
    cout << "Vector v1 : ";
    printVector(v1);
    cout << "Vector v2 : ";
    printVector(v2);
    cout << "Vector v3 : ";
    printVector(v3);
}

Output:

Vector v1 :  5 10 15 20 25
Vector v2 :  10 20 30 40 50
Vector v3 :  5 10 10 15 20 20 25 30 40 50

Example 2

Let's see another simple example:

#include <iostream>     // std::cout
#include <algorithm>    // std::inplace_merge, std::sort, std::copy
#include <vector>       // std::vector

using namespace std;

int main () {
  int first[] = {5,10,15,20,25};
  int second[] = {50,40,30,20,10};
  vector<int> v(10);
  vector<int>::iterator it;

  sort (first,first+5);
  sort (second,second+5);

  it=copy (first, first+5, v.begin());
     copy (second,second+5,it);

  inplace_merge (v.begin(),v.begin()+5,v.end());

  cout << "The resulting vector contains:";
  for (it=v.begin(); it!=v.end(); ++it)
    cout << ' ' << *it;
  cout << '\n';

  return 0;
}

Output:

The resulting vector contains: 5 10 10 15 20 20 25 30 40 50

Example 3

Let's see another simple example demonstrate the use of inplace_merge() using operator<:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(void) {
   vector<int> v = {1, 3, 2, 4, 5};

   inplace_merge(v.begin(), v.begin() + 2, v.end());

   for (auto it = v.begin(); it != v.end(); ++it)
      cout << *it << endl;

   return 0;
}

Output:

1
2
3
4
5

Example 4

Let's see a simple example to demonstrate the use of inplace_merge() using comparison function:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

bool descending_sort(int a, int b) {
   return (a > b);
}

int main(void) {
   vector<int> v = {3, 1, 5, 4, 2};

   inplace_merge(v.begin(), v.begin() + 2, v.end(), descending_sort);

   for (auto it = v.begin(); it != v.end(); ++it)
      cout << *it << endl;

   return 0;
}

Output:

5
4
3
2
1

Example 5

Let's see another simple example:

#include <vector>
#include <iostream>
#include <algorithm>
 
using namespace std; 
 
template<class Iter>
void merge_sort(Iter first, Iter last)
{
    if (last - first > 1) {
        Iter middle = first + (last - first) / 2;
        merge_sort(first, middle);
        merge_sort(middle, last);
        inplace_merge(first, middle, last);
    }
}
 
int main()
{
    vector<int> v{10, 2, -9, 0, 9, 7, 1, 3, 4};
    merge_sort(v.begin(), v.end());
    for(auto n : v) {
        cout << n << ' ';
    }
    cout << '\n';
    
    return 0;
}

Output:

-9 0 1 2 3 4 7 9 10

Next TopicC++ Algorithm




Related Links:

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

Related Links

Adjectives Ado Ai Android Angular Antonyms Apache Articles Asp Autocad Automata Aws Azure Basic Binary Bitcoin Blockchain C Cassandra Change Coa Computer Control Cpp Create Creating C-Sharp Cyber Daa Data Dbms Deletion Devops Difference Discrete Es6 Ethical Examples Features Firebase Flutter Fs Git Go Hbase History Hive Hiveql How Html Idioms Insertion Installing Ios Java Joomla Js Kafka Kali Laravel Logical Machine Matlab Matrix Mongodb Mysql One Opencv Oracle Ordering Os Pandas Php Pig Pl Postgresql Powershell Prepositions Program Python React Ruby Scala Selecting Selenium Sentence Seo Sharepoint Software Spellings Spotting Spring Sql Sqlite Sqoop Svn Swift Synonyms Talend Testng Types Uml Unity Vbnet Verbal Webdriver What Wpf