为什么大多数 C++ STL 库函数使用迭代器作为参数？

Question

我不清楚指针和迭代器之间的区别。谁能帮忙？提前谢谢你。

Answer 1

因为 C++ 迭代器不需要是指针，并且将迭代器作为参数可以使 C++ 用户定义自己的迭代器并能够使用 STL 算法。

例如，这是我的 toy-project B-Tree 的自定义迭代器： (https://github.com/frozenca/CLRS/blob/main/18/18_B_tree.cpp#L145)

template <bool Const>
    struct BTreeIterator {
        using difference_type = std::ptrdiff_t;
        using value_type = T;
        using pointer = std::conditional_t<Const, const T*, T*>;
        using reference = std::conditional_t<Const, const T&, T&>;
        using iterator_category = std::bidirectional_iterator_tag;

        Node* node = nullptr;
        std::size_t index;

        void Increment() {
            if (index == node->key.size()) {
                return;
            }
            if (node->child.empty()) {
                ++index;
                while (node->parent && index == node->key.size()) {
                    index = node->index;
                    node = node->parent;
                }
            } else {
                node = node->child[index + 1]->LeftmostLeaf();
                index = 0;
            }
        }

        void Decrement() {
            if (!node->leaf) {
                node = node->child[index]->RightmostLeaf();
                index = node->key.size() - 1;
            } else {
                if (index > 0) {
                    --index;
                } else {
                    while (node->parent && node->index == 0) {
                        node = node->parent;
                    }
                    if (node->index > 0) {
                        index = node->index - 1;
                        node = node->parent;
                    }
                }
            }
        }

        BTreeIterator() = default;

        BTreeIterator(Node* node, std::size_t i) : node {node}, index {i} {
            assert(node && i <= node->key.size());
        }

        reference operator*() const {
            return node->key[index];
        }

        pointer operator->() const {
            return node->key.begin() + index;
        }

        BTreeIterator& operator++() {
            Increment();
            return *this;
        }

        BTreeIterator operator++(int) {
            BTreeIterator temp = *this;
            Increment();
            return temp;
        }

        BTreeIterator& operator--() {
            Decrement();
            return *this;
        }

        BTreeIterator operator--(int) {
            BTreeIterator temp = *this;
            Decrement();
            return temp;
        }

    };


// ...

using iterator = BTreeIterator<false>;
using const_iterator = BTreeIterator<true>;
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;

由于我提供了iterator_category、difference_type、value_type、pointer、reference，所以classBTreeIterator可以用于为我的 B-Tree.

应用 range-for 循环、std::copy、std::accumulate 等

Answer 2

I not getting a clear difference between pointers and iterators.

迭代器是一个类型的概念，其实例可以指向一个对象，并且可以递增以指向下一个同级元素。

指向同一个容器的一对迭代器表示容器内的一系列对象。

指针可以指向一个对象，如果指向的对象是数组的一个元素，那么指针可以递增以指向数组的下一个元素。指针是数组类型迭代器的一个例子。对于其他容器类型，除了指针还有其他迭代器类型。

Why most of C++ STL library functions use iterator as parameter?

这些函数是对对象序列进行运算的算法的实现，无论保存对象的数据结构如何，它们在根本上都是相同的。

如果你有一个对象数组，你可以通过将一对指针传递到数组中的一系列对象来使用该函数，如果你有另一个容器，那么你可以使用一对迭代器指向该容器的元素。

能够使用任何（有限制的）迭代器调用函数，允许我们将这些函数用于任何容器。

Answer 3

"STL" aka standard template library was largely proposed by Alexander Stephanov in the '80-'90. The iterator (design) pattern在当时还是很新很流行的。

你一定想过当时的电脑还不是很强大，所以性能是个问题。编译时间也很长。在此之前，内存寻址是通过指针算法完成的。但这既不安全（容易出错）又受限，因为并非所有对象（即 vector<bool> 中的位）都可以使用指针访问。迭代器形成一个抽象层。然而，当时人们已经在抱怨这个非常小的层，因为它会增加已经很长的编译时间。因此，更复杂的解决方案甚至不可行。

STL 的优点在于算法组合。（它们一起有意形成稳定排序的部分。）

迭代器也提供一些控制，例如

std::copy(vec.rbegin()+1, vec.rend()-1, std::back_inserter(other));

处理 vec 中的元素，除了第一个和最后一个，以相反的顺序插入它们在 other 的后面。

为什么大多数 C++ STL 库函数使用迭代器作为参数？

Why most of C++ STL library functions use iterator as parameter?

c++

c++14

c++17