STL List Sorting

Pages: 12
Feb 4, 2013 at 2:25pm
Hello guys. I encountered a problem when trying to sort my STL list.

This is my following code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
case 3: {

/* Prompting for user input of price range */
cout << "<<Search by price range>>" << endl << endl;
int search1;
int search2;
cout << "Please enter first range:";
cin >> search1;
cout << endl;
cout << "Please enter second range:";
cin >> search2;

//here is my iterator for my list
//i read up online trying out various sorting like
//i.sort() or WHMgmtDetails.sort(), it does not work.
//when i do list<WHMgmtDetails> lst and then lst.sort(),
//it seems like a command that I could use but how do I use iterator then? do I do lst::iterator i ?              
list<WHMgmtDetails>::iterator i;
   
// this is where i check for the items within the price range                 
while (1) {
for (i = transaction.begin(); i != transaction.end(); ++i) {
if (i->unitPrice >= search1 && i->unitPrice <= search2) {
    cout << "Item ID:    " << i->itemID << endl
    << "Item Description:   " << i->itemDesc << endl
    << "Item Category:      " << i->itemCat << endl
    << "Item Sub Category:  " << i->itemSubCat <<endl
    << "Item amount per unit:       " << i->unitPrice <<endl
    << "Item quantity:      " << i->qty <<endl
    << "Date Purchased:     " << i->date << endl << endl;
    } else {         
    cout << "No such price range found!" << endl;
    }
}
return;
}
}


Feb 4, 2013 at 2:34pm
transaction is your STL Container. std::sort is a global function defined in the <algorithm> header. Try std::sort(transaction.begin(), transaction.end());
http://www.cplusplus.com/reference/algorithm/sort/
Last edited on Feb 4, 2013 at 2:35pm
Feb 4, 2013 at 2:37pm
is there any way for me to sort by the unitPrice(ascending/descending?)
Feb 4, 2013 at 2:41pm
Yes, you can implement a comparator for it:
1
2
3
4
5
6
7
8
9
struct TransactionComparator
{
    bool operator()(const WHMgmtDetails &a, const WHMgmtDetails &b)
    {
        return a.unitPrice < b.unitPrice;
    }
};

std::sort(transaction.begin(), transaction.end(), TransactionComparator());
http://www.cplusplus.com/reference/algorithm/sort/
Last edited on Feb 4, 2013 at 2:42pm
Feb 4, 2013 at 2:48pm
I would imagine you haven't overloaded the comparison operators for your class. If that is the case, then sort has no idea how to sort your object.

You can overload the operators, add a lamda function to the sort that LB posted, or use a comparator function with std::list.sort
http://www.cplusplus.com/reference/list/list/sort/

To change the order of the sort, use a reverse iterator.
Feb 4, 2013 at 2:50pm
thanks alot!
Feb 4, 2013 at 2:50pm
A lambda function is preferable - I used an inline struct because it does not require a C++11 compiler.
Feb 4, 2013 at 3:16pm
L B, I am currently getting errors. instantiated errors from the sort(transaction.begin(), transaction.end(), transactionComparator());

There is also errors for operator- and operator+. How do I solve this
Feb 4, 2013 at 3:24pm
So I have to overload + - and < ?
Feb 4, 2013 at 4:05pm
will this be correct to use?

inline bool operator< (const WHMgmtDetails& a, const WHMgmtDetails& b)
{
return a.unitPrice < b.unitPrice
}
Feb 4, 2013 at 4:33pm
I don't think its recommended to use std:: sort on a std:: list since it will be less efficient then the sort member function, at least that's what I've heard.
Feb 4, 2013 at 10:50pm
@b1b2b3b4 can you post the exact error messages you are getting, along with the code giving you the errors?
Feb 5, 2013 at 8:09am
This is the code I am using to search for price range
And also the code that is giving me error in bold

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
            case 3: {
                    cout << "<<Search by price range (ASCENDING)>>" << endl << endl;
                    int search1;
                    int search2;
                    cout << "Please enter first range:";
                    cin >> search1;
                    cout << endl;
                    cout << "Please enter second range:";
                    cin >> search2;
                    
                    sort(transaction.begin(), transaction.end(), TransactionComparator());
                    list<WHMgmtDetails>::iterator i;
                    while (1) {
                        for (i = transaction.begin(); i != transaction.end(); ++i) {
                            if (i->unitPrice >= search1 && i->unitPrice <= search2) {
                                cout << "Item ID:    " << i->itemID << endl
                                << "Item Description:   " << i->itemDesc << endl
                                << "Item Category:      " << i->itemCat << endl
                                << "Item Sub Category:  " << i->itemSubCat <<endl
                                << "Item amount per unit:       " << i->unitPrice <<endl
                                << "Item quantity:      " << i->qty <<endl
                                << "Date Purchased:     " << i->date << endl << endl;
                            } else {         
                                cout << "No such price range found!" << endl;
                            }
                        }
                        return;
                    }
            }
            break;
