Battlefront3.net

[Scott]

Is this why you wanted to know a sorting algorithm?

No, but I sorting function is a good idea for the myVector class (although the STL sort would probably work). I was just doing the algorithm for kicks and just started myVector yesterday. I got it pretty much finished:

myVector.h

Code: Select all

class myVector
{
    public:
        myVector(){itsLength = 0; pVector = new int[itsLength];} //Constructor sets length and creates a vector
        ~myVector(){clean();} //deletes pointers

        int& operator [] (int location) //allows for the [] subscript
        {
            if (itsLength > 0)
                return pVector[location];
        }

        void operator = (myVector& myVec) //allows to copy vectors to each other
        {
            itsLength = myVec.len();
            delete pVector;
            pVector = new int[itsLength];

            for (int i = 0; i < itsLength; i++)
                pVector[i] = myVec[i];
        }

        void add_on (int newElement) //adds an element to the end
        {
            tempVector = new int[itsLength];

            for (int i = 0; i < itsLength; i++)
                tempVector[i] = pVector[i];

            delete pVector;
            itsLength++;
            pVector = new int[itsLength];

            for (int i = 0; i < itsLength; i++)
                pVector[i] = tempVector[i];

            pVector[itsLength-1] = newElement;

            delete tempVector;
        }

        void add_on (myVector& myVec) //adds another myVector to the end
        {
            tempVector = new int[itsLength+myVec.itsLength];

            for (int i = 0; i < itsLength; i++)
                tempVector[i] = pVector[i];

            for (int i = itsLength, j = 0; i < itsLength+myVec.itsLength; i++, j++)
                tempVector[i] = myVec[j];

            itsLength += myVec.len();
            pVector = new int[itsLength];

            for (int i = 0; i < itsLength; i++)
                pVector[i] = tempVector[i];

            delete tempVector;
        }

        void take_off(int location) //takes off the element at int location
        {
            itsLength--;
            tempVector = new int[itsLength];

            int j = 0;
            for (int i = 0; i < itsLength+1; i++)
            {
                if (i != location)
                {
                    tempVector[j] = pVector[i];
                    j++;
                }
            }

            delete pVector;
            pVector = new int[itsLength];

            for (int i = 0; i < itsLength; i++)
                pVector[i] = tempVector[i];

            delete tempVector;
        }

        void take_off() //takes off the element on the end
        {
            itsLength--;
            tempVector = new int[itsLength];

            int j = 0;
            for (int i = 0; i < itsLength+1; i++)
            {
                if (i != itsLength+1)
                {
                    tempVector[j] = pVector[i];
                    j++;
                }
            }

            delete pVector;
            pVector = new int[itsLength];

            for (int i = 0; i < itsLength; i++)
                pVector[i] = tempVector[i];

            delete tempVector;
        }

        void wipe(int start, int finish) //deletes everything from start() to finish()
        {
            for (int i = start; i < finish+1; i++)
                take_off(start);
        }

        void push_in(int location, int newElement) //Adds an element to a specified location
        {
            tempVector = new int[itsLength];

            for (int i = 0; i < itsLength; i++)
                tempVector[i] = pVector[i];

            delete pVector;
            itsLength++;
            int test = itsLength;
            pVector = new int[itsLength];

            for (int i = 0, j = 0; i < test; i++)
            {
                if (i == location)
                    pVector[i] = newElement;
                else
                {
                    pVector[i] = tempVector[j];
                    j++;
                }
            }

            delete tempVector;
        }

        void push_in(int location, myVector& myVec) //Adds another myVector to a specified location
        {
            tempVector = new int[itsLength];

            for (int i = 0; i < itsLength; i++)
                tempVector[i] = pVector[i];

            delete pVector;
            itsLength+=myVec.itsLength;
            int test = itsLength;
            pVector = new int[itsLength];

            int perm, temp, i;
            for (int j = 0, i = 0; i < test; i++)
            {
                if (i == location)
                {
                    for (perm = location, temp = 0; temp < myVec.itsLength; temp++, perm++)
                        pVector[perm] = myVec[temp];
                    i = perm-1;
                }
                else
                {
                    pVector[i] = tempVector[j];
                    j++;
                }
            }

            delete tempVector;
        }

