2011-03-10 134 views
6

我正在使用boost :: multi_index與我想根據其大小索引的數據類型。但是,此數據類型的size()成員函數執行起來很昂貴。 multi_index是否緩存從其關鍵提取器獲得的值?例如,如果我創建了一個帶有成員函數鍵(element.size())的有序索引的multi_index容器,並且插入了一個元素,該元素的大小將其放置在容器中間的某個位置,容器將重新創建 - 在查找正確的插入點之前,在遍歷其內部數據結構時訪問它所訪問的所有元素上的size()成員函數?是否緩存boost multi_index提取的鍵?

回答

9

那麼,對於成員函數索引的文件說,他們稱之爲引用的成員函數: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 

所以,看起來答案是不,它不緩存值

+0

太棒了,謝謝。這太糟糕了。猜猜我必須包裝我的類型。 – vsekhar 2011-03-10 23:21:48