Dynamic array implementation using void pointers

Question

I'd like to implement something like below:

struct MyArray {
    void* Elements;
    int Capacity;
    int ElementsCount;
    size_t ElementSize;

    //methods
    void AddElement(void* item);
    //...
};

void* Elements should be pointer to items of any type. Every element should have particular size (ElementSize variable) and AddElement(void*) method should add item to existing array. The problem is that I can't do pointer arythmetic with my Array, I know I need to use casting every time I want to use it but I completely don't know how to do it. And I know template would be better solution for it, but in this case I'd like to practise with pointers :)

Thanks for help in advance.

Is this homework, or why don't you just use the container classes provided by the standard library? — Axel
– Axel, Commented Oct 22, 2012 at 10:53
Sorry if I'm missing something but is there a reason that you can't make 'any type' be derived from a base class and simply use polymorphism? That's a key benefit of the language & it seems like your trying to reinvent it. — Component 10
– Component 10, Commented Oct 22, 2012 at 10:56
I suspect that this need to be a pure C dynamic storage container which can be used on processors which aren't supported with C++ compiler or C++ is too large. — pro_metedor
– pro_metedor, Commented Oct 22, 2012 at 10:58
I don’t see what’s wrong with std::vector<boost::any>. — daknøk
– daknøk, Commented Oct 22, 2012 at 11:08

Luchian Grigore · Accepted Answer · 2012-10-22 10:54:00Z

2

To move the pointer around, you can do:

int* nextInt = reinterpret_cast<int*>(Elements) + 1;

This would point to the next int. You can use this technique to move around other types.

Note that this can lead to all kinds of trouble, because of different sizes of the elements.

answered Oct 22, 2012 at 10:54

Luchian Grigore

260k68 gold badges465 silver badges634 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

John Dibling Over a year ago

This assumes the thing begin pointed to is actually an int.

Luchian Grigore Over a year ago

@JohnDibling I was actually implying that you can use any data type instead of int. (guess I should have been more clear)

Yam Marcovic Over a year ago

I was just about to post this almost word for word, when I saw a new answer was posted. Reloaded, and voila. :) Though it's possible to map to char* and keep a list of sizes that corresponds to the actual list, and every time increment by +1 while looping over values from the sizes list. Inefficient, but good practice nonetheless.

CashCow · Accepted Answer · 2012-10-22 11:14:02Z

0

Yes, you cannot do pointer arithmetic on void*, you will have to cast to char* to do the arithmetic e.g. something like:

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

Note that you need static_cast to cast from void* to char* and you do not need to explicity cast at all back to void* which is why I can assign it to insertionPoint.

edited Oct 22, 2012 at 11:14

answered Oct 22, 2012 at 10:56

CashCow

31.6k5 gold badges65 silver badges97 bronze badges

Comments

pro_metedor · Accepted Answer · 2012-10-22 11:00:00Z

0

I would pursue this way:

Create your array specific iterator, like STL ones.
Overload operators for your iterators

Iterators will benefit your array as you may have generic algorithms that iterate through your array without knowledge of storage type needed.

answered Oct 22, 2012 at 11:00

pro_metedor

1,17610 silver badges17 bronze badges

Comments

progician · Accepted Answer · 2012-10-22 11:17:54Z

I don't see how templates and pointers are mutually exclusive, I think this is the sort of situation why people use them in the first place. With a template you give a type to your pointers and problem is sorted.

On the other hand, if you avoid templates completely, you will need the size of the type. Say, the way how CashCow handles the problem:

void MyArray::AddElement( void * item )
{
    auto insertionPoint = static_cast<char *>(Elements) + (ElementSize * ElementsCount );
    memcpy( insertionPoint, item, ElementSize );
    ++ElementsCount;
}

Yet, you're not finished with it. You need to make sure that you will never exceed the pre-allocated buffer. I would modify it this way:

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

Something like this. Of course this is still not complete but gives you perhaps a clue.

Component 10 · Accepted Answer · 2012-10-22 11:58:58Z

I have to question why you'd want to do this. Unless you are doing this for academic / experimental purposes and your planning to throw it away, you're making work for yourself and are almost certain to end up with code which is more vulnerable to problems than if you used facilities that the language and STL already offer. In C, you'd probably have to do this, but with C++ you don't have to as the language support is there.

There are two aspects to what you're doing: Having elements of any type that can be used generically in some defined way and collecting those elements up together. Then first aspect can easily be acheived by polymosphism. Create an abstract base class which defines a common interface:

struct BaseElement { virtual void doSomething( ); };

Then you can derive structs from this which cover what your elements are doing:

struct DerivedElement1 : public BaseElement { void doSomething( ); };

struct DerivedElement2 : public BaseElement { void doSomething( ); };

To collect the types together, you can simply use an STL vector. It provides all of what you need as far as I can see. As a very simple example, you could do the following:

// 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 ) );

At this point you've got everything you need. Vector provides standard functionality such as begin(), end() and size() which help you to traverse the collection and run STL algorithms on it if you so wish. The fact that the collection is polymorphic means that you can run doSomething() on each element knowing it will perform only what was defined for that struct.

(I've not got acccess to a C++11 compiler so I'm sure someone will pick me up on something here. However, the same thing can easily be acheived with pre C++11 code even using raw pointers if you're careful to clear down your objects properly.)

I know this isn't the answer you directly wanted, but I just wanted to emphasise that unless you're simply trying to learn with throw away examples, it's almost always faster, shorter, safer and more reliable to use what's already there.

Collectives™ on Stack Overflow

Dynamic array implementation using void pointers

5 Answers 5

3 Comments

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

3 Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related