Mengurutkan vektor dalam urutan menurun

310

Haruskah saya gunakan

std::sort(numbers.begin(), numbers.end(), std::greater<int>());

atau

std::sort(numbers.rbegin(), numbers.rend());   // note: reverse iterators

untuk mengurutkan vektor dalam urutan menurun? Apakah ada manfaat atau kelemahan dengan satu pendekatan atau yang lain?

fredoverflow
sumber
2
+1 Saya pikir jawabannya jelas, tetapi pertanyaan ini memiliki sedikit hal yang menarik. :)
wilhelmtell
3
Saya akan memilih opsi pertama, hanya karena saya tidak akan pernah harus berurusan dengan reverse_iteratoritu.
evandrix
2
@wilhelmtell Pertanyaan noob tapi mengapa yang kedua harus diurutkan secara menurun? Kami memberikan array yang sama dengan input ke metode sortir. Hanya saja kita memberikannya dalam urutan terbalik jadi mengapa harus diurutkan dalam urutan turun dan tidak naik seperti halnya dengan ar.begin () dan ar.end.
shshnk
6
@shshnk std::sort(b, e);menempatkan minimum di b(dalam kasus kami rbegin, jadi elemen terakhir ) dan maksimum di e(dalam kasus kami rend, jadi elemen pertama ).
fredoverflow

Jawaban:

114

Sebenarnya, yang pertama adalah ide yang buruk. Gunakan yang kedua , atau ini:

struct greater
{
    template<class T>
    bool operator()(T const &a, T const &b) const { return a > b; }
};

std::sort(numbers.begin(), numbers.end(), greater());

Dengan cara itu kode Anda tidak akan diam-diam rusak ketika seseorang memutuskan numbersharus menahan longatau long longbukannya int.

pengguna541686
sumber
1
@FredOverflow: Anda melakukan penghormatan dalam komentar Anda;)
user541686
2
Atau tetap dengan yang pertama. Gunakan typedef untuk numberContainer - ide bagus agar seseorang BISA bertukar menjadi panjang - dan menulis: std :: sort (numbers.begin (), numbers.end (), std :: lebih besar <numContainer :: value_type> ( ));
RichardHowells
1
+1 Yang pertama benar-benar membingungkan. Apa greaterselain itu? rbegindan renddibuat untuk tujuan tertentu.
Abhishek Divekar
6
Kenapa tidak sekadar std::greater<typename decltype(numbers)::value_type>()atau apa?
einpoklum
1
Jawaban ini sudah usang - Anda dapat menggunakan std::greater<>()sejak C ++ 14.
Nikolai
70

Gunakan yang pertama:

std::sort(numbers.begin(), numbers.end(), std::greater<int>());

Ini eksplisit apa yang terjadi - lebih sedikit kesempatan untuk salah membaca rbeginsebagai begin, bahkan dengan komentar. Ini jelas dan mudah dibaca yang persis apa yang Anda inginkan.

Juga, yang kedua mungkin kurang efisien daripada yang pertama mengingat sifat iterator terbalik, meskipun Anda harus membuat profil untuk memastikannya.

Pubby
sumber
68

Dengan c ++ 14 Anda dapat melakukan ini:

std::sort(numbers.begin(), numbers.end(), std::greater<>());
mrexciting
sumber
30

Bagaimana dengan ini?

std::sort(numbers.begin(), numbers.end());
std::reverse(numbers.begin(), numbers.end());
shoumikhin
sumber
13
Alasannya mungkin untuk menghindari kompleksitas tambahan: O (n * log (n)) + O (n) vs O (n * log (n))
greg
32
@reg O (n * log (n)) = O (n * log (n) + n). Mereka adalah dua cara untuk mendefinisikan set yang sama. Anda bermaksud mengatakan, "Ini mungkin lebih lambat."
pjvandehaar
4
@pjvandehaar Greg baik-baik saja. Dia secara eksplisit tidak mengatakan, O (n * log (n) + n), katanya O (n * log (n)) + O (n). Anda benar bahwa kata-katanya tidak jelas (terutama penyalahgunaan kata kompleksitas), tetapi Anda bisa menjawab dengan cara yang lebih baik. Misalnya: Mungkin Anda bermaksud menggunakan kata 'perhitungan' alih-alih kata 'kompleksitas'. Membalik angka adalah langkah O (n) yang tidak perlu ke langkah O (n * log (n)) yang identik.
Ofek Gila
3
@OfekGila Pemahaman saya adalah bahwa notasi O besar adalah tentang set fungsi, dan notasi yang melibatkan =dan +hanya kenyamanan makna dan . Dalam hal ini, O(n*log(n)) + O(n)adalah notasi yang nyaman O(n*log(n)) ∪ O(n)yang sama dengan O(n*log(n)). Kata "perhitungan" adalah saran yang bagus dan Anda benar tentang nadanya.
pjvandehaar
22

Alih-alih functor seperti yang diusulkan Mehrdad, Anda bisa menggunakan fungsi Lambda.

sort(numbers.begin(), numbers.end(), [](const int a, const int b) {return a > b; });
Julian Declercq
sumber
16

Menurut mesin saya, mengurutkan long longvektor [1..3000000] menggunakan metode pertama membutuhkan waktu sekitar 4 detik, sedangkan menggunakan yang kedua membutuhkan waktu sekitar dua kali lipat. Itu mengatakan sesuatu, tentu saja, tetapi saya juga tidak mengerti mengapa. Hanya berpikir ini akan sangat membantu.

Hal yang sama dilaporkan di sini .

Seperti yang dikatakan oleh Xeo, dengan -O3mereka menggunakan waktu yang hampir bersamaan untuk menyelesaikannya.

