dynamic arrays

[??!!]

Hey guys i really need someone todo the following it's urgent:

Declare and initialize a dynamic array of rectangles. Define an array of pointers to the array of rectangles and use it as search index by area. Define two other similar indexes to facilitate search by length and width.

[Unimportant]

Rectangle * rectangles(NULL);

// You can resize this in place.
rectangles = realloc( rectangles, number_of_rects * sizeof( Rectangle ) );

free( rectangles ); // Once you're finished.
rectangles = NULL; // Just for the sake of sanity in more complex cases.

Plus, you probably want a container class to handle indexing...
Without getting into too much detail here,

You'll want Rectangle->area(), ->width(), ->length()
and in the container class you'll want some function

Rectangle * operator[] ( int area ) { return &rectangles[area]; } // which can be NULL or OOB

If you didn't really index it this way, you'll need to iterate.
That means a loop of sorts.

P.S. Feel free to use new/delete if you never resize the array, they are faster operations for single allocations.
P.P.S Indexing by area seems unwise for a number of reasons, including but not limited to wasted memory.

[deceptikon]

P.S. Feel free to use new/delete if you never resize the array, they are faster operations for single allocations.

I'd strongly recommend against using malloc(), calloc(), realloc() (and by extension free()) because they don't respect the presence of constructors and destructors. If you're working with any class type, you're flirting with danger by not using new/delete for explicit dynamic allocation.

If you want to reallocate a block of memory, it's a simple matter to copy and reassign pointers:

if (new_size != old_size)
{
    Rectangle *temp = new Rectangle[new_size];
    size_t n = old_size < new_size ? old_size : new_size;

    copy(temp, temp + n, rectangles);

    delete[] rectangles;
    rectangles = temp;
}

P.P.S Indexing by area seems unwise for a number of reasons, including but not limited to wasted memory.

"Indexing" in this case is nothing more than a search wrapped in a cute little package. It's no different than if you defined it as:

Rectangle *find_by_area(int area);

Though the above would be the better option for a search as it makes clear that a potentially expensive operation is happening.

Do please give an example of how memory is wasted in a search algorithm. And note that since the OP is clearly a beginner, we're looking at probably a simple linear or binary search that uses no extra memory (barring a few variables which are negligible).

[Unimportant]

@deceptikon

Memory waste
I'm not sure you read my post correctly.
If you truly index by area then you have an array such that &array[area] is valid, that's not the same as a search. My intention in pointing out the memory waste was that many area values would be uninitialized or NULL pointers. Plus the nature of area is multiplicative, and so you would allocate a great deal of memory to create even 1 large area rectangle mapped in this way. It would also increase energy demands for a linear search of the array, because of wasted elements.

HENCE, "Indexing by area seems unwise"

P.S. I don't like your reason for avoiding malloc; that you assume the programmer is an idiot.
There are plenty of valid cases both for and against malloc in different circumstances.
That is not one of those.

[deceptikon]

I'm not sure you read my post correctly.

That seems to be the case. You appear to have meant indexing the underlying array whereas I meant a wrapper interface by overloading the subscript operator. I agree with you that making array[area] work (where array is the underlying array) is not a great idea. In fact, I'd flat out call it stupid, given the requirements from the OP. There's no reason at all to organize the underlying array like that. ;)

P.S. I don't like your reason for avoiding malloc; that you assume the programmer is an idiot.

The only time malloc() is guaranteed to be safe is when allocating for a built-in type. The instant classes enter the picture it becomes too risky. To avoid having to remember what types are safe and what types aren't, best practice is to forget that malloc() exists. You have two options in standard C++ that eliminate a need for malloc() entirely:

1. new/new[] and delete/delete[]. These will properly allocate memory and handle the calling of constructors and destructors for all types.

2. std::allocator and derivatives. These give you more control such that you can allocate and release raw memory but also have a clean interface for calling constructors and destructors for all types. The intended use is in the implementation of things like collection classes, but there's nothing stopping you from using an allocator for any dynamic allocation.

There are plenty of valid cases both for and against malloc in different circumstances.

Give me 3 valid reasons for using malloc() in C++.

That is not one of those.

Bullshit. Failure to account for constructors is the canonical reason for not using malloc().

[mike_2000_17]

If you truly index by area then you have an array such that &array[area] is valid

