“Pithy quote here.”

– Some Dude or Dudette, Generic Publication

1 Introduction

A customization point, as will be discussed in this document, is a function used by the Standard Library that can be overloaded on user-defined types in the user’s namespace and that is found by argument-dependent lookup. The Standard Library already defines several customization points:

• swap
• begin
• end

The first is the most well-known and widely used. It is not obvious that begin and end are in fact customization points until one reads the specification of the range-for statement, which mandates that functions begin and end are called unqualified. (iter_swap may also be a customization point depending on how one chooses to read the specification of the reverse algorithm.) We can expect the number of customization points to grow. For instance, N4014[2] suggests adding size as a customization point for fetching the size of a range.

The purpose of this paper is to describe some usability problems with the current approach to defining customization points and to suggest a design pattern that can be used when defining future ones.

2 Motivation and Scope

The correct usage of customization points like swap is to first bring the standard swap into scope with a using declaration, and then to call swap unqualified:

using std::swap;
swap(a, b);

One problem with this approach is that it is error-prone. It is all too easy to call (qualified) std::swap in a generic context, which is potentially wrong since it will fail to find any user-defined overloads.

Another potential problem – and one that will likely become bigger with the advent of Concepts Lite – is the inability to centralize constraints-checking. Suppose that a future version of std::begin requires that its argument model a Range concept. Adding such a constraint would have no effect on code that uses std::begin idiomatically:

using std::begin;
begin(a);

If the call to begin dispatches to a user-defined overload, then the constraint on std::begin has been bypassed.

This paper aims to rectify these problems by recommending that future customization points be global function objects that do argument dependent lookup internally on the users’ behalf.

2.1 Impact on the Standard

This paper recommends no changes to the current working draft. Changing the definition of existing customization points from function templates to global polymorphic function objects is a potentially breaking change. Users are allowed to add specializations of function templates in namespace std for user-defined types. Such code would be broken by this change.

Rather, this paper proposes merely that any customization points added in the future use the design pattern described below.

3 Proposed Design

3.1 Design Goals

The goals of customization point design are as follows (for some hypothetical future customization point cust):

• Code that calls cust either qualified as std::cust(a); or unqualified as using std::cust; cust(a); should behave identically. In particular, it should find any user-defined overloads in the argument’s associated namespace(s).
• Code that calls cust as using std::cust; cust(a); should not bypass any constraints defined on std::cust.
• Calls to the customization point should be optimally efficient by any reasonably modern compiler.
• The solution should not introduce any potential violations of the one-definition rule or excessive executable size bloat.

3.2 Design Details

This design proposes to make customization points global function objects. Below is what std::begin would look like if it were redesigned as a function object (something this paper does not advocate).

namespace std {
  namespace __detail {
    // define begin for arrays
    template <class T, size_t N>
    constexpr T* begin(T (&a)[N]) noexcept {
      return a;
    }

    // Define begin for containers
    // (trailing return type needed for SFINAE)
    template <class _RangeLike>
    constexpr auto begin(_RangeLike && rng) ->
      decltype(forward<_RangeLike>(rng).begin()) {
      return forward<_RangeLike>(rng).begin();
    }

    struct __begin_fn {
      template <class R>
      constexpr auto operator()(R && rng) const
        noexcept(noexcept(begin(forward<R>(rng)))) ->
        decltype(begin(forward<R>(rng))) {
        return begin(forward<R>(rng));
      }
    };
  }

  // To avoid ODR violations:
  template <class T>
  constexpr T __static_const{};

  // std::begin is a global function object
  namespace {
    constexpr auto const & begin =
        __static_const<__detail::__begin_fn>;
  }
}

There are some notable things about this solution. As promised, std::begin is a function object, the type of which is std::__detail::__begin_fn. Also in the std::__detail namespace are the familiar begin free functions which presently live in namespace std. The function call operator of __begin_fn makes an unqualified call to begin which, since it shares the __detail namespace with the begin free functions, will consider those in addition to any overloads that are found by argument-dependent lookup. The strange __static_const template will be described later.

3.3 Analysis

3.3.1 Qualified and unqualified calls should behave identically

From a behavioral perspective, there are two cases to consider: calling std::begin qualified and calling it unqualified.

