c++ - STL set 是否有可能比 STL multiset 更快以防止重复条目？

Question

下午好，我们目前正在使用 STL multimap 和 STL set 来缓存内存映射文件区域。我们希望我们的缓存只有唯一的条目。我们想知道是否有一种方法可以让 STL set 和 STL map 比 STL multiset 和 STL multimap 更快，以防止重复条目。 我们使用以下代码摘录来防止 STL 多映射和 STL 集重复条目。有没有可能让它更快？谢谢。

int distance(char* x, char* y,int error){ 
    if (x >= y && (x - y) <= error){ 
        return 0;
    }
    return (x - y);
};

class MinDist {
public:
    MinDist(){}

    MinDist(char* & p, const int & error){}

    bool operator() (char *  p1, char *  p2 )
    {
      return distance( p1, myPoint, myError) < distance( p2,  myPoint, myError); 
    }

public:
    static char* myPoint;
    static int myError;
};


std::multiset<Range> ranges_type; 
std::multimap<char *,Range, MinDist> mmultimap;


MinDist::myPoint = TmpPrevMapPtr;
MinDist::myError = MEM_BLOCK_SIZE;

std::pair<I,I> b = mmultimap.equal_range(TmpPrevMapPtr); 
for (I i=b.first; i != b.second; ++i){ 
     ranges_type.erase(i->second);
     numerased++;
}

typedef std::multimap<char*,Range,MinDist>::iterator J;
std::pair<J,J> pr = mmultimap.equal_range(TmpPrevMapPtr); 


erasecount = 0;
J iter = pr.first;
J enditer = pr.second;
for(  ; iter != enditer ; ){ 
    if ((*iter).first == TmpPrevMapPtr){
        mmultimap.erase(iter++); 
        erasecount++;
    }
    else{
        ++iter;
    }
}

MinDist::myPoint = 0; 

ranges_type.insert(RangeMultiSet::value_type(n, n + mappedlength,
                &adjustedptr[n],MapPtr,mappedlength));


mmultimap.insert(RangeMultiMap::value_type(MapPtr,
                   Range(n,n + mappedlength,
                      &adjustedptr[n],
                      MapPtr,mappedlength)));

Answer 1

这里有很多东西要读，复杂容器类型的优化是一个棘手的问题。我花了相当多的时间处理类似的问题，所以我会尝试指出一些对我有帮助的事情。

首先，使您的代码更快的常用方法是当 vector 可用时不要使用二叉树。 Microsoft STL 实现将为映射/集合中的每个节点花费大约 14 个字节(3 个指针 + short int 用于我最后检查的红色/黑色标志)的开销，加上 malloc 开销至少再增加 4 个字节才能解决存储您的节点数据。虽然我不太了解您所在领域的具体情况，但内存映射 I/O 让我印象深刻，因为该领域可能存在复杂但速度更快的基于 vector 的解决方案。这将要求您同时映射的 block 数很小——如果您的查找表最多或小于 6,000 字节，则使用用于插入/删除的 memmove 和用于查找的 binary_search 的排序数组实现可能会更快 Release模式(在 Debug模式下，它会更快到几兆字节，遗憾的是)。如果元素是 4 字节指针，则 6,000 字节允许最多 1,500 个映射 block 。

然而，有时您只需要使用树。一种情况是复杂的节点(因此构造/破坏是必不可少的)或相当高的元素计数(因此 O(N) 数组插入变得比 O(log n) 树插入的 malloc 成本慢)。你能在这里做什么？请注意 map/multimap 和 set/multiset 或几乎相同的速度； multi* 版本确实有点慢，但这只是因为处理它们的代码多了几行。

无论如何，有一个大有帮助的事情是弄清楚如何削减 malloc 成本，因为每个节点都会在某个时候调用 malloc/free。削减困难——Release 模式分配器大致相当于大约50-200 次算术运算，因此虽然它是可以击败的，但需要一些努力。不过，您确实有一些希望——map/set 分配的大小都是相同的，因此内存池可以很好地工作。 Google可能是开始的好方法；有很多关于这个主题的好文章。

最后，我发现有一个非常有用的开源采样分析器 -- 它叫做 Very Sleepy ，通常只适用于 Visual Studio 项目。如果您想明确回答 map/multimap 还是 set/multiset 在您的情况下更快，那是我要指出的主要内容。祝你好运!