Jak znaleźć medianę „std :: set” [duplicate]
Próbuję znaleźć medianę a std::set. Skoro std::setjuż wszystko sortuje, to muszę tylko wybrać środkowy element. Moim pomysłem jest przejście do połowy: std::advance(e, rtspUrls.size() / 2);ale nie jestem pewien, jak to się zachowa. A co z liczbami 1.5? Czy do czegoś dojdzie?
Używam próby złapania, aby nie przejść do czegoś nieokreślonego. Czy to jest bezpieczne?
Według http://www.cplusplus.com/reference/algorithm/min_element/?kw=min_element, std::advancezgłasza, jeśli iterator rzuca. Nie jestem pewien, czy iterator dla std :: set rzuca się, gdy próbujemy ++(https://en.cppreference.com/w/cpp/named_req/BidirectionalIterator nic nie mówi).
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;
}
Odpowiedzi
Z std :: set jesteś ograniczony do używania iteratorów do iteracji do środkowego elementu (w przypadku nieparzystej liczby wpisów w twoim zestawie) lub iteracji do middle-1 i middle i biorąc średnią (w przypadku liczby parzystej wpisów) w celu określenia mediany.
Prosta pętla i licznik są tak proste, jak to tylko możliwe. Oto krótki przykład:
#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;
}
}
}
(oczywiście będziesz musiał dostosować typy do swoich danych)
Przykładowe użycie / wyjście
Skompilowane ze ODDzdefiniowanymi:
$ ./bin/set_median
c 3
mediana 3
Opracowano bez dodatkowej definicji dla przypadku EVEN:
$ ./bin/set_median
c 3
d 4
median 3.5
std :: next
Możesz użyć std :: next, aby przejść do n- tego iteratora po bieżącym. Musisz przypisać wynik:
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 :: zaliczka
std :: zaawansowane przesuwa iterator dostarczony jako parametr do n- tego iteratora po bieżącym:
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';
(wyjście medianjest takie samo jak w przypadku pętli powyżej)
Przejrzyj wszystko i daj mi znać, jeśli masz dalsze pytania.
Muszę tylko wybrać środkowy element. Moim pomysłem jest przejście do połowy:
std::advance(e, rtspUrls.size() / 2);ale nie jestem pewien, jak to się zachowa. A co z liczbami takimi jak 1.5? Czy do czegoś dojdzie?
std::setindeksy używają wartości całkowitych bez znaku ( size_t), więc double 1.5zostaną przekonwertowane na size_t 1.
Nie jestem pewien, czy iterator dla
std::setrzutów, kiedy próbujemy++
Nie, nie będzie, ale pójście dalej end()jest nieokreślone.
Prawdziwa mediana dla zestawu z parzystą liczbą elementów byłaby średnią z dwóch środkowych elementów - ale to wymaga, aby typ przechowywany w std::setobu wspornikach +i /. Przykład:
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
W twoim przypadku typ w zestawie nie wygląda na to, że obsługuje +i /tworzy średnio dwa RTSPUrls w przypadku, gdy masz parzystą liczbę elementów, więc prawdopodobnie powinieneś po prostu wybrać jeden z dwóch środkowych elementów na wypadek, gdybyś miał równa kwota. Albo zwracając iterator (aby użytkownik mógł następnie sprawdzić, czy jest rtspUrls.end()):
return std::next(rtspUrls.begin(), rtspUrls.size() / 2);
Lub zwracając odniesienie do elementu lub jego kopię:
if(rtspUrls.empty()) throw std::runtime_error("no elements in set");
return *std::next(rtspUrls.begin(), rtspUrls.size() / 2);
Muszę tylko wybrać środkowy element
Tylko gdy zestaw zawiera nieparzystą liczbę elementów. W przeciwnym razie, gdy wielkość jest równa, mediana jest definiowana jako średnia z dwóch średnich wartości, czasami nazywanych górną i dolną medianą.
A co z liczbami takimi jak 1.5?
Nigdy tego nie dostaniesz, ponieważ rtspUrls.size() / 2jest to dzielenie całkowite, które obcina wszystkie miejsca dziesiętne.
Myślę, że przekazanie floatlub doublejako drugiego parametru, na przykład std::advance(e, 1.5)nie powinno się kompilować. O ile widzę, odniesienie nie określa typu drugiego parametru. Jednak sekcja „możliwe implementacje” zawsze używa typu różnicy specyficznego dla pierwszego parametru, który jest zwykle typem całkowitym i wydaje się rozsądny.
Używam próby złapania, aby nie przejść do czegoś nieokreślonego. Czy to jest bezpieczne?
Nie, wyłuskiwanie lub zwiększanie nieprawidłowego iteratora jest niezdefiniowanym zachowaniem i nie jest wymagane zgłaszanie żadnych wyjątków. Mimo że wiele implementacji zapewnia obszerne sprawdzanie błędów w kompilacjach debugowania i tak miło jest zgłosić wyjątek UB. Ale przejście do połowy rozmiaru zestawu nie będzie problemem.