3

我有一个性能敏感的函数，它使用 amap<string, ...>来存储一些数据。

我需要能够以其他任何子项作为stringstring键来查找值，而无需创建中间值string（即，目标是防止仅因为我想查找某些内容而发生堆分配）。

显而易见的解决方案是保存两个单独的数据结构（可能还有另一个map，以从某个键映射到每个字符串）——一个用于字符串，一个用于对这些字符串的引用。

但我想知道，有没有更好的方法来map单独使用一个，或者我需要另一个数据结构？如果可能的话，我想避免创建太多额外的间接。

4

2 回答 2

5

对不起，如果我误解了，但是如果您可以使用查询字符串的“子字符串视图”来搜索多图而不是普通std::string对象，您的问题会得到解决吗？

在这种情况下，以下几行将起作用（使用基于 C++11 的编码）：

定义子字符串视图对象类型。它由字符串和（从，到）偏移量构成，但不复制子字符串：

class substrview
{
  std::string::const_iterator _from;
  std::string::const_iterator _to;
public:
  substrview(
       const std::string &s,
       const std::size_t from,
       const std::size_t to)
    : _from(s.begin()+from), _to(s.begin()+to)
  { }

  std::string::const_iterator begin() const
  { return _from; }

  std::string::const_iterator end() const
  { return _to; }
};

为了使用子字符串视图搜索多地图，我建议使用std::lower_bound和std::upper_bound方法<algorithm>：

int main()
{
  std::multimap<std::string,int> map {
    { "hello" , 1 },
    { "world" , 2 },
    { "foo" , 3 },
    { "foobar" , 4 },
    { "foo" , 5 },
  };

  std::string query { "barfoo" };
  /* Search for all suffixes of "barfoo", one after the other: */
  for (std::size_t i = 0 ; i < query.size() ; ++i) {
    substrview subquery { query,i,query.size() };
    auto found_from = std::lower_bound(begin(map),end(map),subquery,cmpL);
    auto found_to   = std::upper_bound(begin(map),end(map),subquery,cmpU);

    /* Now [found_from,found_to) is the match range in the multi-map.
       Printing the matches: */
    while (found_from != found_to) {
      std::cout << found_from->first << ", " << found_from->second << '\n';
      ++found_from;
    }

  }
}

为此，我们只需要定义比较运算符cmpL和cmpU(一个 for lower_bound，另一个 for upper_bound- 我们需要两个，因为比较是不对称的：将 multi-map 条目与substringviewincmpL进行比较，并将 asubstringview与 multi-map 条目进行比较在cmpU）：

inline bool cmpL(
    const std::pair<std::string,int> &entry,
    const substrview                 &val)
{
  return std::lexicographical_compare
    (entry.first.begin(),entry.first.end(),val.begin(),val.end());
}

inline bool cmpU(
   const substrview                 &val,
   const std::pair<std::string,int> &entry)
{
  return std::lexicographical_compare
    (val.begin(),val.end(),entry.first.begin(),entry.first.end());
}

完整代码的工作要点：https ://gist.github.com/4070189

于 2012-11-14T04:01:50.903 回答
3

您需要一个string_ref参与<关系的类型std::string。在 TS n3442中，Jeffrey Yaskin 建议引入一种string_ref受 GoogleStringPiece和 llvm影响的类型StringRef。如果您可以使用其中任何一个，那么您就完成了；否则，将您自己的接口写入建议的接口应该相当容易，尤其是当您只需要功能的一个子集时。

请注意，如果您有来自的隐式构造函数std::string：

string_ref(const std::string &s): begin(s.begin()), end(s.end()) {}

然后与的<关系std::string是免费的。

于 2012-11-14T09:54:36.930 回答