zw324
sumber
12
Apakah Anda mungkin tidak kompilasi dengan optimasi yang dihidupkan? Kedengarannya sangat mirip reverse_iteratoroperasi tidak inline, dan mengingat bahwa mereka hanya pembungkus di sekitar iterator yang sebenarnya, tidak heran mereka mengambil dua kali lipat waktu tanpa inline.
Xeo
@Xeo Bahkan jika mereka diikutsertakan beberapa implementasi menggunakan tambahan per referensi.
Pubby
@ildjarn: Karena seperti itu? Fungsi base()anggota misalnya mengembalikan iterator yang dibungkus.
Xeo
1
@Xeo Sekarang keduanya selesai dalam sedetik. Terima kasih!
zw324
3
@ Xeo: Saya ambil kembali; standar sebenarnya mandat yang std::vector<>::reverse_iteratorditerapkan dalam hal std::reverse_iterator<>. Aneh; hari ini saya belajar. :-P
ildjarn
11

Pendekatan pertama mengacu:

    std::sort(numbers.begin(), numbers.end(), std::greater<>());

Anda dapat menggunakan pendekatan pertama karena mendapatkan lebih banyak efisiensi daripada yang kedua.
Kompleksitas waktu pendekatan pertama kurang dari yang kedua.

ruam
sumber
Ini adalah jawaban yang sama dengan jawaban mrexciting. Pernyataan tentang kompleksitas juga tidak jelas bagi saya.
Philipp Claßen
7
bool comp(int i, int j) { return i > j; }
sort(numbers.begin(), numbers.end(), comp);

sumber
4
untuk menjadi jawaban yang valid, Anda harus mempertimbangkan untuk menulis sesuatu tentang kelebihan / kekurangan metode Anda vs. OP yang disebutkan
Stefan Hegny
3

TL; DR

Gunakan apa saja. Mereka hampir sama.

Jawaban yang membosankan

Seperti biasa, ada pro dan kontra.

Gunakan std::reverse_iterator:

  • Saat Anda menyortir jenis khusus dan Anda tidak ingin menerapkan operator>()
  • Saat Anda terlalu malas mengetik std::greater<int>()

Gunakan std::greatersaat:

  • Ketika Anda ingin memiliki kode yang lebih eksplisit
  • Saat Anda ingin menghindari penggunaan iterator terbalik yang tidak jelas

Adapun kinerja, kedua metode sama-sama efisien. Saya mencoba patokan berikut:

#include <algorithm>
#include <chrono>
#include <iostream>
#include <fstream>
#include <vector>

using namespace std::chrono;

/* 64 Megabytes. */
#define VECTOR_SIZE (((1 << 20) * 64) / sizeof(int))
/* Number of elements to sort. */
#define SORT_SIZE 100000

int main(int argc, char **argv) {
    std::vector<int> vec;
    vec.resize(VECTOR_SIZE);

    /* We generate more data here, so the first SORT_SIZE elements are evicted
       from the cache. */
    std::ifstream urandom("/dev/urandom", std::ios::in | std::ifstream::binary);
    urandom.read((char*)vec.data(), vec.size() * sizeof(int));
    urandom.close();

    auto start = steady_clock::now();
#if USE_REVERSE_ITER
    auto it_rbegin = vec.rend() - SORT_SIZE;
    std::sort(it_rbegin, vec.rend());
#else
    auto it_end = vec.begin() + SORT_SIZE;
    std::sort(vec.begin(), it_end, std::greater<int>());
#endif
    auto stop = steady_clock::now();

    std::cout << "Sorting time: "
          << duration_cast<microseconds>(stop - start).count()
          << "us" << std::endl;
    return 0;
}

Dengan baris perintah ini:

g++ -g -DUSE_REVERSE_ITER=0 -std=c++11 -O3 main.cpp \
    && valgrind --cachegrind-out-file=cachegrind.out --tool=cachegrind ./a.out \
    && cg_annotate cachegrind.out
g++ -g -DUSE_REVERSE_ITER=1 -std=c++11 -O3 main.cpp \
    && valgrind --cachegrind-out-file=cachegrind.out --tool=cachegrind ./a.out \
    && cg_annotate cachegrind.out

std::greater demo std::reverse_iterator demo

Pengaturan waktunya sama. Valgrind melaporkan jumlah cache yang sama.

ivaigult
sumber
2

Saya tidak berpikir Anda harus menggunakan salah satu metode dalam pertanyaan karena keduanya membingungkan, dan yang kedua rapuh seperti yang disarankan Mehrdad.

Saya akan menganjurkan berikut ini, karena terlihat seperti fungsi perpustakaan standar dan memperjelas niatnya:

#include <iterator>

template <class RandomIt>
void reverse_sort(RandomIt first, RandomIt last)
{
    std::sort(first, last, 
        std::greater<typename std::iterator_traits<RandomIt>::value_type>());
}
Martin Broadhurst
sumber
2
Ini seperti seribu kali lebih membingungkan daripada hanya menggunakan std::greaterkomparator ....
Apollys mendukung Monica
@ Apolly Saya setuju bahwa dimulai dengan C ++ 14, std :: lebih besar <> sepertinya solusi yang disukai. Jika Anda tidak memiliki C ++ 14, masih bisa berguna jika Anda ingin mengesampingkan kejutan dengan std :: lebih besar <int> (misalnya, ketika jenis di beberapa titik berubah dari int ke panjang).
Philipp Claßen
2

Anda dapat menggunakan yang pertama atau mencoba kode di bawah ini yang sama-sama efisien

sort(&a[0], &a[n], greater<int>());
Krish Munot
sumber