What are vectors?

[Oromis]

Hello people,

My first post on this site, aldo I've used this site a lot already. The tutorial and reference are great.

I've some questions about vectors. I'm reading "C++ Templates: The Complete Guide" and in chapther 3 I came accross vectors. I've read the reference-page about vectors. I didnt understand everyting, but I do understand you can store information in vectors and get it out, and that the vector will do the memory-stuff for you.
I know vectors from math at school. There they represent arrows.I dont see the link with vectors in C++. Is it the same thing?
Furthermore, I dont understand how a vector works. I dont need to know this to use them, but I'm just curious. How do they manage the memory?
What do vectors have to do with templates? I understand you can use templates to create vecotrs to store different datatypes inside object of the same class, but are templates nessesary for vectors?

Another question: I'm learning C++ on my own. If I want someone to judge my (not to long) programs, is there a place where I can post them? Can I post them on this site?

Thanks for any answers,
Oromis

[Bazzy]

C++ Vectors are not the same you studied at school, they are one of the many STL containers.
STL means Standard Template Library so all of that stuff works with Templates,
every container needs Templates to know what it's containing.
I think the actual way a vector works depends on the standard library implementation you have

[Corpus]

Well, there is a connection between high school vectors and STL vectors. Most commonly, "vectors" are used to represent points or directions in a plane or in space, and there they are often a 2- or 3-tuple of real numbers, say the gravity vector is [0, -9.82] m/s^2.

However, the word "vector" has a broader meaning. Mathematicaly, a vector is simply an ordered sequence of ordinates. For example, you also talk about "test vectors" when you test a system. In this situation, the test vector is a sequence of events that you subject your system to over time.

STL vectors shuld be understood in this broader sense. It is an ordered sequence of thingies - you can use it for regular force/velocity/... vectors, but also for a multitude of other purposes.

[Oromis]

Thanks Corpus and Bazzy. That answered my first and most confusing question. So the word "vector" covers a broad range of subjects, meaning "an ordered sequence of ordinates", and at highschool a very limited meaning of this word is used.
I still wonder however why vectors are so strongly connected with templates. Wy "STL containers" and not "containers"? I understand it's usefull to use templates so you can use the same class for any datatype, but is that the only reason? I think it has someting to do with the way vectors work and I know the answer will probably be complex, but if someone could explain this to me (or give a link with the answer) I would be greatfull. Or maybe I will figure it out when I read along in "templates: the complete guide".

[Bazzy]

If containers hadn't the templates, they would work only for some specific data types instead of being general.
As they are part of the standard library they have to be compatible with everything a programmer would create.

[Oromis]

Thanks Bazzy, that makes sense. Only one question left, aldo I doubt or I'll able to understand the answer: how do vectors work? How do they manage the memory? I don't need to know the answer to use vectors, but I'm just curious.

[helios]

Suppose you create a vector with this line: std::vector<int> v;
IIRC, std::vector allocates memory for an int array of capacity 10 and assigns a size of 0.

When you do a push_back(), std::vector checks that the size (how many elements are actually in the array) is not greater than the capacity (the real size of the array). If it isn't, the size is incremented and the last element is assigned to the parameter passed. If it is, the vector is manually copied to a different location. In other words, the copy constructor and the destructor of each of the elements is called, rather than making a call to realloc(). This is important to know, and I'll explaing why later. The destination array is always twice as big as the original, so if before the push_back() size==10 and capacity==10, after it size==11 and capacity==20.

Let's take the following class for example:

struct A{
	int *a;
	A(){
		this->a=new int;
	}
	~A(){
		delete this->a;
	}
};

This class is not suitable to be used as std::vector<A>, but it can be used as std::vector<A *>.
Why? Because, since the class is using the default copy constructor, which just copies each of the elements, copy->a will point to the same int as original->a. When the original is destructed, original->a will point to an invalid location, and by extension so will copy->a.
On the other hand, a vector of pointers to objects will never cause this kind of trouble.

