Structure pour conserver la valeur à l'aide de la touche à distance

Question

J'ai besoin d'une structure pour conserver une valeur basée sur une clé ayant une plage. Mon implémentation est C++, donc tout STL ou Boost serait excellent.

I ont comme plage-clé, qui sont doubles, et la valeur

• [0,2) -> valeur1
• [2,5) -> valeur2
• [5,10) -> value3
• etc

telle que la recherche de 1,23 devrait revenir valeur1, et ainsi de suite.

À l'heure actuelle, j'utilise un vecteur contenant les trois parties, key1/key2/value, avec une recherche personnalisée, mais il semble qu'il devrait y avoir une structure plus propre.

Edit: Merci à tous. Étant donné que les plages dans ce cas sont supposées être contiguës et ne se chevauchent pas, l'utilisation de upper_bound fonctionnera parfaitement. Merci également pour les solutions Range, elles sont classées pour référence future.

Answer 1

Si vos plages sont contiguës et ne se chevauchent pas, vous devez utiliser std :: map et la fonction de membre upper_bound. Ou, vous pouvez utiliser un vecteur trié avec l'algorithme upper_bound. Dans tous les cas, il vous suffit d'enregistrer la valeur la plus basse de la plage, la partie supérieure de la plage étant définie par la valeur immédiatement supérieure. Edit: J'ai exprimé cela de manière confuse, j'ai donc décidé de donner un exemple. En codant l'exemple, j'ai réalisé que vous avez besoin de upper_bound au lieu de lower_bound. Je comprends toujours ces deux confus.

typedef std::map<double, double> MyMap; 
MyMap lookup; 
lookup.insert(std::make_pair(0.0, dummy_value)); 
lookup.insert(std::make_pair(2.0, value1)); 
lookup.insert(std::make_pair(5.0, value2)); 
lookup.insert(std::make_pair(10.0, value3)); 
MyMap::iterator p = lookup.upper_bound(1.23); 
if (p == lookup.begin() || p == lookup.end()) 
    ...; // out of bounds 
assert(p->second == value1); 

Answer 2

class Range 
{ 
public: 
    Range(double a, double b): 
     a_(a), b_(b){} 
    bool operator < (const Range& rhs) const 
    { 
     return a_ < rhs.a_ && b_ < rhs.b_; 
    } 
private: 
    double a_; 
    double b_; 
}; 
int main() 
{ 
    typedef std::map<Range, double> Ranges; 
    Ranges r; 

    r[ Range(0, 2) ] = 1; 
    r[ Range(2, 5) ] = 2; 
    r[ Range(5, 10) ] = 3; 

    Ranges::const_iterator it1 = r.find(Range(2, 2)); 
    std::cout << it1->second; 

    Ranges::const_iterator it2 = r.find(Range(2, 3)); 
    std::cout << it2->second; 

    Ranges::const_iterator it3 = r.find(Range(6, 6)); 
    std::cout << it3->second; 

    return 0; 
} 

Answer 3

Que diriez-vous quelque chose le long de ces lignes:

#include "stdafx.h" 
#include <iostream> 
#include <string> 
#include <map> 
#include <algorithm> 
#include <sstream> 


class Range 
{ 
public: 
    Range(double lower, double upper) : lower_(lower), upper_(upper) {}; 
    Range(const Range& rhs) : lower_(rhs.lower_), upper_(rhs.upper_) {}; 
    explicit Range(const double & point) : lower_(point), upper_(point) {}; 
    Range& operator=(const Range& rhs) 
    { 
     lower_ = rhs.lower_; 
     upper_ = rhs.upper_; 
     return * this; 
    } 

    bool operator < (const Range& rhs) const 
    { 
     return upper_ <= rhs.lower_; 
    } 

    double lower_, upper_; 
}; 

typedef std::string Thing; 
typedef std::map<Range, Thing> Things; 


std::string dump(const std::pair<Range,Thing> & p) 
{ 
    stringstream ss; 
    ss << "[" << p.first.lower_ << ", " << p.first.upper_ << ") = '" << p.second << "'" << endl; 
    return ss.str(); 
} 

int main() 
{ 
    Things things; 
    things.insert(std::make_pair(Range(0.0, 5.0), "First")); 
    things.insert(std::make_pair(Range(5.0, 10.0), "Second")); 
    things.insert(std::make_pair(Range(10.0, 15.0), "Third")); 

    transform(things.begin(), things.end(), ostream_iterator<string> (cout,""), dump); 

    cout << "--------------------------------------" << endl; 

    things[Range(1.5)] = "Revised First"; 

    transform(things.begin(), things.end(), ostream_iterator<string> (cout,""), dump); 


    return 0; 
} 

... Sortie du programme:

[0, 5) = 'First' 
[5, 10) = 'Second' 
[10, 15) = 'Third' 
-------------------------------------- 
[0, 5) = 'Revised First' 
[5, 10) = 'Second' 
[10, 15) = 'Third'