C++ How to use std::sort to sort a array of objects in c++

Question

I have the template class and array of pointers to objects and overloaded logic operators for my objects. My bubble sort is working. So it's know how to compare my objects I want to replace it with standard sort Declaration

Implementation List.tem

#include <stdio.h>
#include <stdlib.h>
#include <vector>
///////////////
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

template <class Type>
List<Type>::List()
{
    itemPtr = NULL;
    used = 0;
    size = 0;
}


template <class Type>
List<Type>::List(const List<Type>& source)
{
    itemPtr = NULL;
    used = 0;
    size = source.size;
    itemPtr = new Type[size];
    for(int i = 0; i < source.used; i++)
        addItem(source.itemPtr[i]);
}

template <class Type>
List<Type>& List<Type>::operator = (const List<Type>& source)
{
    used = 0;
    if(this == &source)
        return(*this);  
    free();

    size = source.size;
    itemPtr = new Type[size];

    for(int i = 0; i < source.used; i++)
        addItem(source.itemPtr[i]);
    return(*this);
}    

template <class Type>
List<Type>::~List()
{
    free();
}

template <class Type>
void List<Type>::free() 
{
    if(itemPtr != NULL)
    {
        delete [] itemPtr;
        itemPtr = NULL;
    }
}

template <class Type>
void List<Type>::alloc(int sizeIcrease) 
{
    Type* tmpPtr = NULL;
    size += sizeIcrease;
    tmpPtr = new Type[size];
    copy(itemPtr, itemPtr+used, tmpPtr);
    free();
    itemPtr = tmpPtr;
}

template <class Type>
Type List<Type>::getItem(int index) const
{
    Type item;
    if(index >= 0 && index < used)
        item = itemPtr[index];
    return (item);
}    

template <class Type>
int List<Type>::findItem(Type itemIn)
{
    int i = 0;
    for(i = 0; i < used; i++)
        if(itemPtr[i] == itemIn)
            break;
    if (i == used)  i = -1;
    return (i);
}

template <class Type>
void List<Type>::addItem(Type itemIn)
{
    if(used == size) alloc(10);
    itemPtr[used++] = itemIn;
    bubbles();
}

template <class Type>
void List<Type>::removeItem(Type itemIn)
{
    int index = findItem(itemIn);
    removeItem(index);
}

template <class Type>
void List<Type>::removeItem(int index)
{
    if(index >= 0 && index < used)
        itemPtr[index] = itemPtr[--used];
    bubbles();
}

template <class Type>
void List<Type>::readFile(Field fileName)
{
    Type itemTmp;   
    ifstream inFile(fileName.c_str());
    if(!inFile)
        cout << "Error opening file\n";
    do
    {
        inFile >> itemTmp;
        if(!inFile.fail())
            addItem(itemTmp);

    } while (!inFile.fail());
    //bubbles();
    vector<Type*> myvector; //(itemPtr, itemPtr+used);

    vector<Type>::iterator it;
    sort (myvector.begin(), myvector.end(), sort_by_pointee<Type>());
    inFile.close();
}


template <class Type>
void List<Type>::writeFile(Field fileName)
{
    ofstream outFile;
    outFile.open(fileName.c_str());
    if(!outFile)
        cout << "Error opening file\n";

    for(int i = 0; i < used; i++)
    {
        outFile << itemPtr[i] << "\n";
    }

    outFile.close();
}
    template <class Type>
void List<Type>::print()
{
//////Coded
}

template <class Type>
void List<Type>::bubbles()
{
////// Coded
}

template <class Type>
ostream& operator<<(ostream& os, const List<Type>& ad)
{
    for(int i = 0; i < ab.used; i++)    
        os << ab.getItem(i) << endl;
    return os;
}
template <class Type>
ofstream& operator<<(ofstream& ofs, const List<Type>& ad)
{
    for(int i = 0; i < ab.used; i++)            
        ofs << ab.getItem(i) << ",";
    return ofs;
}

