Gamme STL conteneur C de
https://stackoverflow.com/questions/1089192
-
23-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je suis à la recherche d'un conteneur qui mappe d'un double objet à des pointeurs. Cependant, chaque clé est tout simplement une série de doubles qui correspondraient à cet objet.
Par exemple, il pourrait y avoir une paire de clés / valeur est <(0.0 3.0), ptr> ou <(3.5 10.0), ptr2>
container [1,0] devrait revenir ptr, le conteneur [3,0] devrait également revenir ptr, et le récipient [-1,0] devrait être indéfini.
Y at-il un objet avec un comportement similaire par défaut ou devrai-je mettre en œuvre moi-même?
Modifier
Voici le code réel que je l'ai écrit, il pourrait être plus facile de conseils debug / offre sur elle.
// Behavior: A range is defined mathematically as (min, max]
class dblRange
{
public:
double min;
double max;
dblRange(double min, double max)
{
this->min = min;
this->max = max;
};
dblRange(double val)
{
this->min = val;
this->max = val;
};
int compare(const dblRange rhs)
{
// 1 if this > rhs
// 0 if this == rhs
//-1 if this < rhs
if (rhs.min == rhs.max && min == max)
{
/*if (min > rhs.min)
return 1;
else if (min == rhs.min)
return 0;
else
return -1;*/
throw "You should not be comparing values like this. :(\n";
}
else if (rhs.max == rhs.min)
{
if (min > rhs.min)
return 1;
else if (min <= rhs.min && max > rhs.min)
return 0;
else // (max <= rhs.min)
return -1;
}
else if (min == max)
{
if (min >= rhs.max)
return 1;
else if (min < rhs.max && min >= rhs.min)
return 0;
else // if (min < rhs.min
return -1;
}
// Check if the two ranges are equal:
if (rhs.min == min && rhs.max == max)
{
return 0;
}
else if (rhs.min < min && rhs.max <= min)
{
// This is what happens if rhs is fully lower than this one.
return 1;
}
else if (rhs.min > min && rhs.min >= max)
{
return -1;
}
else
{
// This means there's an undefined case. Ranges are overlapping,
// so comparisons don't work quite nicely.
throw "Ranges are overlapping weirdly. :(\n";
}
};
int compare(const dblRange rhs) const
{
// 1 if this > rhs
// 0 if this == rhs
//-1 if this < rhs
if (rhs.min == rhs.max && min == max)
{
/*if (min > rhs.min)
return 1;
else if (min == rhs.min)
return 0;
else
return -1;*/
throw "You should not be comparing values like this. :(\n";
}
else if (rhs.max == rhs.min)
{
if (min > rhs.min)
return 1;
else if (min <= rhs.min && max > rhs.min)
return 0;
else // (max <= rhs.min)
return -1;
}
else if (min == max)
{
if (min >= rhs.max)
return 1;
else if (min < rhs.max && min >= rhs.min)
return 0;
else // if (min < rhs.min
return -1;
}
// Check if the two ranges are equal:
if (rhs.min == min && rhs.max == max)
{
return 0;
}
else if (rhs.min < min && rhs.max <= min)
{
// This is what happens if rhs is fully lower than this one.
return 1;
}
else if (rhs.min > min && rhs.min >= max)
{
return -1;
}
else
{
// This means there's an undefined case. Ranges are overlapping,
// so comparisons don't work quite nicely.
throw "Ranges are overlapping weirdly. :(\n";
}
};
bool operator== (const dblRange rhs ) {return (*this).compare(rhs)==0;};
bool operator== (const dblRange rhs ) const {return (*this).compare(rhs)==0;};
bool operator!= (const dblRange rhs ) {return (*this).compare(rhs)!=0;};
bool operator!= (const dblRange rhs ) const {return (*this).compare(rhs)!=0;};
bool operator< (const dblRange rhs ) {return (*this).compare(rhs)<0;};
bool operator< (const dblRange rhs ) const {return (*this).compare(rhs)<0;};
bool operator> (const dblRange rhs ) {return (*this).compare(rhs)>0;};
bool operator> (const dblRange rhs ) const {return (*this).compare(rhs)>0;};
bool operator<= (const dblRange rhs ) {return (*this).compare(rhs)<=0;};
bool operator<= (const dblRange rhs ) const {return (*this).compare(rhs)<=0;};
bool operator>= (const dblRange rhs ) {return (*this).compare(rhs)>=0;};
bool operator>= (const dblRange rhs ) const {return (*this).compare(rhs)>=0;};
};
En ce moment je vais avoir du mal à avoir la carte accepte un double comme une clé, même si les opérateurs de comparaison sont définis.
Voici un code de conduite que j'utilise pour tester si cela fonctionnerait:
std::map<dblRange, int> map;
map[dblRange(0,1)] = 1;
map[dblRange(1,4)] = 2;
map[dblRange(4,5)] = 3;
map[3.0] = 4;
La solution
Créer une DoubleRange de classe pour stocker la double gamme, et mettre en œuvre les opérateurs de comparaison sur elle. De cette façon, std::map fera le reste pour vous, avec la classe DoubleRange comme la clé.
Autres conseils
Je suis d'accord avec la plupart du temps dans Earwicker que vous pouvez définir une plage. Maintenant, je suis en faveur de la mise en œuvre des opérateurs avec le sens réel (ce que font les types de base font: deux gammes comparent égales si les deux plages sont égales). Ensuite, vous pouvez utiliser le troisième paramètre carte pour passer un foncteur de comparaison (ou la fonction) qui résout votre problème avec cette carte.
// Generic range, can be parametrized for any type (double, float, int...)
template< typename T >
class range
{
public:
typedef T value_type;
range( T const & center ) : min_( center ), max_( center ) {}
range( T const & min, T const & max )
: min_( min ), max_( max ) {}
T min() const { return min_; }
T max() const { return max_; }
private:
T min_;
T max_;
};
// Detection of outside of range to the left (smaller values):
//
// a range lhs is left (smaller) of another range if both lhs.min() and lhs.max()
// are smaller than rhs.min().
template <typename T>
struct left_of_range : public std::binary_function< range<T>, range<T>, bool >
{
bool operator()( range<T> const & lhs, range<T> const & rhs ) const
{
return lhs.min() < rhs.min()
&& lhs.max() <= rhs.min();
}
};
int main()
{
typedef std::map< range<double>, std::string, left_of_range<double> > map_type;
map_type integer; // integer part of a decimal number:
integer[ range<double>( 0.0, 1.0 ) ] = "zero";
integer[ range<double>( 1.0, 2.0 ) ] = "one";
integer[ range<double>( 2.0, 3.0 ) ] = "two";
// ...
std::cout << integer[ range<double>( 0.5 ) ] << std::endl; // zero
std::cout << integer[ range<double>( 1.0 ) ] << std::endl; // one
std::cout << integer[ 1.5 ] << std::endl; // one, again, implicit conversion kicks in
}
Vous devez faire attention à l'égalité et des comparaisons entre les valeurs doubles. Différentes façons de se rendre à la même valeur (dans le monde réel) peut donner des résultats légèrement différents en virgule flottante.
Il est préférable d'utiliser arbre Intervalle structure de données. Boost a une mise en œuvre dans la bibliothèque de conteneurs Intervalle
Une approche serait de calculer les « points de rupture » avant la main:
typedef vector< tuple<double, double, foo*> > collisionlist_t;
const collisionlist_t vec;
vec.push_back(make_tuple(0.0, 3.0, ptr));
vec.push_back(make_tuple(3.5, 10.0, ptr2));
// sort
std::map<double, foo*> range_lower_bounds;
for(collisionlist_t::const_iterator curr(vec.begin()), end(vec.end()); curr!=end; ++curr)
{
/* if ranges are potentially overlapping, put some code here to handle it */
range_lower_bounds[curr->get<0>()] = curr->get<2>();
range_lower_bounds[curr->get<1>()] = NULL;
}
double x = // ...
std::map<double, foo*>::const_iterator citer = range_lower_bounds.lower_bound(x);
Une autre suggestion:. Utilisez une transformation mathématique pour cartographier l'indice de REAL en INT qui peut être comparé directement
Si ces plages sont multiples et denses, il y a aussi une structure connue sous le nom d'un « arbre intervalle », qui peut aider.
Les intervalles ouverts ou fermés ou semi-ouverte? Je suppose fermé. Notez que les intervalles ne peuvent pas se chevaucher par la définition d'une carte. Vous aurez également besoin de règles pour diviser quand on insère un intervalle clapotis sur. les règles doivent décider où la scission a lieu et doit prendre en compte à virgule flottante epsilon.
cette implémentation utilise la carte :: lower_bound et ne pas utiliser une classe comme le domaine de la carte
:: carte lower_bound renvoie un itérateur au premier élément dans un plan avec une valeur de clé qui est égale ou supérieure à celle d'une clé spécifiée. (Par exemple la touche moins supérieure ou égale à K. Un mauvais choix de noms de méthodes STL car elle est la borne supérieure de K).
template <class codomain>
class RangeMap : private std::map<double,std::pair<double,codomain>{
public:
typedef double domain;
typedef std::map<double,std::pair<double,codomain>:: super;
typename super::value_type value_type;
protected:
static domain& lower(const value_type& v){
return v.first;
}
static domain& upper(const value_type& v){
return v.second.first;
}
static codomain& v(const value_type& v){
return v.second.second;
}
public:
static const domain& lower(const value_type& v){
return v.first;
}
static const domain& upper(const value_type& v){
return v.second.first;
}
static const codomain& v(const value_type& v){
return v.second.second;
}
static bool is_point(const value_type& vf) {
return lower(v) == upper(v);
}
static bool is_in(const domain& d,const value_type& vf) {
return (lower(v) <= d) && (d <= upper(v));
}
const_iterator greatest_lower_bound(const domain& d)const {
const_iterator j = super::lower_bound(d);
if(j!=end() && j->first==d) return j;//d is the lh side of the closed interval
//remember j->first >= d because it was lower but its the first
if(j==begin()) return end();//d < all intervals
--j; //back up
return j;
}
const_iterator find(domain& d) {
const_iterator j = greatest_lower_bound(d);
if (is_in(j,d)) return j;
return end();
}
iterator greatest_lower_bound(const domain& d) {
iterator j = super::lower_bound(d);
if(j!=end() && j->first==d) return j;//d is the lh side of the closed interval
//remember j->first >= d because it was lower but its the first
if(j==begin()) return end();//d < all intervals
--j; //back up
return j;
}
const_iterator find(domain& d) const{
iterator j = greatest_lower_bound(d);
if (is_in(j,d)) return j;
return end();
} //so much for find(d)
iterator find(domain& d){
iterator j = greatest_lower_bound(d);
if (is_in(j,d)) return j;
return end();
} //so much for find(d)
struct overlap: public std::exception{
};
bool erase(const double lhep,const double rhep);
//you have a lot of work regarding splitting intervals erasing when overlapped
//but that can all be done with erase, and insert below.
//erase may need to split too
std::pair<iterator,bool>
split_and_or_erase_intervals(const double lhep,
const double rhep,
const codomain& cd);
//the insert method - note the addition of the overwrtite
std::pair<iterator,bool>
insert(const double lhep,const double rhep,const codomain& cd,bool overwrite_ok){
if( find(lhep)!=end() || find(rhep)!=end() ) {
if(overwrite_ok){
return split_and_or_erase_intervals(const double lhep,
const double rhep,
const codomain& cd);
}
throw overlap();
}
return insert(value_type(lhep,pair<double,codomain>(rhep,cd)));
}
};
Si vos intervalles doivent être non-chevauchement, vous devez ajouter un code supplémentaire pour vérifier cette propriété lors de l'insertion en temps. Plus précisément, la propriété que vous souhaitez affirmer est que votre nouvel intervalle est tout à fait dans une plage qui était auparavant vide. Un moyen facile de le faire est de permettre deux types de gammes: « occupé » et « vide ». Vous devriez commencer par la création d'une seule entrée « vide » qui couvre toute la gamme utilisable. L'insertion d'une nouvelle gamme « occupée » exige:
(1) recherche une certaine valeur au sein de la nouvelle gamme.
(2) veiller à ce que la plage de retour est vide et entièrement englobe votre nouvelle gamme. (Ce fut l'affirmation nécessaire, ci-dessus)
(3) modifier la plage vide de retour de sorte que son extrémité se trouve au début de votre nouvelle gamme.
(4) insérer une nouvelle gamme vide qui commence à la fin de votre nouvelle gamme, et se termine à l'ancienne de la fourchette de retour.
(5) insérer votre nouvelle gamme, confiant qu'il est entouré de vide-gammes.
(6) Il peut y avoir des cas supplémentaires coin-lors de l'insertion d'une nouvelle gamme occupée qui n'a pas d'espace vide qui sépare des autres plages occupées.
