Problem with comparison function for std::sort()

[Fbody]

I am trying to sort a vector that is a protected member of a templated class into a Descending order based on the second member of the contained std::pair objects. The vector has the following declaration:

vector< pair <const T, int> > mode;  //holds pairs to define the mode(s) of the dataSet

I'm aware of the std::map container, and I had considered it. The problem is the strict weak ordering that it requires is not appropriate for the problem domain as the ordering is based on the first member of the pairs and I need the values sorted based on the second member of the pairs. I would reverse the roles, but the second member isn't unique across the set, so I can't.

I'm trying to provide the sort function with a comparison function declared and implemented thus:

bool Descending(const pair<const T, int> &, const pair<const T, int> &) const;

template <typename T> bool Stats<T>::Descending(const pair<const T, int> &lhs,
         const pair<const T, int> &rhs) const {
    return (lhs.second > rhs.second);
  }

Based on the reference material(s) @ cplusplus.com,, I'm calling the 3-argument version of sort correctly. I have tried it 4 different ways (implicitly and explicitly):

sort(mode.begin(), mode.end(), Descending);  //implicit call 1
std::sort(mode.begin(), mode.end(), Descending);  //implicit call 2

sort< vector <pair<const T, int> >::const_iterator, bool>(mode.begin(), mode.end(), Descending);  //explicit call 1
std::sort< vector < pair< const T, int> >::const_iterator, bool>(mode.begin(), mode.end(), Descending);  //explicit call 2

In all instances, I get this error:

stats.cpp(87) : error C3867: 'Statistics::Stats<T>::Descending': function call missing argument list; use '&Statistics::Stats<T>::Descending' to create a pointer to member

If I try to use the reference operator as it suggests, it tells me that it's illegal. If I change the reference to &Stats<T>::Descending , I get an error in the xutility library file related to the pair and the assignment operator that I wasn't getting before.
Additionally, the implicit versions get this:

stats.cpp(88) : error C2780: 'void std::sort(_RanIt,_RanIt)' : expects 2 arguments - 3 provided

The sort takes place inside a member function of the template class, so I should have access to the data members:

template <typename T> bool Stats<T>::UpdateMode(const T &newDatum) {
  using std::sort;

} //end Stats<T>::UpdateMode()

I have tried moving the comparison function from protected to public, but it didn't make a difference. There are 2 places where I do this, they are both identical calls and have identical member access, but the second one refuses to work correctly. What have I got wrong?

I'm trying to avoid overloading operator< for the 2-argument version. I need the values sorted in Descending order instead of Ascending order so I would have to overload it "backwards" from how it should function.

[mrnutty]

>>I'm aware of the std::map container, and I had considered it. The problem is the strict weak ordering that it requires is not appropriate for the problem domain as the ordering is based on the first member of the pairs and I need the values sorted based on the second member of the pairs.

you can supply the map with a comparion function in its constructor. And can you explain why strict ordering would fail with your data set?

Also your problem is that member function pointer are very different from regular pointer function. With member function pointer you have to provide it with an instance. Try something like std::sort(v.begin(),v.end(),&(this->Descending))

[mitrmkar]

Though I might be missing something here, but anyhow, I think changing the comparison functions to static would be in order here, so you'd have:

static bool Descending(const pair<const T, int> &, const pair<const T, int> &);

sort(mode.begin(), mode.end(), &Statistics::Stats<T>::Descending);

P.S. Why the const in the vector declaration (i.e. const T), are you sure about it?

[Fbody]

>>can you explain why strict ordering would fail with your data set?
Perhaps I said it incorrectly. As described (on cplusplus.com), the way a map orders itself is not correct for what I need. That being said, is it possible to create a comparison function for a map that will compare based on the value of the second data member of the pair instead of the first or "key" value? See explanation below:
The mode of a set of data is the most frequently occurring value. The issue is that there can be more than 1 mode within a given set of data. The mode vector is essentially a vector of "counters". In a pair, the "key" (first data member) represents the specific data value being counted. The second data member is the count of occurrences (or frequency) of that specific value within the data set.

Once all the values have been counted, I need the counts sorted into descending order based on the frequency of occurrence, not the actual value being counted. Doing this puts the mode(s) at the beginning of the vector making them more-easily accessible by the client code, which hopefully makes the whole package more efficient.

I'm starting to think of a different way of doing this as I'm writing this. I'm going to stick with this for now, but I'm going to experiment a little more with a different option.

