Повысьте эффективность контейнера multi_index с помощью составного ключа, пользовательского компаратора и поиска по частичному индексу.

Что касается вашего исходного решения, вам не нужно использовать составные ключи для вашего второго индекса, поскольку ваш экстрактор Compare в основном пытается заменить механизм, автоматически сгенерированный composite_key/composite_key_compare. Следующее было (слегка) проверено на работу:

struct LBFCompare
{
  bool operator() (const A& x, const A& y) const {
    return compare(
      x.getLabel(), x.getFlag(), x.getValue(),
      y.getLabel(), y.getFlag(), y.getValue());
  }
  bool operator() (const std::string& x, const A& y) const{
    return compare(x,y.getLabel());
  }
  bool operator() (const A& x, const std::string& y) const{
    return compare(x.getLabel(),y);
  }
  template<typename T0>
  bool operator() (const boost::tuple<T0>& x, const A& y) const{
    return compare(x.get<0>(),y.getLabel());
  }
  template<typename T0>
  bool operator() (const A& x, const boost::tuple<T0>& y) const{
    return compare(x.getLabel(),y.get<0>());
  }
  template<typename T0,typename T1>
  bool operator() (const boost::tuple<T0,T1>& x, const A& y) const{
    return compare(x.get<0>(),x.get<1>(),y.getLabel(),y.getFlag());
  }
  template<typename T0,typename T1>
  bool operator() (const A& x, const boost::tuple<T0,T1>& y) const{
    return compare(x.getLabel(),x.getFlag(),y.get<0>(),y.get<1>());
  }
  template<typename T0,typename T1,typename T2>
  bool operator() (const boost::tuple<T0,T1,T2>& x, const A& y) const{
    return compare(x.get<0>(),x.get<1>(),x.get<2>(),y.getLabel(),y.getFlag(),y.getValue());
  }
  template<typename T0,typename T1,typename T2>
  bool operator() (const A& x, const boost::tuple<T0,T1,T2>& y) const{
    return compare(x.getLabel(),x.getFlag(),x.getValue(),y.get<0>(),y.get<1>(),y.get<2>());
  }
  bool compare(const std::string& l1, const std::string& l2) const {
    return l1 < l2;
  }
  bool compare(const std::string& l1, bool f1, const std::string& l2, bool f2) const {
    if (l1 != l2) return l1 < l2;
    return f1 < f2;
  }
  bool compare(const std::string& l1, bool f1, float v1, const std::string& l2, bool f2, float v2) const {
    if (l1 != l2) return l1 < l2;
    if (f1 != f2) return f1;
    return f1 ? (v1 > v2) : (v1 < v2);
  }
};

struct by_id_label{};
struct by_label_flag_value{};

typedef boost::multi_index_container<
  Ptr,
  boost::multi_index::indexed_by<
    boost::multi_index::ordered_unique<
      boost::multi_index::tag<by_id_label>,
      id_label_key
    >,
    boost::multi_index::ordered_unique<
      boost::multi_index::tag<by_label_flag_value>,
      boost::multi_index::identity<A>,
      LBFCompare
    >
  >
> Items;
typedef Items::index<by_label_flag_value>::type Items_by_label_flag_value;

int main()
{
  Items c;
  c.insert(Ptr(new A("id","label",true,1.0)));
  Items_by_label_flag_value& i=c.get<by_label_flag_value>();
  i.find("id");
  i.find(boost::make_tuple("id"));
  i.find(boost::make_tuple("id",true));
  i.find(boost::make_tuple("id",true,1.0));
}

Упомянутые вами проблемы неоднозначности связаны с тем, что вы, вероятно, ищете, передавая кортежи с const char*s, а не полностью сформированные std::strings: в этой ситуации есть неявные преобразования и, по-видимому, кортежи 1-, 2- и 3-размера одинаково хорошие кандидаты (имхо проблема реализации с кортежами). Решение состоит в том, чтобы шаблонизировать те LBFCompare::operator(), которые принимают кортежи.

Очень интересная проблема! Самый простой способ решить эту проблему, о которой я могу думать, это: добавить следующее в свой класс

class A {
  ...
  float getTaggedValue()const{return getFlag()?-getValue():getValue();}
  ...
};

а затем оборудуйте свой второй индекс обычным составным ключом на (label,tag,tagged_value). Выполняя поиск с кортежами (l,t,v), вы не должны забывать иметь vnegated, если тег истинен (приложив немного больше усилий, вы можете заставить getTaggedValue возвращать специальный тип, скажем, pair<bool, double>, чтобы вы непреднамеренно не передали непосредственно в кортеж непроверенное число с плавающей запятой.)