Cara mencari median dari `std :: set` [duplikat]
Saya mencoba mencari median dari a std::set. Karena std::setsudah menyortir semuanya, saya tinggal memilih elemen tengah. Ide saya adalah maju ke setengah:, std::advance(e, rtspUrls.size() / 2);tapi saya tidak yakin bagaimana perilakunya. Bagaimana dengan angka seperti itu 1.5? Akankah itu berkembang menjadi sesuatu?
Saya menggunakan coba tangkap untuk mencoba tidak berkembang menjadi sesuatu yang tidak ditentukan. Apakah ini aman?
Berdasarkan http://www.cplusplus.com/reference/algorithm/min_element/?kw=min_element, std::advancemelempar jika iterator melempar. Saya tidak yakin apakah iterator untuk std :: set melempar ketika kita mencobanya ++(https://en.cppreference.com/w/cpp/named_req/BidirectionalIterator tidak mengatakan apapun).
std::set<RTSPUrl, decltype(compare_rtsp_url)*> rtspUrls(compare_rtsp_url);
std::set<RTSPUrl, decltype(compare_rtsp_url)*>::iterator e = rtspUrls.begin();
for (const RTSPUrl &rtspUrl : stream.rtsp_urls())
{
if (rtspUrl.has_resolution())
{
rtspUrls.push_back(rtspUrl);
}
}
try
{
std::advance(e, rtspUrls.size() / 2);
return *e;
}
catch (std::exception &e)
{
return std::nullopt;
}
Jawaban
Dengan std :: set Anda dibatasi untuk menggunakan iterator untuk beralih ke elemen tengah (dalam kasus jumlah entri ganjil dalam set Anda) atau iterasi ke middle-1 dan middle dan mengambil rata-rata (dalam kasus bilangan genap entri) untuk menentukan median.
Loop sederhana dan penghitung adalah hal yang sangat mudah. Contoh singkatnya adalah:
#include <iostream>
#include <set>
int main (void) {
#ifdef ODD
std::set<std::pair<char,int>> s {{'a',1}, {'b',2}, {'c',3}, {'d',4}, {'e',5}};
#else
std::set<std::pair<char,int>> s {{'a',1}, {'b',2}, {'c',3}, {'d',4}, {'e',5}, {'f',6}};
#endif
double median = 0.;
size_t n = 0;
for (auto iter = s.begin(); iter != s.end(); iter++, n++) {
if (n == s.size() / 2 - 1 && s.size() % 2 == 0) {
median += iter->second;
std::cout << iter->first << " " << iter->second << '\n';
}
if (n == s.size() / 2) {
median += iter->second;
if (s.size() % 2 == 0)
median /= 2.;
std::cout << iter->first << " " << iter->second
<< "\n\nmedian " << median << '\n';
break;
}
}
}
(tentu saja Anda harus menyesuaikan jenis untuk memenuhi data Anda)
Contoh Penggunaan / Output
Disusun dengan ODDdidefinisikan:
$ ./bin/set_median
c 3
median 3
Dikompilasi tanpa definisi tambahan untuk kasus EVEN:
$ ./bin/set_median
c 3
d 4
median 3.5
std :: next
Anda dapat menggunakan std :: berikutnya untuk maju ke n th iterator setelah saat ini. Anda harus menetapkan hasilnya:
median = 0.;
auto iter = s.begin();
if (s.size() % 2 == 0) {
iter = std::next(iter, s.size() / 2 - 1);
median += iter->second;
iter = std::next(iter);
median += iter->second;
median /= 2.;
}
else {
iter = std::next(iter, s.size() / 2);
median += iter->second;
}
std::cout << "\nmedian " << median << '\n';
std :: muka
std :: muka kemajuan iterator disediakan sebagai parameter untuk n th iterator setelah saat ini:
median = 0.;
iter = s.begin();
if (s.size() % 2 == 0) {
std::advance(iter, s.size() / 2 - 1);
median += iter->second;
std::advance(iter, 1);
median += iter->second;
median /= 2.;
}
else {
std::advance(iter, s.size() / 2);
median += iter->second;
}
std::cout << "\nmedian " << median << '\n';
(output untuk mediansama dengan loop di atas)
Periksa semuanya dan beri tahu saya jika Anda memiliki pertanyaan lebih lanjut.
Saya hanya harus memilih elemen tengah. Ide saya adalah maju ke setengah:,
std::advance(e, rtspUrls.size() / 2);tapi saya tidak yakin bagaimana perilakunya. Bagaimana dengan angka seperti 1,5? Akankah itu berkembang menjadi sesuatu?
std::setindeks menggunakan nilai integer unsigned ( size_t) sehingga double 1.5akan dikonversi menjadi size_t 1.
Saya tidak yakin apakah iterator untuk
std::setlemparan ketika kita mencoba++
Tidak, itu tidak akan terjadi, tetapi kemajuan melampaui end()tidak ditentukan.
Median sejati untuk satu set dengan jumlah elemen genap akan mengambil rata-rata dari dua elemen tengah - tetapi itu mengharuskan jenis yang Anda simpan di std::setpenyangga +dan /. Contoh:
std::set<double> foo{1., 2., 3., 10.};
if(foo.empty()) throw std::runtime_error("no elements in set");
double median;
if(foo.size() % 2 == 0) { // even number of elements
auto lo = std::next(foo.begin(), foo.size() / 2 - 1);
auto hi = std::next(lo);
median = (*lo + *hi) / 2.;
} else { // odd number of elements
median = *std::next(foo.begin(), foo.size() / 2);
}
std::cout << median << '\n'; // prints 2.5
Dalam kasus Anda, jenis dalam himpunan tampaknya tidak mendukung +dan /untuk membuat rata-rata dua RTSPUrljika Anda memiliki jumlah elemen genap, jadi sebaiknya Anda memilih salah satu dari dua elemen tengah jika Anda memiliki jumlah yang genap. Baik dengan mengembalikan iterator (sehingga pengguna dapat memeriksa apakah itu rtspUrls.end()):
return std::next(rtspUrls.begin(), rtspUrls.size() / 2);
Atau dengan mengembalikan referensi ke, atau salinan, elemen:
if(rtspUrls.empty()) throw std::runtime_error("no elements in set");
return *std::next(rtspUrls.begin(), rtspUrls.size() / 2);
Saya hanya harus memilih elemen tengah
Hanya jika himpunan berisi elemen dalam jumlah ganjil. Sebaliknya, jika ukurannya genap, median didefinisikan sebagai mean dari dua nilai tengah, terkadang disebut median atas dan bawah.
Bagaimana dengan angka seperti 1,5?
Anda tidak akan pernah mendapatkannya karena rtspUrls.size() / 2merupakan pembagian integer yang memotong tempat desimal manapun.
Saya pikir, meneruskan floatatau doublesebagai parameter kedua, seperti std::advance(e, 1.5)tidak boleh dikompilasi. Sejauh yang saya lihat, referensi tidak menentukan jenis parameter kedua. Namun, bagian "implementasi yang mungkin" selalu menggunakan jenis perbedaan khusus untuk parameter pertama, yang biasanya merupakan tipe integral dan tampaknya masuk akal.
Saya menggunakan coba tangkap untuk mencoba tidak berkembang menjadi sesuatu yang tidak ditentukan. Apakah ini aman?
Tidak, mendereferensikan atau menambahkan iterator yang tidak valid adalah perilaku yang tidak ditentukan dan tidak diharuskan untuk memberikan pengecualian apa pun. Meskipun banyak implementasi menyediakan pemeriksaan kesalahan ekstensif dalam pembuatan debug dan sangat baik untuk membuat pengecualian UB terjadi. Tetapi memajukan hingga setengah ukuran set tidak akan menjadi masalah.