- VisualStudio2022插件的安装及使用-编程手把手系列文章
- pprof-在现网场景怎么用
- C#实现的下拉多选框,下拉多选树,多级节点
- 【学习笔记】基础数据结构:猫树
使用迭代器最方便的地方就是和算法库结合,对于实现只需要聚焦于算法,而不用过多考虑数据结构的实现.
举一个常见的的例子,std::copy_n 用作于范围元素的复制,适配于各个容器类型,并且演化出了 back_inserter/front_inserter/inserter 这类更上层的迭代器.
// std::vector 的复制
std::vector<int> v1{2, 1, 3, 4};
std::vector<int> v2(v1.size() / 2); // 初始化大小为 2
std::copy_n(v1.cbegin(), v1.size() / 2, v2.begin()); // 2 1
std::vector<int> v3; // 初始化大小为 0
std::copy_n(v1.cbegin(), v1.size() / 2, std::back_inserter(v3)); // 2 1
// std::list
std::list<int> l1{12, 11, 13, 14};
std::list<int> l2;
std::copy_n(l1.cbegin(), l1.size() / 2, std::back_inserter(l2)); // 12 11
// std::vector -> std::list
std::list<int> l3;
std::copy_n(v1.cbegin(), v1.size() / 2, std::back_inserter(l3)); // 2 1
// std::list -> std::vector
std::vector<int> v4;
std::copy_n(l1.cbegin(), l1.size() / 2, std::back_inserter(v4)); // 12 11
元素的复制可能不是简单的 memcpy,需要考虑深拷贝的情况,在一些其他的语言中,由于标准库的算法实现的不多,对这种统一接口的约束不强.
比如在 Go 中,几乎都是通过接口进行约束。由于 golang 里面只有类似 memcpy 的 copy,换一个 container/heap 的例子,通过定义了三个接口来实现.
type Interface interface {
// Len is the number of elements in the collection.
Len() int
// Less reports whether the element with index i
// must sort before the element with index j.
//
// If both Less(i, j) and Less(j, i) are false,
// then the elements at index i and j are considered equal.
// Sort may place equal elements in any order in the final result,
// while Stable preserves the original input order of equal elements.
//
// Less must describe a transitive ordering:
// - if both Less(i, j) and Less(j, k) are true, then Less(i, k) must be true as well.
// - if both Less(i, j) and Less(j, k) are false, then Less(i, k) must be false as well.
//
// Note that floating-point comparison (the < operator on float32 or float64 values)
// is not a transitive ordering when not-a-number (NaN) values are involved.
// See Float64Slice.Less for a correct implementation for floating-point values.
Less(i, j int) bool
// Swap swaps the elements with indexes i and j.
Swap(i, j int)
}
不讨论接口性能,heap 只针对其本身来说这个定义是够用的,足够简单只要实现了三个接口,那么就可以实现一个堆.
Go 的一个问题是在实现这类基础设施上,通用型做的还不够好,一些相同的语义没有抽取出来形成一个接口规范:比如一个简单的 Copy 操作必须通过手动 for 进行赋值.
通过观察 std::copy 的实现(gcc12)来看看迭代器的设计 。
template <bool _IsMove, bool _IsSimple, typename _Category>
struct __copy_move
{
template <typename _II, typename _OI>
_GLIBCXX20_CONSTEXPR
static _OI __copy_m(_II __first, _II __last, _OI __result)
{
for (; __first != __last; ++__result, (void)++__first)
*__result = *__first;
return __result;
}
};
std::copy 的通用实现中,出现的运算符有 。
!=
同语义还有 ==
<
<=
>
>=
++
同语义还有 --
++(int)
--
--(int)
+
-
+=
-=
*
同语义还有 ->
对于可以随机访问的容器(vector/array)来说,还有 [] 运算符.
迭代器设计为一个类,这样可以通过模版参数来区分不同的类型,见 std::vector 的迭代器 (__normal_iterator) 注释说明 。
// This iterator adapter is @a normal in the sense that it does not
// change the semantics of any of the operators of its iterator
// parameter. Its primary purpose is to convert an iterator that is
// not a class, e.g. a pointer, into an iterator that is a class.
// The _Container parameter exists solely so that different containers
// using this template can instantiate different types, even if the
// _Iterator parameter is the same.
尽管使用起来和指针非常类似,但是都是这个类提供的重载运算符,所以并不能简单的说成是指针.
对于要广泛使用的迭代器而言,统一其接口是一个很有必要的实现,对于 C++ 而言,**_trait* 是一种通用做法.
在 trait 限定各种类型,包括值,指针,引用等。对于各种容器,内部定义好一个迭代器别名 iterator,这个迭代器需要符合 trait 的语义.
class vector {
typedef T value_type; // 符合 trait 的别名
typedef XXX xxx_iterator; // 支持的迭代器适配器,比如 reverse_iterator/iterator
iterator begin() {}
reverse_iterator rbegin() {}
};
这样在一些模版类的地方直接使用这些类型别名
std::iterator_traits<std::vector<char>::iterator>::value_type x = 'x';
decltype(v1.begin())::value_type y = 'y';
容器都支持迭代器,但是容器类型就有不相同的,std::vector 和 std::map 的最大区别就是连续性。故迭代器同样有类型。有了类型可以通过 SFINAE 来选择不同的实现.
通过统一迭代器的语义,在 C++20 以前,对内部变量封装为 begin/end, 就可以通过 for (auto it = x.begin(); it != x.end; ++it) 来完成遍历的功能。 对于算法实现,取值可以通过 *,迭代可以通过 ++/--,配合类似 std::less 提高算法实现的抽象程度了.
iterator_traits 的通用实现如下,只定义了通用别名.
template <typename _Iterator>
struct __iterator_traits<
_Iterator, __void_t<typename _Iterator::iterator_category,
typename _Iterator::value_type,
typename _Iterator::difference_type,
typename _Iterator::pointer,
typename _Iterator::reference>> {
typedef typename _Iterator::iterator_category iterator_category;
typedef typename _Iterator::value_type value_type;
typedef typename _Iterator::difference_type difference_type;
typedef typename _Iterator::pointer pointer;
typedef typename _Iterator::reference reference;
};
template <typename _Iterator>
struct iterator_traits : public __iterator_traits<_Iterator> {};
迭代器的类型在 C++20 之前有 5 种,通过一些高层次的封装来观察其设计 。
reverse_iterator 顾名思义,对比一般的迭代器操作时反过来的 。
__normal_iterator &operator++() {
++_M_current;
return *this;
}
reverse_iterator &operator++() {
--current;
return *this;
}
后面三个迭代器,观察 = 运算符重载函数的实现,通过调用容器成员函数来新增元素.
back_insert_iterator &operator=(const typename _Container::value_type &__value)
{
container->push_back(__value);
return *this;
}
front_insert_iterator &operator=(const typename _Container::value_type &__value) {
container->push_front(__value);
return *this;
}
insert_iterator &operator=(const typename _Container::value_type &__value) {
iter = container->insert(iter, __value);
++iter;
return *this;
}
在容器为空的情况下,可以调用这些辅助迭代器适配器.
每个容器都有自身实现的迭代器,不看 const_iterator 这类变种的迭代器,容器实现分别是 。
__normal_iterator 是一个比较通用的迭代器实现,包含顺序容器(包括 char*),内部实现为对指针的操作.
reference operator*() const noexcept { return *_M_current; }
__normal_iterator &operator++() noexcept {
++_M_current;
return *this;
}
list 的特化迭代器实现,运算符可能涉及到链表的遍历动作 。
reference operator*() const noexcept { return *static_cast<_Node *>(_M_node)->_M_valptr(); }
_Self &operator++() noexcept {
_M_node = _M_node->_M_next;
return *this;
}
map 的特化迭代器实现,++ 运算符涉及到红黑树的遍历动作 。
reference operator*() const noexcept {
return *static_cast<_Link_type>(_M_node)->_M_valptr();
}
_Self &operator++() noexcept {
_M_node = _Rb_tree_increment(_M_node);
return *this;
}
std::map<std::string, in> 的迭代器类型展开为 _Rb_tree_iterator<pair<const __cxx11::basic_string , int>> ,pair 的 first 类型为 const std::string 。
对于 std::copy 来说,内部的赋值实现为 。
*__result = *__first;
等效于pair操作 。
std::pair<const std::string, int> p1{"lebron", 6};
std::pair<const std::string, int> p2 = p1;
// 出现编译错误
/usr/include/c++/12/bits/stl_algobase.h:353:23: error: use of deleted function ‘std::pair<const std::__cxx11::basic_string<char>, int>& std::pair<const std::__cxx11::basic_string<char>, int>::operator=(const std::pair<const std::__cxx11::basic_string<char>, int>&)’
353 | *__result = *__first;
| ~~~~~~~~~~^~~~~~~~~~
In file included from /usr/include/c++/12/bits/stl_algobase.h:64:
/usr/include/c++/12/bits/stl_pair.h:185:12: note: ‘std::pair<const std::__cxx11::basic_string<char>, int>& std::pair<const std::__cxx11::basic_string<char>, int>::operator=(const std::pair<const std::__cxx11::basic_string<char>, int>&)’ is implicitly declared as deleted because ‘std::pair<const std::__cxx11::basic_string<char>, int>’ declares a move constructor or move assignment operator
那是因为 std::pair 只实现了两个复制函数,只支持 key/value 的可复制/移动进行限制,默认的复制赋值函数被删除 。
__pair_base &operator=(const __pair_base &) = delete;
pair &operator=(
__conditional_t<
__and_<is_copy_assignable<_T1>, is_copy_assignable<_T2>>::value,
const pair &, const __nonesuch &>
__p) {
first = __p.first;
second = __p.second;
return *this;
}
pair &operator=(
__conditional_t<
__and_<is_move_assignable<_T1>, is_move_assignable<_T2>>::value,
pair &&, __nonesuch &&>
__p) noexcept(__and_<is_nothrow_move_assignable<_T1>,
is_nothrow_move_assignable<_T2>>::value) {
first = std::forward<first_type>(__p.first);
second = std::forward<second_type>(__p.second);
return *this;
}
要实现 std::map 的复制也很简单,只需要对迭代器使用 std::inserter 进行一下包装即可使用,在 inserter 内部调用 insert 来完成插入.
std::map<std::string, int> m1{{"lebron", 6}, {"tom", 2}};
std::map<std::string, int> m2;
// 错误的,first 类型为 const,不可复制
// std::copy(m1.begin(), m1.end(), m2.begin());
// 正确操作
std::copy(m1.begin(), m1.end(), std::inserter(m2, m2.begin()));
最后此篇关于迭代器的一些简单理解的文章就讲到这里了,如果你想了解更多关于迭代器的一些简单理解的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
如果您有超过 1 个具有相同类名的(动态)文本框,并使用 jquery 循环遍历每个所述文本框,您是否可以假设每次选择文本框的顺序都是相同的? 示例: 文本框 1 值 = 1文本框 2 值 = 2文本
有人知道为什么这段代码无法顺利运行吗?它似乎不喜欢使用yield关键字进行迭代:我正在尝试从任何级别的列表或字典中挖掘所有数字(对列表特别感兴趣)。在第二次迭代中,它找到 [2,3] 但无法依次打印
我关于从 mysql 数据库导出数据并将其保存到 Excel 文件(多表)的创建脚本。我需要让细胞动态基因化。该脚本正确地显示了标题,但数据集为空。当我“回显”$value 变量时,我检查了数据是否存
我正在尝试在 Python 中运行模拟,由此我绘制了一个数组的随机游走图,给定了两个变量参数的设定水平。 但是,我遇到了一个问题,我不确定如何迭代以便生成 250 个不同的随机数以插入公式。例如我已经
我是学习 jquery 的新手,所以如果这是一个相对简单的问题,我深表歉意。我有一个 ID 为 ChartstoDisplay 的 asp.net 复选框列表。我正在尝试创建 jquery 来根据是否
我正在尝试根据在任意数量的部分中所做的选择找出生成有效案例列表的最佳方法。也许它不是真正的算法,而只是关于如何有效迭代的建议,但对我来说这似乎是一个算法问题。如果我错了,请纠正我。实现实际上是在 Ja
如果我使用 sr1 为 www.google.com 发送 DNSQR,我会收到几个 DNSRR(s) 作为回复,例如(使用 ans[DNSRR].show() 完成): ###[ DNS Resou
假设有这样一个实体类 @Entity public class User { ... public Collection followers; ... } 假设用户有成千上万的用户关注者。我想分页..
这个问题已经有答案了: 已关闭11 年前。 Possible Duplicate: Nested jQuery.each() - continue/break 这是我的代码: var steps =
我刚从 F# 开始,我想遍历字典,获取键和值。 所以在 C# 中,我会说: IDictionary resultSet = test.GetResults; foreach (DictionaryEn
我知道已经有很多关于如何迭代 ifstream 的答案,但没有一个真正帮助我找到解决方案。 我的问题是:我有一个包含多行数据的txt文件。 txt 文件的第一行告诉我其余数据是如何组成的。例如这是我的
我有 12 个情态动词。我想将每个模态的 .modal__content 高度与 viewport 高度 进行比较,并且如果特定模态 .modal__content 高度 vh addClass("c
在此JSFiddle (问题代码被注释掉)第一次单击空单元格会在隐藏输入中设置一个值,并将单元格的背景颜色设置为绿色。单击第二个空表格单元格会设置另一个隐藏输入的值,并将第二个单元格的背景颜色更改为红
这是一个非常具体的问题,我似乎找不到任何特别有帮助的内容。我有一个单链表(不是一个实现的链表,这是我能找到的全部),其中节点存储一个 Student 对象。每个 Student 对象都有变量,尽管我在
有没有办法迭代 IHTMLElementCollection? 比如 var e : IHTMLLinkElement; elementCollection:IHTMLElementCollect
我正在尝试用 Java 取得高分。基本上我想要一个 HashMap 来保存 double 值(因此索引从最高的 double 值开始,这样我更容易对高分进行排序),然后第二个值将是客户端对象,如下所示
我想在宏函数中运行 while/until 循环,并限制其最大迭代次数。我找到了如何在“通常”sas 中执行此操作: data dataset; do i=1 to 10 until(con
Iterator iterator = plugin.inreview.keySet().iterator(); while (iterator.hasNext()) { Player key
晚上好我有一个简单的问题,我警告你我是序言的新手。假设有三个相同大小的列表,每个列表仅包含 1、0 或 -1。我想验证对于所有 i,在三个列表的第 i 个元素中,只有一个非零。 此代码针对固定的 i
我在 scheme 中构建了一个递归函数,它将在某些输入上重复给定函数 f, n 次。 (define (recursive-repeated f n) (cond ((zero? n) iden
我是一名优秀的程序员,十分优秀!