Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Сортировка вектора

Автор: Berkut 13.4.2004, 15:07

Как отсортирвать вектор типа структура:
struct A
{
int x,y;
}

vector<A> abc;

abc.sort( ?????????
например по полю х.

Автор: mr.DUDA 13.4.2004, 15:32

Есть два варианта.
Первый: сортировка с помощью единственного оператора сравнения, встраиваемого в класс (тогда нельзя будет выбрать, по какому полю сортировать и т.п.):

Цитата

struct A
{
int x,y;
A(int ax, int ay): x(ax), y(ay) {}

bool operator<(A &ob) {return x<ob.x;}
};

void main()
{
vector<A> abc;
abc.push_back(A(1,300));
abc.push_back(A(2,200));
abc.push_back(A(3,100));

sort(abc.begin(), abc.end());
}

Второй вариант - более гибкий, с использованием 3-го аргумента функции "sort" (функциональный объект либо указатель на сравнивающую функцию):

Цитата

struct A
{
int x,y;
A(int ax, int ay): x(ax), y(ay) {}
};

bool cmp_A_by_x(A &first, A &second) {return first.x<second.x;}
bool cmp_A_by_y(A &first, A &second) {return first.y<second.y;}

void main()
{
vector<A> abc;
abc.push_back(A(1,300));
abc.push_back(A(2,200));
abc.push_back(A(3,100));

// отсортируем сначала по полю x, потом - по полю y
sort(abc.begin(), abc.end(), cmp_A_by_x);
sort(abc.begin(), abc.end(), cmp_A_by_y);
}

Автор: Berkut 13.4.2004, 16:19

Сделал вторым способом, но вот такая ошибка появляется:
error C2039: 'sort' : is not a member of 'vector<struct A,class std::allocator<struct A> >'

Автор: sergejzr 13.4.2004, 16:28

mr.DUDA
Неплохо! А алгоритм сортировки можно указать?

Автор: Berkut 13.4.2004, 16:46

Автор: achmed 13.4.2004, 16:55

очевидно вы пишите abc.sort() вместо sort(abc.begin(),end()), у vector нет встроеного вектора
сортировки, вместо этого исп-ся std::sort - для для итераторов произвольного доступа

Автор: Berkut 13.4.2004, 17:20

спасибо achmed mr.DUDA

Автор: mr.DUDA 13.4.2004, 18:21

Да, кстати совсем забыл напомнить - для удобства записи, в моём примере используются "сокращённые" имена STL:

Цитата

#include <vector>
#include <algorithm>

using namespace std;

// ...
// теперь вместо std::sort можно писать просто sort и т.д.

Добавлено @ 18:26
2 sergej.z,
Алгоритм сортировки сильно зависит от реализации STL. Это может быть как простейшая "пузырьковая" сортировка, так и более навёрнутый алгоритм.

Автор: Fantasist 14.4.2004, 00:29

Цитата

Это может быть как простейшая "пузырьковая" сортировка, так и более навёрнутый алгоритм.

Обычно это все-таки quick sort, как я думаю. C другой стороны, не сложно и свой sort написать.