Кэшируются ли извлеченные ключи boost multi_index? - PullRequest
Новая
       39

Кэшируются ли извлеченные ключи boost multi_index?

7 голосов
/ 10 марта 2011

Я использую boost :: multi_index с типом данных, который я хотел бы проиндексировать в зависимости от его размера. Однако функция-член size () этого типа данных является дорогостоящей для выполнения. Кэширует ли multi_index значения, которые он получает от своих экстракторов ключей?

Например, если бы я создал контейнер multi_index с упорядоченным индексом с функциональной клавишей-членом (element.size ()) и вставил элемент, размер которого поместил бы его где-то посередине контейнера, контейнер перезапустил бы вызывать функцию-член size () для всех элементов, которые она посещает, при обходе внутренней структуры данных, прежде чем найти правильную точку вставки?

1 Ответ

10 голосов
/ 10 марта 2011

Что ж, в документации по индексаторам функций-членов сказано, что они вызывают функцию-член: http://www.boost.org/doc/libs/1_46_0/libs/multi_index/doc/reference/key_extraction.html#key_extractors

Но в случае сомнений профиль: 

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/mem_fun.hpp>
#include <boost/multi_index/indexed_by.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

namespace bmi = boost::multi_index;

int g_calls = 0;
struct A
{
  explicit A(int sz) : m_size(sz) { }
  int size() const { ++g_calls; return m_size; }
private:
  int m_size;
};

typedef boost::multi_index_container<
  A*,
  bmi::indexed_by<
    bmi::ordered_non_unique<
      BOOST_MULTI_INDEX_CONST_MEM_FUN(A,int,A::size)
    >
  >
> container_t;

int main()
{
  container_t cont;
  int n = 100;
  vector<int> o(2*n+1);
  for( int i = 0; i != 2*n+1; ++i )
    o[i] = i;
  random_shuffle(o.begin(), o.end());

  for( int i = 0; i != n; ++i )
    cont.insert(new A(o[i]));
  cout << "Calls to A::size(): "<< g_calls << endl;
  for( int i = n+1; i <= 2*n; ++i )
    cont.insert(new A(o[i]));
  cout << "Calls to A::size(): "<< g_calls << endl;
  cont.insert(new A(o[n]));
  cout << "Calls to A::size(): "<< g_calls << endl;
  for( int i = 0; i != o.size(); ++i )
    cont.find(o[i]);
  cout << "Calls after calling find " << o.size() << " times: "<< g_calls << endl;
  return 0;
}

дает следующий вывод (используяBoost 1.46): 

Calls to A::size(): 629
Calls to A::size(): 1465
Calls to A::size(): 1474
Calls after calling find 201 times: 3262

Итак, похоже, что ответ нет, он не кэширует значения .

...