Feb 5, 2013 at 8:10am
This is the errors I am getting

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
In file included from /usr/include/c++/4.6/algorithm:63:0,
                 from WHMgmt.cpp:2:
WHMgmt.cpp:339:89:   instantiated from here
/usr/include/c++/4.6/bits/stl_algo.h:5445:4: error: no match foroperator-’ in ‘__last - __first’
/usr/include/c++/4.6/bits/stl_algo.h:5445:4: note: candidates are:
/usr/include/c++/4.6/bits/stl_iterator.h:321:5: note: template<class _Iterator> typename std::reverse_iterator::difference_type std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)
/usr/include/c++/4.6/bits/stl_iterator.h:378:5: note: template<class _IteratorL, class _IteratorR> typename std::reverse_iterator<_IteratorL>::difference_type std::operator-(const std::reverse_iterator<_IteratorL>&, const std::reverse_iterator<_IteratorR>&)
/usr/include/c++/4.6/bits/stl_bvector.h:181:3: note: std::ptrdiff_t std::operator-(const std::_Bit_iterator_base&, const std::_Bit_iterator_base&)
/usr/include/c++/4.6/bits/stl_bvector.h:181:3: note:   no known conversion for argument 1 from ‘std::_List_iterator<WHMgmtDetails>’ to ‘const std::_Bit_iterator_base&’
/usr/include/c++/4.6/bits/stl_algo.h: In function ‘void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::_List_iterator<WHMgmtDetails>, _Compare = TransactionComparator]’:
/usr/include/c++/4.6/bits/stl_algo.h:5447:4:   instantiated from ‘void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = std::_List_iterator<WHMgmtDetails>, _Compare = TransactionComparator]’
WHMgmt.cpp:339:89:   instantiated from here
/usr/include/c++/4.6/bits/stl_algo.h:2194:7: error: no match foroperator-’ in ‘__last - __first’
/usr/include/c++/4.6/bits/stl_algo.h:2194:7: note: candidates are:
/usr/include/c++/4.6/bits/stl_iterator.h:321:5: note: template<class _Iterator> typename std::reverse_iterator::difference_type std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)
/usr/include/c++/4.6/bits/stl_iterator.h:378:5: note: template<class _IteratorL, class _IteratorR> typename std::reverse_iterator<_IteratorL>::difference_type std::operator-(const std::reverse_iterator<_IteratorL>&, const std::reverse_iterator<_IteratorR>&)
/usr/include/c++/4.6/bits/stl_bvector.h:181:3: note: std::ptrdiff_t std::operator-(const std::_Bit_iterator_base&, const std::_Bit_iterator_base&)
/usr/include/c++/4.6/bits/stl_bvector.h:181:3: note:   no known conversion for argument 1 from ‘std::_List_iterator<WHMgmtDetails>’ to ‘const std::_Bit_iterator_base&’
/usr/include/c++/4.6/bits/stl_algo.h:2196:4: error: no match foroperator+’ in ‘__first + 16’
/usr/include/c++/4.6/bits/stl_algo.h:2196:4: note: candidates are:
/usr/include/c++/4.6/bits/stl_iterator.h:327:5: note: template<class _Iterator> std::reverse_iterator<_Iterator> std::operator+(typename std::reverse_iterator<_Iterator>::difference_type, const std::reverse_iterator<_Iterator>&)
/usr/include/c++/4.6/bits/stl_bvector.h:266:3: note: std::_Bit_iterator std::operator+(std::ptrdiff_t, const std::_Bit_iterator&)
/usr/include/c++/4.6/bits/stl_bvector.h:266:3: note:   no known conversion for argument 1 from ‘std::_List_iterator<WHMgmtDetails>’ to ‘std::ptrdiff_t {aka long int}’
/usr/include/c++/4.6/bits/stl_bvector.h:352:3: note: std::_Bit_const_iterator std::operator+(std::ptrdiff_t, const std::_Bit_const_iterator&)
/usr/include/c++/4.6/bits/stl_bvector.h:352:3: note:   no known conversion for argument 1 from ‘std::_List_iterator<WHMgmtDetails>’ to ‘std::ptrdiff_t {aka long int}’
/usr/include/c++/4.6/bits/basic_string.h:2306:5: note: template<class _CharT, class _Traits, class _Alloc> std::basic_string<_CharT, _Traits, _Alloc> std::operator+(const std::basic_string<_CharT, _Traits, _Alloc>&, const std::basic_string<_CharT, _Traits, _Alloc>&)
/usr/include/c++/4.6/bits/basic_string.tcc:694:5: note: template<class _CharT, class _Traits, class _Alloc> std::basic_string<_CharT, _Traits, _Alloc> std::operator+(const _CharT*, const std::basic_string<_CharT, _Traits, _Alloc>&)
/usr/include/c++/4.6/bits/basic_string.tcc:710:5: note: template<class _CharT, class _Traits, class _Alloc> std::basic_string<_CharT, _Traits, _Alloc> std::operator+(_CharT, const std::basic_string<_CharT, _Traits, _Alloc>&)
/usr/include/c++/4.6/bits/basic_string.h:2343:5: note: template<class _CharT, class _Traits, class _Alloc> std::basic_string<_CharT, _Traits, _Alloc> std::operator+(const std::basic_string<_CharT, _Traits, _Alloc>&, const _CharT*)
/usr/include/c++/4.6/bits/basic_string.h:2359:5: note: template<class _CharT, class _Traits, class _Alloc> std::basic_string<_CharT, _Traits, _Alloc> std::operator+(const std::basic_string<_CharT, _Traits, _Alloc>&, _CharT)
/usr/include/c++/4.6/bits/stl_algo.h:2197:4: error: no match foroperator+’ in ‘__first + 16’
/usr/include/c++/4.6/bits/stl_algo.h:2197:4: note: candidates are:
/usr/include/c++/4.6/bits/stl_iterator.h:327:5: note: template<class _Iterator> std::reverse_iterator<_Iterator> std::operator+(typename std::reverse_iterator<_Iterator>::difference_type, const std::reverse_iterator<_Iterator>&)
/usr/include/c++/4.6/bits/stl_bvector.h:266:3: note: std::_Bit_iterator std::operator+(std::ptrdiff_t, const std::_Bit_iterator&)
/usr/include/c++/4.6/bits/stl_bvector.h:266:3: note:   no known conversion for argument 1 from ‘std::_List_iterator<WHMgmtDetails>’ to ‘std::ptrdiff_t {aka long int}’
/usr/include/c++/4.6/bits/stl_bvector.h:352:3: note: std::_Bit_const_iterator std::operator+(std::ptrdiff_t, const std::_Bit_const_iterator&)
/usr/include/c++/4.6/bits/stl_bvector.h:352:3: note:   no known conversion for argument 1 from ‘std::_List_iterator<WHMgmtDetails>’ to ‘std::ptrdiff_t {aka long int}’
/usr/include/c++/4.6/bits/basic_string.h:2306:5: note: template<class _CharT, class _Traits, class _Alloc> std::basic_string<_CharT, _Traits, _Alloc> std::operator+(const std::basic_string<_CharT, _Traits, _Alloc>&, const std::basic_string<_CharT, _Traits, _Alloc>&)
/usr/include/c++/4.6/bits/basic_string.tcc:694:5: note: template<class _CharT, class _Traits, class _Alloc> std::basic_string<_CharT, _Traits, _Alloc> std::operator+(const _CharT*, const std::basic_string<_CharT, _Traits, _Alloc>&)
/usr/include/c++/4.6/bits/basic_string.tcc:710:5: note: template<class _CharT, class _Traits, class _Alloc> std::basic_string<_CharT, _Traits, _Alloc> std::operator+(_CharT, const std::basic_string<_CharT, _Traits, _Alloc>&)
/usr/include/c++/4.6/bits/basic_string.h:2343:5: note: template<class _CharT, class _Traits, class _Alloc> std::basic_string<_CharT, _Traits, _Alloc> std::operator+(const std::basic_string<_CharT, _Traits, _Alloc>&, const _CharT*)
/usr/include/c++/4.6/bits/basic_string.h:2359:5: note: template<class _CharT, class _Traits, class _Alloc> std::basic_string<_CharT, _Traits, _Alloc> std::operator+(const std::basic_string<_CharT, _Traits, _Alloc>&, _CharT)
/usr/include/c++/4.6/bits/stl_algo.h: In function ‘void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::_List_iterator<WHMgmtDetails>, _Compare = TransactionComparator]’:
/usr/include/c++/4.6/bits/stl_algo.h:2201:2:   instantiated from ‘void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::_List_iterator<WHMgmtDetails>, _Compare = TransactionComparator]’
/usr/include/c++/4.6/bits/stl_algo.h:5447:4:   instantiated from ‘void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = std::_List_iterator<WHMgmtDetails>, _Compare = TransactionComparator]’


