Standard Libraries

[SoulofDeity]

This is what I called flat, auto sized array, and this is a few improvement/suggestions for you:
1. you may pre-allocate in chunks to avoid frequent allocations
2. you may break down the allocation to reduce stress from realloc (imagine you expand from 10000 ro 10001 elements)

This is what my array look like:

Code: Select all

template <class T>
class	libprefix_Array {
public:
	libprefix_Array();
	~ libprefix_Array (); // not suppose to be inherited, no virtual
	void	clear ();
	T*	get(int index);
	int	count() { return counter; }
protected:
	static const int kChunkSize = 16;
	int	item_node_count, item_node_allocated, counter;
	T**	item;
};
template <class T>
T* libprefix_Array<T>::get(int index) {
    int chunk = index / kChunkSize;
    if ( chunk >= item_node_allocated ) {
        // expand item pointer table
    }
    if ( item[chunk] == NULL ) {
        // allocate payload
    }
    return &item[chunk][index % kChunkSize];
}

And guess what, this is one of the class that I never used in any scenario, in all cases I used linked list, map (hash table), bi-directional map, or just boost.

There's a difference though, my code is C and yours is C++

Obviously, it was kinda stupid for me to allocate so much, but at the time I was writing it I was more concerned with size than speed (no idea why)

EDIT:
Then again, I doubt people are going to constantly be resizing lists. Obviously, this isn't suited for something like memory management. My intentions when writing this were to use it to attach events to the components in my gui.

[Kevin]

The only point in lists is that they can change their size. When people use them, they usually add and remove a lot of things. More importantly, don't call a data structure List if it isn't a list. People have a specific thing in mind when you talk about a list, and amongst others they think of specific performance characteristics that don't match your dynamic array.

For a real list there are two ways: If you have to deal with predefined data structures that you can't extend or if you need to have one object in multiple lists at the same time, you need to malloc a data structure for each list entry like this:

Code: Select all

struct list_node {
    void* data;
    struct list_node* next;
};

If however you have control about the data structure and it's never in more than one list (which is the common case), then have a look at something like sys/queue.h.

/* alternative naming for ladd and lremoveLast

This I consider a bad idea. Choose one good name and stick to it. You can't criticise the C standard library for being inconsistent and then introduce two names for the same thing...

[bluemoon]

I also have another library I've written for command line argument parsing, but its sloppy and slow. I'll try to optimize it a bit and post the code.

I don't think speed is important for command line parsing (except if it is horribly slow), it's the interface that matter, it may impose a specific protocol for the command line (eg. using -key=value pattern); it should follow the rule of least surprise, and convenient for most normal usage (get int of specific command switch, get string, etc).

[jnc100]

The only point in lists is that they can change their size. When people use them, they usually add and remove a lot of things. More importantly, don't call a data structure List if it isn't a list. People have a specific thing in mind when you talk about a list, and amongst others they think of specific performance characteristics that don't match your dynamic array.

I think there's a difference between a list and a linked list (which is only one of a number of possible implementations of a list). For example the mono implementation of List<> uses an internal array that is resized if necessary - specifically it starts at size 4 and doubles in size every time you try to add an item when it has reached capacity. This allows for fast indexing. I would suggest that the only expected requirements of a list are the ability to add/remove/insert items, iterate through it and return the item at a particular index - no one should make performance assumptions without checking the underlying implementation.

Regards,
John.