        void exchange(myVector& myOther) //Exchanges two myVectors
        {
            if (itsLength > myOther.len())
            {
                tempVector = new int[myOther.len()];

                for (int i = 0; i < myOther.len(); i++)
                    tempVector[i] = myOther[i];

                int itsNewLen = itsLength-(itsLength-myOther.len());
                myOther.itsLength+=(itsLength-myOther.len());

                for (int i = 0; i < myOther.len(); i++)
                    myOther[i] = pVector[i];

                itsLength = itsNewLen;

                for (int i = 0; i < itsLength; i++)
                    pVector[i] = tempVector[i];
            }
            else
            {
                tempVector = new int[itsLength];

                for (int i = 0; i < itsLength; i++)
                    tempVector[i] = pVector[i];

                int newLen = myOther.len()-(myOther.len()-itsLength);
                itsLength+=(myOther.len()-itsLength);

                for (int i = 0; i < itsLength; i++)
                    pVector[i] = myOther[i];

                myOther.itsLength = newLen;

                for (int i = 0; i < myOther.len(); i++)
                    myOther[i] = tempVector[i];
            }
        }

        void clean() //deletes and restarts everything
        {
            delete pVector;
            delete tempVector;
            itsLength = 0;
        }

        //SOME SMALL INLINE FUNCTIONS
        int start() {return 0;}
        int finish() {return itsLength;} //Alternative iterator to len()
        int len() {return itsLength;}

    private:
        int itsLength;
        int *pVector;
        int *tempVector;
};

myVector.cpp

Code: Select all

#include <iostream>
#include "myVector.h"

int main()
{
    using namespace std;

    myVector myVec, myOther;
    cout << "myVec is " << sizeof(myVec) << " bytes\n\n";

    myVec.add_on(4);
    myVec.add_on(6);
    myVec.add_on(12);

    myOther.add_on(10);
    myOther.add_on(20);
    myOther.add_on(30);

    cout << "add_on(int) Test: myVec length: " << myVec.len() << "\n";
    for (int i = 0; i < myVec.len(); i++)
        cout << myVec[i] << ", ";

    myVec.add_on(myOther);

    cout << "\n\nadd_on(myVector) Test: myVec length: " << myVec.len() << "\n";
    for (int i = 0; i < myVec.len(); i++)
        cout << myVec[i] << ", ";

    myVec.take_off(0);

    cout << "\n\ntake_off(0) Test: myVec length: " << myVec.len() << "\n";
    for (int i = 0; i < myVec.len(); i++)
        cout << myVec[i] << ", ";

    myVec.take_off();

    cout << "\n\ntake_off Test: myVec length: " << myVec.len() << "\n";
    for (int i = 0; i < myVec.len(); i++)
        cout << myVec[i] << ", ";

    myVec.clean();

    cout << "\n\nclean() Test: myVec length: " << myVec.len() << "\n";

    myVec = myOther;

    cout << "\n\n= operator Test: myVec length: " << myVec.len() << "\n";
    for (int i = 0; i < myVec.len(); i++)
        cout << myVec[i] << ", ";

    myVec.wipe(0, 1);

    cout << "\n\nwipe(0,1) Test: myVec length: " << myVec.len() << "\n";
    for (int i = 0; i < myVec.len(); i++)
        cout << myVec[i] << ", ";

    myVec.add_on(22);
    myVec.add_on(12);

    cout << "\n\nAdded 22 and 12 to the end\n";
    myVec.push_in(0, 28);
    cout << "push_in(0, 28) Test: myVec length: " << myVec.len() << "\n";
    for (int i = 0; i < myVec.len(); i++)
        cout << myVec[i] << ", ";

    myVec.push_in(2, myOther);
    cout << "\n\npush_in(2, myOther) Test: myVec length: " << myVec.len() << "\n";
    for (int i = 0; i < myVec.len(); i++)
        cout << myVec[i] << ", ";

    myVec.exchange(myOther);
    cout << "\n\nmyVec.exchange(myOther) Test: myVec length: " << myVec.len() << "\nmyVec: ";
    for (int i = 0; i < myVec.len(); i++)
        cout << myVec[i] << ", ";
    cout << "\nmyOther: ";
    for (int i = 0; i < myOther.len(); i++)
        cout << myOther[i] << ", ";

    cout << "\n\nExhange again...\nmyVec: ";
    myVec.exchange(myOther);
    for (int i = 0; i < myVec.len(); i++)
        cout << myVec[i] << ", ";
    cout << "\nmyOther: ";
    for (int i = 0; i < myOther.len(); i++)
        cout << myOther[i] << ", ";

    cout << "\n";
    return 0;
}

I just have to think of other functions that would be useful

