c++ - C+ 自定义迭代器？

Question

我一直在尝试为一个简单的类实现一个自定义的前向迭代器。这个类是固定数组的一个非常糟糕的抽象(不幸的是我不能改变它)。只能使用索引访问元素。

template <class T>
struct data
{
    static const size_t MAX_BUFFER{ 50 };
    T* buffer_[MAX_BUFFER] = {};
    int currpos_ = 0;

    void insert(T *value) {
        if (currpos_ < MAX_BUFFER-1)
            buffer_[currpos_++] = value;
    }

    T** at(int i) {
        if (i >= currpos_)
            return NULL;
        return &buffer_[i];
    }

    ~data() {
        for (int i=0; i<currpos_; ++i)
            delete buffer_[i];
    }

    int entries() const { return currpos_; }

    struct iterator : std::iterator<std::forward_iterator_tag, T*>
    {
        using reference = typename std::iterator<std::forward_iterator_tag, T*>::reference;
        using pointer = typename std::iterator<std::forward_iterator_tag, T*>::pointer;

        iterator(data<T> *d, int start) : p{ d }, index{ start } {}
        iterator operator++() { if (index < p->entries()) ++index; return *this; }
        friend bool operator==(const iterator &d1, const iterator &d2) { return d1.p == d2.p && d1.index == d2.index; }
        friend bool operator!=(const iterator &d1, const iterator &d2) { return !(d1== d2); }
        reference operator*() { return *(p->at(index)); }
        pointer operator->() { return p->at(index); }
        data<T> *p;
        int index;
    };

    iterator begin() { return iterator(this, 0); }
    iterator end() { return iterator(this, entries()); }
};

我面临的问题是，通过这个接口(interface)，我可以使用大多数 STL 标准算法，如 for_each、transform、find_if。例如，假设 d 已经用 new{2}, new{3}, new{4}, new{14}, new{-4}, new{-44}, new{42} 这个代码

for (auto &i : d) std::cout <<*i <<" "; std::cout <<std::endl;

auto res=std::find_if(d.begin(), d.end(), [](auto &i) { return *i == -44;});
if (res != d.end())
    std::cout <<**res <<std::endl;

std::transform(d.begin(), d.end(), d.begin(), [](auto &i) {*i *= 2; return i;});
for (auto &i : d) std::cout <<*i <<" "; std::cout <<std::endl;

会正确显示

2 3 4 14 -4 -44 42
-44
4 6 8 28 -8 -88 84

我面临的问题是算法 std::remove_if() 及其排列元素的方式。我添加了一个类似于 vector::erase: 的成员函数:

void remove_range(iterator begin, iterator end)
{
    size_t d=std::distance(begin, end);
    currpos_ -= d;
}

这当然也应该删除与已删除元素关联的内存。在这个例子中调用它时:

auto new_end = std::remove_if(d.begin(), d.end(), [](auto &r) { return *r > 3; });
d.remove_range(new_end, d.end());

valdring 一直告诉我有 3 个内存泄漏(这是有道理的:有 3 个元素 >= 3)。我试图在 remove_range() 中添加一个删除操作，但是这个解决方案不起作用(程序崩溃)。在调试 session 期间，我打印出 d 的内部状态:

(gdb) p d
$1 = {static MAX_BUFFER = <optimized out>, buffer_ = {0x603010, 0x603030, 0x603050, 0x603070, 0x603090, 0x6030b0, 0x6030d0, 0x0 <repeats 43 times>}, currpos_ = 7}
(gdb) p d
$2 = {static MAX_BUFFER = <optimized out>, buffer_ = {0x603010, 0x603030, 0x603090, 0x6030b0, 0x603090, 0x6030b0, 0x6030d0, 0x0 <repeats 43 times>}, currpos_ = 7}

我可以看到 removed_if() 基本上移动了三个元素(大于 3 个)，我认为我有泄漏的原因是因为应该删除的元素被移动了，所以原始指针永远泄漏了。

我的问题是:这里有什么办法可以避免这种泄漏吗？我需要定义一些额外的移动构造函数吗？

Answer 1

您看到的泄漏是由 remove_range 实现引起的，而不是迭代器。

I have added a member function similar to vector::erase ... which of course should also remove the memory associated to the deleted elements.

但事实并非如此。您在容器析构函数中对元素调用 delete，但在 erase 方法中没有对项目的 delete。