Programming Forums > Application Development > C++

Josef_Stalin · May 2nd, 2005, 1:06 AM

What is the difference between the sort function and the sort_heap function in the algorithm header, what is a heap (I suppose it has something to do with memory), and how does it apply to this situation?

Also, what does the Transform function in that header do?

Eggbert · May 2nd, 2005, 9:19 AM

>What is the difference between the sort function and the sort_heap function in the algorithm header
std::sort works correctly with a single call, while to use std::sort_heap, you need to create a heap first, probably with std::make_heap. std::sort does not specify what algorithm it uses. I know at least one implementation that uses a combination of quicksort, heapsort, and insertion sort (the official name is introspective sort, or introsort). On the other hand, std::sort_heap practically requires half of the heapsort algorithm (the other half being the equivalent of std::make_heap).

So there are significant differences, though unless you care about small performance differences or how the algorithms are implemented, this

(Toggle Plain Text)

sort ( begin, end );

is roughly equivalent to this

(Toggle Plain Text)

make_heap ( begin, end );
sort_heap ( begin, end );

>what is a heap
When people talk about a heap, they typically mean a binary heap. It is a simple and intuitive data structure well suited to efficient priority queue operations.

>what does the Transform function in that header do?
std::transform assigns the result of an operation on the first sequence to the second sequence. Assuming I had a vector of int and wanted to add one to all of the values in that vector and print them to cout, I could use transform as such:

(Toggle Plain Text)

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <vector>

using namespace std;

template <typename T, size_t N>
char (&array(T(&)[N]))[N];

int main()
{
  int init[] = {0,1,2,3,4,5,6,7,8,9};
  vector<int> v ( init, init + sizeof array ( init ) );

  copy ( v.begin(), v.end(), ostream_iterator<int> ( cout, " " ) );
  cout<<endl;
  transform ( v.begin(), v.end(), ostream_iterator<int> ( cout, " " ),
    bind1st ( plus<int>(), 1 ) );
  cout<<endl;
}

Alternatively, it is legal for transform to write to the first sequence, so the previous program could be rewritten as:

(Toggle Plain Text)

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <vector>

using namespace std;

template <typename T, size_t N>
char (&array(T(&)[N]))[N];

int main()
{
  int init[] = {0,1,2,3,4,5,6,7,8,9};
  vector<int> v ( init, init + sizeof array ( init ) );

  copy ( v.begin(), v.end(), ostream_iterator<int> ( cout, " " ) );
  cout<<endl;
  transform ( v.begin(), v.end(), v.begin(), bind1st ( plus<int>(), 1 ) );
  copy ( v.begin(), v.end(), ostream_iterator<int> ( cout, " " ) );
  cout<<endl;
}

Josef_Stalin · May 2nd, 2005, 12:18 PM

Thanks again.

May 2nd, 2005, 1:06 AM	#1
Josef_Stalin Programmer Join Date: Apr 2005 Posts: 77 Rep Power: 4	Sort function vs. sort_heap function + Transform Function What is the difference between the sort function and the sort_heap function in the algorithm header, what is a heap (I suppose it has something to do with memory), and how does it apply to this situation? Also, what does the Transform function in that header do? Last edited by Josef_Stalin; May 2nd, 2005 at 1:27 AM.

May 2nd, 2005, 9:19 AM	#2
Eggbert Professional Programmer Join Date: Nov 2004 Posts: 250 Rep Power: 5	>What is the difference between the sort function and the sort_heap function in the algorithm header std::sort works correctly with a single call, while to use std::sort_heap, you need to create a heap first, probably with std::make_heap. std::sort does not specify what algorithm it uses. I know at least one implementation that uses a combination of quicksort, heapsort, and insertion sort (the official name is introspective sort, or introsort). On the other hand, std::sort_heap practically requires half of the heapsort algorithm (the other half being the equivalent of std::make_heap). So there are significant differences, though unless you care about small performance differences or how the algorithms are implemented, this (Toggle Plain Text) sort ( begin, end ); sort ( begin, end ); is roughly equivalent to this (Toggle Plain Text) make_heap ( begin, end ); sort_heap ( begin, end ); make_heap ( begin, end ); sort_heap ( begin, end ); >what is a heap When people talk about a heap, they typically mean a binary heap. It is a simple and intuitive data structure well suited to efficient priority queue operations. >what does the Transform function in that header do? std::transform assigns the result of an operation on the first sequence to the second sequence. Assuming I had a vector of int and wanted to add one to all of the values in that vector and print them to cout, I could use transform as such: (Toggle Plain Text) #include <algorithm> #include <functional> #include <iostream> #include <iterator> #include <vector> using namespace std; template <typename T, size_t N> char (&array(T(&)[N]))[N]; int main() { int init[] = {0,1,2,3,4,5,6,7,8,9}; vector<int> v ( init, init + sizeof array ( init ) ); copy ( v.begin(), v.end(), ostream_iterator<int> ( cout, " " ) ); cout<<endl; transform ( v.begin(), v.end(), ostream_iterator<int> ( cout, " " ), bind1st ( plus<int>(), 1 ) ); cout<<endl; } #include <algorithm> #include <functional> #include <iostream> #include <iterator> #include <vector> using namespace std; template <typename T, size_t N> char (&array(T(&)[N]))[N]; int main() { int init[] = {0,1,2,3,4,5,6,7,8,9}; vector<int> v ( init, init + sizeof array ( init ) ); copy ( v.begin(), v.end(), ostream_iterator<int> ( cout, " " ) ); cout<<endl; transform ( v.begin(), v.end(), ostream_iterator<int> ( cout, " " ), bind1st ( plus<int>(), 1 ) ); cout<<endl; } Alternatively, it is legal for transform to write to the first sequence, so the previous program could be rewritten as: (Toggle Plain Text) #include <algorithm> #include <functional> #include <iostream> #include <iterator> #include <vector> using namespace std; template <typename T, size_t N> char (&array(T(&)[N]))[N]; int main() { int init[] = {0,1,2,3,4,5,6,7,8,9}; vector<int> v ( init, init + sizeof array ( init ) ); copy ( v.begin(), v.end(), ostream_iterator<int> ( cout, " " ) ); cout<<endl; transform ( v.begin(), v.end(), v.begin(), bind1st ( plus<int>(), 1 ) ); copy ( v.begin(), v.end(), ostream_iterator<int> ( cout, " " ) ); cout<<endl; } #include <algorithm> #include <functional> #include <iostream> #include <iterator> #include <vector> using namespace std; template <typename T, size_t N> char (&array(T(&)[N]))[N]; int main() { int init[] = {0,1,2,3,4,5,6,7,8,9}; vector<int> v ( init, init + sizeof array ( init ) ); copy ( v.begin(), v.end(), ostream_iterator<int> ( cout, " " ) ); cout<<endl; transform ( v.begin(), v.end(), v.begin(), bind1st ( plus<int>(), 1 ) ); copy ( v.begin(), v.end(), ostream_iterator<int> ( cout, " " ) ); cout<<endl; }

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

May 2nd, 2005, 12:18 PM	#3
Josef_Stalin Programmer Join Date: Apr 2005 Posts: 77 Rep Power: 4	Thanks again.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > C++

Sort function vs. sort_heap function + Transform Function