Comment trouver la médiane de `std :: set` [duplicate]
J'essaye de trouver la médiane de a std::set. Comme il std::settrie déjà tout, je n'ai plus qu'à choisir l'élément du milieu. Mon idée est de passer à la moitié:, std::advance(e, rtspUrls.size() / 2);mais je ne sais pas comment ça va se comporter. Et les nombres comme 1.5? Va-t-il avancer vers quelque chose?
J'utilise un crochet d'essai pour essayer de ne pas avancer dans quelque chose d'indéfini. Est-ce sûr?
Selon http://www.cplusplus.com/reference/algorithm/min_element/?kw=min_element, std::advancelance si l'itérateur lance. Je ne sais pas si l'itérateur de std :: set se lance lorsque nous essayons de le ++faire (https://en.cppreference.com/w/cpp/named_req/BidirectionalIterator ne dit rien).
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;
}
Réponses
Avec std :: set, vous êtes limité à l'utilisation d'itérateurs pour itérer vers l'élément du milieu (dans le cas d'un nombre impair d'entrées dans votre ensemble) ou itérer vers le milieu-1 et le milieu et prendre la moyenne (dans le cas d'un nombre pair d'entrées) pour déterminer la médiane.
Une simple boucle et un compteur sont à peu près aussi simples que possible. Un court exemple serait:
#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;
}
}
}
(bien sûr, vous devrez ajuster les types pour répondre à vos données)
Exemple d'utilisation / sortie
Compilé avec ODDdéfini:
$ ./bin/set_median
c 3
médiane 3
Compilé sans définition supplémentaire pour le cas EVEN:
$ ./bin/set_median
c 3
d 4
median 3.5
std :: suivant
Vous pouvez utiliser std :: next pour passer au n ième itérateur après le courant. Vous devez attribuer le résultat:
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 :: avance
std :: advance avance l'itérateur fourni comme paramètre au n ième itérateur après le courant:
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';
(la sortie pour medianest la même que pour la boucle ci-dessus)
Regardez les choses et faites-moi savoir si vous avez d'autres questions.
Je dois juste choisir l'élément du milieu. Mon idée est de passer à la moitié:,
std::advance(e, rtspUrls.size() / 2);mais je ne sais pas comment ça va se comporter. Qu'en est-il des nombres comme 1,5? Va-t-il avancer vers quelque chose?
std::setles indices utilisent des valeurs entières non signées ( size_t) donc le double 1.5sera converti en size_t 1.
Je ne sais pas si l'itérateur des
std::setlancers lorsque nous essayons de++
Non, ce ne sera pas le cas, mais aller au end()- delà n'est pas défini.
Une vraie médiane pour un ensemble avec une quantité égale d'éléments prendrait la moyenne des deux éléments du milieu - mais cela nécessite que le type que vous stockez dans vos std::setdeux supports +et /. Exemple:
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
Dans votre cas, le type de l'ensemble ne semble pas prendre en charge +et /pour créer une moyenne de deux RTSPUrls au cas où vous auriez un nombre pair d'éléments, vous devriez donc probablement opter pour l'un des deux éléments du milieu au cas où vous auriez un montant égal. Soit en renvoyant un itérateur (pour que l'utilisateur puisse ensuite vérifier si c'est le cas rtspUrls.end()):
return std::next(rtspUrls.begin(), rtspUrls.size() / 2);
Ou en renvoyant une référence ou une copie de l'élément:
if(rtspUrls.empty()) throw std::runtime_error("no elements in set");
return *std::next(rtspUrls.begin(), rtspUrls.size() / 2);
Je dois juste choisir l'élément du milieu
Uniquement lorsque l'ensemble contient un nombre impair d'éléments. Sinon, lorsque la taille est paire, la médiane est définie comme la moyenne des deux valeurs médianes, parfois appelées médianes supérieure et inférieure.
Qu'en est-il des nombres comme 1,5?
Vous n'obtiendrez jamais cela car il rtspUrls.size() / 2s'agit d'une division entière qui tronque toutes les décimales.
Je pense que, en passant un floatou doublecomme deuxième paramètre, comme std::advance(e, 1.5)ne devrait pas compiler. Autant que je puisse voir, la référence ne spécifie pas le type du deuxième paramètre. Cependant la section "implémentations possibles" utilise toujours le type de différence spécifique au premier paramètre, qui est généralement un type intégral et semble raisonnable.
J'utilise un crochet d'essai pour essayer de ne pas avancer dans quelque chose d'indéfini. Est-ce sûr?
Non, déréférencer ou incrémenter un itérateur non valide est un comportement non défini et n'est pas nécessaire pour lever des exceptions. Bien que de nombreuses implémentations fournissent une vérification d'erreur étendue dans les versions de débogage et soient si gentilles de lever une exception, UB se produit. Mais avancer jusqu'à la moitié de la taille des ensembles ne deviendra pas un problème.