Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.

I want to create a dynamic array of a specific object that would also support adding new objects to the array.

I'm trying to solve this as part of an exercise in my course. In this exercise we are not supposed to use std::vector.

For example, let's say I have a class named Product and declare a pointer:

Products* products;

then I want to support the following:

products = new Product();

/* code here... */

products[1] = new Product(); // and so on...

I know the current syntax could lead to access violation. I don't know the size of the array in advance, as it can change throughout the program.

The questions are:

  1. How can I write it without vectors?

  2. Do I have to use double pointers (2-dimension)?

  3. Every time I want to add a new object, do I have to copy the array to the new array (with +1 size), and then delete the array?

share|improve this question
1  
What's wrong with using vectors? –  OldProgrammer Jan 12 at 12:33
6  
I suggest you use the std::vector class: it is the standard dynamic array in C++. –  Arrigo Jan 12 at 12:34
    
I'm trying to solve exercise in my course. In this exercise we are not supposed to you vectors. –  orohev Jan 12 at 12:36
1  
@orohev What does that mean? I don't see it as a valid statement in English. –  infgeoax Jan 12 at 12:37
    
Your question lacks of precision. 1) what do you mean by "without vectors" ? using "std::vector< >" or using array "Product*" 2) "products = new Product()" should not be "... = new Products()" ? –  hlide Jan 12 at 13:03

5 Answers 5

  1. You should not write this without std::vector. If you for some reason need to, your copying with every resize is by far the easiest option.
  2. I do not see how that would help. (I.e. no)
  3. As mentioned above, this is by far the easiest method if you cannot use std::vector. Everything else would be (partially) reinventing one standard library container or the other, which is hard.
share|improve this answer
  1. You have to use your own memory memory management, i.e. more specifically wrt your other (related) questions:

  2. No, if you have a contiguous allocated chunk of memory where your data lives in.

  3. Yes, if 2. is your desired implementation method. However, if you don't want to use a large memory chunk, you have to use a (double) linked list which does not require you to copy the whole array every time.
share|improve this answer
    
So, If I understood correctly, the best way to implement it, is using a linked list? –  orohev Jan 12 at 12:43
    
No, this is not what I've said. The implementation depends on what you want. Your task can be accomplished by both a linked list, or with contiguously allocated memory. –  Sebastian Dressler Jan 12 at 12:45

I see people already answered your specific questions, so I'll answer a more general answer.

You must implement a way to do it by yourself, but there are lots of Abstract Data Types that you can use, as far as I can see the simplest would be a linked list, such as the following:

class ProductNode
{
    public:
        ProductNode() : _data(NULL), _next(NULL)
        {
        }
        void setProduct(Product* p); //setter for the product pointer
        {
            this->_data = p;
        }
        Product getProduct(); //getter for the product pointer
        {
            return *(this->_data);
        }
        void addNext(); //allocate memory for another ProductNode in '_next'
        {
            if(!next)
            {
                  this->_next = new ProductNode();
            }
        }
        ProductNode* getNext(); //get the allocated memory, the address that is in '_next'
        {
             return this->_next;
        }
        ~ProductNode(); //delete every single node from that node and forward, it'll be recursive for a linked list
    private:
        Product* _data;
        ProductNode* _next;
}

Declare a head variable and go from there. Of course that most of the functions here should be implemented otherwise, it was coded quickly so you could see the basics that you need for this assignment.

That's one way. Also you can make your own data type. Or use some others data types for abstraction of the data.

share|improve this answer

What you probably should do (i.e. what I believe you're expected to do) is write your own class that represents a dynamic array (i.e. you're going to reinvent parts of std::vector.)
Despite what many around here say, this is a worthwhile exercise and should be part of a normal computer science curriculum.

  1. Use a dynamically allocated array which is a member of your class.
  2. If you're using a dynamically allocated array of Product*, you'll be storing a Product**, so yes, in a way. It's not necessary to have "double pointers" for the functionality itself, though.
  3. Technically no - you can allocate more than necessary and only reallocate and copy when you run out of space. This is what vector does to improve its time complexity.
    Expanding for each element is a good way to start though, and you can always change your strategy later.
    (Get the simple way working first, get fancy if you need to.)

It's probably easiest to first implement an array of int (or some other basic numerical type) and make sure that it works, and then change the type of the contents.

share|improve this answer

I suppose by "Products *products;" you mean "Products" is a vector-like container.

1) How can I write it without vectors?

As a linked list. Instantiating a "Products products" will give you an empty linked list. Overriding the operator[] will insert/replace the element in the list. So you need to scan the list to find the right place. If several elements are missing until you got the right place, you may need to append those "neutral" elements before your element. Doing so, through "Product *products" is not feasible if you plan to override the operator[] to handle addition of elements, unless you declare "Products products" instead

2) Do I have to use double pointers (2-dimension)?

This question lacks of precision. As in "typedef Product *Products;" then "Products *products" ? as long as you maintained a " * " between "Products" and "products", there is no way to override operator[] to handle addition of element.

3) Every time I want to add a new object, do I have to copy the array to the new array (with +1 size), and then delete the array?

If you stick with array, you can use a O(log2(n)) time reallocation, by simply growing twice the array size (and supposedly you have a zero-terminal or a count embedded). Or just use a linked list instead to avoid any copy of all elements before adding an element.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.