>>Why the const in the vector declaration (i.e. const T), are you sure about it?
Yes. I do not want the first data member's value to be changeable. Please see explanation above for why. Essentially, it's a "key" or an "ID" whose value I need to be able to rely on the accuracy of.

Hopefully that clears some things up.

So far, I haven't had any luck with using this and/or the reference operator. I'm going to try calling it static in a little bit here.

Thanks so far.

[mrnutty]

Can you settle for this :

template<typename T1, typename T2>
struct Pair : std::pair<T1,T2>{
};
template<typename T1, typename T2>
bool compareSecond(const Pair<T1,T2>& p1, const Pair<T1,T2>& p2){
 return p1.second < p2.second;
}

//use Pair instead of std::pair

[mitrmkar]

>> >>Why the const in the vector declaration (i.e. const T), are you sure about it?
>> Yes. I do not want the first data member's value to be changeable.

The const is likely to cause the code to break at the point where you are e.g. trying to store something in the vector. Maybe you just haven't gotten to that point yet?

A small example of it failing

#include <vector>
#include <utility>

int main()
{
  std::vector<std::pair<const int, int> > vect;  

  // This will not compile ...
  vect.push_back(std::make_pair(0,0));
}

Trying that with Comeau online gives a nice error message:

"stl_pair.h", line 37: error: implicitly generated assignment operator
cannot copy:
const member "std::pair<_T1, _T2>::first [with _T1=const int,
_T2=int]"

[Fbody]

>> >>Why the const in the vector declaration (i.e. const T), are you sure about it?
>> Yes. I do not want the first data member's value to be changeable.

The const is likely to cause the code to break at the point where you are e.g. trying to store something in the vector. Maybe you just haven't gotten to that point yet?

A small example of it failing

#include <vector>
#include <utility>

int main()
{
  std::vector<std::pair<const int, int> > vect;  

  // This will not compile ...
  vect.push_back(std::make_pair(0,0));
}

Trying that with Comeau online gives a nice error message:

"stl_pair.h", line 37: error: implicitly generated assignment operator
cannot copy:
const member "std::pair<_T1, _T2>::first [with _T1=const int,
_T2=int]"

Hmmm.... I've been testing my code right along to make sure things are working. I thought I had successfully tested the pairs with the const member. It's possible I'm mistaken though because if I remove the calls to std::sort, I get errors related to operator= that appear to be originating from the xutility file, which std::pair is part of.

I'm also finding that I may have to implement my own sort(s) for this. It doesn't seem to matter what I do, the compiler won't accept my call to std::sort (thanks for the suggestions by the way). It keeps telling me either that I've not supplied arguments to the custom sorting function or that I'm attempting to call the 2-argument version of it with 3 arguments.

On that note, I think I need to dedicate my time to understanding sorting algorithms better before finishing this. Right now, the only algorithms that I really understand are Bubble and Selection, but those really aren't good for this project. I'm starting to understand Insertion now, but I'm having trouble extending that to a Shell. I seem to have gotten a Shell-like algorithm to work, but I don't think it's technically correct. Thoughts?

template <typename T> class DataSet {
  protected:
    vector<T> m_DataSet;

  public:
    DataSet();
    DataSet(int);
    void GenerateNewRandomSet();
    void ShellSort();

  };  //end DataSet<T> class definition



  //perform a Shell sort
  template <typename T> void DataSet<T>::ShellSort() {
    //calculate the starting increment
    int inc = (m_DataSet.size() / 3);
    while (inc > 0) {
      for(int unsortedIndex = inc; unsortedIndex < m_DataSet.size(); unsortedIndex += inc) {

        for (int destinationIndex = 0; destinationIndex < unsortedIndex; destinationIndex += inc) {

          if (m_DataSet[destinationIndex] > m_DataSet[unsortedIndex]) {
            T temp = m_DataSet[unsortedIndex];

            for (int slideIndex = (unsortedIndex - inc); slideIndex >= destinationIndex; slideIndex -= inc) {
              m_DataSet[slideIndex + inc] = m_DataSet[slideIndex];
            } //end slideIndex for

            m_DataSet[destinationIndex] = temp;

          } //end if
        } //end destinationIndex for
      } //end unsortedIndex for

      inc = inc / 3.0;
    } //end increment while

  } //end DataSet<T>::ShellSort()



int main() {
  srand((unsigned) time(0));

  DataSet<dataSetType> myData(Statistics::SET_SIZE);

  myData.ShellSort();         //run a test shell sort

  return 0;
}