C++自定义迭代器?

eoigrqb6  于 9个月前  发布在  其他
关注(0)|答案(3)|浏览(99)

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

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()); }
};

字符串
我面临的问题是,通过这个接口,我可以使用大多数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()中添加删除操作,但这个解决方案不起作用(程序崩溃)。在调试会话期间,我打印出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的元素),我认为我有泄漏的原因是因为应该被删除的元素被移动了,所以原始指针永远泄漏了。
我的问题是:有什么方法可以避免这种泄漏吗?我需要定义一些额外的移动构造函数吗?

dddzy1tm

dddzy1tm1#

您看到的泄漏是由remove_range实现引起的,而不是迭代器。
我添加了一个类似vector::erase的成员函数.当然,它也应该删除与已删除元素相关的内存。
但它没有。你在容器析构函数中对元素调用delete,但在erase方法中没有对项目调用delete

kgsdhlau

kgsdhlau2#

remove_if收集所有不应该在范围开始时删除的元素。为此,它可以使用交换或移动。如调试输出所示,它似乎使用移动,这似乎与复制相同(这对指针等简单数据结构很有意义)。调试器输出显示如下:指针0x603090在第二次打印时出现两次。因此,当您在remove_if之后调用remove_range时,(并将remove_range修改为实际调用delete),您对已经复制到前面的指针值调用delete,当你释放范围的前半部分时,你可能会第二次调用delete。
另一方面,一些被删除的指针值确实丢失了,所以你不能对它们调用delete,导致valgrind中的内存泄漏。
最简单的修复方法可能是使用partition而不是remove_if

编辑:remove_if是稳定的,partition不是,所以这可能是一个问题。还有stable_partition,但它需要双向迭代器,前向迭代器是不够的。也许你可以改变你的迭代器,使它们是双向的?

fhg3lkii

fhg3lkii3#

我想我终于找到了一个答案,至少对我来说是有意义的。这是从http://en.cppreference.com/w/cpp/algorithm/remove中提取的,显示了std::remove_if的可能实现。

template< class ForwardIt, class T >
ForwardIt remove(ForwardIt first, ForwardIt last, const T& value)
{
    first = std::find(first, last, value);
    if (first != last)
        for(ForwardIt i = first; ++i != last; )
            if (!(*i == value))
                *first++ = std::move(*i);
    return first;
}

字符串
我的代码中有漏洞的原因是

*first++ = std::move(*i).


我找到的解决问题的方法
1.使用一个在调用std::move()之前删除元素的std::remove_if()版本。

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


into(使用相同的remove_range实现)

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


1.使用std::partition()并为需要删除的范围中的每个元素手动调用delete(std::partition使用std::swap)
我用std::vector重现了同样的问题:

std::vector<int*> v{new int{1}, new int{3}, new int{-10}, new int{12}};
v.erase(std::remove_if(v.begin(), v.end(), [](auto &p) { return *p > 3;}));
for (auto &i : v)
    delete i;

相关问题