Problems understanding iterators and operator overload in c++

Question

We have a class example and I just don't get it. I don't quite understand how the operator() works in this case, and everything starting with sort. I looked at the output after running the program, and I don't see how those values are obtained.

sort indices array: 2 8 10 4 1 7 5 3 0 9 6 11
replay numbers array: 37 33 29 36 32 35 39 34 30 38 31 40
number array via indices 29 30 31 32 33 34 35 36 37 38 39 40

I tried looking up functors on this board since the title is functor example, but I guess I don't see how functors are in play here. Any thoughts would be GREATLY appreciated as I am COMPLETELY lost. Thanks!

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

#include "IndexCompare.h"

using namespace std;

template <class ForwardIterator, class T>
void iota(ForwardIterator first, ForwardIterator last, T value) {
     while (first != last) {
        *first++ = value++;
     }
}

const int MAX = 12;

int main() {
    int numbers[] = {37, 33, 29, 36, 32, 35, 39, 34, 30, 38, 31, 40};

    vector<int> vecNum(numbers, numbers + MAX);

    // Display original number array.
    cout << "--- initial numbers array ---" << endl;

    vector<int>::iterator iter = vecNum.begin();
    for (; iter != vecNum.end(); iter++ ) {
        cout << *iter << " ";
    }
    cout << "\n";

    vector<int> indices( vecNum.size() );

    // fill indices array
    cout << "\n--- invoke 'iota' on indices array ---";
    iota( indices.begin(), indices.end(), 0 );

    // Display original indices array.
    cout << "\n linear indices array: ";
    vector<int>::iterator iterIdx = indices.begin();
    for (; iterIdx != indices.end(); iterIdx++ ) {
        cout << *iterIdx << " ";
    }
    cout << "\n";

    // sort indices array
    cout << "\n--- invoke 'Sort' on indices based on number array ---";
    sort(indices.begin(), indices.end(),
          IndexCompare<vector<int>::iterator>(vecNum.begin(),vecNum.end()));

    // Display sorted indices array
    cout << "\n Sorted indices array: ";
    for (iterIdx = indices.begin(); iterIdx != indices.end(); iterIdx++ ) {
        cout << *iterIdx << " ";
    }
    cout << "\n";

    cout << "\n--- Run check on number array indexed normally ---";
    // Display original numbers array.
    cout << "\n replay numbers array: ";
    iter = vecNum.begin();
    for (; iter != vecNum.end(); iter++ ) {
        cout << *iter << " ";
    }
    cout << "\n";

    cout << "\n--- Run check on number array indexed with sorted indices ---";
    // Print original nums array indirectly through indices.
    cout << "\n number array via indices: ";
    for (int index = 0; index < vecNum.size(); index++ )
        cout << vecNum[indices[index]] << " ";
    cout << "\n";

    getchar();

    return 0;
}

// IndexCompare.h - interface for IndexCompare class template
#ifndef _INDEXCOMPARE_H_
#define _INDEXCOMPARE_H_
#pragma once

template <class random_iterator>
class IndexCompare {
public:
    IndexCompare(random_iterator begin, random_iterator end)
        : begin(begin), end(end) {}

    ~IndexCompare() {}

    bool operator() (unsigned int first, unsigned int second) {
            return (*(begin + first) < *(begin + second));

    }

private:
    random_iterator begin;
    random_iterator end;
};

#endif

Answer 1

I am not sure I will be able to explain this correctly. Here is my try:

(1). vector<int> indices( vecNum.size() );

You are creating a vector to hold the indexes for the elements in vector vecNum. Obviously the number of elements in this vector is same as number of elements in vecNum.

(2). iota( indices.begin(), indices.end(), 0 );

Initializing the indices with values from 0 - vecNum.size() - 1

(3).

sort(indices.begin(), indices.end(),
              IndexCompare<vector<int>::iterator>(vecNum.begin(),vecNum.end()));

For each element in the indices vector invoke the functor IndexCompare. This functor in its operator() gets the value from the vecNum vector corresponding to the given index position. So basically you are sorting the indices vector (not vecNum) based on the values in vecNum. Hence the vecNum remains unaffected and indices gets sorted based on the values from vecNum.

To make it more clearer (I hope), the initial state of the indices vector will be say: indices = 0,1,2 and vecNum = 20,10,30

Now you are calling std::sort on this with your own functor. So to determine whether 0 is less than 1 sort algorithm will use your functor. Inside the functor you are determinng whether 0 < 1 using the logic whether vecNum[0] (i.e. 20) < vecNum[1] (i.e. 10). So the sorted out put will be indices = 1,0,2.