When an element is removed from the vector (at least when it's not the last element), it's only destructed, but its memory is not freed. This is important to know when using vectors with large or many objects.

[Oromis]

Thanks helios! I understand the first part of your post and the last two sentences.
I understand that the example class A can't be used for a vector, because each time the capacity of the vector is reached, the destructer will be called and the value inside a will be lost. This wont be the problem with pointers, because the actuall objects where they're pointing to won't be destroyed and again construced. Right?
I do have a question about your example. I'm not really familiair with the this-keyword and the -> operator (I had to look it up), but wy are you using them here? This returns a pointer to the object, -> can be used to access a member from a pointer to an object, so isnt this->a=new int; the same as a=new int;?

[helios]

This wont be the problem with pointers, because the actuall objects where they're pointing to won't be destroyed and again construced. Right?

Exactly.

wy are you using them here? [...] isnt this->a=new int; the same as a=new int;?

I once had to read a large (10k+ lines) piece of code that used globals and didn't use the explicit this-> syntax. It's very frustrating to look at unfamiliar code and to not know whether a line is modifying global, local, or member data.

I swore at that moment to always use this-> if I had to reference member data.

[Oromis]

Thanks helios, that makes sense. I will from now on always try to use this-> ;)

[Oromis]

Hello people, I'm back :D

I figured it would be a good practice to create my own vector-like class. To avoid confusion I called it "save", and it seems to work pretty well with all build-in types and string (didn't test it on other types yet). But any suggestions are advizes are greatly apprecianted:

template <typename T>
class save
{
  public:
    save();
    void store(T);
    T get(int);
    T get();
    int get_size();
    int get_capacity();
    void delete_last();
    void clear();
    void sort();
  private:
    T* element;
    T* temp;
    int size;
    int capacity;
};

template <typename T>
save<T>::save()
{
    size=0;
    capacity=10;
    temp=NULL;
    element= new T [capacity];
}

template <typename T>
void save<T>::store(T new_element)
{
    if (size==capacity)
    {
        temp= new T [capacity];
        for (int i=0;i<capacity;i++)
            temp[i]=element[i];
        delete [] element;
        capacity*=2;
        element= new T [capacity];
        for (int i=0;i<capacity;i++)
            element[i]=temp[i];
        delete[] temp;
    }
    element[size]=new_element;
    size++;
}

template <typename T>
T save<T>::get(int index)
{
    if (index>=size || size==0)
       return false;
    return element[index];
}

template <typename T>
T save<T>::get()
{
    if (size==0)
        return false;
    return element[size-1];
}

template <typename T>
int save<T>::get_size()
{
    return size;
}

template <typename T>
int save<T>::get_capacity()
{
    return capacity;
}

template <typename T>
void save<T>::delete_last()
{
    size--;
}

template <typename T>
void save<T>::clear()
{
    delete [] element;
    size=0;
    capacity=10;
    element= new T [capacity];
} 

Now I got that right, I thought it would be fun to add some more features. So I started to create a sort-function. But I came across some problems. Here is the function:

template <typename T>
void save<T>::sort()
{
    temp= new T [size];
    for (int i=0;i<size;i++)
    {
        int high=0;
        for (int i=0;i<size;i++)
        {
            if (element[i]>element[high])
                high=i;
        }
        temp[i]=element[high];
        element[high]=NULL;
    }
    for (int i=0;i<size;i++)
        element[i]=temp[i];
    delete [] temp;
}

My questions/problems are:
- What do you think about the algorithm? Is it workable or should I use another one?
- I use the '>' operator. This would normally limit the class to datatypes that support this operator. Is there a way to work around this? The first solution I thought of wast to create another class that inherite from "save" and add this specific function, but is there an easier way? This would be quit a lot of work when using a lot of operators in a template-class.
- In line 14 I'm assigning NULL to an element. This is essential to the algorithm I'm using, but isn't supported by all types. Maybe I could use pointers and assign them to NULL after being used, but again: is there an easier way?

Thanks for any ansers/general advize

Ps. Sorry helios, I didnt use this-> :) I tried, but it looked very confusing to me. Maybe in bigger applications it's usefull, but for now I think it's easier to refere to membervariables with just their names.