I think your definition of "indexing" is bit off of the conventional definition of the term. For one, the OP states "a search index", which is very explicit. But even without that precision, the term "index" still refers to a method by which to look up elements of a collection / container. In an array, you can look up the elements by their position in memory (or offset from the first element of the array), and that's why we call that position value (usually an integer) the "index" of the array. But, in other contexts, the term "index" refers to whatever way you look up the elements. For instance, in containers like std::set or std::unordered_set, we say the elements are indexed by their value. In a container like std::map or std::unordered_map, we say the elements are indexed by their key values. There are also techniques for "multi-indexing".

So, to me, and to most programmers, when it is said "index by area", it means that the elements are looked up by their area values. It does not imply that every possible area value must be a valid integer index into a large array. And of course, that would be very wasteful of memory.

I don't like your reason for avoiding malloc;

Whether you like it or not, you have to accept it. malloc does not call any constructor, and free does not call any destructor. The only way to be sure that you never need to call a constructor / destructor is if you are programming in C. In C++, the compiler decides whether a constructor / destructor call is required according to some very strict rules. If it can, it will optimize away the constructor / destructor calls during a new / delete operation (these are called POD-types (Plain-Old-Data types)). Why bother yourself with making that decision when the compiler does it for you?

And, of course, using malloc / free on class types (non-POD types) is a tricky affair, and very error prone. See this example:

#include <cstdlib>
#include <string>

// This is a non-POD type (contains a string):
struct Employee {
  int ID_number;
  std::string name;
};

int main() {

  const std::size_t num_employees = 10;

  // here is the valid malloc version:
  {
  Employee* employees = (Employee*) std::malloc( num_employees * sizeof(Employee) );

  // call the constructor for each employee:
  for(std::size_t i = 0; i < num_employees; ++i)
    new( &employees[i] ) Employee;

  // ... some code that uses the employees array ...

  // call the destructor for each employee:
  for(std::size_t i = 0; i < num_employees; ++i)
    employees[i]->~Employee();

  // free the memory:
  std::free( employees );
  };

  // here is the version with new / delete:
  {
  Employee* employees = new Employee[num_employees];

  // ... some code that uses the employees array ...

  delete[] employees;
  };

  // here is the version most usually used, using std::vector:
  {
  std::vector<Employee> employees( num_employees );

  // ... some code that uses the employees array ...

  }; // array is automatically freed as 'employees' goes out of scope.

};

The last version, with std::vector, is by far the preferred version. Most modern C++ libraries do not contain any manual allocation / deallocation of memory, whether it is with malloc or new.

In C++, to do optimizations like avoiding constructors when not necessary or trying to do bulk memory copies (without individual copy-constructors), we typically go through something called an "allocator". The one provided by the standard is called std::allocator and it is used by all standard containers to do exactly those kinds of optimizations whenever possible. There is no reason for you to burden yourself with the task of doing this manually.

that you assume the programmer is an idiot.

Yes, programmers are idiots. That's the working assumption for all experienced programmers, that you are an idiot and every one of your colleagues is too. Being a good programmer is not about never making mistakes, it's about never forgetting that you always make mistakes. More code means more mistakes, more repetitions means more mistakes (or trouble making changes in all the places), more manual labor means more mistakes, etc...

What would be the alternative? Consider that every programmer is absolutely brilliant? So, no need for comments, no need to reasonable variable names, no need for clear interfaces, no need for easy-to-use classes that wrap the manual allocations and stuff, etc..., because, after all, the brilliant programmers can just look at any code and understand it all, and write perfect code all the time. I don't know of any such programmer, and probably wouldn't want to work with one. And obviously, this is totally unrealistic, the vast majority of programmers are mediocre programmers (which is usually correlated with them thinking they are the best programmers). So, you must set the bar low in that regard, that's just reality.

[Unimportant]

@Deceptikon
For example, the A star algorithm performs nearly an order of magnitude faster with realloc.
I don't see how you can say the functionality of reallocation in place is useless.
You are wrong.

Edit:
@Mike
You're right about my use of index, that was my own misunderstanding.
I don't believe you understand the cases in which realloc can and should be used.

[deceptikon]

For example, the A star algorithm performs nearly an order of magnitude faster with realloc.

I'll take your word for it.

