Added Array

[bogdanm]

Array is a simple container class that can be accessed using indexes (array[i]). It can grow automatically and is reentrant. Still TODO: issue runtime errors for allocation failures and invalid index access. The only thing preventing this at the moment is that it'd add a dependency on mbed-core (where the error() function is defined), which is not ideal.

[bogdanm]

OK, a bit of background: I'm planning to use an implicit binary heap in minar, since that has good runtime performance and doesn't take a lot of storage. To implement that, I need this Array. Just to let you know that I'm not implementing data structures randomly :)

[bogdanm]

@0xc0170 , @autopulated , you know the drill. There's this, and there's going to be BinaryHeap, and hopefully we're done with (large) PRs on this repo for now :)

[autopulated]

I assume you're not planning to heapify in a reentrant manner, and just disable interrupts during the whole operation? I had assumed that it would be easier to make the structure fully reentrant, or disable interrupts for shorter periods of time, if you maintained a sorted linked list.

[bogdanm]

I assume you're not planning to heapify in a reentrant manner, and just disable interrupts during the whole operation? I had assumed that it would be easier to make the structure fully reentrant, or disable interrupts for shorter periods of time, if you maintained a sorted linked list.

@autopulated , yes, i wasn't planning to heapify in a reentrant manner. If you have suggestions about how to improve this, please let me know. Specifically, what kind of sorted link list do you have in mind? I've chosen the implicit heap representation mostly because it's extremely efficient in terms of storage, but I can certainly be convinced to use something better.

[bogdanm]

OK, I've pushed a new commit (45debdd) with an alternative API. It looks more sane, but I don't know if it's actually useful (see the commit message). Opinions welcome.

[autopulated]

I think operator[] is preferred for accessing, and it's fine to treat undefined access as fatal (although maybe you could assert() and return a reference to a global instance of T, I'm torn as to whether that's a good idea?).

I don't think growing the capacity in operator[] makes sense or is what you'd expect as a user though. Thinking about it, why not mimic std::vector's API, and have a push_back() function?

[bogdanm]

On point 1 of your reply, I'm working on exactly that at the moment. Returning a pointer to a global T or to a new T is equally good/bad, since that code will come after a runtime error (display error message, then exit()) and won't execute anyway.

About your second point, I simply wanted to express array[i] = something in the same way when i < size and i == size. I still think that looks consistent enough to be useful. You might find it weird because vector does things differently, but I'm not aiming for std compatibility.

[0xc0170]

I would expect operator[] for a class named Array

Note, std::array in c++1x, there's array::at which does a bound check and throws an error.

[autopulated]

I think I'd find it surprising for [] to increase the size of an array, unless it is a sparse array.

All the std:: containers that have unchecked subscript access also have a checked .at() accessor function, but the checking in the standard library throws exceptions so we cannot directly copy that pattern anyway.

On 15 Jul 2015, at 10:25, Bogdan Marinescu notifications@github.com wrote:

On point 1 of your reply, I'm working on exactly that at the moment. Returning a pointer to a global T or to a new T is equally good/bad, since that code will come after a runtime error (display error message, then exit()) and won't execute anyway.

About your second point, I simply wanted to express array[i] = something in the same way when i < size and i == size. I still think that looks consistent enough to be useful. You might find it weird because vector does things differently, but I'm not aiming for std compatibility.

— Reply to this email directly or view it on GitHub.

[bogdanm]

If the array is supposed to grow, I don't see why [] won't change the size when needed. We can 'replace' exceptions with runtime errors for most cases.

[autopulated]

I don't think it's what people would expect it to do.

[bogdanm]

If by 'people' you mean 'regular users of the std library', then I guess you're right, but otherwise it really makes a lot of sense :) In any case, I'll implement push_back to move this forward.

[autopulated]

Well, standard library, Qt, all the various vector containers in boost (small, stable, etc...), llvm smallvector, bitvector, basically every C++ resizable array/vector-like container that I can think of.

[bogdanm]

Closing this, I'll open a new PR.