[Matthew]

You are allowed to write implementations of classes in header files with C++?

I think you should separate the two add_on methods into push or append and concatenate.

In a list data structure I'd have:
push - Add element to end of list
pop - remove element from end of list and return it
insert - Add element anywhere, adjusting adjacent elements.
get_object - Get object from index
concatenate/join - Add two lists together
sub_list - return list of values between two indicies.
sort - sort list
flip - Flip multidimensional list. Eg. Rows become columns.
delete - remove element
immutable - Get fixed size C array

[Scott]

You are allowed to write implementations of classes in header files with C++?

You bet. You don't even need macros like when you create a header of functions.

I think you should separate the two add_on methods into push or append and concatenate.

Separate them? They are separate

push - Add element to end of list

Check

pop - remove element from end of list and return it

Check

insert - Add element anywhere, adjusting adjacent elements.

Check

get_object - Get object from index

Check. Well, it's not a function but you can simply use the subscript operator [ ] thanks to operator overloading.

concatenate/join - Add two lists together

Check. You can even push_in another vector (or list) into another

sub_list - return list of values between two indicies.

Huh?

sort - sort list

Something I will be looking into. Unless sort() works.

flip - Flip multidimensional list. Eg. Rows become columns.

I haven't even tried multidimensional arrays yet. Usually with vectors you don't do any multidimensional work but it's not a bad feature. Some people dislike multidimensional work to great lengths: http://www.cplusplus.com/forum/articles/17108/

delete - remove element

Check

immutable - Get fixed size C array

Huh? Your naming conventions are a bit complex

Oh, and you know much about templates?

[Matthew]

I know nothing about templates.

I meant to separate the name of your two methods.

"sub_list - return list of values between two indicies."

Eg. In pseudocode:

Code: Select all

list = (1,2,3,4,5,6,7,8,9)
sub = list.sub_list(2,4)
print sub

Output - (3,4,5)

The immutable methods would simply return a c array containing what the "vector" contains.

[Scott]

I know nothing about templates.

Are they not part of C at all? I know little about them, but I think it allows for types to be more dynamic (such as making the myVector class work with char, int, long, short, ect).

sub_list - return list of values between two indicies."

Eg. In pseudocode:

Code: Select all

list = (1,2,3,4,5,6,7,8,9)
sub = list.sub_list(2,4)
print sub

Output - (3,4,5)

Oh, I get ya. You could just go:

Code: Select all

for (int i = start; i < end; i++)
    std::cout << myVec[i];

I'm not a fan of functions that write to the screen as different programs require different formatting which causes complications.

The immutable methods would simply return a c array containing what the "vector" contains.

What would be the use? The vector is an array.

[Matthew]

It's not a C array.

The sub_list method is supposed to return a vector which is part of a vector. It's not supposed to print anything.

[Scott]

It's not a C array.

I guess not. I'm going straight up C++ though.

The sub_list method is supposed to return a vector which is part of a vector. It's not supposed to print anything.

Oh, I see:

Code: Select all

CODE WILL BE HERE WHEN I FINISH.

[Matthew]

I'm sure many C++ functions take normal arrays, don't they? I'm sure various libraries will.

[Scott]

I'm sure many C++ functions take normal arrays, don't they? I'm sure various libraries will.

Weren't you talking about returning a C array? Yes, you can use arrays as parameters (usually as references or pointers) but returning is another story (as you know). You can however return a myVector and place it in another myVector. Hence the previous code I said I would post:

Code: Select all

void copy_paste(int start, int finish, myVector& new_myVector) //returns a cut section of a myVector
        {
            new_myVector.clean();
            new_myVector.itsLength = ((finish+1)-start);

            for (int i = start, j = 0; i < finish+1; i++, j++)
                new_myVector[j] = pVector[i];
        }

        void cut_paste(int start, int finish, myVector& new_myVector) //returns a cut section of a myVector and deletes those variables from the myVector
        {
            new_myVector.clean();
            new_myVector.itsLength = ((finish+1)-start);

            for (int i = start, j = 0; i < finish+1; i++, j++)
                new_myVector[j] = pVector[i];

            int count = 0;

            for (int i = start; i < finish+1; i++)
            {
                take_off(i-count);
                count++;
            }
        }

Originally going to use the operator = something went wrong I don't have the time to look through the code to figure it out. It's not a big problem anyway.

NOTE: My comments say return because they originally did that.

[Matthew]

