Language Version

I am using a version of the GNU C compiler that supports C 17 (though I am not yet familiar with all that was added in C 11/14/17).

The Problem

In the code below, I have found that I can insert into a set<> using a custom sorting criterion, but I cannot test for the presence of an element using set<>::find(). The following compilation error results upon a call to 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();

This is confusing to me since element equivalence is defined by:

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

As can be seen below, I have the required operator defined.

Undesirable Alternative

As an alternative, I can search through the set<> element-by-element, but that is not preferable since doing so would run in linear time.

My Questions

1. What am I misunderstanding?
2. Is there a way I can search in logarithmic time, as one normally could with set<>::find()?

Code

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();
}

CodePudding user response：

Your comparator takes two arguments of type const node_sp_t&, so you must have a node_sp_t object to compare against.

In C 14, you can use a transparent comparator, allowing you to compare against a different type (in this case, 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();
}

But since you are using C 11, this isn't an option with std::set (you can use this or something like it with alternative implementations, like boost::container::set).

An "easy" way to create a shared_ptr for cheap without dynamically allocating is to use the aliasing constructor:

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();
}

Unfortunately, you have to pay for the cost of constructing a node_t in C 11.

You might also want to move from this in add_child if default constructing is expensive:

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)));
}

Alternatively, you can use something like std::map<char, node_sp_t> instead.