2

I'm confused as to why the following code compiles in some cases, but not others.

#include <iostream>
#include <vector>
#include <algorithm>

int main(){
  std::vector<int> v(3);
  int a[] = {3, 6, 2};
  std::copy(a, a+3, v.begin());
#define CASE 2
#if CASE == 0
  std::cout << *max_element(a, a+3) << "\n";
#elif CASE == 1
  std::cout << *std::max_element(a, a+3) << "\n";
#else 
  std::cout << *max_element(v.begin(), v.end()) << "\n";
#endif
  return 0;
}

I have placed in three cases: CASE 0 fails to compile because there's no such thing as "max_element". I fix this in CASE 1 by changing to "std::max_element" instead, and it does compile and works as expected.

However, interestingly for CASE 2 (technically anything but 0 or 1), it also compiles and works. But CASE 2 has the same problem as CASE 0, so why does it work?

Jarod42
  • 203,559
  • 14
  • 181
  • 302
xdavidliu
  • 2,411
  • 14
  • 33
  • 1
    [Argument-dependent lookup](http://en.cppreference.com/w/cpp/language/adl). – songyuanyao Apr 20 '16 at 03:23
  • 1
    @songyuanyao so this code depends on implementation details of `vector::iterator`. If it were of non-class type then ADL would fail – M.M Apr 20 '16 at 03:31
  • if I try defining my own version of max_element, with the same name, and then calling it using CASE 2 above, the compiler complains that "call to max_element" is ambiguous, which I'm assuming means that argument-dependent lookup is making the existing max_element conflict with the one I explicitly defined. Why am I not allowed to do this? Does this mean that argument-dependent lookup is polluting my non-std namespace? – xdavidliu Apr 20 '16 at 03:32
  • @M.M Yes you're right definately. – songyuanyao Apr 20 '16 at 03:36
  • @xdavidliu because your own function is not in namespace `std` – M.M Apr 20 '16 at 03:46

1 Answers1

4

In the last case, which you denote "CASE 2", the arguments are iterators that for your standard library implementation are of a type define in namespace std.

Then argument-dependent lookup, more commonly known as just ADL, and nowadays less commonly known as Koenig lookup (after Andrew Koenig), finds the function name in that namespace.

ADL is the mechanism that e.g. finds the non-member operator+ for you when you write

std::string const a = "Blah";
foo( a + "Blah " );

But it can also find ordinary named functions, not just operators.

There is unfortunately no similar mechanism for going the other way, a hypothetical “function-dependent lookup” that e.g. could find a type defined in a class and used in an argument expression for a call of a member function of that class.

Since ¹std::vector is permitted to use raw pointers as iterators, you are not guaranteed that the code will work with another standard library implementation.

Notes:
¹ std::vector and std::basic_string guarantee contiguous internal buffers, and this permits raw pointers as iterators.

Cheers and hth. - Alf
  • 142,714
  • 15
  • 209
  • 331
  • "Since std::vector is permitted to use raw pointers as iterators" I don't think any of the standard library containers are required to use something derived from `std::iterator`. – user657267 Apr 20 '16 at 03:35
  • @user657267: For example, a `std::list` can't use raw pointers as iterators, because incrementing such an iterator would land you in an arbitrary part of memory (just past or within some allocated node). `std::vector` and `std::basic_string` are special in that they guarantee contiguous internal buffers. And this permits raw pointers as iterators. – Cheers and hth. - Alf Apr 20 '16 at 03:37
  • I know, but there's still no requirement that the typedefed type of `std::list::iterator` is defined inside `std`, unless I'm misunderstanding the requirements. – user657267 Apr 20 '16 at 03:50
  • 1
    @user657267: There have been implementations with raw pointers, but AFAIK none with iterators defined in other namespaces. I do not think it's worth cluttering the answer with that possibility. Another unmentioned and far more likely possibility that can make code like this fail, is where the function name is found in two or more namespaces, which can make the call ambiguous. – Cheers and hth. - Alf Apr 20 '16 at 03:53