Returning an array is easy. This is the type of thing you need to understand pointers for. In C you do something like this (I wont test it so take it with a pinch of salt):

Code: Select all

int * range(int start,int stop,int step){
    int * array = malloc(sizeof(int) * (stop - start)/step);
    int y = 0;
    for(int x = start,x < stop,x += step){
        int[y] = x;
        y++;
    }
    return array;
}

[Scott]

Returning an array is easy. This is the type of thing you need to understand pointers for. In C you do something like this (I wont test it so take it with a pinch of salt):

Code: Select all

int * range(int start,int stop,int step){
    int * array = malloc(sizeof(int) * (stop - start)/step);
    int y = 0;
    for(int x = start,x < stop,x += step){
        int[y] = x;
        y++;
    }
    return array;
}

Yes, but I wasn't returning an array. I was returning a myVector, which usually does work, but for some reasons comes up with errors which contradict my class. In myVector, the developer using the class never deals with arrays. The class does array management and the developer just uses myVector.

On a separate note, I just made a huge improvement to myVector. I read up on templates and am very glad I did so:

Code: Select all

template <typename T>
class myVector
{
    public:
        myVector(){itsLength = 0; pVector = new T[itsLength];} //Constructor sets length and creates a vector
        ~myVector(){clean();} //deletes pointers

        T& operator [] (int location) //allows for the [] subscript
        {
            if (itsLength > 0)
                return pVector[location];
        }

        void operator = (myVector& myVec) //allows to copy vectors to each other
        {
            itsLength = myVec.len();
            delete pVector;
            pVector = new T[itsLength];

            for (int i = 0; i < itsLength; i++)
                pVector[i] = myVec[i];
        }

        void add_on (T newElement) //adds an element to the end
        {
            tempVector = new T[itsLength];

            for (int i = 0; i < itsLength; i++)
                tempVector[i] = pVector[i];

            delete pVector;
            itsLength++;
            pVector = new T[itsLength];

            for (int i = 0; i < itsLength; i++)
                pVector[i] = tempVector[i];

            pVector[itsLength-1] = newElement;

            delete tempVector;
        }

        void add_on (myVector& myVec) //adds another myVector to the end
        {
            tempVector = new T[itsLength+myVec.itsLength];

            for (int i = 0; i < itsLength; i++)
                tempVector[i] = pVector[i];

            for (int i = itsLength, j = 0; i < itsLength+myVec.itsLength; i++, j++)
                tempVector[i] = myVec[j];

            itsLength += myVec.len();
            pVector = new T[itsLength];

            for (int i = 0; i < itsLength; i++)
                pVector[i] = tempVector[i];

            delete tempVector;
        }

        void take_off(int location) //takes off the element at int location
        {
            itsLength--;
            tempVector = new T[itsLength];

            int j = 0;
            for (int i = 0; i < itsLength+1; i++)
            {
                if (i != location)
                {
                    tempVector[j] = pVector[i];
                    j++;
                }
            }

            delete pVector;
            pVector = new T[itsLength];

            for (int i = 0; i < itsLength; i++)
                pVector[i] = tempVector[i];

            delete tempVector;
        }

        void take_off() //takes off the element on the end
        {
            itsLength--;
            tempVector = new T[itsLength];

            int j = 0;
            for (int i = 0; i < itsLength+1; i++)
            {
                if (i != itsLength+1)
                {
                    tempVector[j] = pVector[i];
                    j++;
                }
            }

            delete pVector;
            pVector = new T[itsLength];

            for (int i = 0; i < itsLength; i++)
                pVector[i] = tempVector[i];

            delete tempVector;
        }

        void wipe(int start, int finish) //deletes everything from start() to finish()
        {
            for (int i = start; i < finish+1; i++)
                take_off(start);
        }

        void push_in(int location, T newElement) //Adds an element to a specified location
        {
            tempVector = new T[itsLength];

            for (int i = 0; i < itsLength; i++)
                tempVector[i] = pVector[i];

            delete pVector;
            itsLength++;
            int test = itsLength;
            pVector = new T[itsLength];

            for (int i = 0, j = 0; i < test; i++)
            {
                if (i == location)
                    pVector[i] = newElement;
                else
                {
                    pVector[i] = tempVector[j];
                    j++;
                }
            }

            delete tempVector;
        }

