Sorting a vector of objects

Question

I have a vector filled with some vertex object instances and need to sort it, according to its 'x' and after it its 'y' coordinate.

vertex.h

#ifndef VERTEX_H
#define VERTEX_H 1

class Vertex
{
private:
  double __x;
  double __y;
public:
  Vertex(const double x, const double y);
  bool operator<(const Vertex &b) const;
  double x(void);
  double y(void);
};

#endif // VERTEX_H

vertex.cpp

#include "vertex.h"

Vertex::Vertex(const double x, const double y) : __x(x), __y(y)
{
}

bool Vertex::operator<(const Vertex &b) const
{
  return __x < b.x() || (__x == b.x() && __y < b.y());
}

double Vertex::x(void)
{
  return __x;
}

double Vertex::y(void)
{
  return __y;
}

run.cpp

#include <algorithm>
#include <stdio.h>
#include <vector>

#include "vertex.h"

void prnt(std::vector<Vertex *> list)
{
  for(size_t i = 0; i < list.size(); i++)
    printf("Vertex (x: %.2lf y: %.2lf)\n", list[i]->x(), list[i]->y());
}

int main(int argc, char **argv)
{
  std::vector<Vertex *> list;
  list.push_back(new Vertex(0, 0));
  list.push_back(new Vertex(-3, 0.3));
  list.push_back(new Vertex(-3, -0.1));
  list.push_back(new Vertex(3.3, 0));

  printf("Original:\n");
  prnt(list);

  printf("Sorted:\n");
  std::sort(list.begin(), list.end());

  prnt(list);

  return 0;
}

What I expect as output is:

Original:
Vertex (x: 0.00 y: 0.00)
Vertex (x: -3.00 y: 0.30)
Vertex (x: -3.00 y: -0.10)
Vertex (x: 3.30 y: 0.00)
Sorted:
Vertex (x: -3.00 y: -0.10)
Vertex (x: -3.00 y: 0.30)
Vertex (x: 0.00 y: 0.00)
Vertex (x: 3.30 y: 0.00)

But what I actually get is:

Original:
Vertex (x: 0.00 y: 0.00)
Vertex (x: -3.00 y: 0.30)
Vertex (x: -3.00 y: -0.10)
Vertex (x: 3.30 y: 0.00)
Sorted:
Vertex (x: 0.00 y: 0.00)
Vertex (x: -3.00 y: -0.10)
Vertex (x: -3.00 y: 0.30)
Vertex (x: 3.30 y: 0.00)

I don't know what exactly is going wrong, any idea?

How does that compile? Your operate< takes a const &Vertex but there is no `double Vertex::x() const`? — Chris, Jun 22 '11 at 02:54
read this: http://stackoverflow.com/questions/228783/what-are-the-rules-about-using-an-underscore-in-a-c-identifier/228797#228797 — Martin York, Jun 22 '11 at 02:56

jterrace · Accepted Answer · 2011-06-22T03:09:36.163

6

You are storing Vertex * in the container not Vertex. When you call std::sort, you're actually sorting the value of the pointers, not the items themselves.

If you really need to be storing pointers (which I doubt), you can use a workaround like this (untested):

struct less_than_key {
    inline bool operator() (const Vertex*& v1, const Vertex*& v2) {
        return ((*v1) < (*v2));
    }
};
std::sort(list.begin(), list.end(), less_than_key());

edited Jun 22 '11 at 03:09

answered Jun 22 '11 at 02:56

jterrace

64,866
22
157
202

@Wanderson so how did you fix the problem? you changed std::vector to std::vector or sth else? – shengy Jun 22 '11 at 03:05
Added an edit to fix it without changing pointer to non-pointer. I didn't try compiling, so if I made any mistakes, let me know so I can edit. – jterrace Jun 22 '11 at 03:10

score 1 · Answer 2 · edited Jun 22 '11 at 16:23

1

You are sorting pointers, not the actual Vertex objects. Try this:

std::vector<Vertex> list;
list.push_back(Vertex(0, 0);
list.push_back(Vertex(-3, 0.3);
...

I.e. get rid of the pointer in the list container and the new's in the calls to push_back.

edited Jun 22 '11 at 16:23

DarthJDG

16,511
11
49
56

answered Jun 22 '11 at 03:05

Brian Lenoski

117
4

score 1 · Answer 3 · answered Jun 22 '11 at 03:06

1

If you want to save yourself writing all those classes yourself (and violating the double-underscore rule!), you could consider just using a

std::vector< std::pair<float, float> >

and using std::sort. Pairs are by default lexicographically compared (which is what you asked for), so you don't need any extra code.

answered Jun 22 '11 at 03:06

Kerrek SB

464,522
92
875
1,084

I know I can use std::pair, but it is a simplified version of Vertex class, the complete one has methods for angle, distance and other calculations I need. And about the double-underscore rule, I'll make sure to apply it in my future codes. – Wanderson Silva Jun 22 '11 at 03:26
@Wanderson: Fair enough. If you can't get away with free functions for those conversions and calculations, then you'll have to make your own class (though it could well have the pair-vector as its main data member and expose its comparison operator). – Kerrek SB Jun 22 '11 at 03:30

score 0 · Answer 4 · answered Jun 22 '11 at 03:01

Seems like you want to sort be abolute values for some reason:
Try this:

bool Vertex::operator<(const Vertex &b) const
{
  return std::abs(__x) < std::abs(b.__x) || (std::abs(__x) == std::abs(b.__x) && std::abs(__y) < std::abs::(b.__y));
}

Note: you do not need to call b.x() to get the member of another object when you are the same class. You can just access the other member.

Note: Don't use double underscore in your identifiers. Prefer not to prefix identifiers with underscore.

Actually I need the leftmost vertex in the beginning of the list. Then, it can't be the absolute value. — Wanderson Silva, Jun 22 '11 at 03:27

Sorting a vector of objects

4 Answers4

Linked

Related