I am sorry for the spam, there were more error messages but I don't wanna spam too much
Feb 5, 2013 at 2:04pm
Oh right, you can't do std::sort with a std::list. You need a random access iterator for std::sort.

Use the list's sort method, and see how your errors change:
1
2
std::list myList;
myList.sort(); 
Feb 5, 2013 at 2:39pm
Yeah, sorry, that was my bad. I forgot you couldn't do that. (I don't use std::list often)
Feb 5, 2013 at 4:02pm
@LowestOne

do i do transaction.sort(); ?

I just did transaction.sort(); and i got the following error

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
In file included from /usr/include/c++/4.6/list:65:0,
                 from WHMgmt.h:13,
                 from WHMgmt.cpp:3:
/usr/include/c++/4.6/bits/list.tcc:374:3:   instantiated from ‘void std::list<_Tp, _Alloc>::sort() [with _Tp = WHMgmtDetails, _Alloc = std::allocator<WHMgmtDetails>]’
WHMgmt.cpp:331:38:   instantiated from here
/usr/include/c++/4.6/bits/list.tcc:305:6: error: no match foroperator<’ in ‘__first2.std::_List_iterator<_Tp>::operator* [with _Tp = WHMgmtDetails, std::_List_iterator<_Tp>::reference = WHMgmtDetails&]() < __first1.std::_List_iterator<_Tp>::operator* [with _Tp = WHMgmtDetails, std::_List_iterator<_Tp>::reference = WHMgmtDetails&]()’
/usr/include/c++/4.6/bits/list.tcc:305:6: note: candidates are:
/usr/include/c++/4.6/bits/stl_pair.h:207:5: note: template<class _T1, class _T2> bool std::operator<(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)
/usr/include/c++/4.6/bits/stl_iterator.h:291:5: note: template<class _Iterator> bool std::operator<(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)
/usr/include/c++/4.6/bits/stl_iterator.h:341:5: note: template<class _IteratorL, class _IteratorR> bool std::operator<(const std::reverse_iterator<_IteratorL>&, const std::reverse_iterator<_IteratorR>&)
/usr/include/c++/4.6/bits/stl_vector.h:1290:5: note: template<class _Tp, class _Alloc> bool std::operator<(const std::vector<_Tp, _Alloc>&, const std::vector<_Tp, _Alloc>&)
/usr/include/c++/4.6/bits/basic_string.h:2510:5: note: template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const std::basic_string<_CharT, _Traits, _Alloc>&, const std::basic_string<_CharT, _Traits, _Alloc>&)
/usr/include/c++/4.6/bits/basic_string.h:2522:5: note: template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const std::basic_string<_CharT, _Traits, _Alloc>&, const _CharT*)
/usr/include/c++/4.6/bits/basic_string.h:2534:5: note: template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const _CharT*, const std::basic_string<_CharT, _Traits, _Alloc>&)
/usr/include/c++/4.6/bits/stl_list.h:1593:5: note: template<class _Tp, class _Alloc> bool std::operator<(const std::list<_Tp, _Alloc>&, const std::list<_Tp, _Alloc>&)


do i have to make a operator<?

1
2
3
4
bool operator<(const WHMgmtDetails& a, const WHMgmtDetails& b)
{
    return a.unitPrice < b.unitPrice;
}
Last edited on Feb 5, 2013 at 4:08pm
Feb 5, 2013 at 4:12pm
ok i got it right, i made the

1
2
3
4
bool operator<(const WHMgmtDetails& a, const WHMgmtDetails& b)
{
 return a.unitPrice < b.unitPrice;
}


and then

transaction.sort();


everything worked out fine. thanks for all your help LB and LowestOne!
Feb 5, 2013 at 4:59pm
But what if you need to sort by a different thing? You can only have one operator<
Feb 5, 2013 at 5:22pm
I did another.

1
2
3
4
bool operator>(const WHMgmtDetails& a, const WHMgmtDetails& b)
{
 return b.qty < a.qty;
}


For operator>

and luckily i have only 2 things to sort. I know this is bad practice but... it solves my current issue so i am happy enough.

Do you have any other idea how to make this better?
Pages: 12