Document number: N4017
Date: 2014-05-22
Project: Programming Language C++,
Library Evolution Working Group
Reply-to: Riccardo Marcangelo
<ricky.65@outlook.com>
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