It is clear that code that calls std::begin qualified will get the desired behavior. The call routes to __begin_fn::operator(), which makes an unqualified call to begin, thereby finding any user-defined overloads.

In the case that begin is called unqualified after bringing std::begin into scope, the situation is different. In the first phase of lookup, the name begin will resolve to the global object std::begin. Since lookup has found an object and not a function, the second phase of lookup is not performed. In other words, if std::begin is an object, then using std::begin; begin(a); is equivalent to std::begin(a); which, as we’ve already seen, does argument-dependent lookup on the users’ behalf.

3.3.2 Unqualified calls should not bypass constraints checking

Since calls route through the global function object whether calls are made qualified or unqualified, we are sure to get the benefit of any constraints checking done there.

3.3.3 Calls to the customization point should be optimally efficient

Given the above defintion of std::begin the following program was compiled with GCC 4.9.2 both with and without the USE_CUSTPOINT define (after switching __static_const from a variable template to a class template with a static constexpr data member to get it to compile).

int main() {
  int rgi[] = {1,2,3,4};
#ifdef USE_CUSTPOINT
  // Go through the customization point
  int * p = std::begin(rgi);
#else
  // Call the free functions directly
  using namespace std::__detail;
  int * p = begin(rgi);
#endif
  std::printf("%p\n",(void*)p);
}

The resulting optimized (-O3) assembly listings were exactly identical:

Global object

Free function

    .file   "custpnt.cpp"
    .def    ___main;    .scl    2;  .type   32; .endef
    .section .rdata,"dr"
LC0:
    .ascii "%p\12\0"
    .section    .text.startup,"x"
    .p2align 4,,15
    .globl  _main
    .def    _main;  .scl    2;  .type   32; .endef
_main:
    pushl   %ebp
    movl    %esp, %ebp
    andl    $-16, %esp
    subl    $32, %esp
    call    ___main
    leal    16(%esp), %eax
    movl    $LC0, (%esp)
    movl    $1, 16(%esp)
    movl    $2, 20(%esp)
    movl    $3, 24(%esp)
    movl    %eax, 4(%esp)
    movl    $4, 28(%esp)
    call    _printf
    xorl    %eax, %eax
    leave
    ret
    .ident  "GCC: (GNU) 4.9.2"
    .def    _printf;    .scl    2;  .type   32; .endef

   .file   "custpnt.cpp"
    .def    ___main;    .scl    2;  .type   32; .endef
    .section .rdata,"dr"
LC0:
    .ascii "%p\12\0"
    .section    .text.startup,"x"
    .p2align 4,,15
    .globl  _main
    .def    _main;  .scl    2;  .type   32; .endef
_main:
    pushl   %ebp
    movl    %esp, %ebp
    andl    $-16, %esp
    subl    $32, %esp
    call    ___main
    leal    16(%esp), %eax
    movl    $LC0, (%esp)
    movl    $1, 16(%esp)
    movl    $2, 20(%esp)
    movl    $3, 24(%esp)
    movl    %eax, 4(%esp)
    movl    $4, 28(%esp)
    call    _printf
    xorl    %eax, %eax
    leave
    ret
    .ident  "GCC: (GNU) 4.9.2"
    .def    _printf;    .scl    2;  .type   32; .endef

This makes sense. Although the use of a global reference to a function object would appear to introduce an indirection to every call of the customization point, the body of __begin_fn::operator() is available in every translation unit and does not refer to the implicit this parameter. Therefore, compilers should have no difficulty eliding the parameter, removing the indirection, and inlining the call.

3.3.4 No violations of the one-definition rule

The example code above uses a strange __static_const variable template to avoid ODR violations. The need for it is illustrated by simpler code like below:

// <iterator>
namespace std {
  // ... define __detail::__begin_fn as before...
  constexpr __detail::_begin_fn {};
}

// header.h
#include <iterator>
template <class RangeLike>
void foo( RangeLike & rng ) {
  auto * pbegin = &std::begin; // ODR violation here
  auto it = (*pbegin)(rng);
}

// file1.cpp
#include "header.h"
void fun() {
  int rgi[] = {1,2,3,4};
  foo(rgi); // INSTANTIATION 1
}

