Jump to content




Recent Status Updates

View All Updates

Binpress - Cut your development time and costs in half
Photo
- - - - -

More About Vectors

linked list

  • Please log in to reply
5 replies to this topic

#1 chili5

chili5

    CC Mentor

  • Expert Member
  • PipPipPipPipPipPipPipPip
  • 3,031 posts
  • Programming Language:Java, C#, PHP, JavaScript, Transact-SQL
  • Learning:C, Java, C++, C#, PHP, JavaScript, Transact-SQL, Assembly, Scheme

Posted 17 July 2009 - 08:53 AM

More about Vectors

A little while ago I talked about Vectors but I didn't cover as much about them as I wanted too. I was completely blind as to how the structure truly works and why it isn't always the best choice.



Generics and Vectors


In the previous tutorial I showed how the Vector can hold objects but there is a bit more to it than that. The Vector class is a generic class which means you can indicate what type of data the Vector can hold. The default value is of type Object.

Since the default value is of type Object, it can hold any type of data. Why? In Java, all classes are subclasses of type Object. If you declare a Vector to hold objects of type Object it can hold data of type Object and anything that is a subclass of Object.

In Netbeans, if I press Ctrl-B I can see the code that creates the Vector object. I've learned so much reading the code in the Vector class.

Let us look at the class declaration of the Vector.

public class Vector<E>

The <E> indicates that the Vector is a generic class. When you declare an instance of the class you call the constructor but you also specify the type of data the vector holds.

Example:

Vector<Object> v = new Vector<Object>();

The above code creates a Vector object that holds Objects. This is the same as writing

Vector v = new Vector();

However, if I want a Vector that just holds Integer object, I would declare it as follows:

Vector<Integer> v = new Vector<Integer>();

You can change the data type in the angle brackets to whatever you want. It has to be a Object though. It cannot be a primitive data type.

Why use generics?

Generics enforce that the structure only holds data of a certain type. If you try to add something that is not of the declared type then the program will fail. It also eliminates the need to use typecasting to get the data out from the vector. If you declare a vector to be of type Object you have to use typecasting to get the correct data type.

Example:

Vector v = new Vector();
v.add(new Integer(6));
v.add(new String("test"));

System.out.println((Integer)v.get(0));
System.out.println((String)v.get(1));

This is messy and more prone to errors. If you declare it to be more generic you do not have to make the type casts. The above lines return a value of type Object which has to be converted to the appropriate type.

Example:

Vector<Integer> v = new Vector<Integer>();
v.add(6);
v.add(8);

System.out.println(v.get(0));
System.out.println(v.get(1));

Since the method is a generic method, the return type is whatever type the Vector was declared as. The above 2 lines return a value of type Integer instead of type Object. The idea of generics is very similar to the idea of templates in C++. I haven't explained very much (if anything) about how generics actually work but it can make your code a lot easier to follow and helps to prevent silly errors.

Deleting values

Deleting items from the vector is as simple as calling the remove method and passing the index to delete at. As simple as this is, this isn't the most efficient operation when deleting items from the middle of the list.

Example:

v.remove(0);


Efficient operations

Looking at how the Vector works we can determine that it is inefficient at inserting and deleting items in the structure. Why? When a vector is created it has a certain size. When an item is added at the end of the structure, the array has to be resized.

If the array has 450 items in it and an item is deleted at the end, we have to copy 449 items into a new array.

If this occurs often then the program has to constantly maintain the vector which results in lower performance.

Now imagine if an item is added at position 5 in the vector. The vector has to be resized and everything after position 5 has to be moved over to make room for the new item.

If you need to remove or add items in random positions in the list then the Vector is not the most efficient structure and you should be using a Linked List structure instead.

However, when you need an array structure that grows this is a great structure to use. It is used in Java's implementation of the Stack.

Hope this helps explain more about how the Vector works.
  • 2

#2 Guest_Jordan_*

Guest_Jordan_*
  • Guest

Posted 17 July 2009 - 09:09 AM

Another great one! Thanks Chili! +rep
  • 0

#3 WingedPanther

WingedPanther

    A spammer's worst nightmare

  • Moderator
  • 16,930 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 17 July 2009 - 10:11 AM

Can you resize Java Vectors? One of the nice things about C++ is you can specify a size in advance to avoid the constant size adjustments. +rep
  • 0
Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

#4 chili5

chili5

    CC Mentor

  • Expert Member
  • PipPipPipPipPipPipPipPip
  • 3,031 posts
  • Programming Language:Java, C#, PHP, JavaScript, Transact-SQL
  • Learning:C, Java, C++, C#, PHP, JavaScript, Transact-SQL, Assembly, Scheme

Posted 17 July 2009 - 11:49 AM

Yes, you can resize vectors using the setSize(int newSize); method. What happens when you call this method and newSize is greater than the newSize then a new array is allocated with the old items and null items added to the end.

If the new size is less than the current size then all items at index newSize and greater are discarded.

