сортиране, стд

Std::sort е алгоритъм за сортиране, един от членовете на семейството от алгоритми stl. Както подсказва името му, std::sort сортира данни. Между другото, std::sort често (или почти винаги?) е по-бърза от стандартната функция sort(). Като цяло има много полезни алгоритми в STL и сортирането е един от най-често използваните. Нека да разгледаме използването на STL алгоритми, като използваме std::sort() като пример и да видим къде и как точно трябва да се използват алгоритмите, както и как можем да променим поведението им с помощта на функтори.

std::алгоритъм за сортиране

Подобно на повечето STL алгоритми, сортирането се дефинира в две форми:

Първата форма на алгоритъма използва функтора за сравнение по подразбиране, докато втората ви позволява да го зададете сами. Нека направим просто сортиране на масиви:

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

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

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

И ето използването на функтора:

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

И така, как можете да сортирате контейнер от обекти, като използвате алгоритъма за сортиране? Да, всъщност почти същото - малки промени. Да приемем, че имаме клас и контейнер с обекти от този клас:

Ето как можем да сортираме обектите в този масив по местоположението им по оста x:

Сортиране на същия набор от обекти, но по маса:

И, разбира се, нищо не ви пречи да пишете по-сложни функции за сортиране. Например, направете функтор, който ще сортира обектите по маса, а обектите с еднаква маса ще бъдат сортирани по X-координатата:

Нещо като това. Ако имате въпроси - питайте.

в. Готино нещо. Благодаря ти за урока.

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

Тази реплика притеснява ли ви? ако (i.m_fMass==j.m_fMass)

Между другото, std::sort често (или почти винаги?) е по-бърза от стандартната функция sort().

И защо изобщо се нуждаете от функтор, с цената на конструктор / деструктор / хранилище, ако можете да зададете функция?

Не е задължително функторът да има тежък конструктор и деструктор (и ако те са празни, тогава разходите обикновено ще бъдат нула). И основното му предимство е, че често може да работи по-бързо. Какво се случва, например, когато извикаме qsort? Плюсовете за всеки две сравнени стойности ги поставят в стека и извикват функцията за сортиране, която посочихме (която е доста бавна). Когато използваме функтор, често (не винаги, но обикновено) компилаторът разбира какво искаме от него (и ние искаме да подредим всичко колкото е възможно повече) и оптимизира съответно. В резултат на това обикновено получаваме забележим тласък (т.е. увеличение на скоростта).

В същото време обикновено си струва същото (не е посочено в статията, но е) да направите функцията за сравнение постоянна, а самите сравнявани променливи, ако не са типове POD, а някои сравнително сложни данни, да се предават като постоянни препратки - това ще помогне на компилатора да разбере по-добре какво се изисква от него.

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

---