// file2.cpp
#include "header.h"
int main() {
  int rgi[] = {1,2,3,4};
  foo(rgi); // INSTANTIATION 2
}

The code above demonstrates the potential for ODR violations if the global std::begin function object is defined naïvely. Both functions fun in file1.cpp and main in file2.cpp cause the implicit instantiation foo<int[4]>. Since global const objects have internal linkage, both translation units file1.cpp and file2.cpp see separate std::begin objects, and the two foo instantiations will see different addresses for the std::begin object. That is an ODR violation.

In contrast, variable templates are required to have external linkage ([temp]/4). Customization points can take advantage of that to avoid the ODR problem, as below:

namespace std {
  template <class T>
  constexpr T __static_const{};
  namespace {
    constexpr auto const& begin =
      __static_const<__detail::__begin_fn>;
  }
}

Because of the external linkage of variable templates, every translation unit will see the same address for __static_const<__detail::__begin_fn>. Since std::begin is a reference to the variable template, it too will have the same address in all translation units.

The anonymous namespace is needed to keep the std::begin reference itself from being multiply defined. So the reference has internal linkage, but the references all refer to the same object. Since every mention of std::begin in all translation units refer to the same entity, there is no ODR violation ([basic.def.odr]/6).

The relevant parts of the standard are:

[basic.link]/6:

A name having namespace scope (3.3.6) has internal linkage if it is the name of

• […]
• a non-volatile variable that is explicitly declared const or constexpr and neither explicitly declared extern nor previously declared to have external linkage; or

So the reference has internal linkage unless it is considered a variable. Variable is defined in [basic]/6:

A variable is introduced by the declaration of a reference other than a non-static data member or of an object. The variable’s name denotes the reference or object.

So a reference is a variable unless it is a non-static data member. From [basic.scope.namespace]/1, we see that entities at namespace scope are members:

[…] Entities declared in a namespace-body are said to be members of the namespace, and names introduced by these declarations into the declarative region of the namespace are said to be member names of the namespace.[…]

So references declared at namespace scope are not considered variables, and hence do not have internal linkage by default. (This reading is consistent with the implementations we’ve tested, which give such references external linkage.) As a result, the anonymous namespace is needed to give the reference internal linkage, avoiding multiple definition errors.

The author can imagine a reading of [basic.def.odr]/6 that makes the use of std::begin from multiple translation units an ODR violation. The relevant part of [basic.def.odr]/6 is as follows:

[…] in each definition of D, corresponding names, looked up according to 3.4, shall refer to an entity defined within the definition of D, or shall refer to the same entity, after overload resolution (13.3) and after matching of partial template specialization (14.8.3), except that a name can refer to a non-volatile const object with internal or no linkage if the object has the same literal type in all definitions of D, and the object is initialized with a constant expression (5.19), and the object is not odr-used, and the object has the same value in all definitions of D

The question then comes down to whether the reference std::begin is an entity (which, according to [basic]/3, it is), whether the reference is odr-used (this is unclear to the author), and what “refer to” means in this context. Does the name std::begin refer to the reference with internal linkage, or to the object referenced with external linkage. An expert from core may need to weigh in to settle the issue definitively.

Whether this solution conforms to the letter of the standard, from a purely practical standpoint, it seems patently impossible that the destinction could have any significance to real-world code. It is impossible to get the “address” of a reference entity (as opposed to the address of the object it references), so any template that uses the std::begin function object is guaranteed to generate identital code in all translation units.

3.3.5 No executable bloat

If you refer back to the assembly listing for the simple program that uses the std::begin function object, you will notice the lack of any storage for the global objects std::begin or __static_const<__detail::__begin_fn>. The optimizer has removed them. Unoptimized code does have these global objects, but the number of customization points in the STL is so small that their presence in unoptimized object files is not expected to amount to any significant bloat.

3.4 Hooking the Customization Point

End users who wish to “hook” the customization point simply provide the appropriately named overload in their namespace, as they always have.

namespace My {
  struct S {
  };
  int *begin(S &);
}

Since the global function object performs ADL internally, the overload in the My namespace gets found.

int main() {
  My::S s;
  int *p = std::begin(s); // this calls My::begin
}

