Уроки Коммент.

Создание игр » Featured, STL » Std::sort

Std::sort

std::sortStd::sort это алгоритм сортировки, один из представителей семейства алгоритмов stl. Как понятно из его названия, std::sort занимается сортировкой данных. Кстати, std::sort часто (или почти всегда?) опережает по скорости стандартную функцию sort(). Вообще, в STL очень много полезных алгоритмов и sort – один из наиболее часто используемых. Давайте рассмотрим на примере std::sort() использование алгоритмов STL и разберём, где именно и как именно надо использовать алгоритмы, а так же как мы можем модифицировать их поведение с помощью функторов.

Алгоритм std::sort

Как и большинство алгоритмов STL, sort определён в двух формах:

template <class RandomAccessIterator>
	void sort ( RandomAccessIterator first, RandomAccessIterator last );
 
template <class RandomAccessIterator, class Compare>
	void sort ( RandomAccessIterator first, RandomAccessIterator last,
		Compare comp );

Первая форма алгоритма использует дефолтный функтор сравнения, а вторая позволяет задать его самостоятельно. Выполним простую сортировку массива:

// sort algorithm example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main ()
{
	int myints[] = {32,71,12,45,26,80,53,33};
	vector<int> myvector (myints, myints+8);
	// теперь в контейнере: 32 71 12 45 26 80 53 33
	vector<int>::iterator it;
 
	// используем сравнение по-умолчанию
	sort (myvector.begin(), myvector.begin()+4);
	// теперь в контейнере: (12 32 45 71)26 80 53 33
 
	// вот сюда будем добавлять остальные варианты сортировки
 
	// печатаем содежимое
	cout << "myvector contains:";
	for (it=myvector.begin(); it!=myvector.end(); ++it)
		cout << " " << *it;
 
	cout << endl;
 
	return 0;
}}

std::sort через функцию

Сортировка с использованием нашей собственной функции сравнения элементов в контейнере:

// это функция сравнения для использования внутри std::sort
bool sort_function (int i,int j)
{
	return (i<j);
}
	// добавляем в конец main()
	// иcпользуем нашу функцию сравнения
	sort (myvector.begin()+4, myvector.end(), sort_function);
	// теперь в контейнере: 12 32 45 71(26 33 53 80)

std::sort + функтор

А вот использование функтора:

// это наш функтор сортировки
struct sort_class
{
	bool operator() (int i, int j)
	{ return (i<j);}
} sort_object;
 
	// это добавляем в конец main()
	// используем функутор сортировки
	sort (myvector.begin(), myvector.end(), sort_object);
	// теперь в контейнере: (12 26 32 33 45 53 71 80)

std::sort и сортировка объектов

Как же с помощью алгоритма sort можно отсортировать контейнер с объектами? Да, собственно, практически так же – меняется мало что. Давайте предположим, что у нас есть класс и контейнер с объектами этого класса:

class MyObject
{
	float m_fPosX;
	float m_fPosY;
	float m_fMass;
}
std::vector<MyObject> vecObjects;

Вот так мы можем отсортировать объекты в этом массиве по их расположению вдоль оси Х:

struct sort_class_x
{
	bool operator() (MyObject i, MyObject j)
	{ return (i.m_fPosX<j.m_fPosX);}
} sort_objectX;
 
sort (myvector.begin(), myvector.end(), sort_objectX);

Сортировка того же самого набора объектов, но уже по массе:

struct sort_class_mass
{
	bool operator() (MyObject i, MyObject j)
	{ return (i.m_fMass<j.m_fMass);}
} sort_objectMass;
 
sort (myvector.begin(), myvector.end(), sort_objectMass);

И, конечно же, ничего не мешает Вам написать более сложные функции сортировки. Например, сделать функтор, который будет сортировать объекты по массе, а объекты с равной массой будут сортироваться по Х-координате:

struct sort_class_mass_pos
{
	bool operator() (MyObject i, MyObject j)
	{
		if (i.m_fMass==j.m_fMass)
			return (i.m_fPosX<j.m_fPosX);
		return (i.m_fMass<j.m_fMass);
	}
} sort_objectMassPos;
 
sort (myvector.begin(), myvector.end(), sort_objectMassPos);

Как-то так. Если есть вопросы – задавайте.

Ещё по этой теме:




Раздел: Featured, STL · Теги: STL

6 комментариев на "Std::sort"
  1. ShineKami пишет:

    Во. Классная штука. Спасибо за урок. :)

  2. Viktor пишет:

    в структуре
    struct sort_class_mass_pos

    вас не смущает вот эта строка?
    if (i.m_fMass==j.m_fMass)

  3. anon пишет:

    Кстати, std::sort часто (или почти всегда?) опережает по скорости стандартную функцию sort()

    whaaat?

  4. M пишет:

    А зачем вообще нужен функтор, с затратами на конструктор/деструктор/хранение, если можно задать функцию?

    1. Вячеслав пишет:

      Функтор совсем не обязательно должен иметь тяжеловсные конструктор и деструктор (а если они будут пустые – то и затраты будут вообще нулевые). А главное его приемущество состоит в том, что он зачастую может работать быстрее. Что происходит, например, когда мы вызывает qsort? Плюсы для каждых двух сравниваемых заничений помещают их в стек и вызывают указанную нами функцию сортировки (что достаточно медленно). Когда же мы используем функтор – часто (не всегда, но как правило) компилятор понимает чего мы от него хотим (а хотим мы максимально зианлайнить всё) и оптимизирует соответсвующим образом. Как итог – обычно получаем заметный буст (прирост скорости т.е.).

      При этом обычно стоит так же (в статье это не указано, но это так) делать функцию сравнения константной, а сами сравниваемые переменные, если это не POD-типы, а какие-то отсносительно сложные данные, передавать как константные ссылки – это поможет компилятору лучше сообразить что от него требуется.

      Вы можете сами сравнить производительность – например, напишите сортировку относительного большого массива (несколько миллионов интов, например) обычным qsort и второй вариант через std::sort и засеките время работы в том и другом случае – разница будет весьма существенной.

Оставить комментарий

*

Вы можете использовать это HTMLтеги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>