        void push_in(int location, myVector& myVec) //Adds another myVector to a specified location
        {
            tempVector = new T[itsLength];

            for (int i = 0; i < itsLength; i++)
                tempVector[i] = pVector[i];

            delete pVector;
            itsLength+=myVec.itsLength;
            int test = itsLength;
            pVector = new T[itsLength];

            int perm, temp, i;
            for (int j = 0, i = 0; i < test; i++)
            {
                if (i == location)
                {
                    for (perm = location, temp = 0; temp < myVec.itsLength; temp++, perm++)
                        pVector[perm] = myVec[temp];
                    i = perm-1;
                }
                else
                {
                    pVector[i] = tempVector[j];
                    j++;
                }
            }

            delete tempVector;
        }

        void exchange(myVector& myOther) //Exchanges two myVectors
        {
            if (itsLength > myOther.len())
            {
                tempVector = new T[myOther.len()];

                for (int i = 0; i < myOther.len(); i++)
                    tempVector[i] = myOther[i];

                int itsNewLen = itsLength-(itsLength-myOther.len());
                myOther.itsLength+=(itsLength-myOther.len());

                for (int i = 0; i < myOther.len(); i++)
                    myOther[i] = pVector[i];

                itsLength = itsNewLen;

                for (int i = 0; i < itsLength; i++)
                    pVector[i] = tempVector[i];
            }
            else
            {
                tempVector = new T[itsLength];

                for (int i = 0; i < itsLength; i++)
                    tempVector[i] = pVector[i];

                int newLen = myOther.len()-(myOther.len()-itsLength);
                itsLength+=(myOther.len()-itsLength);

                for (int i = 0; i < itsLength; i++)
                    pVector[i] = myOther[i];

                myOther.itsLength = newLen;

                for (int i = 0; i < myOther.len(); i++)
                    myOther[i] = tempVector[i];
            }
        }

        void copy_paste(int start, int finish, myVector& new_myVector) //Creates a cut section of a myVector
        {
            new_myVector.clean();
            new_myVector.itsLength = ((finish+1)-start);

            for (int i = start, j = 0; i < finish+1; i++, j++)
                new_myVector[j] = pVector[i];
        }

        void cut_paste(int start, int finish, myVector& new_myVector) //Creates a cut section of a myVector and deletes those variables from the myVector
        {
            new_myVector.clean();
            new_myVector.itsLength = ((finish+1)-start);

            for (int i = start, j = 0; i < finish+1; i++, j++)
                new_myVector[j] = pVector[i];

            int count = 0;

            for (int i = start; i < finish+1; i++)
            {
                take_off(i-count);
                count++;
            }
        }

        void clean() //deletes and restarts everything
        {
            delete pVector;
            delete tempVector;
            itsLength = 0;
        }

        //SOME SMALL INLINE FUNCTIONS
        int start() {return 0;}
        int finish() {return itsLength;} //Alternative iterator to len()
        int len() {return itsLength;}

    private:
        int itsLength;
        T *pVector;
        T *tempVector;
};

It now handles all types and is initialized just like std::vector is:

Code: Select all

myVector <type> name;

I have only tried it with numbers (float, int, ect) and characters so far, but it works! I will be trying strings soon. I'm curious to what the results will be...

EDIT:
Results: Not so good. I get a compilation, but no output. I'll have to look through to see what's going on but I don't see a use for a dynamic container of strings anyway. I wonder if std::vector is even compatible with strings...

[Matthew]

But since APIs may want a C array, you should have a method to return an array. Allocate memory to store the contents and then copy each element from your class to the array and return the array.

You must free the memory afterwards though. That is an unavoidable must because you are using memory management.

[Scott]

If you think it's that important

myVector.h

Code: Select all

T* return_array(){return pVector;}

myVector.cpp

Code: Select all

cout << "\n\nreturn_array() Test: newVec length: " << newVec.len() << "\newArray: ";
    char *newArray = new char[newVec.len()];
    newArray = newVec.return_array();
    for (int i = 0; i < myVec.len()+1; i++)
        cout << newArray[i] << ", ";

return_array() Test: newVec length: 4
newArray: d, e, f, g,

[Matthew]

I'm not sure about c++ much but I think there is a leak there. You are allocating space for an array with new char[newVec.len()]; and you are then using the pointer which points to that memory to point to the array returned by your class. The allocated memory is no longer pointed to and is leaked.

[Scott]

The allocated memory is no longer pointed to and is leaked.

You mean the memory from the class? I'm not being arrogant but attempting to understand what you mean; where does the allocated memory no longer point to the array? I do think there is a leak too as the results required me to increment it's length in the loop but I'm new to even having memory leaks.