Use templates to implement heap sorting (three ways to customize comparison rules: overload comparison operators, namespace extension & template specialization, and custom function objects)

Using templates to implement heap sorting:

How to sort user-defined types during heap sorting? (Such as Point class)

For custom types, we need to define our own set of size comparison rules, the following three methods are used

1. Operator overloading (< and >)
2. Namespace extensions, template specializations
3. custom function object

1. Overloading comparison operators

//overload comparison operator
bool operator<(const Point & amp; lhs, const Point & amp; rhs)
{<!-- -->
    if(lhs. getDistance() < rhs. getDistance())
    {<!-- -->
        return true;
    }
    else if(lhs. getDistance() == rhs. getDistance())
    {<!-- -->
        if(lhs. getX() < rhs. getX())
        {<!-- -->
            return true;
        }
        else if(lhs. getX() == rhs. getX())
        {<!-- -->
            if(lhs. getY() < rhs. getY())
            {<!-- -->
                return true;
            }
            else
            {<!-- -->
                return false;
            }
        }
        else
        {<!-- -->
            return false;
        }
    }
    else
    {<!-- -->
        return false;
    }
}

2. The namespace is expanded and the template is specialized

namespace std
{<!-- -->
//The specialization of less in the std namespace, pay attention to the specialization of the template
template<>
struct less<Point>
{<!-- -->
    bool operator()(const Point & amp; lhs, const Point & amp; rhs) const
    {<!-- -->
        if(lhs. getDistance() < rhs. getDistance())
        {<!-- -->
            return true;
        }
        else if(lhs. getDistance() == rhs. getDistance())
        {<!-- -->
            if(lhs. getX() < rhs. getX())
            {<!-- -->
                return true;
            }
            else if(lhs. getX() == rhs. getX())
            {<!-- -->
                if(lhs. getY() < rhs. getY())
                {<!-- -->
                    return true;
                }
                else
                {<!-- -->
                    return false;
                }
            }
            else
            {<!-- -->
                return false;
            }
        }
        else
        {<!-- -->
            return false;
        }
    }
};

3. Custom function object

//Function object
struct Comparetion
{<!-- -->
    bool operator()(const Point & amp; lhs, const Point & amp; rhs) const
    {<!-- -->
        if(lhs. getDistance() < rhs. getDistance())
        {<!-- -->
            return true;
        }
        else if(lhs. getDistance() == rhs. getDistance())
        {<!-- -->
            if(lhs. getX() < rhs. getX())
            {<!-- -->
                return true;
            }
            else if(lhs. getX() == rhs. getX())
            {<!-- -->
                if(lhs. getY() < rhs. getY())
                {<!-- -->
                    return true;
                }
                else
                {<!-- -->
                    return false;
                }
            }
            else
            {<!-- -->
                return false;
            }
        }
        else
        {<!-- -->
            return false;
        }
    }
};

All code

#include 
#include 
#include 
#include 

using std::cout;
using std::cin;
using std::endl;
using std::vector;

template
void swap(T & amp; lhs, T & amp; rhs)
{
    auto temp = lhs;
    lhs = rhs;
    rhs = temp;
}

class point
{
public:
    Point(int ix = 0, int iy = 0)
    : _ix(ix)
    , _iy(iy)
    {
    }

    ~Point()
    {
    }

    void print() const
    {
        cout << "(" << _ix
            << ", " << _iy
            << ")" << endl;
    }

    double getDistance() const
    {
        return hypot(_ix, _iy);
    }

    int getX() const
    {
        return _ix;
    }

    int getY() const
    {
        return _iy;

    }

