对于具有线性存储的容器,可以使用原始指针而不是具有 STL 算法的迭代器吗?
我有一个自定义向量容器,它在内部存储项目一个线性数组.昨晚,我试图为我的类实现自定义迭代器,以便能够将它们与 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;
}
没有迭代器的实例
我的问题如下:
- 这是否总是适用于具有线性存储的容器?我知道这不适用于例如链表.
- 如果它们确实在这种情况下工作,我为什么还要经历实现迭代器的麻烦呢?我知道迭代器如何泛化我的代码等等,但是如果这个简单的数组 是 我所需要的,那么我看不到重点.
- 如果这种方法始终有效,我正在做的事情有哪些负面问题?一方面,我可以看到我正在破坏数据封装.
- Does this always work for containers that have linear storage? I know that this would not work for linked-lists for example.
- 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.
- 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* 迭代器;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 amy_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 :-)
相关文章