[psault]

Hi Oromis.
I like your save class, it looks like good exercise. I looked it over, and I found a couple things that you might consider to be flaws. In your get() methods, what happens if the value passed in as index is a negative number? Also, what happens if someone calls delete_last() too many times and reduces the attribute "size" to a negative number?

I'm sorry that I have no comments for your sort() method, but I'm interested in seeing how this thread continues.

~psault

[Oromis]

Thanks psault! Two important things I didn't thought of. Chanced it:

template <typename T>
T save<T>::get(int index)
{
    if (index>=size || index<0 || size==0)
       return false;
    return element[index];
}

//other get() function returns last element and so there is no need to secure that to,
//as long as the rest of the methods doesnt turn size in someting wrong 

template <typename T>
void save<T>::delete_last()
{
    if (size>0) 
        size--;
}

When someting goes wrong in such cases (where I used return false or just did nothing), what is the best way to handle this? It depends on the situation I guess, but does anyone have suggestions?

[seymore15074]

Oromis, as far as the sort function relying on operator >, you might want to change it to rely on operator <.

The STL containers commonly require their elements to be LessThanComparable for many of their algorithms; additionally, there is usually a separate function that accepts a function object Comp that performs the comparison.

You might want to try to emulate the STL implementation, so that your class is consistent with concepts that are already well-known.

Other than that, I haven't taken enough time to really analyze your class, but I do have a few comments:

1. Add a destructor that releases element's memory!
2. Use an initialization list in the constructor.
3. Use inline methods (templates are usually great candadites for inlining because their size/types are known at compile time).

[Oromis]

Thanks seymore!

I added a destructor. What happens to the allocated memory when there is no destructor (isn't there a default one that releases all the memory)?
I replaced my constructor with a initialization list, mostly because it's shorter. I know the need for those lists when it comes to parent-constructors, but in this case, are there any reason to use such a list besides it's shorter?
I made most methods inline, since they're all pretty short. I dont understan your statement about size/types known at compile time. Isn't this the case with normal function/methods to?

I want to add more features to the class: that's why I started with the sort() function. I chanced the > operator into a <. I dont understand how a seperate function would solve anything. I need to perform a comparison on a unknown type. When that type does support the operation, I can do it inside the method. If not, a function wouldn't be able to do it either.
Any help or suggestions about my problems with the sort() function as I mentioned before (and any suggestions about the class itself) are still greatly appriciated.

[seymore15074]

If the memory isn't deleted by your code, it's leaked. There is no garbage collection facility in C++.

The initialization list is slightly more efficient (although, I'm unsure if some compilers will do some kind of optimization here, anyway). What happens without it is that the members are default-constructed and then assigned values rather than with the initialization list they are constructed with those values (saving the extra instruction(s) to do the additional assignment).

In order for function to be inline, I believe that it must be non-virtual (having its implementation known at compile-time).

As for the sort algorithm, it looks like a bubble sort, except it does it in a temp array and then copies that back element by element. I think that will work ok, but its performance will be a little short of anything good. ;) I suggest first trying to implement it such that it modifies the element array in place, and once you get that, try to find another algorithm (quicksort, for example).

Although this project will serve as a valuable learning exercise, note that the STL has proven/tested containers and algorithms that could perform all of this capability more efficiently.

[Oromis]

Thanks! Of course, I understand my class won't be even to compare with the existing containers. I'm just doing this to learn about templates. I will play around with your advizes and some algorithms. I'll see what wikipedia says about them ;). After that maybe add some more features. We'll see. Thanks again.