我正在使用C++数组列表,每个数组都在一个对象中,并希望拆分其中的一些。这些是动态分配的。
我想在恒定时间内进行拆分,因为理论上是可能的: 从
[ pointer, size1 ]
自
[ pointer, size2 ]; [ other array ]; [ pointer + size2, size1-size2 ]
(+ other data each time)
我尝试使用malloc
并简单地创建一个随大小递增的新指针。正如预期的那样,由于自动释放内存,我遇到了错误。
我尝试从第二个地址开始realloc
,但正如"malloc
和calloc
有什么区别"一样,这个网站上已经告诉我这是不可能的。
有没有办法避免重新复制第二部分并正确定义指针?有一个线性成本,我知道我可以有恒定的时间是令人沮丧的。
class TableA
{
public:
(constructor)
void divide(int size); // the one i am trying to implement
(other, geteur, seteur)
private
Evenement* _el;
vector<bool>** _old;//said arrays
int _size;
}
没什么复杂的
基本上,malloc 库无法处理错误地分配内存块然后释放它的切片。
你可以做你想做的事,但你只能在最后使用 malloc 交给你的原始指针一次释放内存。
例如
int* p = malloc(9 * sizeof(int));
int* q = p + 3;
int* r = p + 6;
// Now we have three pointers to three arrays of three integers.
// Do stuff with p, q, r
free(p); // p is the only pointer it is valid to free.
顺便说一下,如果这真的是关于C++,您可能可以使用标准C++数据结构。
我认为你不能通过跟踪指针和长度来释放动态数组的一部分。但是,您可以通过创建一个新类来管理起始数组,根据需要分配它并由 std::shared_ptr 管理它来伪造这一点。
您只需返回一个类,其中包含内存shared_ptr、指向第一个元素的纯指针和数组大小。当当前 Array 类超出范围时,shared_ptr会递减,当不再使用内存切片时,将释放内存。
不过,您需要小心这一点,因为可能有多个对象引用相同的内存,但是有一些方法可以解决这个问题(例如,在用布尔值拆分后将原始对象标记为无效(。
[编辑] 下面是这个想法的一个非常基本的实现。split()
运算符可以很容易地实现 2 个slice()
操作。我不确定你想如何在上面的例子中实现这一点,因为我不确定你如何管理你的vector<bool> **
,但是如果你想要拆分你的vector<bool>
的可能性,你可以实例化一个ShareVector<bool>
,或者如果你有一个vector<bool>
数组,你做一个SharedVector<vector<bool>>
。
#ifndef __SharedVector__
#define __SharedVector__
#include <memory>
#include <assert.h>
template <typename T>
class SharedVector {
std::shared_ptr<T> _data;
T *_begin;
size_t _size;
// perhaps add size_t capacity if need for limited resizing arises.
public:
SharedVector<T>(size_t const size)
: _data(std::shared_ptr<T>(new T[size], []( T *p ) { delete[] p; })), _begin(_data.get()), _size(size)
{}
// standard copy and move constructors work fine
// pass shared_ptr by reference to avoid unnecessary refcount changes
SharedVector<T>(std::shared_ptr<T> &data, T *begin, size_t size)
: _data(data), _begin(begin), _size(size)
{}
T& operator[] (const size_t nIndex) {
assert(nIndex < _size);
return _begin[nIndex];
}
T const & operator[] (const size_t nIndex) const {
assert(nIndex < _size);
return _begin.get()[nIndex];
}
size_t size(){
return _size;
}
SharedVector<T> slice(size_t const begin, size_t const end) {
assert(begin + end < _size);
return SharedVector<T>(_data, _begin + begin, end - begin);
}
T *begin() {
return _begin;
}
T *end() {
return _begin + _size;
}
};
#endif
我认为malloc
和创建新指针的想法很好。但是我认为您需要手动释放内存。
也许你可以使用 std::copy
.
int* p = (int*)malloc(sizeof(int) * 5);
for (int i = 0; i < 5; i++)
p[i] = i;
for (int i = 0; i < 5; i++)
std::cout << p[i];
// tmp will hold 3 values
// p2 will hold 2 values
// so we want to copy first 3 into tmp
// and last 2 into p2
int tmp[3];
std::copy(p, p+3, tmp);
for (int i = 0; i < 3; i++)
std::cout << tmp[i];
int p2[2];
std::copy(p+3, p+5, p2);
for (int i = 0; i < 2; i++)
std::cout << p2[i];
// get rid of original when done
free(p);
输出:
0123401234
这个问题相对不清楚
但根据您的主题
拆分动态分配的数组,无需线性时间复制
我建议您使用链表而不是数组,您不需要复制任何东西(因此除非您想删除其中一个项目,否则无需释放任何内容(,操作指针足以拆分链表