Although you may still be growing accustomed to templates, it’s time to explore some common tools used to write templates: concepts, traits, and policies. Programming with concepts relates closely to traits, which relate closely to policies. Together and separately, they probably introduce a new programming style for you, but this style forms the foundation for the C++ standard library. As you will discover in this Exploration, these techniques are extremely flexible and powerful. This Exploration looks at these techniques and how to take advantage of them.
Case Study: Iterators
Consider the humble iterator. Consider the std::advance function
(Exploration 46). The advance function changes the position to which an iterator points. The advance function knows nothing about container types; it knows only about iterators. Yet somehow, it knows that if you try to advance a vector’s iterator, it can do so simply by adding an integer to the iterator. But if you advance a list’s iterator, the advance function must step the iterator one position at a time until it arrives at the desired destination. In other words, the advance function implements the optimal algorithm for changing the iterator’s position. The only information available to the advance function must come from the iterators themselves, and the key piece of information is the iterator kind. In particular, only random access and contiguous iterators permit rapid advancement via addition. All other iterators must follow the step-by-step approach. Bidirectional, random access, and contiguous iterators can go backward, but forward and input iterators cannot. (Output iterators require an assignment to produce an output value, so you cannot use advance on an output iterator.) So how does advance know what kind of iterator it has and how to choose the correct implementation?
In most OOP languages, an iterator would derive from a common base class, which would implement a virtual advance function. The advance algorithm would call that virtual function and let normal object-oriented dispatching take care of the details. Or maybe overloading would let you define multiple advance functions that differ in the use of the base class as a parameter type. C++ certainly could take either approach, but it doesn’t.
A simple solution is to use
constraints for overloaded
advance functions. The three functions needed are as follows:
Random access and contiguous iterators: Use addition
Bidirectional iterators: Step-by-step forward or backward
Forward and input iterators: Step-by-step forward only
The
<iterator> module defines several concepts that you can use as constraints to ensure that each advance function definition applies only to the appropriate iterator kind.
Try defining the advance functions before looking at my solution in Listing
70-1.
import <deque>;
import <iostream>;
import <iterator>;
import <list>;
import <string_view>;
import <vector>;
void trace(std::string_view msg)
{
std::cout << msg << '
';
}
template<class Iterator, class Distance>
requires std::random_access_iterator<Iterator> and std::integral<Distance>
void advance(Iterator& iterator, Distance distance)
{
trace("random access or contiguous advance");
iterator += distance;
}
template<class Iterator, class Distance>
requires std::bidirectional_iterator<Iterator> and std::integral<Distance>
void advance(Iterator& iterator, Distance distance)
{
trace("bidirectional iterator");
for ( ; distance < 0; ++distance)
--iterator;
for ( ; distance > 0; --distance)
++iterator;
}
template<class Iterator, class Distance>
requires std::input_iterator<Iterator> and std::unsigned_integral<Distance>
void advance(Iterator& iterator, Distance distance)
{
trace("forward or input iterator");
for ( ; distance > 0; --distance)
++iterator;
}
template<class Iterator, class Distance>
void test(std::string_view label, Iterator iterator, Distance distance)
{
advance(iterator, distance);
std::cout << label << *iterator << '
';
}
int main()
{
std::deque<int> deque{ 1, 2, 3 };
test("deque: ", deque.end(), -2);
std::list<int> list{ 1, 2, 3 };
test("list: ", list.end(), -2);
std::vector<int> vector{ 1, 2, 3};
test("vector: ", vector.end(), -2);
test("istream: ", std::istream_iterator<int>{}, 2);
}
Listing 70-1.One Possible Implementation of std::advance
Another technique uses a single function, but relies on type traits to distinguish the different iterator categories. The <iterator> module defines various template classes that describe common traits or attributes of iterator types. The most important is std::iterator_traits<T>, which defines a member type, iterator_category. The advance function can test that type and compare it with std::random_access_iterator_tag and other iterator tag types to determine the iterator’s kind. Other traits are more focused, such as incrementable_traits, which defines the member difference_type for any iterator that either defines its own difference_type memory or allows subtraction of iterators, in which case difference_type is the type of the subtraction result.
Combine the iterator traits with other traits class templates that are defined in <type_traits>, such as std::is_same<T,U>, which determines whether T and U are the same type. More useful in this case is the template is_base_of<B, D> to test whether B is a base class of D. This helps you because the iterator tag types form a class hierarchy of capability; thus, std::is_base_of<std::input_iterator_tag, T> is true if T is any iterator tag type except std::output_iterator_tag. A trait is “true” when it has a compile-time data member value that is true. The type std::true_type is the most common way to express this.
The easiest way to use the traits for the
advance function is to use the
if constexpr statement
. This is a special kind of conditional that is evaluated at compile time. The code in the body of the
if constexpr statement
is compiled only when the condition is true. Listing
70-2 shows this traits-oriented style of writing
advance.
import <deque>;
import <iostream>;
import <iterator>;
import <list>;
import <string_view>;
import <type_traits>;
import <vector>;
void trace(std::string_view msg)
{
std::cout << msg << '
';
}
template<class Iterator, class Distance>
requires std::input_iterator<Iterator> and std::integral<Distance>
void advance(Iterator& iterator, Distance distance)
{
using tag = std::iterator_traits<Iterator>::iterator_category;
if constexpr(std::is_base_of<std::random_access_iterator_tag, tag>::value)
{
trace("random access+ iterator");
iterator += distance;
}
else {
trace("input+ iterator");
if constexpr(std::is_base_of<std::bidirectional_iterator_tag,tag>::value)
{
while (distance++ < 0)
--iterator;
}
while (distance-- > 0)
++iterator;
}
}
template<class Iterator, class Distance>
void test(std::string_view label, Iterator iterator, Distance distance)
{
advance(iterator, distance);
std::cout << label << *iterator << '
';
}
int main()
{
std::deque<int> deque{ 1, 2, 3 };
test("deque: ", deque.end(), -2);
std::list<int> list{ 1, 2, 3 };
test("list: ", list.end(), -2);
std::vector<int> vector{ 1, 2, 3};
test("vector: ", vector.end(), -2);
test("istream: ", std::istream_iterator<int>{}, 2);
}
Listing 70-2.Implementing std::advance with Type Traits
Type Traits
The <type_traits> header (first introduced in Exploration 53) defines a suite of traits templates that describe the characteristics of a type. They range from simple queries, such as std::is_integral<>, which tells you whether a type is one of the built-in integral types, to more sophisticated queries, such as std::is_nothrow_move_constructible<>, which tells you whether a class has a noexcept move constructor. Some traits modify types, such as std::remove_reference<>, which transforms int& to int, for example.
The
std::move() function
uses type traits, just to name one use of type traits in the standard library. Remember that all it does is change an lvalue to an rvalue. It uses
remove_reference to strip the reference from its argument and then adds
&& to turn the result into an rvalue reference, as follows:
template<class T>
typename std::remove_reference<T>::type&& move(T&& t) noexcept
{
return static_cast<typename std::remove_reference<T>::type&&>(t);
}
Notice the use of the type member typedef. That is how the type traits expose the result of their transformation. The query traits declare type to be a typedef for std::true_type or std::false_type; these classes declare a value member to be true or false at compile time. Although you can create an instance of true_type or false_type and evaluate them at runtime, the typical use is to use them to specialize a template.
Type traits often form the basis for defining concepts. Defining
concepts is an advanced
topic, so I do not cover it in depth, but it helps to get a sense of how a concept is defined. Knowing that the type traits
std::is_integral<T> determines whether a type is one of the built-in integral types, you can define a concept
integral<T> as follows:
template<class T>
concept integral = std::is_integral<T>::value;
A concept is a way of assigning a name to a
constraint. The value after the equal sign is a Boolean expression, treating other concepts as Boolean values. For example, knowing that integral is a concept and
is_signed is a type trait, define the concept
signed_integral
as follows:
template<class T>
concept signed_integral = integral<T> and std::is_signed<T>::value;
Concepts can get very complicated very quickly. For now, let’s tackle a more mundane traits class, std::char_traits.
Case Study: char_traits
Among the difficulties in working with characters in C++ is that the char type may be signed or unsigned. The size of a char relative to the size of an int varies from compiler to compiler. The range of valid character values also varies from one implementation to another and can even change while a program is running. A time-honored convention is to use int to store a value that may be a char or a special value that marks end-of-file, but nothing in the standard supports this convention. You may need to use unsigned int or long.
In order to write portable code, you need a traits class to provide a typedef for the integer type to use, the value of the end-of-file marker, and so on. That’s exactly what char_traits is for. When you use std::char_traits<char>::int_type, you know you can safely store any char value or the end-of-file marker (which is std::char_traits<char>::eof()).
The standard
istream class has a
get() function
that returns an input character or the special end-of-file marker when there is no more input. The standard
ostream class offers
put(c) to write a character.
Use these functions with char_traits to write a function that copies its standard input to its standard output, one character at a time. Call
eof() to obtain the special end-of-file value and
eq_int_type(a,b) to compare two integer representations of characters for equality. Both functions are static member functions of the
char_traits template, which you must instantiate with the desired character type. Call
to_char_type to convert the integer representation back to a
char. Compare your solution with Listing
70-3.
import <iostream>;
import <string>; // for char_traits
int main()
{
using char_traits = std::char_traits<char>; // for brevity and clarity
char_traits::int_type c{};
while (c = std::cin.get(), not char_traits::eq_int_type(c, char_traits::eof()))
std::cout.put(char_traits::to_char_type(c));
}
Listing 70-3.Using Character Traits when Copying Input to Output
First, notice the loop condition. A
comma serves many purposes in C++, separating parameters in function and template declarations, separating values in function calls and initializers, separating declarators in a declaration, and so on. A comma can also separate two expressions where only one is expected; the first sub-expression is evaluated, the result is discarded, and then the second is evaluated. The result of the entire expression is the result of the second sub-expression. In this case, the first sub-expression assigns
get() to
c, and the second sub-expression calls
eq_int_type, so the result of the loop condition is the return value from
eq_int_type
, testing whether the result of
get, as stored in
c, is equal to the end-of-file marker. Another way to write the loop condition is as follows:
not char_traits::eq_int_type(c = std::cin.get(), char_traits::eof())
I don’t like to bury assignments in the middle of an expression, so I prefer to use the comma operator in this case. Other developers have a strong aversion to the comma operator. They prefer the embedded assignment style. Another solution is to use a
for loop instead of a
while loop
, as follows:
for (char_traits::int_type c = std::cin.get();
not char_traits::eq_int_type(c, char_traits::eof());
c = std::cin.get())
The for loop solution has the advantage of limiting the scope of the variable, c. But it has the disadvantage of repeating the call to std::cin.get(). Any of these solutions is acceptable; pick a style and stick with it.
In this case, char_traits seems to make everything more complicated. After all, comparing two integers for equality is easier and clearer when using the == operator. On the other hand, using a member function gives the library writer the opportunity for added logic, such as checking for invalid character values.
In theory, you could write a char_traits specialization that, for instance, implements case-insensitive comparison. In that case, the eq() (which compares two characters for equality) and eq_int_type() functions would certainly require extra logic. On the other hand, you learned in Exploration 59 that such a traits class cannot be written for many international character sets, at least not without knowing the locale.
In the real world, specializations of char_traits are rare.
The char_traits class template is interesting nonetheless. A pure traits class template would implement only typedef members, static data members, and sometimes a member function that returns a constant, such as char_traits::eof(). Another good example of such a traits class is std::numeric_limits. Functions such as eq_int_type()
are not traits, which describe a type. Instead, they are policy functions. A policy class template contains member functions that specify behavior, or policies. The next section looks at policies.
Policy-Based Programming
A policy is a class or class template that another class template can use to customize its behavior. The line between traits and policy is fuzzy, but to me, traits are static characteristics and policies are dynamic behavior. In the standard library, the string and stream classes use the char_traits
policy class template to obtain type-specific behavior for comparing characters, copying character arrays, and more. The standard library provides policy implementations for the char and wchar_t types.
Suppose you are trying to write a high-performance server. After careful design, implementation, and testing, you discover that the performance of std::string introduces significant overhead. In your particular application, memory is abundant, but processor time is at a premium. Wouldn’t it be nice to be able to flip a switch and change your std::string implementation from one that is optimized for space into one that is optimized for speed? Instead, you must write your own string replacement that meets your needs. In writing your own class, you end up rewriting the many member functions, such as find_first_of, that have nothing to do with your particular implementation but are essentially the same for most string implementations. What a waste of time.
Imagine how simple your job would be if you had a string class template that took an extra template argument with which you could select a storage mechanism for the string, substituting memory-optimized or processor-optimized implementations according to your needs. That, in a nutshell, is what policy-based programming is all about.
In a way, the std::string class offers this flexibility because std::string is actually a specialization of std::basic_string
for the char type and for a particular memory allocation policy. In fact, all of the standard container templates (except array) take an allocator template parameter. Writing a new allocator is beyond the scope of this book, so instead, we will write a simpler, hypothetical policy class that can guide the implementation of a mystring class.
For the sake of simplicity, this book implements only a few of the member functions of
std::string. Completing the interface of
std::string is left as an exercise for the reader. Listing
70-4 shows the new string class template and a few of its member functions. Take a look, and you can see how it takes advantage of the
Storage policy.
import <algorithm>;
import <string>;
template<class Char, class Storage, class Traits = std::char_traits<Char>>
class mystring {
public:
using value_type = Char;
using size_type = std::size_t;
using iterator = typename Storage::iterator;
using const_iterator = Storage::const_iterator;
mystring() : storage_{} {}
mystring(mystring&&) = default;
mystring(mystring const&) = default;
mystring(Storage const& storage) : storage_{storage} {}
mystring(Char const* ptr, size_type size) : storage_{} {
resize(size);
std::copy(ptr, ptr + size, begin());
}
static constexpr size_type npos = static_cast<size_type>(-1);
mystring& operator=(mystring const&) = default;
mystring& operator=(mystring&&) = default;
void swap(mystring& str) { storage_.swap(str.storage_); }
Char operator[](size_type i) const { return *(storage_.begin() + i); }
Char& operator[](size_type i) { return *(storage_.begin() + i); }
void resize(size_type size, Char value = Char()) {
storage_.resize(size, value);
}
void reserve(size_type size) { storage_.reserve(size); }
size_type size() const noexcept { return storage_.end() - storage_.begin(); }
size_type max_size() const noexcept { return storage_.max_size(); }
bool empty() const noexcept { return size() == 0; }
void clear() { resize(0); }
void push_back(Char c) { resize(size() + 1, c); }
Char const* data() const { return storage_.c_str(); }
Char const* c_str() const { return storage_.c_str(); }
iterator begin() { return storage_.begin(); }
const_iterator begin() const { return storage_.begin(); }
const_iterator cbegin() const { return storage_.begin(); }
iterator end() { return storage_.end(); }
const_iterator end() const { return storage_.end(); }
const_iterator cend() const { return storage_.end(); }
size_type find(mystring const& s, size_type pos = 0) const {
pos = std::min(pos, size());
auto result{ std::search(begin() + pos, end(),
s.begin(), s.end(), Traits::eq) };
if (result == end())
return npos;
else
return static_cast<size_type>(result - begin());
}
private:
Storage storage_;
};
template<class Char, class Storage1, class Storage2, class Traits>
bool operator <(mystring<Char, Storage1, Traits> const& a,
mystring<Char, Storage2, Traits> const& b)
{
return std::lexicographical_compare(
a.begin(), a.end(), b.begin(), b.end(), Traits::lt
);
template<class Char, class Storage1, class Storage2, class Traits>
bool operator ==(mystring<Char, Storage1, Traits> const& a,
mystring<Char, Storage2, Traits> const& b)
{
return std::equal(a.begin(), a.end(), b.begin(), b.end(), Traits::eq);
}
Listing 70-4.The mystring Class Template
The mystring class
relies on Traits for comparing characters and Storage for storing them. The Storage policy must provide iterators for accessing the characters themselves and a few basic member functions (data, max_size, reserve, resize, swap), and the mystring class provides the public interface, such as the assignment operator and search member functions.
Public comparison functions use standard algorithms and Traits for comparisons. Notice how the comparison functions require their two operands to have the same Traits (otherwise, how could the strings be compared in a meaningful way?) but allow different Storage. It doesn’t matter how the strings store their contents if you want to know only whether two strings contain the same characters.
The next step is to write some storage policy templates. The storage policy is parameterized on the character type. The simplest
Storage is
vector_storage, which stores the string contents in a
vector. Recall from Exploration
21 that a C character string ends with a null character. The
c_str() member function returns a pointer to a C-style character array. In order to simplify the implementation of
c_str, the vector stores a trailing null character after the string contents. Listing
70-5 shows part of an implementation of
vector_storage. You can complete the implementation on your own.
template<class Char>
class vector_storage {
public:
using size_type = std::size_t;
using value_type = Char;
using iterator = std::vector<Char>::iterator;
using const_iterator = std::vector<Char>::const_iterator;
vector_storage() : string_{1, Char{}} {}
void swap(vector_storage& storage) { string_.swap(storage.string_); }
size_type max_size() const { return string_.max_size() - 1; }
void reserve(size_type size) { string_.reserve(size + 1); }
void resize(size_type newsize, value_type value) {
// if the string grows, overwrite the null character, then resize
if (newsize >= string_.size()) {
string_[string_.size() - 1] = value;
string_.resize(newsize + 1, value);
}
else
string_.resize(newsize + 1);
string_[string_.size() - 1] = Char{};
}
Char const* c_str() const { return &string_[0]; }
iterator begin() { return string_.begin(); }
const_iterator begin() const { return string_.begin(); }
// Skip over the trailing null character at the end of the vector
iterator end() { return string_.end() - 1; }
const_iterator end() const { return string_.end() - 1; }
private:
std::vector<Char> string_;
};
Listing 70-5.The vector_storage Class Template
The only difficulty in writing vector_storage is that the vector stores a trailing null character, so the c_str function can return a valid C-style character array. Therefore, the end function has to adjust the iterator that it returns.
Another possibility for a storage policy is
array_storage, which is just like
vector_storage, except it uses an
array. By using an array, all storage is local. The array size is the maximum capacity of the string, but the string size can vary up to that maximum.
Write array_storage. Compare your result with mine in Listing
70-6.
import <algorithm>;
import <stdexcept>;
import <array>;
template<class Char, std::size_t MaxSize>
class array_storage {
public:
using array_type = std::array<Char, MaxSize>;
using size_type = std::size_t;
using value_type = Char;
using iterator = array_type::iterator;
using const_iterator = array_type::const_iterator;
array_storage() : size_(0), string_() { string_[0] = Char(); }
void swap(array_storage& storage) {
string_.swap(storage.string_);
std::swap(size_, storage.size_);
}
size_type max_size() const { return string_.max_size() - 1; }
void reserve(size_type size) {
if (size > max_size()) throw std::length_error("reserve");
}
void resize(size_type newsize, value_type value) {
if (newsize > max_size())
throw std::length_error("resize");
if (newsize > size_)
std::fill(begin() + size_, begin() + newsize, value);
size_ = newsize;
string_[size_] = Char{};
}
Char const* c_str() const { return &string_[0]; }
iterator begin() { return string_.begin(); }
const_iterator begin() const { return string_.begin(); }
iterator end() { return begin() + size_; }
const_iterator end() const { return begin() + size_; }
private:
size_type size_;
array_type string_;
};
Listing 70-6.The array_storage Class Template
One difficulty when writing new
string classes is that you must write new I/O functions too. Unfortunately, this takes a fair bit of work and a solid understanding of the stream class templates and stream buffers. Handling padding and field adjustment is easy, but there are subtleties to the I/O streams that I have not covered, such as integration with C stdio, tying input and output streams so that prompts appear before the user is asked for input, and so on. So just copy my solution in Listing
70-7 into the
mystring module
.
template<class Char, class Storage, class Traits>
std::basic_ostream<Char, Traits>&
operator<<(std::basic_ostream<Char, Traits>& stream,
mystring<Char, Storage, Traits> const& string)
{
typename std::basic_ostream<Char, Traits>::sentry sentry{stream};
if (sentry)
{
bool needs_fill{stream.width() != 0 and string.size() > std::size_t(stream.width())};
bool is_left_adjust{
(stream.flags() & std::ios_base::adjustfield) == std::ios_base::left };
if (needs_fill and not is_left_adjust)
{
for (std::size_t i{stream.width() - string.size()}; i != 0; --i)
stream.rdbuf()->sputc(stream.fill());
}
stream.rdbuf()->sputn(string.data(), string.size());
if (needs_fill and is_left_adjust)
{
for (std::size_t i{stream.width() - string.size()}; i != 0; --i)
stream.rdbuf()->sputc(stream.fill());
}
}
stream.width(0);
return stream;
}
Listing 70-7.Output Function for mystring
The sentry class manages some bookkeeping on behalf of the stream. The output function handles padding and adjustment. If you are curious about the details, consult a good reference.
The input function also has a
sentry class, which skips leading white space on your behalf. The input function has to read characters until it gets to another white space character or the string fills or the width limit is reached. See Listing
70-8 for my version.
template<class Char, class Storage, class Traits>
std::basic_istream<Char, Traits>&
operator>>(std::basic_istream<Char, Traits>& stream,
mystring<Char, Storage, Traits>& string)
{
typename std::basic_istream<Char, Traits>::sentry sentry{stream};
if (sentry)
{
std::ctype<Char> const& ctype(
std::use_facet<std::ctype<Char>>(stream.getloc()) );
std::ios_base::iostate state{ std::ios_base::goodbit };
std::size_t max_chars{ string.max_size() };
if (stream.width() != 0 and std::size_t(stream.width()) < max_chars)
max_chars = stream.width();
string.clear();
while (max_chars-- != 0) {
typename Traits::int_type c{ stream.rdbuf()->sgetc() };
if (Traits::eq_int_type(Traits::eof(), c)) {
state |= std::ios_base::eofbit;
break; // is_eof
}
else if (ctype.is(ctype.space, Traits::to_char_type(c)))
break;
else {
string.push_back(Traits::to_char_type(c));
stream.rdbuf()->sbumpc();
}
}
if (string.empty())
state |= std::ios_base::failbit;
stream.setstate(state);
stream.width(0);
}
return stream;
}
Listing 70-8.Input Function for mystring
The break statement
exits a loop immediately. You are probably familiar with this statement or something similar. Experienced programmers may be surprised that no example has required this statement until now. One reason is that I gloss over error-handling, which would otherwise be a common reason to break out of a loop. In this case, when the input reaches end-of-file or white space, it is time to exit the loop. The partner to break is continue, which immediately reiterates the loop. In a for loop, continue evaluates the iterate part of the loop header and then the condition. I have rarely needed to use continue in real life and could not think of any reasonable example that uses continue, but I mention it only for the sake of completeness.
As you know, the compiler finds your I/O operators by matching the type of the right-hand operand, mystring, with the type of the function parameter. In this simple case, you can easily see how the compiler performs the matching and finds the right function. Throw some namespaces into the mix, and add some type conversions, and everything gets a little bit more muddled. The next Exploration delves more closely into namespaces and the rules that the C++ compiler applies in order to find your overloaded function names (or not find them and, therefore, how to fix that problem).
