我一直在尝试为一个简单的类实现一个自定义的前向迭代器。这个类是固定数组的一个非常糟糕的抽象(不幸的是我无法更改它)。元素只能通过索引来访问。
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),我认为泄漏的原因是因为元素(应该被删除)被移动,因此原始指针永远泄漏。
我的问题是:有什么办法可以避免这里的泄漏吗?我需要定义一些额外的移动构造函数吗?
您看到的泄漏是由
remove_range
实现引起的,而不是迭代器。
我添加了一个类似于vector::erase的成员函数... 当然,这也应该删除与已删除元素相关的内存。
但事实并非如此。您对容器析构函数中的元素调用
delete
,但擦除方法中的项目没有 delete
。
remove_if
收集范围开头不应删除的所有元素。为此,它可以使用交换或移动。正如您的调试输出所示,它似乎使用移动,这似乎与复制相同(这对于简单的数据结构(例如指针)是有意义的)。您的调试器输出显示如下:第二次打印时,指针 0x603090 出现两次。因此,当您在 remove_range
之后调用 remove_if
(并且将 remove_range
修改为实际调用删除)时,您对已经复制到前面的指针值调用删除,并且稍后您可能会再次对它们调用删除,当您释放范围的前部时。
另一方面,一些被删除的指针值确实丢失了,因此你无法对它们调用delete,从而导致valgrind中的内存泄漏。
partition
而不是 remove_if
。
编辑:
remove_if
稳定,partition
不稳定,所以这可能是一个问题。还有stable_partition
,但是那需要双向迭代器,前向迭代器是不够的。也许你可以改变你的迭代器,使它们是双向的?
我想我终于找到了一个至少对我来说有意义的答案。 这取自 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).
我找到的解决问题的唯一方法是
使用 std::remove_if() 的一个版本,在调用 std::move() 之前删除元素。在我的例子中,我只需要改变
auto new_end = std::remove_if(d.begin(), d.end(), [](auto &r) { return (*r > 3); });
进入(具有相同的remove_range实现)
auto new_end = std::remove_if(d.begin(), d.end(),
[](auto &r) {
bool res = (*r > 3);
if (res) delete r;
return res; });
我用 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;