对于具有线性存储的容器,是否可以使用原始指针代替具有STL算法的迭代器？

Question

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

使用自定义迭代器的实例

在这样做时,我发现我只能将原始指针传递给STL算法,它们似乎工作得很好.这是没有任何迭代器的示例:

#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. 如果这种方法总是有效的话,我正在做什么的负面问题是什么？首先,我可以看到我打破了数据封装.

Answer 1

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

在以下情况下,您可以实现"真实"迭代器:

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

我只说这个最后一个优势非常值得写一个简单的包装类.如果你不通过使不同类型的东西有不同的类型来利用C++的类型系统,你不妨切换到Javascript :-)

Answer 2

1. 是.请参阅有效STL,第16项,它使用线性存储容器进行演示,您可以简单地获取项目的地址并使用该指针,就好像它指向一个简单的数组一样.
2. 我想你回答了自己的问题 - 你可能不应该,如果你知道简单数组就是你所需要的.
3. 可能最大的问题就是 - 打破数据封装.考虑一个抽象(如显式迭代器类型)是否会为您购买任何东西而不是成本.