I don't see how you can say the functionality of reallocation in place is useless.

It is when you assume that the reallocation is in-place, which is not guaranteed even for realloc().

You are wrong.

False. You are wrong within this thread. For niche applications I'll concede that realloc() has potential unguaranteed performance benefits if used safely. However, that in no way excuses your recommendation that realloc() be used in the general case, or even in the specific case of this thread, especially given that your example of using it was in fact unsafe.

I don't believe you understand the cases in which realloc can and should be used.

What I (and Mike) understand are the limitations of realloc(), which directly apply to how it can and should be used. Your example in this thread was one of the cases where it should not be used, which immediately brings into question your understanding.

[Unimportant]

@deceptikon

Reallocation in place
I'll conceed this point, realloc can equal new if there is not enough contiguous memory available; though this case is not the most frequent.

"For this thread"
I didn't like your general attack on realloc.
You're right that the OP is inexperienced and so malloc/free could cause him some problems.

Given my misunderstanding of the OP's phrasing and primarily of "index", I would say that my solution was generally wrong, too.

To be fair though, for all you know he doesn't need to use new/delete at all, and could allocate all memory onto the stack. I never suggested that realloc() should be used in a general case.

[deceptikon]

I didn't like your general attack on realloc.

I suspect you're just miffed that the "attack" was both accurate and happened to be directed at your code. In my experience, bruised egos are one of the more common reasons for stubbornly defending a losing argument.

You're right that the OP is inexperienced and so malloc/free could cause him some problems.

I'm tempted to think the same of you. Once again, your example was a pefect case of how not to use realloc() in C++. Rather than fight to the death for your beloved function, maybe you should sit back and objectively consider what Mike and I have said.

To be fair though, for all you know he doesn't need to use new/delete at all, and could allocate all memory onto the stack.

Given the phrase "dynamic array of rectangles" in the OP, I'd say that's extremely unlikely. Dynamic allocation on the stack, while possible through solutions such as alloca(), generally isn't taught to beginners. Further, it's unconventional enough to justify explictly stating that the allocation is to be both dynamic and on the stack.

Though if you're grasping at something to be right about in this thread, I'll give you that point if it'll make you feel better.

[Unimportant]

Ah, well in that case you're also wrong "in this thread"
since the OP stated "Define an array of pointers to the array"

Maybe you should calm down.
I'm sure you think you're right, it's natural or you wouldn't be arguing in the first place.
It's good to remember that the person you're arguing with also feels that way.

I don't think you've made strong points, other than the fact that you think the language is difficult to use.

[mike_2000_17]

You must also keep in mind that in any half-decent implementation, the need for reallocations of the memory is an amortized constant cost, which is the case, of course, for all standard containers that rely on contiguous storage. So, any benefit you might get from the occasional in-place reallocation is marginal at best. In my experience, the cost of reallocations (create new memory and copy the old one into it) is almost negligible, and shows up only as low-performance spikes at geometrically increasing intervals.

You gain significant performance from using realloc only in situations where you are constantly increasing or decreasing the size of the array by small increments (e.g., like with the priority queue used in an A* algorithm). However, such an implementation is very very naive, the proper way to do it is with either a classic dynamic array (like std::vector) with amortized constant reallocation costs, or other more specialized containers like std::deque (multiple small arrays) or unrolled linked lists.

If you have an implementation of the A* algorithm that performs an order of magnitude faster because of realloc, it means that either everything else (besides memory management work) is really crazy efficient, or the approach used for memory management is really really bad (like the naive approach mentioned in the previous paragraph). I suspect the latter.

About realloc, I could conceive of some cases where you could achieve some marginal performance benefits from using it. But the reason why this "reallocate with the benefit of maybe not copying the existing data" mechanism was never incorporated directly into any native C++ construct (i.e., something like renew or a reallocate() function in standard allocators), which has been proposed on occasions, is because the cases when that mechanism gives you any measurable benefit are far too few to justify the contortions that would be required to allow it (how do you accomodate constructor / destructor calls when doing a realloc?). So, realloc is definitely very far from being "general case" solution, more like an extremely rare solution only useful in very marginal cases (can't really think of any, to be honest). The "general case" recommendation in C++ is always std::vector, i.e., "when in doubt, use std::vector" (paraphrased from Bjarne Stroustrup).