As shown, the customization point is hooked by defining a free function of the same name as the global function object. That works well for types in other namespaces but for types that are in std themselves, attempting to define such a free function would lead to an error. So the recommendation for types in std is different. Such types can hook the customization point by defining a friend function, as below:

namespace std {
  template <class T>
  class vector {
  public:
    // ...
    friend T * begin(vector & v) {
      // ...
    }
  };
}

This works for class types. For enums in namespace std that must hook customization points – if any such exist – the recommendation is somewhat less elegant. The enum and the overload must be defined in a hidden namespace, and then the enum is pulled into namespace std with a using declaration, as shown below.

namespace std {
  namespace {
    // If hash were a customization point...
    constexpr auto const & hash =
      __static_const<__detail::__hash_fn>::value;
  }
  namespace __hidden {
    enum memory_order {
      // ...
    };
    // If memory_order needed to hook hash...
    size_t hash(memory_order) {
      // ...
    }
  }
  using __hidden::memory_order;
}

4 Design Drawbacks

The author is aware of a few relatively minor drawbacks to the approach described here. The first is added complexity of implementing and specifying customization points. That could be alleviated by centrally defining customization point as a term of art in the standard – describing the properties of customization points instead of the implementation details – and then saying which APIs are customization points.

Another drawback is the added complexity from the perspective of end users. Although this design doesn’t change how people hook the customization point[*] or necessitate changes in how they are called, it will require users to understand what’s going on when things break. It also may not be obvious that a qualified call to a function std::foo will find a foo function in another namespace. This is somewhat mitigated by the fact that users can continue doing using std::foo; foo(a); as they have been told to do for years.

This design may also negatively impact compiler error messages when the customization point is misused. Since the call redirects though an intermediate function object, there will necessary be more noise in the compiler backtrace. This problem is likely to go away with Concepts Lite.

Unoptimized builds will get somewhat slower and larger with this change, it’s unlikely to be enough to be noticed.

There would also necessarily be some inconsistency in the standard if we accepted this new design for future customization points but left the existing ones alone. But that hardly seems a reason to the author to continue doing things in a sub-standard way if the committee decides that the new approach is better. An alternate approach that would not introduce inconsistency would be to adopt the new design for any future TS to redesign the STL as has been discussed in the context of Concepts Lite[5] and Ranges[3].

[*] This design does not permit users to hook customization points by specializing function templates in namespace std. If users are accustomed to doing that, they will need to learn new behavior. But in the opinion of the author, they should anyway.

5 Implementation Experience

The customization point design recommended here has been used for the past year in the Range-v3[4] library. The library is popular judging from the number of people who have registered for notifications, cloned it, and submitted issues and pull requests. There have thus far been no negative comments from users about the customization point design.

6 Alternative Designs

One alternative is to not change anything. The approach to customization point design that the current standard takes – namely, just making them free functions and requiring using declarations to call them – has served the community with some degree of success since the beginning. The drawbacks of this approach have already been described.

Another approach is to replace the function object described here with a free function that dispatches to a differently named function. For instance, a std::begin free function could make an unqualified call to a free function named adl_begin, as below:

namespace std {
  // define begin for arrays
  template <class T, size_t N>
  constexpr T* adl_begin(T (&a)[N]) noexcept {
    return a;
  }

  // Define begin for containers
  // (trailing return type needed for SFINAE)
  template <class _RangeLike>
  constexpr auto adl_begin(_RangeLike && rng) ->
    decltype(forward<_RangeLike>(rng).begin()) {
    return forward<_RangeLike>(rng).begin();
  }

  template <class R>
  constexpr auto begin(R && rng) ->
    decltype(adl_begin(forward<R>(rng))) {
    return adl_begin(forward<R>(rng));
  }
}

Users hook customization points like this by overloaded adl_begin in their namespace. They call std::begin qualified. This design is certainly more straightforward than the design presented here. It is used in Boost.Range[1], where boost::begin makes an unqualified call to a range_begin function that users can overload.

The problems with this approach are:

• It make current practice of calling customization points unqualified after a using declaration wrong. With this approach, ADL shouldn’t be happening on the name “begin” – it should happen only on the name “adl_begin”.
• It makes it unclear how to hook the customization point. Do users overload begin or adl_begin? Or do they specialize begin in namespace std? All will work to one degree or another, but only one is “correct”.