通过自定义标准搜索集合<>

Question

语言版本

我正在使用支持 C++17 的 GNU C++ 编译器版本（尽管我还不熟悉 C++11/14/17 中添加的所有内容）。

问题

在下面的代码中，我发现我可以使用自定义排序标准插入 set<>，但我无法使用 设置<>::查找()。调用 set<>::find():

时会产生以下编译错误

error: no matching function for call to ‘std::setstd::shared_ptr<node_t, node_comp_t>::find(char&) const’
return children.find(c) != children.end();

这让我感到困惑，因为元素等价由以下定义：

!(lhs < rhs) && !(rhs < lhs)

如下所示，我定义了所需的运算符。

不受欢迎的选择

作为替代方案，我可以逐个元素地搜索 set<>，但这并不可取，因为这样做会在线性时间内运行 .

我的问题

我误会了什么？
有没有一种方法可以按对数时间进行搜索，就像通常使用 set<>::find()?

代码

struct node_t;
using node_sp_t = shared_ptr<node_t>;

class node_comp_t
{
   public:
      inline bool operator()(const node_sp_t &lhs, const node_sp_t &rhs) const;
};

using node_sp_set_t = set<node_sp_t, node_comp_t>;

class node_t
{
   public:
      explicit node_t(char c_p): c{c_p} {}

      inline char get_c() const
      {
         return c;
      }

      void add_child(char c)
      {
         if (!child_exists(c))
            children.insert(make_shared<node_t>(c));
      }

      bool child_exists(char c) const
      {
         // c is not of the children set element type (node_sp_t).
         // So, find() cannot be used with c.
         //
         // Why does node_comp_t not get used by find()?
         //
         // How may I search for c in logarithmic time if not by using find()?
         //
         return children.find(c) != children.end();

         // This works, but it runs in linear time!
         // for (const node_sp_t &node_sp : children)
         // {
         //    if (node_sp->get_c() == c)
         //       return true;
         // }

         // return false;
      }

   private:
      char c;
      node_sp_set_t children;
};

inline bool node_comp_t::operator()(const node_sp_t &lhs, const node_sp_t &rhs) const
{
   return lhs->get_c() < rhs->get_c();
}

Answer 1

你的比较器有两个 const node_sp_t& 类型的参数，所以你必须有一个 node_sp_t 对象来比较。

在 C++14 中，您可以使用 transparent comparator，允许您与不同的类型进行比较（在本例中，char）

class node_comp_t
{
   public:
      inline bool operator()(char lhs, const node_sp_t &rhs) const;
      inline bool operator()(const node_sp_t &lhs, char rhs) const;
      inline bool operator()(const node_sp_t &lhs, const node_sp_t &rhs) const;
      using is_transparent = void;
};

inline bool node_comp_t::operator()(char lhs, const node_sp_t &rhs) const
{
   return lhs < rhs->get_c();
}
inline bool node_comp_t::operator()(const node_sp_t &lhs, char rhs) const
{
   return lhs->get_c() < rhs;
}
inline bool node_comp_t::operator()(const node_sp_t &lhs, const node_sp_t &rhs) const
{
   return lhs->get_c() < rhs->get_c();
}

但是因为您使用的是 C++11，所以这不是 std::set 的选项（您可以将它或类似的东西用于其他实现，例如 boost::container::set）。

一种无需动态分配就可以廉价创建 shared_ptr 的“简单”方法是使用别名构造函数：

bool child_exists(char c) const
{
    node_t compare_against{c};
    return children.find(node_sp_t{node_sp_t{nullptr}, &compare_against}) != children.end();
}

不幸的是，你必须支付在 C++11 中构建 node_t 的成本。

如果默认构造很昂贵，您可能还想在 add_child 中从这里移动：

void add_child(char c)
{
   node_t compare_against{c};
   if (children.find(node_sp_t{node_sp_t{nullptr}, &compare_against}) == children.end())
      children.insert(std::make_shared<node_t>(std::move(compare_against)));
}

或者，您可以使用 std::map<char, node_sp_t> 之类的东西。

通过自定义标准搜索集合<>

Searching a set<> via Custom Criterion

c++

stl

c++11

c++14

c++17

语言版本

问题

不受欢迎的选择

我的问题

代码