Оцените дерево в C++

Предполагается, что вы ссылаетесь на goog.dom.DomHelper - это, похоже, обеспечивает эффективное решение для работы с DOM в разных браузерах.

Не делайте этого .

Это означает, что вы должны иметь возможность сделать это, сделав свое окно ребенком другого.

Ранг данного ключа K - это число ключей, которое меньше или равно K.

Например, пусть набор = {1, 3, 4, 6, 9}. Затем ранг (1) = 1, ранг (4) = 3, ранг (9) = 5.

Расстояние функции STL () может использоваться для вычисления ранга элемента x, появляющегося в наборе s.

rank = distance (s.begin (), s.find (x));

Проблема заключается в том, что его временная сложность составляет O (n).

Обратите внимание, что предлагаемые две карты (или наборы), индексированные по ключу и рангу, не являются правильным решением. Проблема в том, что смена одного элемента влияет на ряды многих других. Например, добавление элемента 0 в набор s выше изменяет ранги всех существующих элементов: s «» = {0, 1, 3, 4, 6, 9}. ранг (1) = 2, ранг (4) = 4, ранг (9) = 6.

Спасибо.

Я полагаю, что под rank вы подразумеваете расстояние от корня, так как если бы его можно было хранить смежно со значением, вам не пришлось бы так долго возиться.

Я думаю, вы могли бы сделать это "внешне", так как в этом случае ранг может быть экстраполирован из количества раз использования предиката сравнения...

namespace detail
{
  template <class Comparator>
  class CounterComparator: Comparator
  {
  public:
    CounterComparator(size_t& counter):
        Comparator(), mCounter(&counter) {}
    CounterComparator(Comparator comp, size_t& counter):
        Comparator(comp), mCounter(&counter) {}

    template <class T, class U>
    bool operator()(T& lhs, U& rhs) const
    { 
      ++(*mCounter);
      return this->Comparator::operator()(lhs,rhs);
    }
  private:
    size_t* mCounter;
  };
} // namespace detail

template <
  class Key, 
  class Value, 
  class Cmp = std::less<Key>, 
  class Allocator = std::allocator< std::pair<const Key,Value> >
>
class SuperMap
{
  typedef detail::CounterComparator<Cmp> Comparator;
public:
  SuperMap(): mCounter(0), mData(Comparator(mCounter)) {}

  Value& operator[](const Key& key) { return mData[key]; }

  size_t rank(const Key& key) const
  { 
    mCounter = 0; mData.find(key); return mCounter;
  }

private:
  typedef std::map<Key,Value, Comparator, Allocator> data_type;

  mutable size_t mCounter;
  data_type mData;
}; // class SuperMap

int main(int argc, char* argv[])
{
  SuperMap<int,int> superMap;
  superMap[1] = 42;
  std::cout << superMap.rank(1) << std::endl;
}

// outputs
// 2

Он считает количество тестов, но поскольку std::map прекращает тестирование, как только получает правильный ключ... все должно быть в порядке :) Хотя, возможно, там есть какое-то смещение для вывода (1 или 2), чтобы получить ранг вместо этого.

Если вы дали лучшее определение ранга, я могу поработать немного больше, но я не хочу тратить слишком много времени в неправильном направлении.