对于具有线性存储的容器，可以使用原始指针代替带有 STL 算法的迭代器吗? [英] Can raw pointers be used instead of iterators with STL algorithms for containers with linear storage?

问题描述

我有一个自定义向量容器，它在内部存储一个线性数组项.昨晚，我试图为我的类实现自定义迭代器，以便能够将它们与 STL 算法一起使用.我取得了一些成功，你可以在这里看到:

I have a custom vector container that internally stores item a linear array. Last night, I was trying to implement custom iterators for my class to be able to use them with STL algorithms. I have had some success that you can see in here:

自定义迭代器的实例

这样做时，我发现我只能将原始指针传递给 STL 算法，而且它们似乎工作正常.这是没有任何迭代器的示例:

While doing so, I discovered I can merely pass raw pointers to STL algorithm and they just seem to work fine. Here's the example without any iterators:

#include <cstddef>
#include <iostream>
#include <iterator>
#include <algorithm>

template<typename T>
class my_array{
    T* data_;
    std::size_t size_;

public:

    my_array()
        : data_(NULL), size_(0)
    {}
    my_array(std::size_t size)
        : data_(new T[size]), size_(size)
    {}
    my_array(const my_array<T>& other){
        size_ = other.size_;
        data_ = new T[size_];
        for (std::size_t i = 0; i<size_; i++)
            data_[i] = other.data_[i];
    }
    my_array(const T* first, const T* last){
        size_ = last - first;
        data_ = new T[size_];

        for (std::size_t i = 0; i<size_; i++)
            data_[i] = first[i];
    }

    ~my_array(){
        delete [] data_;
    }
    const my_array<T>& operator=(const my_array<T>& other){
        size_ = other.size_;
        data_ = new T[size_];
        for (std::size_t i = 0; i<size_; i++)
            data_[i] = other.data_[i];
        return other;
    }
    const T& operator[](std::size_t idx) const {return data_[idx];}
    T& operator[](std::size_t& idx) {return data_[idx];}
    std::size_t size(){return size_;}

    T* begin(){return data_;}
    T* end(){return data_+size_;}
};

template<typename T>
void print(T t) {
    std::cout << t << std::endl;
}

int main(){


    typedef float scalar_t;
    scalar_t list [] = {1, 3, 5, 2, 4, 3, 5, 10, 10};
    my_array<scalar_t> a(list, list+sizeof(list)/sizeof(scalar_t));

    // works!
    for (scalar_t* it = a.begin(), *end = a.end();
         it != end; ++it)
        std::cout << ' ' << *it;
    std::cout << std::endl;

    // works!
    std::for_each(a.begin(), a.end(), print<scalar_t>);
    std::cout << std::endl;

    // works!
    my_array<int> b(a.size());
    std::copy(a.begin(), a.end(), b.begin());

    // works!
    scalar_t* end = std::remove(a.begin(), a.end(), 5);
    std::for_each(a.begin(), end, print<scalar_t>);
    std::cout << std::endl;

    // works!
    std::random_shuffle(a.begin(), end);
    std::for_each(a.begin(), end, print<scalar_t>);
    std::cout << std::endl;

    // works!
    std::cout << "Counts of 3 in array = " << std::count(a.begin(), end, 3) << std::endl << std::endl;

    // works!
    std::sort(a.begin(), end);
    std::for_each(a.begin(), end, print<scalar_t>);
    std::cout << std::endl;

    // works!
    if (!std::binary_search(a.begin(), a.end(), 5))
        std::cout << "Removed!" << std::endl;

    return 0;
}

没有迭代器的实例

我的问题如下:

1. 这是否总是适用于具有线性存储的容器?例如，我知道这不适用于链表.
2. 如果它们在这种情况下确实有效，我为什么还要经历实现迭代器的麻烦?我知道迭代器如何概括我的代码等等，但是如果这个简单的数组就是我所需要的一切，那么我就看不到重点了.
3. 如果这种方法始终有效，我正在做的事情有哪些负面问题?一方面，我可以看到我正在破坏数据封装.

1. Does this always work for containers that have linear storage? I know that this would not work for linked-lists for example.
2. If they do work in this situation, why should I ever go through the hassle of implementing iterators anyway? I know how iterators generalize my code and whatnot, but if this simple array is all I ever need then I don't see the point.
3. What are the negative issues of what I'm doing if this approach would always work? For one thing, I can see I'm breaking data encapsulation.

推荐答案

基于运算符重载的迭代器的特性之一是指针已经是随机访问迭代器.在 STL 的早期，这是一个巨大的设计胜利，因为它可以更轻松地将算法与现有代码一起使用(并使程序员更熟悉界面).包裹一个数组是完全合理的，添加 typedef T* iterator;typedef const T* const_iterator，从你的 begin() 和 &array[size] 返回 &array[0]从您的 end() 开始，然后将您的容器与任何基于迭代器的算法一起使用.正如您已经意识到的，这适用于任何元素在内存中是连续的容器(例如数组).

One of the features of iterators being based on operator-overloading, is that pointers are already random-access iterators. This was a big design win in the early days of STL, as it made it easier to use algorithms with existing code (as well as making the interface more familiar to programmers). It's perfectly reasonable to wrap an array, add typedef T* iterator; typedef const T* const_iterator, return &array[0] from your begin() and &array[size] from your end(), and then use your container with any iterator-based algorithm. As you already realise, this will work for any container where elements are contiguous in memory (such as an array).

如果满足以下条件，您可能会实现真正的"迭代器:

You might implement 'real' iterators if:

• 您有一个不同形状的容器(例如树或列表)；
• 您希望能够在不使迭代器失效的情况下调整数组大小；
• 您想在迭代器使用中添加调试检查，例如检查迭代器是否在失效或容器被删除后使用，或进行边界检查；
• 您想引入类型安全性，并确保人们不会意外地将任意 T* 分配给 my_array::iterator.

• You have a different-shaped container (such as a tree or list);
• You want to be able to resize the array without invalidating the iterators;
• You want to add debugging checks to your iterator use, for example to check if the iterator is used after being invalidated or after the container has been deleted, or to bounds-check;
• You want to introduce type-safety, and make sure people can't accidentally assign an arbitrary T* to a my_array::iterator.

我想说仅凭最后一个优势就值得为其编写一个简单的包装类.如果你不利用 C++ 的类型系统让不同类型的东西有不同的类型，你不妨切换到 Javascript :-)

I'd say this last advantage alone is well worth writing a trivial wrapper class for. If you don't take advantage of C++'s type system by making different kinds of thing have different types, you might as well switch to Javascript :-)

这篇关于对于具有线性存储的容器，可以使用原始指针代替带有 STL 算法的迭代器吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！