If I change from std::vector to std::list my compiler becomes very displeased with me

[Eric Lilja]

Hello, consider this complete program (sorry, it's not minimal but I hope
it's readable at least):

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

class Row
{
public:
Row(int row)
:
m_row(row) {}

int get_row() const
{
return m_row;
}

private:
int m_row;
};

static void print_collection(const std::vector<Row>&);

bool less_wrt_row(const Row& lhs, const Row& rhs)
{
return lhs.get_row() < rhs.get_row();
}

int
main()
{
std::vector<Row> collection;

collection.push_back(Row(39));
collection.push_back(Row(3));
collection.push_back(Row(202));
collection.push_back(Row(1));

std::cout << "Before sorting:" << std::endl;

print_collection(collection);

std::sort(collection.begin(), collection.end(), less_wrt_row);

std::cout << "After sorting:" << std::endl;

print_collection(collection);

return 0;
}

static void
print_collection(const std::vector<Row>& collection)
{
std::vector<Row>::const_iterator itr = collection.begin();

while(itr != collection.end())
{
std::cout << itr->get_row() << std::endl;

++itr;
}
}

This program compiles and links and runs without noticable error. But if I
change the type of collection from std::vector to std::list, my compiles
becomes very displeased with me. The output is very long and quite
unreadable for a beginner like me. I assume std::list and std::vector are
not "compatible" with each other with regards to the sorting functions in
the standard library. But say I do have a std::list that I want sorted using
a binary predicate, how should I do it? Am I crazy wanting a std::list if I
want it to be sorted? What data structure should I use then?

Thanks for any replies

 

[Shan]

std::sort(collection.begin(), collection.end(), less_wrt_row);

Random access of list cannott be done, as we can do with vector. The
sort algorithm should access randomly inorder to sort which is not
possible with list.
One of the first error i got is

MurugesanSH@INP-Murgesansh /cygdrive/d/shanprog/ccprog
$ g++ -o list list.cc
/usr/include/c++/3.3.1/bits/stl_algo.h: In function `void
std::sort(_RandomAccessIter, _RandomAccessIter, _Compare) [with
_RandomAccessIter = std::_List_iterator<Row, Row&, Row*>, _Compare =
bool
(*)(const Row&, const Row&)]':
list.cc:44: instantiated from here
/usr/include/c++/3.3.1/bits/stl_algo.h:2209: error: no match for
'operator-' in

From which it can be seen that random access is not possible with list.

-Shan

 

[John Carson]

Hello, consider this complete program (sorry, it's not minimal but I
hope it's readable at least):

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

class Row
{
public:
Row(int row)
:
m_row(row) {}

int get_row() const
{
return m_row;
}

private:
int m_row;
};

static void print_collection(const std::vector<Row>&);

bool less_wrt_row(const Row& lhs, const Row& rhs)
{
return lhs.get_row() < rhs.get_row();
}

int
main()
{
std::vector<Row> collection;

collection.push_back(Row(39));
collection.push_back(Row(3));
collection.push_back(Row(202));
collection.push_back(Row(1));

std::cout << "Before sorting:" << std::endl;

print_collection(collection);

std::sort(collection.begin(), collection.end(), less_wrt_row);

std::cout << "After sorting:" << std::endl;

print_collection(collection);

return 0;
}

static void
print_collection(const std::vector<Row>& collection)
{
std::vector<Row>::const_iterator itr = collection.begin();

while(itr != collection.end())
{
std::cout << itr->get_row() << std::endl;

++itr;
}
}

This program compiles and links and runs without noticable error. But
if I change the type of collection from std::vector to std::list, my
compiles becomes very displeased with me. The output is very long and
quite unreadable for a beginner like me. I assume std::list and
std::vector are not "compatible" with each other with regards to the
sorting functions in the standard library. But say I do have a
std::list that I want sorted using a binary predicate, how should I
do it? Am I crazy wanting a std::list if I want it to be sorted? What
data structure should I use then?
Thanks for any replies

The std::sort function requires a random access iterator. Lists do not
permit random access. Accordingly, if you want to sort a list, you use the
sort member function for lists, i.e., you replace

std::sort(collection.begin(), collection.end(), less_wrt_row);

with

collection.sort(less_wrt_row);

 

[Shan]

std::sort(collection.begin(), collection.end(), less_wrt_row);

with
collection.sort(less_wrt_row);

But comparison operator < ("less than") must be defined for the list
element type.

-Shan

 

[Ivan Vecerina]

But comparison operator < ("less than") must be defined for the list
element type.

No.
As for std::sort, there are two overloads of std::list::sort :
one that uses the < operator, the other that takes a predicate
as a parameter (as in the above usage).

BTW: list's sort member function provides guaranteed O(lgN)
performance, and will not copy elements -- which makes it
more efficient than std::sort when collection items are
expensive to copy.


Happy 2005,
Ivan

 

[Ivan Vecerina]

BTW: list's sort member function provides guaranteed O(lgN)
performance,

Of course I meant O(NlgN).
[ for std::sort worst case could be e.g. O(N2) ]