I like how in C++ you specify a size in advance. In Java you can't do that as far as I know. You specify an initial capacity but the size of the vector remains 0 until you add elements.

If I use this constructor:

Vector v = new Vector(10);

The size of the underlying array is 10 but the size of the vector is 0.
  • 0

#5 kishkabear

kishkabear

    CC Lurker

  • Just Joined
  • Pip
  • 5 posts

Posted 03 May 2010 - 11:32 AM

More about Vectors

A little while ago I talked about Vectors but I didn't cover as much about them as I wanted too. I was completely blind as to how the structure truly works and why it isn't always the best choice.



Generics and Vectors


In the previous tutorial I showed how the Vector can hold objects but there is a bit more to it than that. The Vector class is a generic class which means you can indicate what type of data the Vector can hold. The default value is of type Object.

Since the default value is of type Object, it can hold any type of data. Why? In Java, all classes are subclasses of type Object. If you declare a Vector to hold objects of type Object it can hold data of type Object and anything that is a subclass of Object.

In Netbeans, if I press Ctrl-B I can see the code that creates the Vector object. I've learned so much reading the code in the Vector class.

Let us look at the class declaration of the Vector.

public class Vector<E>

The <E> indicates that the Vector is a generic class. When you declare an instance of the class you call the constructor but you also specify the type of data the vector holds.

Example:

Vector<Object> v = new Vector<Object>();

The above code creates a Vector object that holds Objects. This is the same as writing

Vector v = new Vector();

However, if I want a Vector that just holds Integer object, I would declare it as follows:

Vector<Integer> v = new Vector<Integer>();

You can change the data type in the angle brackets to whatever you want. It has to be a Object though. It cannot be a primitive data type.

Why use generics?

Generics enforce that the structure only holds data of a certain type. If you try to add something that is not of the declared type then the program will fail. It also eliminates the need to use typecasting to get the data out from the vector. If you declare a vector to be of type Object you have to use typecasting to get the correct data type.

Example:

Vector v = new Vector();
v.add(new Integer(6));
v.add(new String("test"));

System.out.println((Integer)v.get(0));
System.out.println((String)v.get(1));

This is messy and more prone to errors. If you declare it to be more generic you do not have to make the type casts. The above lines return a value of type Object which has to be converted to the appropriate type.

Example:

Vector<Integer> v = new Vector<Integer>();
v.add(6);
v.add(8);

System.out.println(v.get(0));
System.out.println(v.get(1));

Since the method is a generic method, the return type is whatever type the Vector was declared as. The above 2 lines return a value of type Integer instead of type Object. The idea of generics is very similar to the idea of templates in C++. I haven't explained very much (if anything) about how generics actually work but it can make your code a lot easier to follow and helps to prevent silly errors.

Deleting values

Deleting items from the vector is as simple as calling the remove method and passing the index to delete at. As simple as this is, this isn't the most efficient operation when deleting items from the middle of the list.

Example:

v.remove(0);


Efficient operations

Looking at how the Vector works we can determine that it is inefficient at inserting and deleting items in the structure. Why? When a vector is created it has a certain size. When an item is added at the end of the structure, the array has to be resized.

If the array has 450 items in it and an item is deleted at the end, we have to copy 449 items into a new array.

If this occurs often then the program has to constantly maintain the vector which results in lower performance.

Now imagine if an item is added at position 5 in the vector. The vector has to be resized and everything after position 5 has to be moved over to make room for the new item.

If you need to remove or add items in random positions in the list then the Vector is not the most efficient structure and you should be using a Linked List structure instead.

However, when you need an array structure that grows this is a great structure to use. It is used in Java's implementation of the Stack.

Hope this helps explain more about how the Vector works.


===============================================================
This should not be listed as an advanced topic... Multidimensional Vectors would qualify though...

ie:

java.util.Vector <java.awt.Point> v = new java.util.Vector<java.awt.Point>(); // fill with xy data

java.util.Vector <java.awt.Point> vPoints[][][] = new java.util.Vector[10][10][10];
// reports  >> warning: [unchecked] unchecked conversion


// create a new Vector at 0,0,0 with size 20
vPoints[0][0][0] = new java.util.Vector<java.awt.Point>(20);

java.util.Collections.copy(vPoints[0][0][0], v);
// reports >> warning: [unchecked] unchecked method invocation: <T>copy(java.util.List<? super T>,java.util.List<? extends T>) in java.util.Collections is applied to (java.util.Vector,java.util.Vector<java.awt.Point>)

// and then lets have an accesor method...
public java.util.Vector <java.awt.Point> getPoints()
{
            return (vPoints[0][0][0] != null) ? (java.util.Vector)vPoints[0][0][0] : null;
}
//reports >> warning: [unchecked] unchecked conversion
any suggestions?

by KishkaBear
================================================================
  • 0

#6 GMVResources

GMVResources

    CC Resident

  • Just Joined
  • PipPipPipPip
  • 71 posts

Posted 14 June 2010 - 04:05 AM

Nice tut!
  • 0





Also tagged with one or more of these keywords: linked list

Powered by binpress