“展平”std :: set <std::string>用于存储和比较？

Question

这可能是一个愚蠢的问题，基于std :: set <>已经有完美的比较运算符的事实，但我想我可能会对我的特定用例进行优化，并且要确保我没有伤害到自己不知何故。

基本上，我有一个昂贵的操作，需要输入std :: set &。我缓存操作的结果，这样我就可以返回的结果，如果相同的输入已经在过去。这确实需要存储套复印件（我做的

std::map<std::set<std::string>, Result*> 

，然后每次调用操作时都要搜索一次，因为很可能连续调用同一个操作数千次，所以我会说缓存的std :: set在99％以上的时间内找到了。最近，我根据传入字符串中某些字符无效的事实，尝试了一些我认为可能的小改进：我将std :: set压扁成单个字符串，组件字符串用'：'分隔。 '字符，然后我的std :: map变成

std::map<std::string, Result*> 

并且每次调用该操作时，都会将该集合展平并在缓存中搜索单个字符串。

我实际上对性能改进感到惊讶。我的测试运行使用包含5个字符串的std :: sets，每个字符串长30个字符，并且运行10,000,000次搜索。在我的工作站，每次运行的时间分别为

std::map<std::set<std::string>, Result*> : 138.8 seconds 
std::map<std::string, Result>   : 89.2 seconds 

看来，即使压扁设定每次调用的开销，第二种方法是一个巨大的进步。我想我的问题是：为什么？我在这里做了一些可能不好的事情，那就是有目的地避免了std :: set的实现者（即可能导致较大字符串导致坏堆碎片？）是因为集合中的单个字符串位于不同位置并且必须单独进行比较？我在脚下开枪自杀吗？在这种特殊情况下，这似乎是一个明显的改进，以提高性能。

Answer 1

为什么？

数据局部性。

std::set通常实现为二进制搜索树。可能由于您的计算机上使用std::string缓存而导致搜索操作更快，与std::set相比，搜索操作更快。

Answer 2

我会考虑写一个小的包装器来跟踪它的地址和版本号。它将包括修改该组的操作的重载（插入，擦除等），并且当插入/擦除发生时，它会增加版本号。

然后为了确定相等性，你只看两件事：集合的地址和版本号。如果修改相当罕见，并且对平等的测试相当普遍，那么在比较中节省的时间可能会比跟踪更改所花费的时间大得多 - IOW，您将获得巨大的速度优势。

如果你必须写一个完整的包装（一个暴露所有的set的功能）这很可能是大量的工作。但在大多数情况下，这是不必要的。最典型的代码只需要几个功能就可以看到 - 通常只有两个或三个。

#include <iostream> 
#include <set> 
#include <utility> 

template <class T> 
class tracked_set { 
    std::set<T> data; 
    size_t version = 0; 
public: 
    typedef typename std::set<T>::iterator iterator; 

    std::pair<iterator, bool> insert(T &&d) { 
     auto ret = data.insert(std::forward<T>(d)); 
     version += ret.second; 
     return ret; 
    } 

    iterator erase(iterator i) { 
     auto ret = data.erase(i); 
     if (ret != data.end()) 
      ++version; 
    } 

    // At least if memory serves, even non-const iterators on a `set` don't 
    // allow the set to be modified, so these should be safe. 
    auto begin() { return data.begin(); } 
    auto end() { return data.end(); } 
    auto rbegin() { return data.rbegin(); } 
    auto rend() { return data.rend(); } 

    // The `c*` iterator functions return const_iterator's, so 
    // they're definitely safe. 
    auto cbegin() const { return data.cbegin(); } 
    auto cend() const { return data.cend(); } 
    auto crbegin() const { return data.crbegin(); } 
    auto crend() const { return data.crend(); } 

    class token { 
     std::set<T> const *addr; 
     size_t version; 
    public: 
     friend bool operator==(token const &a, token const &b) { 
      return a.addr == b.addr && a.version == b.version; 
     } 

     token(tracked_set const &ts) { 
      addr = &ts.data; 
      version = ts.version; 
     } 
    }; 

    operator token() const { return token(*this); } 
}; 

int main() { 
    using T = tracked_set<int>; 

    T ts; 

    ts.insert(1); 
    ts.insert(2); 

    T::token t(ts); 

    if (t == T::token(ts)) 
     std::cout << "Good\n"; 

    ts.insert(3); 

    if (t == T::token(ts)) 
     std::cout << "bad\n"; 
}