I don't understand why you have a struct inside the class.
To me this is much clearer instead of having both a type for the SmartArray and a type inside the SmartArray class. I'm lost as to why you have a typedef in the class.Code:template <class T> class SmartArray { public: ... private: T* m_pArray; unsigned int m_start; unsigned int m_end; unsigned int m_num_elems; unsigned int m_max_elems; std::stack<unsigned int> m_IndexCache; };
Last edited by VirtualAce; 03-06-2008 at 08:58 PM.
I don't know what i was thinking with the struct, unless i was planning on having ownership of the type, but as for the raw array I didn't think it would work well since it is hard to modify the size of an array that contains data.
Modified the post with the template manager, and changed it to not use the struct.
This one seems pretty stable... Maybe not, but looks like it
Code:/* Author: Cody Doughty Data: March, 6, 2008 */ #ifndef SMART_ARRAY_H #define SMART_ARRAY_H #include <cstdio> #include <vector> #include <list> namespace Varia { template<class Type> class XArray { public: XArray(unsigned int p_iMax = 2000, bool p_bDebug = false):m_iMax(p_iMax),m_bDebug(p_bDebug),m_iSize(0) { if (m_bDebug) { printf("Creating XArray. Size = %d.\n", m_iMax); printf("-->Estimated memory usage: %dbytes.\n", (sizeof(Type)*m_iMax)); } m_vArray.resize(m_iMax); std::vector<Type*>::iterator it; for ( it = m_vArray.begin(); it != m_vArray.end(); ++it ) (*it) = NULL; } ~XArray() { std::vector<Type*>::iterator it; for ( it = m_vArray.begin(); it != m_vArray.end(); ++it ) if ( (*it) != NULL ) { delete (*it); } } void SetDebug(bool p_bDebug) { m_bDebug = p_bDebug; } int AddElement(Type* type) { if ( m_iSize >= m_iMax && m_vList.empty() ) { return -1; } if ( !m_vList.empty() ) { unsigned int index = m_vList.front(); if ( m_vArray.at(index) == NULL ) { if ( m_bDebug ) printf("Setting Resource:%d\n",index); m_vArray.at(index) = type; m_vList.erase(m_vList.begin()); } return index; } else { if ( m_bDebug ) printf("Setting Resource:%d\n",m_iSize); m_vArray.at(m_iSize) = type; ++m_iSize; return m_iSize-1; } } int RemoveElement(unsigned int p_iIndex) { if ( p_iIndex <= m_iMax-1 ) { if ( m_vArray.at(p_iIndex) != NULL ) { if (m_bDebug) printf("Removing element:%d\n",p_iIndex); delete m_vArray.at(p_iIndex); m_vArray.at(p_iIndex) = NULL; m_vList.push_back(p_iIndex); return p_iIndex; } else { return -1; } } return -1; } void IncrementSize() { if ( m_iMax < m_vArray.max_size() ) { if ( m_bDebug ) printf("Incrementing Array size from %d to %d.\n",m_iMax,m_iMax+1); ++m_iMax; m_vArray.push_back(NULL); m_vList.push_back(m_vArray.size()-1); } } void DecrementSize() { if (!m_vArray.empty()) { if ( m_bDebug ) printf("Decrementing Array size from %d to %d.\n",m_iMax,m_iMax-1); if ( m_vArray.back() != NULL ) delete (m_vArray.back()); if ( m_iMax == m_iSize ) --m_iSize; --m_iMax; m_vArray.pop_back(); } } void Clear() { if ( m_bDebug ) printf("Clearing Array.\n"); std::vector<Type*>::iterator it; for ( it = m_vArray.begin(); it != m_vArray.end(); ++it ) if ( (*it) != NULL ) { delete (*it); } m_vArray.clear(); m_iMax = 0; m_iSize = 0; } Type* GetElement(int p_iIndex) { if ( p_iIndex < m_iMax ) return m_vArray.at(p_iIndex); } private: bool m_bDebug; // unsigned int m_iMax; unsigned int m_iSize; std::vector<Type*> m_vArray; std::list<int> m_vList; }; } #endif //SMART_ARRAY_H
Just a few observations:
You need to construct members in the same order they are declared. (Some compilers hate it when you don't.)
You need to construct the 'std::vector' as well. (You can specify the size in the constructor.)
There is nothing wrong with deleting a null pointer.
You need a copy constructor and assignment operator, or you need to disallow them.
Anyway, I don't know what your strategy is, but you might want to look at implementing a 'span block'* instead of just recording every removal.
Say you want to remove element '14': First check if any span starts or ends at element '13' or '15'. If a span ends at element '13' you simply increment the span length by 1 and erase the element. If a span starts at element '15' you decrement the span starting position by 1, increase the span length by 1 and erase the element. If neither of these are available you start a new span block with the position 14 and length of 1 and erase the element.
Now again, I don't know your strategy. However, if you may be adding or erasing ranges (say elements '13', '14', [...] '37', '38') often this will be a nice improvement. If your strategy involves... a wide range of ranges (adding ranges of only a few elements and ranges of many elements) you may want to provide a way to sort the list of span blocks by length. The kicker here is two additional functions: 'AddRange(Type * StartPosition, size_t ElementCount)' and 'RemoveRange(int StartPosition, size_t ElementCount)'. Without these functions the span block would be too costly for average use.
My strategy (for the curious):
I was actually using something very similar to this in an old tile engine of mine. Many tiles were loaded at startup. Most tiles were around only for a specific field. Dealing with towns, where a particular building may have it's own set of 9 to 512 tiles, was the rationale for the span block implementation. It was slow restoring and removing even the small building sets every time the character entered/exited a building. I changed things so that tile sets were cached. The cache was reclaimed by key events.
Soma
* Not actually what it is called, but I think the more descriptive name useful. It is actually an idea heavily associated with "first fit" and "best fit" allocators.
Last edited by phantomotap; 03-07-2008 at 12:54 AM.
I talked with a co-worker over lunch today and he had a very good idea on how to solve the issue of increasing indices in this algorithm.
Raigne, PM me and I'll show you a possible solution. Given this would correct a serious flaw in an otherwise very fast and good container this fix may prove extremely viable. If it does indeed solve the problem I will most likely use this container for my entire resource management system.
Why not post it publically so anyone can see? Or is the code restricted?
Originally Posted by Adak
No this is for a personal project. I'll post it as soon as I verify it works. I'm basically treating each element in the array as a node in a linked list.
Last edited by VirtualAce; 03-08-2008 at 09:44 AM.
