算法的实现需要一个通用的 I/O 接口。您需要决定函数获取数据和写入结果的方式和位置，以及如何和保留哪些中间结果。迭代器是帮助解决这个问题的现有抽象。
一个迭代器 是一个小的数据类型，它提供了一个数据集的顺序视图。简单地说，它是一个实现指针可以执行的操作子集的类。
迭代器 的重要性在于它们将函数与实际的数据存储解耦。一个算法通过几个迭代器读取它的输入...end ),并经常将其输出写入另一个范围:
template <typename iterator_t>
... sort(iterator_t begin, iterator_t end);
template <typename iter1_t, typename iter2_t >
... copy(iter1_t input_begin, iter1_t input_end, iter2_t output_begin);可以根据算法的 I/O 接口对它们进行粗略的分类。非变异算法迭代一个或多个只读范围。有两个子系列:
- “find”算法返回一个指向结果(比如 std::min_element)的迭代器，如果没有结果，则返回 end。
- “累加”算法返回一个任意值，该值不需要对应于范围内的任何元素。
选择性复制算法 取一个输入只读范围和一个输出范围，结果写入其中。输出范围被认为是可写的。如果输出范围可以存储任意数量的元素或者简单地存储与输入范围一样多的元素，那么只给出最左边的位置(比如 std::copy)。
- 通常每个算法都描述了如果输入和输出范围重叠会发生什么。“变换”算法接受与 begin 不相交或完全重合的输出范围...结束。
重新排序算法 对输入范围的元素进行混洗，并确保结果将在某个特殊的位置，或者等价地，结果将是某个特定的子范围(例如 std::nth_element 和 std::partition)。
- “收缩”算法(std::remove_if)在 begin 中重新排列数据...end，如果结果比输入序列短，则返回新的 end1，在 end1 范围内留下未指定的元素..结束。
根据迭代器编写算法可以提供显著的优势:
- 所有的容器，标准的和非标准的，都可以很容易地提供迭代器，所以这是一种解耦算法和数据存储的方法。
- 迭代器有一个默认的和方便的方式来表示“失败”，即返回 end。
- 根据算法的细节，忽略迭代器下实际的“指向类型”可能是可行的。
另一方面，有两个困难:
-
迭代器是数据集的视图。您经常需要修改一个给定的视图来匹配另一个算法所期望的。例如，您编写了一个函数，它获取一个 pair 序列作为输入，但是在内部您可能需要调用一个需要 x 序列的例程。
-
应该尽可能避免迭代器的确切类型。假设 v 是一个容器的 const-reference，比较下面两种遍历所有元素的方法(姑且非正式地说两个“循环”)。
for (vector<string>::const_iterator i = v.begin(); i != v.end(); ++i) { ... } std::for_each(v.begin(), v.end(), ...);
第一个“循环”不太通用，也更详细。它与您正在使用的容器(即 vector )紧密相关。如果你替换了数据结构，这段代码就不能再编译了。此外，它会在每次迭代中重新计算一次 v.end()。1T4】
第二个循环也有它的缺点。您必须传递一个函数对象作为“循环体”，这可能不太方便。
6.1.算法输入/输出
算法通常是通过通用范围执行输入/输出操作的函数。在这种情况下，一个范围由一对泛型类型 iterator_t 的迭代器表示，函数假设 iterator_t 支持所有需要的操作。然而，你会看到，这种假设不仅是一种方便的简化，而且通常是最好的，因为如果一个泛型类型 T 是迭代器，那么很难检测出。
这些假设是:
- *i 返回 STD::iterator _ traits::reference，其行为类似于对底层对象的引用。 2
- 无论*i 返回什么，指向值的副本都可以存储为 STD::iterator _ traits:::value _ type；通常，您会进一步强调这种类型是可分配的或可交换的。3T4】
- 对 I 的任何基本操作(复制、解引用、递增等等)都是廉价的。
- 可以使用 STD::iterator _ traits::iterator _ category 作为类型标签，为不同类型的迭代器分派专门的算法。
- 所有在 I 上有效的递增/递减操作符都返回一个可取消引用的对象(通常是 T 的另一个实例)。这使您可以安全地编写*(i++)。
有时你会隐含地假设同一个迭代器的两个副本是独立的。这通常会被 I/O 相关的迭代器所违背，比如读/写文件或内存的对象，像 std::back_insert_iterator，因为*i 在概念上为一个新对象分配空间；它不检索该范围的现有元素。
6.1.1.基于交换还是基于拷贝
作为基本假设的结果，算法中的大多数(如果不是全部)I/O 应该在没有显式声明类型的情况下编写。如果可能的话，应该尽量少用引用和值类型，通常是通过交换和直接取消引用和赋值。
例如，copy 解决了输出问题。它只是询问一个有效的迭代器，结果写在哪里:
template <typename iter1_t, typename iter2_t>
iter2_t copy(iter1_t begin, iter1_t end, iter2_t output)
{
while (begin != end)
*(output++) = *(begin++); // dereference-and-assign
return output;
}在不知道元素是什么的情况下，您可以假设交换操作没有普通的赋值操作繁重。POD 交换执行三个赋值，所以稍微差一点，但是如果对象包含资源句柄(比如指向堆分配的内存的指针)，交换通常被优化以避免临时对象的构造(这可能会失败或抛出)。如果 s1 是一个短字符串，s2 是一个很长的字符串，那么赋值 s1=s2 将需要大量的内存，而 swap(s1，s2)则不需要任何开销。
例如，std::remove_if 的实现可以用 smart_swap 覆盖不合适的元素。
move 是一个破坏性的复制过程，其中原始值保持一致，但调用者不知道。
template <typename iterator_t>
void move_iter(iterator_t dest, iterator_t source)
{
if (dest == source)
return;
if (is_class<std::iterator_traits<iterator_t>::value_type>::value)
smart_swap(*dest, *source);
else
*dest = *source;
}
template <typename iterator_t, typename func_t>
iterator_t remove_if(iterator_t begin, iterator_t end, func_t F)
{
iterator_t i = begin;
while (true)
{
while (i != end && F(*i))
++i;
if (i == end)
break;
move_iter(begin++, i++);
}
return begin;
}该算法返回新的范围终点。它将使用赋值来“移动”一个基本类型，使用交换来“移动”一个类。由于决策规则是隐藏的， 4 因此，该算法将在新旧范围端点之间留下不可预测的对象:
struct less_than_3_digits
{
bool operator()(const std::string& x) const
{
return x.size()<3;
}
bool operator()(const int x) const
{
return x <= 99;
}
};
std::string A1[] = { "111", "2", "3", "4444", "555555", "66" };
int A2[] = { 111 , 2 , 3 , 4444 , 555555 , 66 };
remove_if(A1, A1+6, less_than_3_digits());
remove_if(A2, A2+6, less_than_3_digits());执行这段代码后，数组 A1 和 A2 将会不同。尾随范围由未指定的对象填充，并且它们确实不同。
| [0] | One hundred and eleven | "111" | | [1] | Four thousand four hundred and forty-four | "4444" | | [2] | Five hundred and fifty-five thousand five hundred and fifty-five | "555555" | | [3] | Four thousand four hundred and forty-four | "2" | | [4] | Five hundred and fifty-five thousand five hundred and fifty-five | "3" | | [5] | Sixty-six | "66" |
注意 C++0x 有一个移动语义的语言构造:R 值引用。
声明为对 T 的 R 值引用(写为 T&&)的函数参数将绑定到非常数临时对象。由于是临时的，该函数可以自由地从中窃取资源。特别是，您可以编写一个特殊的“移动构造函数”，从一个临时对象初始化一个新的实例。
此外，将引用转换为 R 值引用具有将现有对象标记为“可移动”的效果(这种转换封装在 STL 函数 std::move 中)。
结合这些功能，三拷贝交换可以重写为:
void swap(T& a, T& b)
{
T x(std::move(a));
a = std::move(b);
b = std::move(x);
}所以如果 T 实现了一个 move 构造函数，这个函数的复杂度和原生交换一样。
move_iter 的其他实现可以:
- 测试是否(！has _ trivial _ destructor<...>::value)。值得交换一个拥有资源的类，这样的类应该有一个不平凡的析构函数。但是，请注意，如果类型不是可交换的，这种方法可能会慢一些，因为它最终会调用三个副本的交换，而不是一个赋值。
- 测试交换成员函数的存在，并在任何其他情况下使用赋值。
template <typename iterator_t>
void move_iter(iterator_t dest, iterator_t source, selector<true>)
{
dest->swap(*source);
}
template <typename iterator_t>
void move_iter(iterator_t dest, iterator_t source, selector<false>)
{
*dest = *source;
}
template <typename iterator_t>
void move_iter(iterator_t dest, iterator_t source)
{
typedef typename std::iterator_traits<iterator_t>::value_type val_t;
if (dest != source)
move_iter(dest, source, has_swap<val_t>());
}6.1.2.算法分类
回想一下非变异、选择性复制和重新排序算法之间的区别。本节展示了有时即使算法的数学细节很清楚，几种实现也是可能的，并讨论了每种实现的副作用。
假设您想同时找到一个范围的最小值和最大值。如果范围有 N 个元素，一个简单的算法使用大约 2N 次比较，但是有可能做得更好。迭代时，您可以一次检查两个连续的元素，然后将较大的元素与最大值进行比较，将较小的元素与最小值进行比较，因此每两个元素使用三次比较，或者总共大约 1.5*N 次比较。
首先考虑一个非变异函数(宏只是为了简洁) 5 :
#define VALUE_T typename std::iterator_traits<iterator_t>::value_type
template <typename iterator_t, typename less_t>
std::pair<VALUE_T, VALUE_T> minmax(iterator_t b, iterator_t e, less_t less)minmax(begin，end)从头到尾扫描范围一次，不改变任何元素，它返回一对(min，max)。如果范围为空，您可以返回默认构造的对，或者使用 std::numeric_limits 打破 result.first < result.second 的假设。
下面是一个合理的实现，它只需要前向迭代器:
template <typename scalar_t, typename less_t>
inline scalar_t& mmax(scalar_t& a, const scalar_t& b, less_t less)
{
return (less(a, b) ? a=b : a);
}
template <typename scalar_t, typename less_t>
inline scalar_t& mmin(scalar_t& a, const scalar_t& b, less_t less)
{
return (less(b, a) ? a=b : a);
}
template <typename iterator_t, typename less_t>
std::pair<...> minmax(iterator_t begin, const iterator_t end,
less_t less)
{
typedef
typename std::iterator_traits<iterator_t>::value_type value_type;
std::pair<value_type, value_type> p;
if (begin != end)
{
p.first = p.second = *(begin++);
}
while (begin != end)
{
const value_type& x0 = *(begin++);
const value_type& x1 = (begin != end) ? *(begin++) : x0;
if (less(x0, x1))
{
mmax(p.second, x1, less);
mmin(p.first , x0, less);
}
else
{
mmax(p.second, x0, less);
mmin(p.first , x1, less);
}
}
return p;
}通常，返回迭代器更有价值，原因有二。首先，复制对象的成本可能很高，其次，如果没有答案，则返回 end。
因此，考虑到解引用迭代器的开销不大，一种可能的改进是:
template <typen.ator_t, typename less_t>
std::pair<iterator_t, iterator_t> minmax(...)
{
std::pair<iterator_t, iterator_t> p(end, end);
if (begin != end)
{
p.first = p.second = begin++;
}
while (begin != end)
{
iterator_t i0 = (begin++);
iterator_t i1 = (begin != end) ? (begin++) : i0;
if (less(*i1, *i0))
swap(i0, i1);
// here *i0 is less than *i1
if (less(*i0, *p.first))
p.first = i0;
if (less(*p.second, *i1))
p.second = i1;
}
return p;
}请注意，您再也没有提到 value_type。
最后，您可以概述重新排序的变体:
template <typename iterator_t>
void minmax(iterator_t begin, iterator_t end);该函数对范围重新排序，以便在执行后，begin 是最小值，(end-1)是最大值。所有其他元素将被移动到未指定的位置。迭代器是双向的，所以 end-1 只是一种形式符号。
假设 F 取一个范围[begin...结束)。它比较第一个和最后一个元素，如果它们没有按顺序排列，就交换它们，然后继续处理第二个和倒数第二个元素。当迭代器交叉时，它停止并返回一个迭代器 H，指向范围的中间。f 执行大约 N/2 次“比较和交换”操作，其中 N 是范围的长度。
显然，最大值不能属于左半部分，最小值不能属于右半部分。你必须在两个半区间上再次调用 F，让 HL=F(begin，HL)和 HR=F(HR，end)。
当一个区间中只有一个元素时，它一定是极值。
如果一个复杂性单元是一个“比较和交换”，则该算法在迭代 0 时执行 N/2 以找到 H，对第二个分区执行 2 (N/4 ),对第三个分区执行 2 (N/8 ),依此类推，因此操作的总数也是大约 3/2 N
图 6-1。重新排序最小最大算法的图形表示
6.1.3.迭代器需求
算法对迭代器必须提供的操作类型有要求。根据经验，“平均”迭代器是双向的。 6 支持单增单减(+和-)、等式/不等式(==和！=).然而，它不提供任意整数、差和运算符<的加法。随机访问迭代器用在需要最高速度的地方，用于排序，所以它们通常需要特殊算法的特殊处理。
如前所述，您可以通过分派给另一个接受“迭代器类别”类型的附加形式参数的函数来确保满足迭代器的要求:
template <typename iter_t>
void do_something(iter_t begin, iter_t end)
{
return do_something(begin, end,
typename std::iterator_traits<iter_t>::iterator_category());
}
template <typename iter_t>
void do_something(iter_t begin, iter_t end, std::bidirectional_iterator_tag)
{
// do the work here
}发明这种技术是为了调用任何迭代器类型的算法的优化版本，但是它也可以用来限制调用。标准迭代器标签形成了一个类层次结构，因此一个“强”标签可以很好地转换为“弱”需求。
以下是一些指导原则:
- 有时你会先写一个算法，然后再推导出算法运行需要哪个迭代器。虽然后验推理是完全可以接受的，但人们很容易低估子程序的要求。
- 将具有不同需求的算法分开通常是好的设计。比如不要先排序再迭代，只规定范围应该已经排序了。这可能会降低对双向迭代器的要求。
template <typename iterator_t>
void do_something(iterator_t begin, iterator_t end)
{
// the following line has stronger requirements than all the rest
std::sort(begin, end, std::greater<...>());
std::for_each(begin, end, ...);
}
template <typename iterator_t>
void do_something_on_sorted_range(iterator_t begin, iterator_t end)
{
// much better: all lines have the same complexity
std::reverse(begin, end);
std::for_each(begin, end, ...);
}6.1.4.一个例子:集合分区
假设给你一组整数 X，你需要把它分成两个子集，使得每个子集的和大致相同。 7
对于这个问题，快速找到可接受的分区(可能是次优的)的启发式算法是已知的。最简单的是贪婪算法，它规定:
Let P1={} and P2={} be empty sets;
While X is not empty, repeat:
{
Assign the largest remaining integer in X to the set Pi which currently has the lower sum
(break ties arbitrarily);
}这个处方听起来像是重新排序，所以你可以考虑一个变异算法。您对输入范围重新排序并返回一个迭代器 h，这样[begin，h]和[h，end 就是所需的分区。另外，作为一个额外的奖励，您可以计算两个分区之和的差
，这是要最小化的目标。因此，结果将是 std::pair <迭代器，value_type >。
该实现的行为如下:
- 该范围被分成三个逻辑块:左边的分区 A [begin，end _ of _ A]，右边的分区 B[begin _ of _ B，end]，以及剩余的中间块 m。
- a 和 B 最初是空的，M = [begin，end。
- 当 M 不为空时，重复:
- M 的元素按降序排序。
- 迭代 m 的元素。分配给 A 的对象被交换到 A 的右边(在位置“A 的结尾”)，分配给 B 的对象被交换到 B 的左边(在位置“B 的开头减 1”)。 8
这段代码是变异算法的简明示例:
- 它不分配临时内存
- 它的运行时复杂性是有文档记录的
#define mxt_value_type(T) typename std::iterator_traits<T>::value_type
template <typename iterator_t>
std::pair<iterator_t, mxt_value_type(iterator_t)>
equal_partition (iterator_t begin, iterator_t end)
{
typedef mxt_value_type(iterator_t)> scalar_t;
scalar_t sum_a = 0;
scalar_t sum_b = 0;
iterator_t end_of_A = begin;
iterator_t beg_of_B = end;
while (end_of_A != beg_of_B)
{
std::sort(end_of_A, beg_of_B, std::greater<scalar_t>());
iterator_t i = end_of_A;
do
{
if (sum_b < sum_a)
{
sum_a = sum_a - sum_b;
sum_b = *i;
smart_swap(*i, *(--beg_of_B));
}
else
{
sum_b = sum_b - sum_a;
sum_a = *i;
smart_swap(*i, *(end_of_A++));
}
}
while ((i != beg_of_B) && (++i != beg_of_B));
}
return std::make_pair(end_of_A,
sum_a<sum_b ? sum_b-sum_a : sum_a-sum_b);
}让我们检查一下实现，以确定对迭代器和类型的要求。
- 乍一看，它可能看起来像一个双向 iterator_t 就足够了，因为代码只使用了复制构造、不等式、++、和-。但是，std::sort 需要随机访问迭代器。 9
- 底层的 scalar_t 需要实现运算符
sum_b = sum_b - sum_a;
sum_b -= sum_a;第二个选项将引入一个新的需求(即操作符-=)。
6.1.5.识别迭代器
如果 T 是迭代器或指针，元函数 STD::iterator _ traits将返回几个类型(在这种情况下，类型被简单地推导出来)。这也是确保 T 是迭代器的最可靠的方法，因为对于大多数其他类型，它不会编译:
template
<
typename T,
typename IS_ITERATOR = std::iterator_traits<T>::value_type
>
class require_iterator
{
// similar to a static assertion,
// this will compile only if T is a compliant iterator
};您可以通过使用迭代器需要提供的五个基本类型定义来猜测一个类型是否是符合迭代器。 10
再次使用 SFINAE 技巧 11 ，您将编写:
template <typename T>
struct is_iterator
{
static const bool value =
static_AND
<
has_type_value_type<T>,
static_AND
<
has_type_reference<T>,
static_AND
<
has_type_pointer<T>,
static_AND
<
has_type_iterator_category<T>,
has_type_difference_type<T>
>
>
>
>::value;
};
template <typename T>
struct is_iterator<T*>
{
static const bool value = true;
};启发式的理由如下:
- std::map 不是迭代器，但是它定义了除 iterator_category 之外的所有类型。因此，您确实需要测试这五种类型是否都存在。
- 您无法测试 std::iterator_traits 是否定义良好，因为如果 T 无效，它将无法编译。
- 存在 is_iterator 为真的类型，但它们甚至不是可取消引用的(很简单，假设 T 是 std::iterator_traits )。
这里有一个测试，可以很精确地识别非常数迭代器。 12
主要动机如下:
- 迭代器会定义一个值类型 T 和一个引用类型，通常是 T&或者 const T&。
- T&可以转换成 T，但不能反过来
- const T&和 T 是可以相互转换的。 十三
有几种可能的情况:
- 如果 T 不是迭代器，它甚至不是可变迭代器(这由最后一个部分专门化处理)。
- 如果 reference 是 value_type&那么答案为真(这种情况由 helper 类处理)。
- 如果 reference 可以转换为 value_type，但不能反过来，那么答案也是正确的。
template <typename T1, typename T2>
struct is_mutable_iterator_helper
{
static const bool value = false;
};
template <typename T>
struct is_mutable_iterator_helper<T&, T>
{
static const bool value = true;
};
template <typename T, bool IS_ITERATOR = is_iterator<T>::value>
class is_mutable_iterator
{
typedef typename std::iterator_traits<T>::value_type val_t;
typedef typename std::iterator_traits<T>::reference ref_t;
public:
static const bool value =
static_OR
<
is_mutable_iterator_helper<ref_t, val_t>,
selector
<
has_conversion<ref_t, val_t>::L2R &&
!has_conversion<val_t, ref_t>::L2R
>
>::value;
};
template <typename T>
class is_mutable_iterator<T, false>
{
public:
static const bool value = false;
};- Has_conversion <ref_t val_t="">:根据值类型的定义，L2R 应该为 true。</ref_t>
- 您将静态 bool 包装在选择器中，因为 static_OR 需要两种类型，而不是常量。
一些迭代器被认为是有序集合上的视图，例如，set ::iterator。你能发现他们吗？
事实上，这个问题是病态的:set ::迭代器是一个依赖类型，在 C++ 中，对于给定的迭代器，没有“反向匹配”来推导 T。 14
template <typename T>
void wrong(std::set<T>::iterator i) // error: T is non-deducible
{
}但是，如果将选项限制在一些特殊的候选人身上，就可以让问题变得简单一些。事实上，一个集合被声明为 set ，但是在某些情况下你可能会猜测 L 和 a。
下面的代码给出了一个实际的例子:
template <typename T, typename less_t, typename alloc_t = std::allocator<T> >
class sorted_vector
{
std::vector<T, alloc_t> data_;
less_t less_;
public:
template <typename iterator_t>
sorted_vector(iterator_t begin, iterator_t end, less_t less = less_t())
: data_(begin, end), less_(less)
{
// this is unnecessary if begin...end is already sorted
std::sort(data_.begin(), data_.end(), less_);
}
};由于底层排序算法即使在范围已经排序的情况下也会消耗 CPU，所以尝试猜测是否可以避免这一步。 15
有两种不同的测试。首先，一些迭代器保证它们指向的范围是有序的(这是一个“静态测试”，因为它只取决于迭代器的类型)；第二，任何迭代器对都可能恰好指向一个排序范围(这是一个“运行时测试”)。您可以按以下顺序组合静态测试和运行时测试:
if (!is_sorted_iterator<iterator_t, less_t>::value)
{
if (!is_sorted(begin, end, less_)
std::sort(begin, end, less_);
}一个非常重要的观察是，is_sorted_iterator <iterator_t less_t="">被允许返回假阴性而不是假阳性。您可以容忍不必要的排序，但是不能让未排序的范围通过。</iterator_t>
注意测试一个范围是否已经排序需要线性时间。
在 C++0x 中，有一个专用的算法:
template <typename FwdIter>
bool is_sorted(FwdIter begin, FwdIter end);
template <typename FwdIter, typename less_t>
bool is_sorted(FwdIter begin, FwdIter end, less_t LESS);在经典的 C++ 中，后一个函数的实现非常简洁:
using std::adjacent_find;
using std::reverse_iterator;
return
adjacent_find(reverse_iterator<FwdIter>(end), reverse_iterator<FwdIter>(begin), LESS)
== reverse_iterator<FwdIter>(begin);is_sorted_iterator <iterator_t less_t="">可以简单地尝试将 iterator_t 与一些特殊的标准迭代器进行匹配:</iterator_t>
#define ITER(C,T1) typename std::C<T1,less_t>::iterator
#define CONST_ITER(C,T1) typename std::C<T1,less_t>::const_iterator
template
<
typename iter_t,
typename less_t,
typename value_t = typename std::iterator_traits<iter_t>::value_type
>
struct is_sorted_iterator
{
static const bool value =
static_OR
<
static_OR
<
typeequal<iter_t, ITER(set, value_t)>,
typeequal<iter_t, CONST_ITER(set, value_t)>
>,
static_OR
<
typeequal<iter_t, ITER(multiset, value_t)>,
typeequal<iter_t, CONST_ITER(multiset, value_t)>
>
>::value;
};地图有部分专门化:
#define ITER(C,T1,T2) typename std::C<T1,T2,less_t>::iterator
#define CONST_ITER(C,T1,T2) typename std::C<T1,T2,less_t>::const_iterator
template
<
typename iter_t,
typename less_t,
typename T1,
typename T2
>
struct is_sorted_iterator< iter_t, less_t, std::pair<const T1, T2> >
{
static const bool value =
static_OR
<
static_OR
<
static_OR
<
typeequal<iter_t, ITER(map,T1,T2)>,
typeequal<iter_t, CONST_ITER(map,T1,T2)>
>,
static_OR
<
typeequal<iter_t, ITER(multimap,T1,T2)>,
typeequal<iter_t, CONST_ITER(multimap,T1,T2)>
>
>,
static_OR
<
static_OR
<
typeequal<iter_t, ITER(map,const T1,T2)>,
typeequal<iter_t, CONST_ITER(map,const T1,T2)>
>,
static_OR
<
typeequal<iter_t, ITER(multimap,const T1,T2)>,
typeequal<iter_t, CONST_ITER(multimap,const T1,T2)>
>
>
>::value;
};6.1.6.通过迭代器值类型选择
采用迭代器的函数可能想要调用另一个模板，用迭代器值类型标记调用。特别是，这允许一些变异算法处理异常，比如具有常量引用的可变迭代器(例如 std::map)。
template <typename iterator_t>
iterator_t F(iterator_t b, iterator_t e)
{
typedef typename std::iterator_traits<iterator_t>::value_type value_type;
return F(b, e, instance_of<value_type>());
}
template <typename iterator_t, typename T1, typename T2>
iterator_t F(iterator_t b, iterator_t e, instance_of< std::pair<const T1, T2> >)
{
// modify only i->second
}
template <typename iterator_t, typename T>
iterator_t F(iterator_t b, iterator_t e, instance_of<T>)
{
// modify *i
}选择性复制算法可以使用输出迭代器值类型来决定返回什么。假设计算产生一系列值和相应的权重；如果输出类型是一对，转储将同时写入两者；否则，它只写入值:
template <[...], typename iterator_t>
void do_it([...], iterator_t out_begin, iterator_t out_end)
{
typedef typename
std::iterator_traits<iterator_t>::value_type value_type;
// ...
dump([...], out_begin, out_end, instance_of<value_type>());
}
private:
template <[...], typename iterator_t, typename T1, typename T2>
void dump([...], iterator_t b, iterator_t e, instance_of< std::pair<T1, T2> >)
{
for (i=b; i!=e; ++i)
// write value in b->first and weight in b->second
}
template <typename iterator_t, typename T>
void dump([...], iterator_t b, iterator_t e, instance_of<T>)
{
for (i=b; i!=e; ++i)
// write value in *b
}注意，可以使用访问器来统一实现。详情见下一节。
6.2.一般化
本节讨论使用不同的 I/O 接口编写函数的替代方法。由于迭代器提供了数据视图，它们可能不够灵活，尤其是对于具有特殊语义的算法。
一些计算可以用属性来描述，例如“找到价格最小的对象”。当然，你需要迭代器来扫描对象，但是如何读取价格呢？
6.2.1.属性和访问器
接受迭代器的算法可能不使用指向类型的实际接口。通常，它们有两个版本，一个版本中所需的操作由指向的类型直接处理，另一个版本采用一个完全取代对象接口的额外函子。
例如，std::sort(b，e)假设所指向的类型小于可比类型，它使用指针的运算符
作为这个概念的概括，算法可以根据属性来定义。
属性一般化数据成员:(只读)属性只是单个(常量)参数的非空函数，默认情况下，它调用参数的常量成员函数或返回参数的数据成员的副本。这里有一个小例子。
template <typename T>
struct property_size
{
typedef size_t value_type;
value_type operator()(const T& x) const
{
return x.size();
}
};传递给算法的 property_size 实例被称为属性的访问器。
许多计算算法可以用性质来定义。他们忽略尖型，但需要读“其大小”；因此，它们需要合适的访问器。
根据假设，应用访问器并不昂贵。
注意一个属性是一个仿函数，因此正确的 typedef 应该是 result_type，但是用户需要存储一个属性值的副本，这个副本在概念上位于对象中，只被仿函数“访问”。因此，value_type 是首选。
一个读写属性有一个额外的成员写回一个值:
template <typename T>
struct property_size
{
typedef size_t value_type;
value_type operator()(const T& x) const
{
return x.size();
}
value_type operator()(T& x, const value_type v) const
{
x.resize(v);
return x.size();
}
};访问器在不同的上下文中很有用。在最简单的情况下，它们保存对 std::transform 或自定义二元运算符的调用。
假设您有一个 std::string 范围，需要找到总大小和最大大小。使用经典的 STL，你可以写一个自定义的“sum”和一个自定义的“less”。从字符串到整数(大小)的转换是在这些函子内部执行的。
struct sum_size
{
size_t operator()(size_t n, const std::string& s) const
{
return n + s.size();
}
};
struct less_by_size
{
bool operator()(const std::string& s1, const std::string& s2) const
{
return s1.size() < s2.size();
}
};
// assume beg!=end
size_t tot = std::accumulate(beg, end, 0U, sum_size());
size_t max = std::max_element(beg, end, less_by_size())->size();使用访问器，您将有更多的代码重用:
#define VALUE typename accessor_t::value_type
template <typename iterator_t, typename accessor_t>
VALUE accumulate(iterator_t b, iterator_t e, accessor_t A, VALUE init = 0)
{
while (b != e)
init = init + A(*b++);
return init;
}
template <typename iterator_t, typename accessor_t>
iterator_t max_element(iterator_t b, iterator_t e, accessor_t A)
{
if (b == e)
return e;
iterator_t result = b;
while ((++b) != e)
{
if (A(*result) < A(*b))
result = b;
}
return result;
}
size_t tot = accumulate(beg, end, property_size<std::string>());
size_t max = max_element(beg, end, property_size<std::string>());默认访问器返回对象本身:
template <typename T>
struct default_accessor
{
typedef T value_type;
T& operator()(T& x) const
{
return x;
}
};在一次需要几个“命名属性”的复杂计算算法中，访问器提供了很好的抽象度。我们举背包问题作为例子。
每个对象都有两个属性:一个(非负)价格和一个(非负)质量。给你一笔初始的钱，你的目标是购买具有最高质量的物品子集。在计算结束时，(部分)结果是原始范围的子集，因此您选择一种重新排序算法。您返回一个划分范围的迭代器，与算法的一个额外的副产品配对——在本例中是总质量。
访问器方面的函数原型很长，但是非常清楚:
#define QUALITY typename quality_t::value_type
#define PRICE typename price_t::value_type
template <typename price_t, typename quality_t, typename iterator_t>
std::pair<iterator_t, QUALITY> knapsack(iterator_t begin, iterator_t end,
PRICE budget,
price_t price,
quality_t quality)price_t 和 quality_t 是必需属性的访问器。
所以元素*i 的价格就是 price(*i)，它可以存储在一个类型为 typename price_t::value_type 的变量中。
为了说明用法，这里有一个非变异函数，它简单地评估解决方案的总体质量，假设您从头开始购买所有可能的元素:
template <typename price_t, typename quality_t, typename iterator_t>
QUALITY knapeval(iterator_t begin, iterator_t end, PRICE money,
price_t price, quality_t quality)
{
typename quality_t::value_type total_q = 0;
while (begin != end)
{
const typename price_t::value_type p = price(*begin);
if (p > money)
break;
money -= p;
total_q += quality(*begin++);
}
return total_q;
}对于算法测试，通常需要固定访问器。生成符合以下条件的占位符结构会很方便:
struct property_price
{
typedef unsigned value_type;
template <typename T>
value_type operator()(const T& x) const
{
return x.price();
}
};
struct price_tag_t {};
struct quality_tag_t {};
struct knapsack_object
{
property<unsigned, price_tag_t> price;
property<unsigned, quality_tag_t> quality;
};接下来描述属性类。
extra 标记禁止在具有相同基础类型(例如，unsigned int)的不同属性之间赋值。
template <typename object_t, typename tag_t = void>
class property
{
object_t data_;
public:
property()
: data_() // default-constructs fundamental types to zero
{}
property(const object_t& x)
: data_(x)
{}
const object_t& operator()() const
{
return data_;
}
const object_t& operator()(const object_t& x)
{
return data_ = x;
}
const char* name() const
{
return typeid(tag_t).name();
}
};6.2.2.拟态
一些通用算法接受一个范围——即两个迭代器[begin，end 和一个附加值——或者一个一元谓词。这些算法实现了两次。后一个版本使用谓词来测试元素，前一个版本测试“与给定值相等”。
一个经典的例子是 std::find 对 std::find_if。
| 模板对象 _ tT2】 | 模板函子 _t > | | iter_t find(iter_t begin，iter_t end， object_t x ) | iter_t find_if(iter_t begin，iter_t end， functor_t f | | { | { | | for(；开始！=结束；++begin) | for(；开始！=结束；++begin) | | { | { | | if (*begin == x) | if (f(*begin)) | | 打破； | 打破； | | } | } | | 返回开始； | 返回开始； | | } | } |
原则上，find 可以用 find_if 来重写:
template <typename iter_t, typename object_t>
iter_t find(iter_t begin, const iter_t end, object_t x)
{
std::equal_to<object_t> EQ;
return std::find_if(begin, end, std::bind2nd(EQ, x));
}但是反过来也是可能的:
template <typename functor_t>
class wrapper
{
functor_t f_;
public:
wrapper(functor_t f = functor_t())
: f_(f)
{
// verify with a static assertion that
// functor_t::result_type is bool
}
bool operator==(const typename functor_t::argument_type& that) const
{
return f_(that);
}
};
template <typename iter_t, typename functor_t>
iter_t find_if(iter_t begin, const iter_t end, functor_t F)
{
return std::find(begin, end, wrapper<functor_t>(F));
}类型 T 的模拟对象非正式地表现为 T 的实例，但在内部它是一元谓词。一个拟态实现 operator==(const T &)，operator！=(const T &)，以及运算符“cast to T”(所有运算符均为 const)。
要调用谓词，您需要编写:
if (f(x))要调用模拟，等效的语法应该是:
if (f == x)这些要求有些不完整:
- 等式和不等式应该以任意顺序接受拟态本身和 T，以防止不希望的使用“cast to T”进行比较(您将在后面读到更多相关内容)。
- 转换运算符应该返回满足相同条件的原型值。
换句话说，如果 M 是 T 类型的模拟，那么 M 的基本属性是:
M<T> m;
assert(m == static_cast<T>(m));T 型最简单的模拟就是 T 本身。
作为一个非常简单的例子，让我们实现一个识别正数的模拟:
template <typename scalar_t >
struct positive
{
bool operator==(const scalar_t& x) const
{
return 0<x;
}
bool operator!=(const scalar_t& x) const
{
return !(*this == x);
}
operator scalar_t() const
{
return 1; // an arbitrary positive number
}
};这是第一个不再需要 find_if 的应用程序。
double a[] = { -3.1, 2.5, -1.0 };
std::find(a, a+3, positive<double>()); // fine, returns pointer to 2.5关键是 find 中的 value 参数有独立的模板类型，所以正的照原样传递，不做强制转换。
推导出的模板类型，例如:
template <typename I>
iter_t find(I, I, typename std::iterator_traits<I>::value_type x)将导致模拟衰减到其默认值(因此，将返回错误的查找结果)。
模拟界面实际上可以更加丰富:
template <typename scalar_t, bool SIGN = true>
struct positive
{
bool operator==(const scalar_t& x) const
{
return (0<x) ^ (!SIGN);
}
bool operator!=(const scalar_t& x) const
{
return !(*this == x);
}
operator scalar_t() const
{
// arbitrary positive and non-positive numbers
return SIGN ? +1 : -1;
}
positive<scalar_t, !SIGN> operator!() const
{
return positive<scalar_t, !SIGN>();
}
};
template <typename scalar_t, bool SIGN>
inline bool operator==(const scalar_t& x, const positive<scalar_t, SIGN> p)
{
return p == x;
}
template <typename scalar_t, bool SIGN>
inline bool operator!=(const scalar_t& x,
const positive<scalar_t, SIGN> p)
{
return p != x;
}因此，正数将等于任何严格的正双精度数，并在需要时转换为 1.0。另一方面，正数将等于非正数，它将返回-1.0。
请注意，用户只需写正的()或！正()。
std::find(a, a+3, !positive<double>());您已经看到，编写拟态比编写仿函数要花费更多的精力，但这是值得的，尤其是对于将特殊值作为参数的通用函数。下一节提供了另一个应用程序。
6.2.3.范围结束
基于迭代器的算法不能动态计算范围的结尾。例如，您不能表达“查找 5.0，但在第一个负数处停止”的概念，因为范围是预先计算的。您需要两个函数调用。
using namespace std;
find(begin, find_if(begin, end, bind2nd(less<double>(), 0.0)), 5.0)C 字符串给出了范围低效的典型例子。假设您正在复制一个 C 字符串，并得到一个到目标的输出迭代器:
const char* c_string = "this is an example";
// can we avoid strlen?
std::copy(c_string, c_string+strlen(c_string), destination);strlen 必须遍历字符串寻找终止符，然后 copy 再次遍历它。这个过程在实践中非常快，但它做了一个不必要的传递。
假设你重写了副本。你不改变函数体，只是允许范围的端点有不同的类型。
template <typename iter1_t, typename iter2_t, typename end_t>
iter2_t copy_2(iter1_t begin, end_t end, iter2_t output)
{
while (begin != end)
*(output++) = *(begin++),
return output;
}这相当于要求 end 是 iter1_t 类型的模拟。
比较以下代码:
template <typename char_t, char_t STOP = 0>
struct c_string_end
{
typedef char_t* iterator_t;
operator iterator_t() const { return 0; }
bool operator!=(const iterator_t i) const
{
return !(*this == i);
}
bool operator==(const iterator_t i) const
{
return i==0 || *i==STOP;
}
};
// implement operator== and != with arguments in different order
// ...
const char* begin = "hello world!";
copy_2(begin, c_string_end<const char>(), output); // ok and efficient!
copy_2(begin, begin+5, output); // also ok!对 copy_2 的后一个调用等效于 std::copy。
总而言之，模仿有两种用途:
- 接受“测试”的算法，测试可以是值，也可以是谓词。
- 处理范围的算法开始...end，其中 end 只是一个终止条件(也就是说，它不会递减)。
注意两者的区别。第一点中提到的“测试”是元素上的跳过并继续条件*；end 是迭代器上的终止和退出准则。*
当对象充当跳过并继续过滤器时，模拟接口中的 cast 操作符证明是有用的。假设您正在计算满足某些标准的所有元素的平均值。首先，你写一个试探性的“经典”版本。
template <class iter_t, class predicate_t>
typename std::iterator_traits<iter_t>::value_type
average_if(iter_t begin, iter_t end, predicate_t f)
{
size_t count = 0;
typename std::iterator_traits<iter_t>::value_type result = 0;
for (; begin != end; ++begin)
{
if (f(*begin))
{
result += *begin;
++count;
}
}
return count>0 ? result/count : [[???]];
}如果谓词拒绝所有元素，你不知道返回什么，除了可能 STD::numeric _ limits<...>::quiet _ NaN()(希望 has_quiet_NaN 为真)。
然而，最好的选择是询问函数对象返回什么。如果 F 被视为拒绝逻辑(而不是接受)，它还应该负责提供被拒绝元素的原型，这正是模拟的基本属性。
这就是为什么你用一个代表安静的拟态来重写算法 _NaN: 16
template <typename iter_t, typename end_t, typename nan_t>
typename std::iterator_traits<iter_t>::value_type
average(iter_t begin, const end_t end, nan_t NaN)
{
size_t count = 0;
typename std::iterator_traits<iter_t>::value_type result = 0;
for (; begin != end; ++begin)
{
if (NaN != *begin)
{
result += *begin;
++count;
}
}
return count>0 ? result/count : NaN;
}模拟的典型作用是表示“排除过滤器”:
template <typename scalar_t>
struct ieee_nan
{
operator scalar_t() const
{
return std::numeric_limits<scalar_t>::quiet_NaN();
}
bool operator!=(const scalar_t& x) const
{
return x == x;
}
bool operator==(const scalar_t& x) const
{
return x != x;
}
};强制转换运算符的危险之处在于它可能会被意外调用。再次考虑四页前的例子:
template <typename iterator_t, char STOP = 0>
struct c_string_end
{
// ...
};
// ooops. forgot to implement operator== and !=
// with arguments in different order
// later...
while (begin != end)
{
// ...
}开始！=end 会实际调用 bool 运算符！=(const char*，const char*)传递已经是指针的 begin，并对 end 应用强制转换(这会产生一个空指针)。因此，循环永远不会退出。
还要注意，可以包装一个拟态并将其转换为谓词，反之亦然。
6.3.迭代器换行
编写符合 STL 的迭代器是一项复杂的活动，它涉及到大量的代码重复。幸运的是，编写 const _ iterators 要容易得多。
包装迭代器，常量或非常量，是一个包含另一个迭代器作为成员的类。包装器将每个“定位操作”(例如，递增和递减)转发给成员，但是它截取解引用，改变结果以便表达底层数据集的逻辑视图。
由于最终用户可能看不到实际的数据，而是一个定制的伪造值，所以通常不可能通过视图修改原始对象，所以包装的迭代器大多是 const_iterators 。
假设您有一个整数向量和一个迭代器包装器，它返回乘以 5 的实际值。
template <typename iterator_t>
class multiplier_iterator
{
// ...
};
// Later...
int main()
{
std::vector<int> data;
data.push_back(8);
multiplier_iterator<std::vector<int>::iterator> i(data.begin(), 5);
int a = *i; // now a = 5*8
*i = 25; // what about data[0] now???
assert(*i == 25);
*i = 24; // what about data[0] now???
assert(*i == 25); // are you sure?
}即使 multiplier_iterator 可以在位置 data[0]物理上写一个整数，它应该怎么做？如果它足够聪明的话，它会写 25/5=5，这样*i 从那一点开始返回 25。
但是，指令*i = 24 就更成问题了。它应该抛出异常吗？还是什么都不做？还是反正 set data[0]=(24+(5-1))/5？
运算符-> 的正确实现确实是最困难的问题。幸运的包装器会简单地将执行递归地分派给包装的迭代器，但是由于这通常揭示了底层的“真实”数据，所以它可能与包装逻辑不兼容。
考虑省略不太可能被使用的操作符。>——算符是第一候选，除非它们的实现既琐碎又正确。 17
箭头操作符用于访问指向类型的成员，但是在这种类型是泛型的代码部分(例如，可以推导出一个模板参数)，这些成员通常是未知的*，所以不应该使用箭头。 18*
*例如，std::vector::assign 即使在没有操作符的迭代器上也能正常工作。
6.3.1.迭代器扩展器
迭代器包装器会将大多数操作委托给被包装的对象，比如 operator++。
使用一个静态接口 19 (名为 iterator_expander )调度部分非常容易自动化:
class wrapper
: public iterator_expander<wrapper>
, public std::iterator_traits<wrapped>
{
wrapped w_;
public:
wrapped& base()
{
return w_;
}
const wrapped& base() const
{
return w_;
}
wrapper(wrapped w)
: w_(w)
{
}
[...] operator* () const
{
// write code here
}
[...] operator-> () const
{
// write code here
}
};iterator_expander 接口(下面列出)负责所有可能的定位(++、++、+=、-=、+和-)和比较操作符。都实现了，照例只有用了才会编译。如果 wrapped 不支持它们中的任何一个，就会发出一个错误(不需要静态断言，因为错误的原因很明显)。
还要注意，接口中的每个操作符都返回 true_this()，而不是this，因为否则像(i++)这样的组合表达式将不起作用。iterator_expander 不实现运算符*，但 true_this()返回实际的包装器。
template <typename iterator_t, typename diff_t = ptrdiff_t>
class iterator_expander
{
protected:
// the static interface part, see Section 6.2
~iterator_expander() {}
iterator_expander() {}
iterator_t& true_this()
{ return static_cast<iterator_t&>(*this); }
const iterator_t& true_this() const
{ return static_cast<const iterator_t&>(*this); }
public:
iterator_t& operator++() { ++true_this().base(); return true_this(); }
iterator_t& operator--() { --true_this().base(); return true_this(); }
iterator_t& operator+=(diff_t i)
{ true_this().base() += i; return true_this(); }
iterator_t& operator-=(diff_t i)
{ true_this().base() -= i; return true_this(); }
iterator_t operator++(int)
{ iterator_t t(true_this()); ++(*this); return t; }
iterator_t operator--(int)
{ iterator_t t(true_this()); --(*this); return t; }
iterator_t operator+(diff_t i) const
{ iterator_t t(true_this()); t+=i; return t; }
iterator_t operator-(diff_t i) const
{ iterator_t t(true_this()); t-=i; return t; }
diff_t operator-(const iterator_expander& x) const
{ return true_this().base() - x.true_this().base(); }
bool operator<(const iterator_expander& x) const
{ return true_this().base() < x.true_this().base(); }
bool operator==(const iterator_expander& x) const
{ return true_this().base() == x.true_this().base(); }
bool operator!=(const iterator_expander& x) const
{ return !(*this == x); }
bool operator> (const iterator_expander& x) const
{ return x < *this; }
bool operator<=(const iterator_expander& x) const
{ return !(x < *this); }
bool operator>=(const iterator_expander& x) const
{ return !(*this < x); }
};您还需要一个外部运算符:
template <typename iterator_t, typename diff_t>
iterator_t operator+(diff_t n, iterator_expander<iterator_t, diff_t> i)
{
return i+n;
}注意 difference_type 是取的，不是推导的。iterator_expander 无法读取 T 中定义的类型，因为它是 T 的基，所以在 T 之前编译。
因此包装器将被声明如下:
template <typename iterator_t>
class wrapper
: public iterator_expander
<
wrapper<iterator_t>,
typename std::iterator_traits<iterator_t>::difference_type
>
{
// ...
};这里有一个简单的实际例子，它也显示了迭代器的基底可以是一个简单的整数。
class random_iterator
: public iterator_expander<random_iterator>
, public std::iterator_traits<const int*>
{
int i_;
public:
int& base() { return i_; }
const int& base() const { return i_; }
explicit random_iterator(const int i=0)
: i_(i)
{
}
int operator*() const
{
return std::rand();
}
};
int main()
{
std::vector<int> v;
v.assign(random_iterator(0), random_iterator(25));
// now v contains 25 random numbers
//...
}注意，这个例子跳过了 arrow 操作符，解引用返回一个值，而不是一个引用(但是由于这个类继承了 const int* traits，仍然可以将一个引用绑定到*iterator，因为引用是 const int&)。
注意不在迭代器中存储值的副本。虽然这实际上允许返回真正的引用和指针，但被引用的实体有一个绑定到迭代器的生存期，而不是绑定到“容器”(换句话说，破坏迭代器，引用变得无效)，这将导致微妙的错误。下面是一些不好的代码:
class random_iterator
: public iterator_expander<random_iterator>
, public std::iterator_traits<const int*>
{
int i_;
int val_; // bad
public:
const int& operator*() const
{
return val_ = std::rand(); // bad
}
const int* operator->() const
{
return &*(*this); // even worse
}
};迭代器包装器解决了对映射中的值进行迭代的问题(或者等价地，对键进行常量迭代的问题)。
这一次，这个例子将是一个真正的非常数迭代器实现，因为您迭代了现有的元素，所以您可以返回指针和引用。
template <typename T, int N>
struct component;
template <typename T1, typename T2>
struct component<std::pair<T1, T2>, 1>
{
typedef T1 value_type;
typedef T1& reference;
typedef const T1& const_reference;
typedef T1* pointer;
typedef const T1* const_pointer;
};
template <typename T1, typename T2>
struct component<std::pair<const T1, T2>, 1>
{
typedef T1 value_type;
typedef const T1& reference;
typedef const T1& const_reference;
typedef const T1* pointer;
typedef const T1* const_pointer;
};
template <typename T1, typename T2>
struct component<std::pair<T1, T2>, 2> : component<std::pair<T2, T1>, 1>
{
};假设 iterator_t(包装类型)指向一个类似 std::pair 的类。如果不是这样，编译器将在编译一个 ref 重载时给出一个错误。
template <typename iterator_t, int N>
class pair_iterator
: public iterator_expander< pair_iterator<iterator_t, N> >
{
static const bool IS_MUTABLE =
is_mutable_iterator<iterator_t>::value;
iterator_t i_;
typedef std::iterator_traits<iterator_t> traits_t;
typedef component<typename traits_t::value_type, N> component_t;
typedef typename component_t::reference ref_t;
typedef typename component_t::const_reference cref_t;
typedef typename component_t::pointer ptr_t;
typedef typename component_t::const_pointer cptr_t;
template <typename pair_t>
static ref_t ref(pair_t& p, static_value<int, 1>)
{ return p.first; }
template <typename pair_t>
static ref_t ref(pair_t& p, static_value<int, 2>)
{ return p.second; }
template <typename pair_t>
static cref_t ref(const pair_t& p, static_value<int, 1>)
{ return p.first; }
template <typename pair_t>
static cref_t ref(const pair_t& p, static_value<int, 2>)
{ return p.second; }
public:
explicit pair_iterator(iterator_t i)
: i_(i)
{}
iterator_t& base() { return i_; }
const iterator_t& base() const { return i_; }
typedef typename typeif<IS_MUTABLE, ref_t, cref_t>::type reference;
typedef typename typeif<IS_MUTABLE, ptr_t, cptr_t>::type pointer;
typedef typename component_t::value_type value_type;
typedef typename traits_t::iterator_category iterator_category;
typedef typename traits_t::difference_type difference_type;
reference operator* () const
{
return ref(*i_, static_value<int, N>());
}
pointer operator->() const
{
return &*(*this);
}
};这是一个驱动函数:
template <int N, typename iterator_t>
inline pair_iterator<iterator_t, N> select(iterator_t i)
{
return pair_iterator<iterator_t, N>(i);
}最后是一些示例代码。驱动程序的语法是 select (i)其中 N 是 1 或 2，I 是一个迭代器，其 value_type 是一对:
template <typename T>
struct Doubler
{
void operator()(T& x) const
{
x *= 2;
}
};
template <typename T>
struct User
{
void operator()(const T& x) const
{
std::cout << x << ';';
}
};
typedef std::map<int, double> map_t;
MXT_ASSERT(!is_mutable_iterator<map_t::const_iterator>::value);
MXT_ASSERT(is_mutable_iterator<map_t::iterator>::value);
map_t m;
const map_t& c = m;
m[3] = 1.4;
m[6] = 2.8;
m[9] = 0.1;
// print 3;6;9; via iterator
std::for_each(select<1>(m.begin()), select<1>(m.end()), User<int>());
// print 3;6;9; via const_iterator
std::for_each(select<1>(c.begin()), select<1>(c.end()), User<int>());
// multiplies by 2 each value in the map
std::for_each(select<2>(m.begin()), select<2>(m.end()), Doubler<double>());
std::vector<double> v1;
v1.assign(select<1>(c.begin()), select<1>(c.end()));
std::vector< std::pair<int, double> > v2(m.begin(), m.end());
// multiplies by 2 each key in the vector (the key is not constant)
std::for_each(select<1>(v2.begin()), select<1>(v2.end()), Doubler<int>());
// these two lines should give an error:
// std::for_each(select<1>(m.begin()), select<1>(m.end()), Doubler<int>());
// std::for_each(select<1>(c.begin()), select<1>(c.end()), Doubler<int>());6.3.2.假对子
逆问题是“合并”两个逻辑视图，并获得一个使它们看起来像对的迭代器。使用 pair_iterator ，您可以构建一个键向量和一个值向量来读取一个映射，但不能反过来。
std::vector<int> key;
std::vector<double> value;
std::map<int, double> m = /* ??? */;实际上，您可以扩展迭代器扩展器的接口，以允许派生类有多个基的可能性。简单地让 base 有 N 个重载，带一个 static_value <size_t n="">，每个重载都可能返回一个对不同类型迭代器的引用。</size_t>
您可以分离出要应用于基底的基本修饰符，并编写一个非常简单的静态递归方法。 二十
由于您事先不知道 base(static_value <size_t k="">)是什么，所以您必须引入一些带有模板成员函数的辅助“修饰符”对象，如下所示:</size_t>
struct plusplus
{
template <typename any_t>
void operator()(any_t& x) const { ++x; }
};
class pluseq
{
const diff_t i_;
public:
pluseq(const diff_t i) : i_(i) {}
template <typename any_t>
void operator()(any_t& x) const { x += i_; }
};
template <typename iterator_t, size_t N, typename diff_t>
class iterator_pack
{
protected:
typedef static_value<size_t, N> n_times;
~iterator_pack() {}
iterator_pack() {}
iterator_t& true_this()
{
return static_cast<iterator_t&>(*this);
}
const iterator_t& true_this() const
{
return static_cast<const iterator_t&>(*this);
}
/* static recursion */
template <typename modifier_t, size_t K>
void apply(const modifier_t modifier, const static_value<size_t, K>)
{
modifier(true_this().base(static_value<size_t, K-1>()));
apply(modifier, static_value<size_t, K-1>());
}
template <typename modifier_t>
void apply(const modifier_t modifier, const static_value<size_t, 0>)
{
}
public:
typedef diff_t difference_type;
iterator_t& operator++()
{
apply(plusplus(), n_times());
return true_this();
}
iterator_t& operator+=(const diff_t i)
{
apply(pluseq(i), n_times());
return true_this();
}您需要再添加几个成员函数。为了简单起见，一些操作符，比如比较，只使用第一个元素: 21
typedef static_value<size_t,0> default_t;
diff_t operator-(const iterator_pack& x) const
{
const default_t d;
return true_this().base(d) - x.true_this().base(d);
}
bool operator<(const iterator_pack& x) const
{
const default_t d;
return true_this().base(d) < x.true_this().base(d);
}
bool operator==(const iterator_pack& x) const
{
const default_t d;
return true_this().base(d)==x.true_this().base(d);
}所有其他操作符都以通常的方式从基本操作符派生而来——后缀++ 和操作符+来自前缀++ 和+=以及其他比较来自
有了这个新工具，这里有一个不完全标准的迭代器，它假装在 std::pair 上迭代。
首先，一些亮点:
- 这里指针是 void，因为你不想支持 operator->，但是要编译 std::iterator_traits < iterator_couple<...>>指针需要定义；然而，这个定义将阻止任何其他用途。
- iterator_category 是两个类别中较弱的一个；然而，您可以静态地断言两个类别应该是可比较的，以避免不寻常的配对(比如输入/输出迭代器)。当然，这种限制可以取消。
- 主要问题是如何定义引用。显然，你必须依赖 r1_t 和 r2_t，但不能使用 std::pair <r1_t r2_t="">。(主要是因为，在经典 C++ 中，std::pair 不支持，不会编译。) 22</r1_t>
#define TRAITS(N) std::iterator_traits<iterator##N##_t>
template <typename iterator1_t, typename iterator2_t>
class iterator_couple
: public iterator_pack
<
iterator_couple<iterator1_t, iterator2_t>,
2,
typename TRAITS(1)::difference_type
>
{
typedef typename TRAITS(1)::value_type v1_t;
typedef typename TRAITS(2)::value_type v2_t;
typedef typename TRAITS(1)::reference r1_t;
typedef typename TRAITS(2)::reference r2_t;
typedef typename TRAITS(1)::iterator_category cat1_t;
typedef typename TRAITS(2)::iterator_category cat2_t;
public:
iterator_couple(iterator1_t i1, iterator2_t i2)
: i1_(i1), i2_(i2)
{
}
typedef typename
typeif
<
is_base_of<cat1_t, cat2_t>::value,
cat1_t,
cat2_t
>::type iterator_category;
typedef std::pair<v1_t, v2_t> value_type;
typedef void pointer;
struct reference
{
/* see below... */
};
iterator1_t& base(static_value<size_t, 0>) { return i1_; }
iterator2_t& base(static_value<size_t, 1>) { return i2_; }
const iterator1_t& base(static_value<size_t, 0>) const
{ return i1_; }
const iterator2_t& base(static_value<size_t, 1>) const
{ return i2_; }
reference operator* () const
{
MXT_ASSERT
(
(is_base_of<cat1_t, cat2_t>::value
|| is_base_of<cat2_t, cat1_t>::value)
);
return reference(*i1_, *i2_);
}
private:
iterator1_t i1_;
iterator2_t i2_;
};您必须模拟一对引用，而 std::pair 不允许:
struct reference
{
r1_t first;
r2_t second;
reference(r1_t r1, r2_t r2)
: first(r1), second(r2)
{
}
operator std::pair<v1_t, v2_t>() const
{
return std::pair<v1_t, v2_t>(first, second);
}
template <typename any1_t, typename any2_t>
operator std::pair<any1_t, any2_t>() const
{
return std::pair<any1_t, any2_t>(first, second);
}
reference& operator= (const std::pair<v1_t, v2_t>& p)
{
first = p.first;
second = p.second;
return *this;
}
void swap(reference& r)
{
swap(first, r.first);
swap(second, r.second);
}
void swap(std::pair<v1_t, v2_t>& p)
{
swap(first, p.first);
swap(second, p.second);
}
};模板 cast-to-pair 操作符是必需的，因为 std::map 可能不会将引用转换为 pair ，而是转换为 pair 。
这种实现可能足以编写如下代码:
template <typename iter1_t, typename iter2_t>
iterator_couple<iter1_t, iter2_t> make_couple(iter1_t i1, iter2_t i2)
{
return iterator_couple<iter1_t, iter2_t>(i1, i2);
}
std::vector<int> k;
std::list<double> v1;
std::vector<double> v2;
std::map<int, double> m;
std::pair<int, double> p = *make_couple(k.begin(), v1.begin());
m.insert(make_couple(k.begin(), v1.begin()),
make_couple(k.end(), v1.end()));
std::vector< std::pair<int, double> > v;
v.assign(make_couple(k.begin(), v2.begin()),
make_couple(k.end(), v2.end()));注意，第一次插入得到一个双向迭代器，而最后一次赋值得到一个随机访问迭代器。 23
6.4.收据
收据是空类，只能由“合法授权的实体”创建，并作为必需的参数解锁功能的执行。有些收据可以储存起来以备后用，但有些则必须立即传递。
在一个非常简单的例子中，当您需要强制函数 F 在 G 之前被调用时，您修改 F 并让它返回一个回执 R，否则无法构造它。最后，G 将 R 作为一个附加的形式参数。
当每个派生类中的虚拟成员函数 foo 应该在某个时候调用 BASE::foo 时，receiving 在类的层次结构中非常有用。
假设 foo 返回 void。
有两种类似的解决方案:
- 在公共非虚拟/受保护虚拟技术中，基类实现了一个公共非虚拟 foo，它在适当的时候调用受保护的虚函数。
class BASE
{
protected:
virtual void custom_foo()
{
}
public:
void foo()
{
/* ... */
custom_foo();
}
};- 使用收据。BASE::foo 返回一个秘密收据，私有给 BASE。
class BASE
{
protected:
class RECEIPT_TYPE
{
friend class BASE;
RECEIPT_TYPE() {} // constructor is private
};
public:
virtual RECEIPT_TYPE foo()
{
/* ... */
return RECEIPT_TYPE();
}
};
class DERIVED : public BASE
{
public:
virtual RECEIPT_TYPE foo()
{
/* ... */
// the only way to return is...
return BASE::foo();
}
};如果 RECEIPT_TYPE 有公共复制构造函数，DERIVED 可以随时存储 BASE::foo 的结果。否则，它将被迫在返回行上调用它。
注意，非 void 返回类型 T 可以更改为 std::pair ，或者一个自定义类，它需要一个收据，但是忽略它。
收据在对象中特别有用，在对象中你想要控制成员函数的执行顺序(8.6 节描述了算法):
class an_algor
{
public:
bool initialize();
void iterate();
bool stop() const;
double get_result() const;
};
double execute_correctly_algor(an_algor& a)
{
if (!a.initialize())
throw std::logic_error("something bad happened");
do
{
a.iterate();
} while (!a.stop());
return a.get_result();
}
double totally_crazy_execution(an_algor& a)
{
if (a.stop())
a.iterate();
if (a.initialize())
return a.get_result();
else
return 0;
}通常，您希望在迭代之前调用 initialize，并在至少一次迭代之后调用 get_result。因此，您需要修改接口，如下所示:
template <int STEP, typename T>
class receipt_t : receipt_t<STEP-1, T>
{
friend class T;
receipt_t() {} // note: private
};
template <typename T>
class receipt_t<0, T>
{
friend class T;
receipt_t() {} // note: private
};
class a_better_algor
{
public:
typedef receipt_t<0, a_better_algor> init_ok_t;
typedef receipt_t<1, a_better_algor> iterate_ok_t;
init_ok_t initialize();
iterate_ok_t iterate(init_ok_t);
bool stop(iterate_ok_t) const;
double get_result(iterate_ok_t) const;
};有了模板友谊声明(它还不是标准的)的必要的邪恶，想法应该是清楚的:因为用户不能伪造收据，她必须存储 initialize 的返回值并传递它来迭代。最后，为了得到结果，需要证明至少执行了一次迭代: 24
a_better_algor A;
a_better_algor::init_ok_t RECEIPT1 = A.initialize();
while (true)
{
a_better_algor::iterate_ok_t RECEIPT2 = a.iterate(RECEIPT1);
if (a.stop(RECEIPT2))
return a.get_result(RECEIPT2);
} 注代码:
template <typename T>
class ...
{
friend class T;在经典 C++ 中不是标准的，因为当 T 是本机类型|(比如 int)时，该语句可能是无意义的。然而，它被一些编译器接受为扩展。在 C++0x 中，它是合法的，但是语法是:
朋友
作为一种变通方法，一些(但不是全部)经典 C++ 编译器接受这一点。这种变通方法的基本原理是，它引入了一个额外的间接方式，允许编译器将 T 视为“间接”类型，而不是模板参数。
模板 类... { struct nested _ T { typedef T type；}; 友类嵌套 _ t::type；
6.5.代数要求
6.5.1.少和楠
泛型类型 T 的对象通常被假定为小于可比的。
这意味着要么 T::运算符< is defined, or an instance of a binary predicate “less” is given as an extra argument. 25
一个算法应该避免混合不同的比较操作符，比如操作符<= and operator>，因为它们可能不一致。最好的解决方案是用运算符
| X | (假设有效) | | X>Y | Y | | x≤y) | ！(Y | | X≥Y | ！(X | | X==Y | ！(X | | x！=Y | (X |
运算符==是否应该被假定为有效，或者用等价测试来代替，这是有问题的。事实上，对操作符<的两次调用可能会慢很多(如在 std::string 中)。然而，在某些情况下，有了额外的假设，其中一个测试可能会被省略。例如，如果一个范围是排序的，那么一个带有迭代器*i == *(i+k)的测试可以替换为！减去(i，(i+k))。
NaN(非数字)是导致任何比较运算符“失败”的 T 的一个实例。换句话说，如果 x 和 y 中至少有一个是 NaN，那么 x OP y 如果 OP 是，<=,> =，==则返回 false，如果 OP 是！=.事实上，NaN 可以通过这个简单的测试检测出来:
template <typename T>
bool is_nan(const T& x)
{
return x != x;
}类型 double 和 float 有一个本机 NaN。
如果 T 有一个 NaN，它可能会给排序算法带来问题。如果两个元素都不小于另一个，那么它们就是等价的， 26 所以一个 NaN 等价于任何其他元素。例如，如果你写:
std::map<double, int> m;
// insert elements...
m[std::numeric_limits<double>::quiet_NaN()] = 7;您实际上是用 7 覆盖了一个随机(即依赖于实现的)值。
处理可能包含 NaN 的范围的正确方法是在排序前将它们分隔开，或者修改比较运算符，例如，它们位于范围的开头:
template <typename T>
struct LessWithNAN
{
bool operator()(const T& x, const T& y) const
{
if (is_nan(x))
return !is_nan(y);
else
return x<y;
}
};6.6.巴顿-纳克曼骗局
Knuth 写道，一个技巧是一个聪明的想法，只使用一次，而一个技巧是一个至少使用两次的技巧。巴顿-纳克曼技术，也称为受限模板扩展，是一种在类中声明非成员函数和操作符的方法，将它们标记为朋友:
template <typename T>
class X
{
public:
friend int f(X<T> b) // global function #1
{
return 0;
}
friend bool operator==(X<T> a, X<T> b) // global operator #2
{
return ...;
}
};
X<double> x;
f(x); // calls #1
x == x; // calls #2这里显示的非成员函数和运算符是非模板函数，在类被实例化时被注入到 X < T >的范围内。换句话说，它们是用 ADL 找到的，所以至少有一个参数必须有 X 类型< T >。
这种技术的主要用途是声明接受模板类内部类的全局函数。
template <typename T>
struct outer
{
template <int N>
struct inner {};
};你不能为任意的 T 编写一个带外:·内的模板，因为 T 是不可推导的。然而，巴顿-纳克曼的把戏就可以了:
template <typename T>
struct outer
{
template <int N>
struct inner
{
friend int f(inner<N>)
{ return N; }
};
};不管 f 不是模板，您都可以随意操作模板参数:
template <typename T>
struct outer
{
template <int N>
struct inner
{
friend inner<N+1> operator++(inner<N>)
{ return inner<N+1>(); }
};
};
outer<double>::inner<0> I1;
++I1; // returns outer<double>::inner<1>你也可以用同样的方法写模板函数，但是所有的参数都应该是可推导的因为 ADL 找不到有显式模板参数的函数。以下代码是正确的:
template <typename T>
struct outer
{
template <int N>
struct inner
{
inner(void*) {}
template <typename X>
friend inner<N+1> combine(inner<N>, X x)
{ return inner<N+1>(&x); }
};
};
outer<double>::inner<0> I;
combine(I, 0);相反，以下示例仅在 outer 位于全局范围内时有效，但如果它包含在命名空间中则无效:
template <typename T>
struct outer
{
template <typename S>
struct inner
{
template <typename X>
friend inner<X> my_cast(inner<S>)
{ return inner<X>(); }
};
};
outer<double>::inner<int> I;
outer<double>::inner<float> F = my_cast<float>(I);这里显示的具有功能性 my_cast 的唯一解决方法是静态接口，基类在名称空间级别，但是所需的机制是不可忽略的:
// note: global scope
template <typename T, typename S>
struct inner_interface
{
};
namespace XYZ
{
template <typename T>
struct outer
{
template <typename S>
struct inner : inner_interface<T, S>
{
inner(int = 0) {}
};
};
}
// note: global scope
template <typename X, typename T, typename S>
typename XYZ::outer<T>::template inner<X>
my_cast(const inner_interface<T,S>& x)
{
// cast x to outer<T>::inner<S> if necessary
return 0;
}
int main()
{
XYZ::outer<double>::inner<int> I;
my_cast<float>(I);
}显然，my_cast 可能只是 inner 的一个模板成员函数，但这可能会迫使客户端在点和函数名之间引入一个模板关键字:
template <typename S>
struct inner
{
template <typename X>
inner<X> my_cast() const
{ return inner<X>(); }
};
outer<double>::inner<int> I;
outer<double>::inner<float> F = I.my_cast<float>(); // Ok.
template <typename T>
void f(outer<T>& o)
{
o.get_inner().my_cast<float>();
// error: should be
// o.get_inner().template my_cast<float>()
}
//...1 在现代 C++ 中，有一些名为 cbegin()和 cend 的成员函数总是返回常量迭代器，所以循环会是 for(auto I = v . C begin()；我！= v . cend()；++i)。
2 不是所有的容器都是符合标准的，事实上，甚至 std::vector < bool >也不是。
3 value_type 被标准授予非常数合格，但这还不够。比如 std::map 的 value_type 是 pair < const key_type，mapped_type >不可赋值；关于这个问题的更多信息在第 6.3 节。
4 并且可能是次优的，但是这在这里并不真正相关。
5 类似的函数是现代 C++ 标准的一部分。参见 http://en.cppreference.com/w/cpp/algorithm/minmax[。](http://en.cppreference.com/w/cpp/algorithm/minmax)
6 这当然公平，但是武断。大约一半的 STL 容器有双向迭代器和一半的随机访问。然而，如果您根据使用情况对它们进行加权，并且包含普通的指针，那么一般的迭代器会更加随机访问。
理想情况下，你希望这些和相差 0 或 1。反正这是 NP 难问题。
8 交换过程会留下一些元素。这就是在 M 的大小上循环的原因，最坏的情况下会跳过 M 的一半左右的成员，所以算法复杂度还是超线性的；即在处理 n 个元素时，需要的时间与~ n log(n)成正比。
9 最快的经典算法 quicksort 和 heapsort 可以在超线性时间内对随机存取容器进行就地排序(通常 std::sort 是两者的组合)。mergesort 是第三种超线性方法，使用前向迭代器，但是它需要额外的内存来保存整个输入的副本。然而，在实践中，如果有这样的额外内存可用，那么复制/交换向量中的输入、对向量进行排序并返回结果可能会很方便。
11 参见 SFINAE 第 4.3.1 节。
当然，如果已知某个元函数对于某个特定的类型来说是失败的，用户总是有可能显式地专门化它。还要注意，boost 库采用了另一种方法:如果 x 是 T 的实例，它会检查*x 是否可以转换为 T 的 value_type。请参见 boost::is_readable_iterator。
13 记住如果给定两个函数 void F(X)和 Y G()，则 X 可转换为 Y，调用 F(G())是合法的。如果 X=T 且 Y=T &或 Y=const T &，则通话正常。或者，如果 X=T &，Y=T，则调用无效。这正是 has_conversion 的工作方式。
14 正如在第 1 章中所说的，实际上有一种方法可以做到这一点，但是它不能很好地扩展，而且很麻烦。它需要 std::set 作者的合作；这种技术是 6.6 节的主题。
15 在所有的超线性算法中，只有一些 mergesort 变体可以利用排序后的输入；另一方面，quicksort 和 heapsort 并不明显依赖于初始数据的“熵”。
16 算法现在应该命名为 average_if_not。
一般来说，迭代器包装器不需要 100%符合标准，因为有一些常见问题不会影响它们的功能。最常见的是缺少 operator- >和 operator*返回值而不是引用(换句话说:iterator::reference 和 iterator::value_type 是一样的)。另一方面，这些简化功能的实现可能会容易得多。请参阅本章后面的 random_iterator 示例。
18 一个例外是 std::map，可以名正言顺地称 i- >第一，i- >第二。
像往常一样，Boost 库提供了一个更完整的解决方案，但这个更简单，功能也更全。
20 为简洁起见，省略了所有“减法”功能。
21 在综合中，迭代器包是一个类似迭代器的类，它保持 N 个不同迭代器之间的同步。如果 P 是这样一个包，那么只有当所有迭代器都是随机访问时，才能调用 P += 2。否则，代码将无法编译。然而，如果第一个组件是一个随机访问迭代器，那么这个包将有一个恒定的时间差。
22 std::pair 通过常量引用在构造函数中接受参数，但如果其中一个类型是引用，它会创建对引用的引用，这是禁止的。
有趣的是，全局帮助函数的使用避免了构造函数和函数声明之间所有令人讨厌的歧义。在[7]的“第 6 项”中描述并解决了该问题。
24 一个基于类型的收据系统不处理实例。例如，你可以有两个 algors，用第一个的收据解锁第二个。这可以减轻(在运行时！)通过在收据上添加州名。例如，您可能希望在收据本身中存储一个指向 algor 的指针，并在 algor 中添加断言，以强制收据中的指针确实等于“this”。
25 作为一个经验法则，如果 T 是这样的，有一个单一的方法来决定 A 是否< B，因为比较是琐碎的或固定的，那么你应该提供 T::运算符<(例如，T = RomanNumber)。相反，如果有不止一个可行的比较，你不应该每次都实现操作符<并传递正确的函数，以使你的意图明确(例如，T = Employee)。这些泛函可以在 t 内部定义。
26 或者，如果 x < y 和 y < x 都为真，那么比较运算符无效。*