template<class Type>
struct sort_by_pointee 
{
    bool operator() (const Type* lhs, const Type* rhs) const
    {
        return (*lhs < *rhs);
    }
};

Or en.cppreference.com/w/cpp/algorithm/sort, which is better than the old, somewhat incorrect cpluplus.com. — user406009
– user406009, Commented Mar 25, 2012 at 17:41

André Caron · Accepted Answer · 2012-03-27 03:58:48Z

3

If the third argument to std::sort() is not provided, objects are sorted using operator< like:

if (a < b) {
   // ...
}

So all you need to sort objects of type Foo is to have either:

bool Foo::operator< (const Foo& rhs) const;

or

bool operator< (const Foo& lhs, const Foo& rhs);

That being said, if you have an array of pointers, then you will need to provide a custom predicate unless you want to sort objects by their memory address (I highly doubt this is what you want). You can do something like:

template<class T>
struct sort_by_pointee {
    bool operator() (const T* lhs, const T* rhs) const
    {
        return (*lhs < *rhs);
    }
};

And use it like:

std::vector<Foo*> foos;
// ...
std::sort(foos.begin(), foos.end(), sort_by_pointee<Foo>());

Edit: the sample you posted will work fine and sort the data, but the vector does not act as a proxy for the data stored in the itemPtr array. Read it again with my annotations:

{ 
    vector<Type> myvector (itemPtr, itemPtr+8);
    // 'myvector' holds a copy of the first 8 elements in the 'itemPtr' array.

    sort (myvector.begin(), myvector.end());
    // contents of 'myvector' are sorted, but this is a copy of 'itemPtr''s
    // contents, so items in 'itemPtr' are still in their original order.
}

If you want to sort the contents of [itemPtr,itemPtr+8) in-place, you can just do:

std::sort(itemPtr, itemPtr+8); // use custom predicate if required.

Edit: OK, following the code you posted, I would fix the readFile() method from its original definition to:

template <class Type>
void List<Type>::readFile(Field path)
{
    ifstream file(path.c_str());
    if(!file.is_open()) {
        cout << "Error opening file\n";
    }
    for (Type item; file >> item;) {
        addItem(item);
    }
    sort (itemPtr, itemPtr+used);
}

edited Mar 27, 2012 at 3:58

answered Mar 25, 2012 at 17:41

André Caron

45.5k12 gold badges72 silver badges125 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

nekto Over a year ago

Compiled, but still not sorted. I have my "bool operator<" overloading inside my object class. Is this a problem?

André Caron Over a year ago

@user1290873: Perhaps it'd be easier if you posted a minimal program that reproduces your problem. In particular, the class name, operator< declaration, the std::vector<> object and the call to std::sort() will be relevant. If you don't mind posting your code as is, just make sure you strip it down so that we can focus on the important parts.

nekto Over a year ago

OK, let's try ... template <class Type> void List<Type>::addItem(Type itemIn) { if(used == size) alloc(5); itemPtr[used++] = itemIn; //bubbles(); vector<Type*> myvector; sort (myvector.begin(), myvector.end(), sort_by_pointee<Type>()); } template<class Type> struct sort_by_pointee { bool operator() (const Type* lhs, const Type* rhs) const { return (*lhs < *rhs); } }; Inside my object class friend bool operator>(const Contact& c1, const Contact& c2); friend bool operator<(const Contact& c1, const Contact& c2);

André Caron Over a year ago

@user1290873: You can't format the code inside comments. Edit your question to post the code.

André Caron Over a year ago

@user1290873: There's a lot of code missing. Also, the code you put in the comments sorts an empty vector of pointers. Perhaps you should post more code, including the definition of your List class.

|

Collectives™ on Stack Overflow

C++ How to use std::sort to sort a array of objects in c++

1 Answer 1

8 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

8 Comments

Your Answer

Sign up or log in

Post as a guest

Related