Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Do custom container iterators guarantee ADL to consider namespace std?

I have no intention of using this in real code. I promise.

Does the standard guarantee that std namespace is going to be found when a function argument is of type container::iterator and container::iterator isn't a typedef for a built-in type?

For example

#include <set>
#include <algorithm>
int main()
{
   std::set<int> s;
   find(s.begin(), s.end(), 0); //do I have a guarantee that std::find will be found?
}

In other words, can the iterator class be defined in such a namespace that std won't be considered by ADL?

Thanks in advance.

like image 631
Armen Tsirunyan Avatar asked Jul 23 '11 21:07

Armen Tsirunyan


2 Answers

I believe that the answer is no in the most general case, but yes for most practical implementations.

According to the C++ ISO standard, §3.4.2/2, there is a notion of an "associated namespace" for an argument, which is defined in a way that includes

If T is a class type (including unions), its associated classes are: the class itself; the class of which it is a member, if any; and its direct and indirect base classes. Its associated namespaces are the namespaces in which its associated classes are defined.

This suggests that if the iterator type is really a nested type inside of some container like std::set, then an associated namespace for that iterator in the call to find would be std, since std::set is an associated class and std is the namespace containing set. The standard then says that (§3.4.2/2a)

If the ordinary unqualified lookup of the name finds the declaration of a class member function, the associated namespaces and classes are not considered. Otherwise the set of declarations found by the lookup of the function name is the union of the set of declarations found using ordinary unqualified lookup and the set of declarations found in the namespaces and classes associated with the argument types.

This would mean that you would indeed find the find function in namespace std.

However, this is not guaranteed to work in general. We also have from the spec (§3.4.2) that

Typedef names and using-declarations used to specify the types do not contribute to this set.

So, as you mentioned in your question, if the iterator type is some sort of typedef, this isn't guaranteed to work correctly. But barring that, it appears that if you know that the type is not a typedef, it has to be in namespace std or nested in a class in namespace std and should get picked up for ADL. But don't do it! :-)

like image 193
templatetypedef Avatar answered Oct 10 '22 11:10

templatetypedef


The exact type of ::iterator etc. for the standard containers is implementation-defined, so in theory there's nothing stopping it from being a typedef to something outside of std:: (e.g. a plain pointer).

I can't find anything else in the standard that suggests that ADL will always work in this case, so -- unless someone corrects me -- I'm going to have to say that the answer is: no, you can't assume that find will be found via ADL.

like image 35
Peter Alexander Avatar answered Oct 10 '22 12:10

Peter Alexander