Реализация динамического массива с использованием указателей void
Я хотел бы реализовать что-то вроде ниже:
struct MyArray {
void* Elements;
int Capacity;
int ElementsCount;
size_t ElementSize;
//methods
void AddElement(void* item);
//...
};
void* Elements должен быть указатель на элементы любого типа. Каждый элемент должен иметь определенный размер (ElementSize переменная) и AddElement(void*) Метод должен добавить элемент в существующий массив.
Проблема в том, что я не могу сделать арифметику указателя с моим массивом, я знаю, что мне нужно использовать приведение каждый раз, когда я хочу его использовать, но я совершенно не знаю, как это сделать.
И я знаю, что шаблон будет лучшим решением для этого, но в этом случае я хотел бы попрактиковаться с указателями 🙂
Спасибо за помощь заранее.
Решение
Да, вы не можете делать арифметику указателей на void *, вам придется приводить к char * для выполнения арифметики, например что-то вроде:
void MyArray::AddElement( void * item )
{
// verify that ElementsCount is not already Capacity and if so, reallocate or throw
void * insertionPoint = static_cast<char *>(Elements) + (ElementSize * ElementsCount );
memcpy( insertionPoint, item, ElementSize );
++ElementsCount;
}
Обратите внимание, что вам нужно static_cast приведение из void * к char *, и вам вообще не нужно преобразовывать приведение к void *, поэтому я могу назначить его для inserttionPoint.
Другие решения
Чтобы переместить указатель, вы можете сделать:
int* nextInt = reinterpret_cast<int*>(Elements) + 1;
Это будет указывать на следующее int, Вы можете использовать эту технику для перемещения по другим типам.
Обратите внимание, что это может привести к всевозможным проблемам из-за разных размеров элементов.
Я бы продолжил так:
- Создайте свой итератор для массива, например, STL.
- Операторы перегрузки для ваших итераторов
Итераторы принесут пользу вашему массиву, поскольку у вас могут быть общие алгоритмы, которые выполняют итерацию по вашему массиву без знания необходимого типа хранилища.
Я не понимаю, как шаблоны и указатели являются взаимоисключающими, я думаю, что именно в такой ситуации люди используют их в первую очередь. С помощью шаблона вы даете тип указателям, и проблема сортируется.
С другой стороны, если вы полностью избегаете шаблонов, вам потребуется размер шрифта. Скажем, как CashCow решает проблему:
void MyArray::AddElement( void * item )
{
auto insertionPoint = static_cast<char *>(Elements) + (ElementSize * ElementsCount );
memcpy( insertionPoint, item, ElementSize );
++ElementsCount;
}
Тем не менее, вы не закончили с этим. Вы должны убедиться, что вы никогда не превысите заранее выделенный буфер. Я бы изменил это так:
void MyArray::AddElement( void * item )
{
if ((Capacity + 1) < ElementSize * ElementsCount)
{
Capacity <<= 1; // Double the size of the buffer.
auto newBlock = new char[Capacity];
memcpy(Elements, newBlock, Capacity >> 1); // Copy the old data
delete Elements;
Elements = static_cast<void*>(newBlock);
}
auto insertionPoint = static_cast<char *>(Elements) + (ElementSize * ElementsCount );
memcpy( insertionPoint, item, Elementize );
++ElementsCount;
}
Что-то вроде этого. Конечно, это все еще не завершено, но дает вам, возможно, ключ к разгадке.
У меня вопрос, почему ты хочешь это сделать. Если вы не делаете это для академических / экспериментальных целей и не планируете выбрасывать это, вы делаете работу для себя и почти наверняка получите код, более уязвимый для проблем, чем если бы вы использовали средства, которые используются в языке и STL уже предлагают. В C вам, вероятно, придется делать это, но в C ++ вам не нужно, поскольку есть языковая поддержка.
Есть два аспекта того, что вы делаете: наличие элементов любого типа, которые можно использовать в общем определенным образом, и сбор этих элементов вместе. Тогда первый аспект может быть легко достигнут полимосфизмом. Создайте абстрактный базовый класс, который определяет общий интерфейс:
struct BaseElement { virtual void doSomething( ); };
Тогда вы можете извлечь из этого структуры, которые охватывают то, что делают ваши элементы:
struct DerivedElement1 : public BaseElement { void doSomething( ); };
struct DerivedElement2 : public BaseElement { void doSomething( ); };
Чтобы собрать типы вместе, вы можете просто использовать вектор STL. Это обеспечивает все, что вам нужно, насколько я вижу. В качестве очень простого примера вы можете сделать следующее:
// Convenient shorthand.
typedef std::vector< std::shared_ptr<BaseElement> > MyElements;
MyElements m;
// Create two different but commonly derived objects.
std::shared_ptr<DerivedElement1> e1(new DerivedElement1);
std::shared_ptr<DerivedElement2> e2(new DerivedElement2);
// Push them onto the collection.
m.push_back( e1.static_pointer_cast<BaseElement>( e1 ) );
m.push_back( e2.static_pointer_cast<BaseElement>( e2 ) );
На данный момент у вас есть все, что вам нужно. Вектор обеспечивает стандартную функциональность, такую как begin(), end() а также size() которые помогут вам пересмотреть коллекцию и запустить алгоритмы STL, если хотите. Тот факт, что коллекция является полиморфной, означает, что вы можете запустить doSomething() для каждого элемента, зная, что он будет выполнять только то, что было определено для этой структуры.
(У меня нет доступа к компилятору C ++ 11, поэтому я уверен, что кто-то здесь меня зацепит. Однако то же самое можно легко достичь с помощью кода до C ++ 11, даже используя необработанные указатели, если вы будьте осторожны, чтобы очистить ваши объекты должным образом.)
Я знаю, что это не тот ответ, который вы хотели получить напрямую, но я просто хотел подчеркнуть, что если вы просто не пытаетесь учиться на выброшенных примерах, почти всегда быстрее, короче, безопаснее и надежнее использовать то, что уже есть.