    friend std::ostream & amp; operator<<(std::ostream & amp;os, const Point & amp;rhs);
private:
    int _ix;
    int _iy;
};

std::ostream & amp; operator<<(std::ostream & amp;os, const Point & amp;rhs)
{
    os << "(" << rhs._ix
       << ", " <
    if(lhs. getDistance() < rhs. getDistance())
    {
        return true;
    }
    else if(lhs. getDistance() == rhs. getDistance())
    {
        if(lhs. getX() < rhs. getX())
        {
            return true;
        }
        else if(lhs. getX() == rhs. getX())
        {
            if(lhs. getY() < rhs. getY())
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        else
        {
            return false;
        }
    }
    else
    {
        return false;
    }
}

// function object
struct comparison
{
    bool operator()(const Point & amp; lhs, const Point & amp; rhs) const
    {
        if(lhs. getDistance() < rhs. getDistance())
        {
            return true;
        }
        else if(lhs. getDistance() == rhs. getDistance())
        {
            if(lhs. getX() < rhs. getX())
            {
                return true;
            }
            else if(lhs. getX() == rhs. getX())
            {
                if(lhs. getY() < rhs. getY())
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            else
            {
                return false;
            }
        }
        else
        {
            return false;
        }
    }
};

namespace std
{
//Specialization of less in the std namespace, pay attention to the specialization of the template
template<>
struct greater
{
    bool operator()(const Point & amp;lhs,const Point & amp;rhs) const
    {
        if(lhs. getDistance() > rhs. getDistance())
        {
            return true;
        }
        else if(lhs. getDistance() == rhs. getDistance())
        {
            if(lhs. getX() > rhs. getX())
            {
                return true;
            }
            else if(lhs. getX() == rhs. getX())
            {
                if(lhs. getY() > rhs. getY())
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            else
            {
                return false;
            }
        }
        else
        {
            return false;
        }
    }
};

}//end of namespace std

bool operator>(const Point & amp;lhs, const Point & amp;rhs)
{
    if(lhs. getDistance() > rhs. getDistance())
    {
        return true;
    }
    else if(lhs. getDistance() == rhs. getDistance())
    {
        if(lhs. getX() > rhs. getX())
        {
            return true;
        }
        else if(lhs. getX() == rhs. getX())
        {
            if(lhs. getY() > rhs. getY())
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        else
        {
            return false;
        }
    }
    else
    {
        return false;
    }
}

template >
class HeapSort
{
public:
    HeapSort(T *arr, size_t size, Compare);
    void heapAdjust(size_t, size_t, Compare &);
    void sort(Compare &);
    void print();

private:
    vector vec;
};

template 
HeapSort::HeapSort(T *arr, size_t size, Compare com)
{
    for (size_t i = 0; i < size; i ++ )
    {
        vec.push_back(arr[i]);
    }
    for (int i = size/2 - 1; i >= 0; i--)
    {
        heapAdjust(i, size, com);
    }
    swap(arr[0], arr[size - 1]);
    sort(com);

}

template 
void HeapSort::heapAdjust(size_t adjustpos, size_t arrlen, Compare & amp; com)
{

    size_t dad = adjustpos;
    size_t son = 2 * dad + 1;
    while(son < arrlen)
    {
        if(son + 1 < arrlen & amp; & com(vec[son], vec[son + 1]))
        {
             + + son;
        }
        if(com(vec[dad], vec[son]))
        {
            swap(vec[dad], vec[son]);
            dad = son;
            son = 2 * dad + 1;
        }
        else
        {
            break;
        }
    }
}


template 
void HeapSort::sort(Compare & amp; com)
{
    size_t size = vec. size();
    for (size_t i = size; i > 1; i--)
    {
        heapAdjust(0, i, com);
        swap(vec[0], vec[i - 1]);
    }
}

template 
void HeapSort::print()
{
    for(auto & elem : vec)
    {
        cout << elem << " ";
    }
    cout << endl;
}



int main(int argc, char **argv)
{
    int arr[10] = {1, 2, 6, 3, 4, 8, 5, 7, 9, 10};
    HeapSort hs(arr, 10, std::less());
    hs. print();
    cout << endl;
    Point par[5] = {{1,2}, {3,4}, {-1 ,2}, {4,5}, {2,5}};

    HeapSort hsPt(par, 5, std::less());
    hsPt. print();

    return 0;
}

Cause analysis:

Tip: Fill in the analysis of the question here:

For example: Handler There are two ways to send messages, namely Handler.obtainMessage() and Handler.sendMessage(), where obtainMessage method When the amount of data is too large, because the size of MessageQuene is also limited, so when the message is not processed in time, the first transmitted data will be overwritten, and then result in data loss.

Solution:

Tip: Fill in the specific solution to this problem here:

For example: create a new Message object, and store the read data into Message, then mHandler.obtainMessage(READ_DATA, bytes, -1, buffer). sendToTarget(); is replaced by mHandler.sendMessage().