Avoiding const_cast when calling std::set<Type*>::find

Question

Is there any good way to obviate the const_cast below, while keeping const correctness?

Without const_cast the code below doesn't compile. set::find gets a const reference to the set's key type, so in our case it guarantees not to change the passed-in pointer value; however, nothing it guaranteed about not changing what the pointer points to.

class C {
public:
   std::set<int*> m_set;

   bool isPtrInSet(const int* ptr) const
   {
       return m_set.find(const_cast<int*>(ptr)) != m_set.end();
   }
};

Maurene

You are returning an iterator in a function that returns a bool, this code does not currently compile. Did you mean to use return m_set.find(const_cast<int*>(ptr)) != std::cend(m_set);? – Greenwich

Whoops, fixed. Thanks – Maurene

std::find could help. I wonder if they ever partly specialize it to run in logarithmic time on std::set bounds. – Pliske

Answer 1

Yes.

In C++14, you can use your own comparator that declares int const* as transparent. This would enable the template overload of find() that can compare keys against arbitrary types. See this related SO question. And here's Jonathan Wakely's explanation.

Outrush

Answer 2

I want to explain the underlying logic of why this is impossible.

Suppose set<int*>::find(const int*) would be legitimate. Then you could do the following:

set<int*> s;
const int* p_const;
// fill s and p
auto it = s.find(p_const);
int* p = *it;

Hey presto! You transformed const int* to int* without performing const_cast.

Vault

Following your logic comparing const and not const pointer should be illegal, or somebody can make this hocus pocus by find_if(). Pretty convoluted logic imho – Outofdoor

Answer 3

Is there any good way to obviate the const_cast below, while keeping const correctness?

I am not sure whether what I am going to suggest qualifies as a "good way". However, you can avoid the const_cast if you don't mind iterating over the contents of the set yourself. Keep in mind that this transforms what could be an O(log(N)) operation to an O(N) operation.

bool isPtrInSet(const int* ptr) const
{
   for ( auto p : m_set )
   {
      if ( p == ptr )
      {
         return true;
      }
   }
   return false;
}

Cyanogen

Is there somebody in good mind that would pay O(N) vs O(log(N)) just to avoid const_cast? – Outofdoor

@Slava, I wouldn't but I can't speak for everybody. – Cyanogen