Document number: N4017

Date: 2014-05-22

Project: Programming Language C++, Library Evolution Working Group

Reply-to: Riccardo Marcangelo <[email protected]>

 

Non-member size() and more

 

Introduction

This is a proposal to add non-member std::size and other useful utility functions (std::empty, std::front, std::back, and std::data). The inclusion of these functions would provide benefits in regards to safety, efficiency, and generality.

Motivation And Scope

A common task in C++ is to determine the number of elements in a built-in C array, especially when working with legacy code. This is usually achieved using the sizeof operator by taking the size of the entire array and dividing it by the size of a single element. For example, sizeof(a)/sizeof(*(a)) where a is an array. For convenience, this is often wrapped in a macro with a name such as "ARRAYSIZE" or "countof".  For example:

#define ARRAYSIZE(a) (sizeof(a)/sizeof(*(a)))

The problem with such a macro is that it isn't type safe. If a pointer is passed instead of a built-in array, code will compile but yield an erroneous result with no compiler warning or error. More advanced versions such as Microsoft's _countof macro use extra trickery to issue a compile time error if a pointer is passed to it.

In C++11 we can dispose of a macro and instead use a constexpr function template to return the number of elements in a built-in array at compile time. Such a function provides a drop-in replacement for an old macro.

For example:

template <class T, std::size_t N>

constexpr std::size_t size(const T (&array)[N]) noexcept

{

    return N;

}

 

We can currently use std::distance(std::begin(c), std::end(c)) to generically obtain the number of elements for both built-in arrays and Standard containers. However, as Stephan T. Lavavej pointed out, std::distance is verbose and inefficient for many containers. The Standard containers have a constant time size() member function yet std::distance is linear time for containers with a weaker than random-access iterator (list, the associative containers, and the unordered associative containers). Another disadvantage of std::distance is that it is not constexpr.

Writing about the STL containers in his "Notes on Programming", Alexander Stepanov states - "I made size into a member function in STL in an attempt to please the standard committee. I knew that begin, end and size should be global functions but was not willing to risk another fight with the committee." Thankfully std::begin() and std::end() global functions were included in C++11 but sadly not a global std::size().

It would be beneficial to unify containers that have a size() member function and built-in arrays by providing an overload for containers that have a size() member function. This would enable programmers to simply remember to use std::size() to determine the number of elements for both built-in arrays and containers with a size() member function.

Similarly, it would also be useful to have the non-member functions std::empty(), std::front(), std::back(), and std::data().

Example usage:

int builtin_one [10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

std::vector<int> vec (5, 13);

 

//non-member size

int builtin_two [std::size(builtin_one)];

std::array<int, std::size(builtin_one)> arr;

               

std::cout << std::size(builtin_one) << '\n';

std::cout << std::size(builtin_two) << '\n';

std::cout << std::size(arr) << '\n';

std::cout << std::size(vec) << '\n';         

           

//non-member front/back

//allow the result to be used as an lvalue

std::front(builtin_two) = 53;

std::back(vec) = 11;

std::cout << std::front(builtin_two) << '\n';

std::cout << std::back(vec) << '\n';

           

//non-member empty

std::cout << std::boolalpha << "std::empty(builtin_one): " << std::empty(builtin_one) << '\n';

std::cout << "std::empty(vec): " << std::empty(vec) << '\n';

           

//non-member data

std::cout << "std::data(builtin_one): " << std::data(builtin_one) << '\n';

std::cout << "std::data(vec): " << std::data(vec) << '\n';                    

 

In C++11 an alternative approach to obtain the number of elements in a built-in array is to use std::extent. For example:

int array [10];

auto array_size = std::extent<decltype(array)>::value;

Disadvantages of this approach are that it is verbose and we lose the opportunity to unify built-in arrays and containers.

Impact On The Standard

This proposal is a pure library extension that can be implemented in C++11.

Design Decisions

I chose not to provide an overload of std::size() for forward_list.  My concern was that some people may feel that std::size() should always have constant complexity as all STL containers with a size() member function require it to be constant. A std::size() overload for forward_list would be the oddball in that it would have linear complexity. It could be easily included if desired.

Deciding where these functions should live is something that Committee members may want to discuss.

I suggest that header <iterator> is the most suitable location for the aforementioned functions. std::data() returns a pointer and all of the other proposed functions (std::size(), std::empty(), std::front(), and std::back() ) have their operational semantics defined in terms of begin() and end(). Therefore it appears to be a natural fit that all of these functions should live together.

Question

In regards to the proposed "Runtime-sized arrays with automatic storage duration" in the Array Technical Specification, is it correct that they cannot be supported here as they cannot be passed to a function? The same problem exists with std::begin and std::end for such arrays. Is there anything that can be done?

Proposed Wording

Modify the section 24.3 Header <iterator> synopsis [iterator.synopsis] by adding the following at the end of the synopsis:

// 24.8, container access:

// capacity:

template <class C> constexpr auto size(const C& c) noexcept;

template <class T, size_t N> constexpr size_t size(const T (&array)[N]) noexcept;

template <class C> constexpr bool empty(const C& c) noexcept;

template <class T, size_t N> constexpr bool empty(const T (&array)[N]) noexcept;

// element access:

template <class C> constexpr decltype(auto) front(C& c);

template <class C> constexpr decltype(auto) front(const C& c);

template <class C> constexpr decltype(auto) back(C& c);

template <class C> constexpr decltype(auto) back(const C& c);

template <class T, size_t N> constexpr T& front(T (&array)[N]) noexcept;

template <class T, size_t N> constexpr T& back(T (&array)[N]) noexcept;

// data access:

template <class C> constexpr auto data(C& c) noexcept;

template <class C> constexpr auto data(const C& c) noexcept;

template <class T, size_t N> constexpr T* data(T (&array)[N]) noexcept;

 

Add a new section 24.8 container access [iterator.container] containing the following:

In addition to being available via inclusion of the <iterator> header, the function templates in [iterator.container] are also available when any of the following headers are included: <array>, <deque>, <forward_list>, <list>, <map>, <regex>, <set>, <string>, <unordered_map>, <unordered_set>, or <vector>.

// capacity:

template <class C> constexpr auto size(const C& c) noexcept;

            Returns: c.size().

template <class T, size_t N> constexpr size_t size(const T (&array)[N]) noexcept;

            Returns: N.

template <class C> constexpr bool empty(const C& c) noexcept;

            Returns: c.empty().

template <class T, size_t N> constexpr bool empty(const T (&array)[N]) noexcept;

            Returns: false.

// element access:

template <class C> constexpr decltype(auto) front(C& c);

template <class C> constexpr decltype(auto) front(const C& c);

            Returns: c.front().

template <class C> constexpr decltype(auto) back(C& c);

template <class C> constexpr decltype(auto) back(const C& c);

            Returns: c.back().

template <class T, size_t N> constexpr T& front(T (&array)[N]) noexcept;

            Returns: array[0].

template <class T, size_t N> constexpr T& back(T (&array)[N]) noexcept;

            Returns: array[N - 1].

// data access:

template <class C> constexpr auto data(C& c) noexcept;

template <class C> constexpr auto data(const C& c) noexcept;

            Returns: c.data().

template <class T, size_t N> constexpr T* data(T (&array)[N]) noexcept;

            Returns: array.

Acknowledgments

A big thank you to Stephan T. Lavavej for his numerous and valuable feedback, suggestions, and corrections for this proposal.

Credit to Daniel Krügler for suggesting "container access" as the name of the new sub-clause in <iterator>.

References

Stepanov, A., "Notes on Programming", p. 21. Available from: http://www.stepanovpapers.com/notes.pdf

Microsoft Developer Network, "_countof Macro". Available from: http://msdn.microsoft.com/en-us/library/ms175773.aspx

Maurer, J., N3639 "Runtime-sized arrays with automatic storage duration (revision 5)". Available from: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3639.html