Instead of writing a new class from scratch... It could be much easier to modify existing code (there are good Open Source STLs).Quote:
Originally Posted by aewarnick
It would avoid the pain of debugging, and the fear of the last(s) bug(s)...
Printable View
Instead of writing a new class from scratch... It could be much easier to modify existing code (there are good Open Source STLs).Quote:
Originally Posted by aewarnick
It would avoid the pain of debugging, and the fear of the last(s) bug(s)...
0 is garbage. just like an unitialised variable, thus C++ saw no logic for this superkoko
So I guess I should modify my stance on the subject just a tiny bit.Quote:
IMHO, it is a Good Idea to improve C++ determinism... But, if there is any performance tradeoff, there must be an explicit way to avoid the penalty, at the cost of safety.
I definitely agree with this statement. If such a huge performance
penalty DID exist, then there should be a way to avoid it definitely.
However, as you pointed out this will be at the cost of safety.
But as a general rule of thumb, unless such a situation explicity
existed, the majority ( like 99%) of the time I believe you should always
initialize an array or vector :)
I think you'll be much happier with this. Although, now I remember why I never coded a copy constructor or assignment operator: Because I couldn't, and still can't without sacrificing speed. I have now handled the copy constructor and assignment operator by coding an error message if it is used. Ideally, I'd like to have the compiler halt if that section of code is needed...Is that possible?
The const thing you were talking about, I don't know what you mean.
The public members that should be protected are still public. I'll change that later. I knew when I coded it that way that I should not have...but I did it anyway.
PHP Code://About 1.5 times faster than vector
//USE POINTERS instead of classes.
//NEVER do this: aArr<class1> arr. Do this: aArr<class1*> arr
//The reason I created it this way is for speed. Otherwise, every time the array needs copied for
//reasons such as removing, inserting, resizing...classes would be created and then all the members copied
//over.
//NEVER assign another aArr to this class with =. Copy the data by looping instead.
template < typename T >
class aArr
{
protected:
uint capacity;
public:
//Both should be protected:
T* _Items;
uint Count;
aArr()
{
Reset();
}
aArr(uint initCapacity)
{
Reset();
capacity= initCapacity;
_Items= (T*)malloc(initCapacity*sizeof(T));
}
aArr(aArr &arr)
{
*this= arr;
}
/*aArr(const T &item) //ambiguous when item is uint
{
Reset();
Add(item);
}*/
~aArr()
{
Del();
}
void Del(uint initCapacity= 0)
{
if(_Items)
{
free(_Items); //free is 2x faster than delete[]
_Items= 0;
}
Count= 0; capacity= 0;
}
void Reset()
{
_Items= 0;
Count= 0;
capacity= 0;
}
//Unsafe to code this because data that class pointers point to would need memcpy'd.
void operator=(aArr& arr)
{
MB("Fatal Error!\n\naArr: cannot assign directly (arr1=arr2). Copy Manually.");
throw "aArr=";
}
T& operator[](uint ind)
{
return _Items[ind];
}
T& Ind(uint ind)
{
return _Items[ind];
}
void Add(const T& d)
{
if(Count >= capacity)
Resize(Count < 10 ? 20 : Count*1.5f);
memcpy(&_Items[Count], &d, sizeof(T));
++Count;
}
void Ins(uint where, aArr < T* > &arr)
{
if(!arr.Count) return;
if(!Count || where >= Count)
{
for(uint i= 0; i < arr.Count; ++i)
Add(arr[i]);
return;
}
if(Count+arr.Count >= capacity)
Resize(Count < 10 ? 20+arr.Count : Count*1.5f +arr.Count);
uint sT= sizeof(T), sTemp= (Count-where)*sT;
aBuffer buf(sTemp);
//T* temp= (T*)malloc(sTemp);
memcpy(buf.Ptr(), &_Items[where], sTemp);
memcpy(&_Items[where], arr[0], sT*arr.Count);
memcpy(&_Items[where+arr.Count], buf.Ptr(), sTemp);
//free(temp);
Count += arr.Count;
}
void Ins(uint where, const T& d)
{
//aArr<T*> arr; arr.Add(&d);
//Ins(where, arr);
//return;
if(!Count || where >= Count)
{
Add(d);
return;
}
if(Count >= capacity)
Resize(Count < 10 ? 20 : Count*1.5f);
uint sT= sizeof(T), sTemp= (Count-where)*sT;
aBuffer buf(sTemp);
//T* temp= (T*)malloc(sTemp);
memcpy(buf.Ptr(), &_Items[where], sTemp);
memcpy(&_Items[where], &d, sT);
memcpy(&_Items[where+1], buf.Ptr(), sTemp);
//free(temp);
++Count;
}
void Rem(aArr < uint > & arr)
{
T* temp= _Items;
capacity= Count;
_Items= (T*)malloc(capacity*sizeof(T));
uint count= Count;
Count= 0;
uint removed= -1;
for(uint i= 0; i < count; ++i)
{
for(uint j= 0; j < arr.Count; ++j)
{
if(i == arr[j])
{
removed= i;
break;
}
}
if(removed == -1)
{
Add(temp[i]);
}
else
{
removed= -1;
}
}
free(temp);
}
void Rem(uint ind)
{
aArr < uint > arr(1);
arr.Add(ind);
Rem(arr);
}
void RemAll()
{
Del();
}
void Resize(uint newSize)
{
capacity= newSize;
_Items= (T*)realloc(_Items, newSize*sizeof(T));
if(capacity < Count)
Count= capacity;
}
private:
static int _ascending(const void *v1, const void *v2)
{
if(*((T*)v1) > *((T*)v2)) return 1;
if(*((T*)v1) < *((T*)v2)) return -1;
return 0;
}
static int _descending(const void *v1, const void *v2)
{
if(*((T*)v1) > *((T*)v2)) return -1;
if(*((T*)v1) < *((T*)v2)) return 1;
return 0;
}
public:
void Sort(char A_D= 'A')
{
if(A_D == 'A') qsort(&_Items[0], Count, sizeof(T), &_ascending);
else qsort(&_Items[0], Count, sizeof(T), &_descending);
return;
const int tSize= sizeof(T);
void* hold[tSize];
for(int i= 0; i < Count; ++i)
{
for(int j= 0; j < Count-1; ++j)
{
if((A_D == 'A' && _Items[j] > _Items[j+1]) || (A_D == 'D' && _Items[j] < _Items[j+1]))
{
Swap(&_Items[j], &_Items[j+1], tSize, &hold);
}
}
}
}
aStr ToStr()
{
aStr s;
for(uint i= 0; i < Count; ++i)
{
s= s << _Items[i] << "\n";
}
return s;
}
};
Not really. Much happier using vector.Quote:
Originally Posted by aewarnick
What does a copy constructor have to do with speed? If a class never gets copied, the copy constructor doesn't get called.Quote:
Although, now I remember why I never coded a copy constructor or assignment operator: Because I couldn't, and still can't without sacrificing speed.
You make the copy constructor and assignment operator private. Also, you have the wrong prototype for your assignment operator:Quote:
I have now handled the copy constructor and assignment operator by coding an error message if it is used. Ideally, I'd like to have the compiler halt if that section of code is needed...Is that possible?
and I don't see a copy constructor in what you posted.Code:aArr& operator = (const aArr& arr)
Const-correctness should be known by any programmer attempting to code a class such as this.Quote:
The const thing you were talking about, I don't know what you mean.
All you did was attempt to simulate a vector<T*>. Never quote numbers without showing what you did to test.Quote:
About 1.5 times faster than vector
Any competent C++ programmer who knows how to use vector will judge for themself whether to use objects or pointers in a vector. What if I wanted to use your class and I want to make copies? It isn't unreasonable for this to occur.Quote:
//reasons such as removing, inserting, resizing...classes would be created and then all the members copied
What if the class is tiny, say two char members? Why shouldn't the programmer not make copies of these? It isn't large and should not have a performance penalty.
It is not a good idea to force what you think is good on a programmer -- let the programmer decide what they want to do.
Why don't you provide a function to do this instead of making the user have to code their own function?Quote:
//NEVER assign another aArr to this class with =. Copy the data by looping instead.
Also, unless you use some template magic, you cannot use non-POD types such as aArr<std::string>, and have your code not have undefined behavior due to the memcpy().
Basically, you're attempting to reinvent the wheel of a vector<T*> (note the T*, not T) where T is non-POD, or a vector<T> where T is a POD type. If a C++ programmer wants an array of pointers, they have vector<T*>.
Also, you still are missing the second operator[] prototype I mentioned. It has everything to do with the const thing you do not know about.
Bottom line -- there are just too many things wrong and other issues with the class you posted. If you wanted to write a class that uses only pointers in the array, you could have written a wrapper around vector<T*> instead of creating your own class from scratch.
Also, what is Sort() doing in the class?
I'll be honest with you:
It takes a seasoned C++ programmer to write classes such as this correctly. Just because it seems "in your skill set" to do something like this, it really isn't unless you are an experienced C++ programmer (and the standard library implementation is more than likely written by ace C++ programmers).
Regards,
Paul McKenzie
"What does a copy constructor have to do with speed?"
Nothing. But I cannot code it unless I stop using memcpy and do the whole class the C++ way rather than C.
"Why don't you provide a function to do this instead of making the user have to code their own function?"
See first response.
"Also, what is Sort() doing in the class?"
Convenience. If the user want to sort data, they can. Say they have an array of integers.
"If you wanted to write a class that uses only pointers in the array"
Pointers ONLY need to be used for classes.
"you cannot use non-POD types such as aArr<std::string>"
See former response.
"If you wanted to write a class that uses only pointers in the array, you could have written a wrapper around vector<T*> instead"
Wrappers slow things down and increase binary size.
"I don't see a copy constructor in what you posted"
It is there.
"make the copy constructor and assignment operator private"
Why? The user can't access them directly.
I don't understand. You are mixing the 'C' way with C++ classes? What's wrong with using the proper C++ techniques? i.e. operator new[], or use placement-new(), not malloc() and memcpy(). Please don't say "they're slower" -- they are not. Mixing 'C' techniques in C++ is a recipe for disaster.Quote:
Originally Posted by aewarnick
No. Provide a function that the user must call themselves to do the copy. Look at the MFC CArray for example. There is a CopyData() function that is never called by the CArray class. It is only a convenience function provided to the user of the class if they want to copy the data.Quote:
"Why don't you provide a function to do this instead of making the user have to code their own function?"
See first response.
And what is wrong with std::sort() to do this? That's what std::sort() is there for. Also, the sort is totally useless if they provided pointers. It won't sort their data, only the pointers. Also std::sort() on many implemetations outperforms qsort().Quote:
"Also, what is Sort() doing in the class?"
Convenience. If the user want to sort data, they can. Say they have an array of integers.
And how do you enforce that? This is the restriction that I'm referring to. Your code will exhibit undefined behavior.Quote:
"If you wanted to write a class that uses only pointers in the array"
Pointers ONLY need to be used for classes.
That still doesn't answer how you enforce this, except to write in a comment that it can't be used.Quote:
"you cannot use non-POD types such as aArr<std::string>"
See former response.
Again, you are stating what will slow things down without any concrete evidence. And I don't want to go into the "binary size" issue. I've proven a few times in this forum and in other forums that this is a myth, at least for the Visual C++ 6.0 compilers.Quote:
"If you wanted to write a class that uses only pointers in the array, you could have written a wrapper around vector<T*> instead"
Wrappers slow things down and increase binary size.
But the big picture is why can't someone just use a vector<T*> instead of your class? It works already and doesn't have all of these problems, and they are using pointers.
The prototype is incorrect, just as the assignment operator is.Quote:
"I don't see a copy constructor in what you posted"
It is there.
You asked how to make sure that copies and assignments are not done, and how do you make the compiler catch these operations. The answer is to make these functions private. This is explained in any good C++ book on class design -- if you don't want copies or assignment, make these functions private.Quote:
"make the copy constructor and assignment operator private"
Why? The user can't access them directly.
And your current implementations, save for the wrong prototype, can be accessed by the user. Their public, so of course the user has access to them. The copy constructor is also faulty. What do you think happens here?:
It calls your assignment operator. But your assingment operator doesn't assign -- it throws an exception.Code:aArr(aArr &arr)
{
*this= arr;
}
Regards,
Paul McKenzie
aewarnick, you code is really buggy, and alo your not using an allocater, basicly meaning users cannot make their own allocation methods. i have written an array class and i have learn alot from poeple on codeguru.
Your sort function is very slow. Your insert function is very slow. Standards are doing this faster than you. Though imho insert programming is very bad. an array should be resized respectivly.
Zero is not garbage. Consider this case - you have several new bank accounts - they all start with the same account balance - that is 0. But they may change at different relative rates. It is significant. It signals the "beginning" in many practical cases.Quote:
Originally Posted by Mitsukai
than the user initializes it to 0 not the vector.Quote:
Originally Posted by exterminator
The Sort funk uses qsort and then returns. How is that very slow?
std::sort is parameterized on comparison function, so comparison may be inlined in sort algorithm.Quote:
Originally Posted by aewarnick
Read the comments again. The std::sort() outperforms qsort() due to the compiler having better optimization strategies with std::sort() than qsort().
Also, usage of qsort() is discouraged in a C++ program, just like memcpy() is discouraged for doing copies of T. The qsort() knows nothing about C++ non-POD types, therefore dangerous to use -- same thing with memcpy().
If you want to code in 'C', then you can do that. The issue is that you want to code in C++ (i.e. use templates, create classes, etc.) and use 'C' techniqes to accomplish this. This is wrong in many respects already pointed out here.
Regards,
Paul McKenzie
"The copy constructor is also faulty. What do you think happens here?:
Code:
aArr(aArr &arr)
{
*this= arr;
}
It calls your assignment operator. But your assingment operator doesn't assign -- it throws an exception"
I coded it that way because my if arr is an array of class pointers, I have no way to safely copy the data because the code supports pointer and non-pointer data types. I guess the best thing to do would be to code an array that is used strictly for pointer types in this case.
I agree that my Ins function is a little slow and can easily be optimized, but I wouldn't say it's very slow.
What is your argument? What are your points that you want to prove? To me the whole comparison between an array and a vector is meaningless. It's like comparing two people who basically have the same role (and that is storage of a collection of data) but do it quite differently with difference in ease of usability and extra services that they provide above their basic functionality. But before going any forward with this argument I would like to know what exactly are you arguing about? If you don't want initialization use std::vector::reserve (which is even suggested while using vectors and knowing approximate count of objects that you would be storing in them and doing push_backs).Quote:
Originally Posted by Mitsukai