http://www.developer.com/

Back to article

Objects and Collections: Vectors


August 3, 2006

Introduction

This series, The Object-Oriented Thought Process, is intended for someone just learning an object-oriented language and who wants to understand the basic concepts before jumping into the code, or someone who wants to understand the infrastructure behind an object-oriented language he or she is already using. These concepts are part of the foundation that any programmer will need to make the paradigm shift from procedural programming to object-oriented programming.

Click here to start at the beginning of the series.

In keeping with the code examples used in the previous articles, Java will be the language used to implement the concepts in code. One of the reasons that I like to use Java is because you can download the Java compiler for personal use at the Sun Microsystems Web site http://java.sun.com/. You can download the standard edition, J2SE 5.0, at http://java.sun.com/j2se/1.5.0/download.jsp to compile and execute these applications. I often reference the Java J2SE 5.0 API documentation and I recommend that you explore the Java API further. Code listings are provided for all examples in this article as well as figures and output (when appropriate). See the first article in this series for detailed descriptions for compiling and running all the code examples.

In the previous column, you moved from the topic of primitives (basically the low-level system variables), objects, and wrappers to the concept of collections. To begin the discussion on the relationship between objects and collections, you covered the topic of arrays, perhaps the original collection.

In many ways, you are covering a bit of history as you make your way through the topic of collections. Although arrays may be the original collection, there are now certainly many different types of collections to consider. In the beginning, Java did not include a collection framework. Over the past 10 years or so, collections have been added and others have become obsolete. The way to process certain collections also has evolved in different ways.

Because you are focusing more on conceptual matters in this column, you often take a different approach when inspecting actual code. Instead of looking at the code from a purely technical perspective, you can step back and consider some of the reasons why certain design decisions were made. For example, why were some collections introduced and why did certain ones become obsolete?

As already stated, you want to take a historical perspective, as well as one that is purely technical. Curiously enough, this approach also has a solid technical basis. There are many people who wonder what the advantage is to learning technical implementations that are considered obsolete. In the software industry, most cutting-edge developers want to work on cutting-edge code. This is understandable. However, there are two compelling technical reasons why developers should study code that may have recently been deemed obsolete — testing and maintenance.

I often stress to my students that they need to be prepared to encounter all sorts of code — not just the latest technology. All developers are involved in maintenance, which involves bug fixing or enhancements. Often, code that is being maintained may have been in production for quite a while.

In the case of Java, the code could potentially be up to a decade old. When testing, a developer may need to test with code that may be just as old. In any event, a developer must be aware of the historical evolution of the system being worked with. Although there are certainly more recent collections available to developers, Arrays and Vectors are important constructs that need to be understood.

In this column, I will discuss processing techniques for Vectors, a few of which have become obsolete. However, understanding the code when you do see it is important. Although I have stated that the Array may be the original collection, it may not be the best or most efficient. Take a look at some of the limitations of the Array and see what has evolved over time to address some of these limitations.

Arrays

Baseline

First, you should revisit the code from the last column. The code in Listing 1 creates a very simple array called items and then prints out the contents of the array. Compile and execute this code to verify that your system is working properly. You will use this as the baseline for the remainder of the article.

public class TestArray {
   public static void main(String[] args) {
      int[] items = {0,1,2,3,4};
      for (int i = 0; i<5; i++) {
         System.out.println("items[" + i + "]=" + items[i]);
      }
   }
}

Listing 1: TestArray.java

When this application is executed, you should get the following output (the actual program output is in bold).

C:column25>"C:Program FilesJavajdk1.5.0_06binjava" TestArray
items[0]=0
items[1]=1
items[2]=2
items[3]=3
items[4]=4
C:column25>

Array Limitations

Although arrays have been used successfully for about as long as computer languages have existed, there is one obvious drawback to arrays — their size is static. In other words, the size of an array, once defined, cannot change. This leads to two obvious problems.

First, consider the code in Listing 1. The size of the array items is determined by the compiler to be 5. In this simple application, this works. However, most applications are not quite as simple, and you quickly can run into problems. What if, after the application is running, you find out that you need a sixth, or seventh, item in the array? There is nothing that you can do. To allow a sixth or seventh item in the array, you must update and recompile the code and then re-distribute the application.

Second, if it turns out that you only needed two of the items in the array, there is no way to free-up the memory of the unused thee array items. In this case, that means that the space for three integers will be lost for the remainder of the run of the application. 32 bits are used to store a Java integer. That means that in this example, there would be 96 (32*3) bits of unused (basically lost) memory.

You might wonder what the concern is because 96 bits is not really that much memory. The problem becomes more acute when you have large arrays that are created multiple times. For example, assume that you have an application that creates an array of 100 elements for 1000 customers. Further assume that the customers use an average of only 50 elements. That means that, on average, 50 elements for each of the 1000 customers will be unused.

Doing the math, you can determine that for the 50000 unused elements you have 1,600,000 bits (32*50,000) that are not available to the computer system. With the proliferation of small devices, such as phones, PDAs, and others, the footprint (size) of the code can be very important. Even a small amout of memory can make a difference.

One question might be: If you only use an average of 50 elements per customer, why don't you just make the array size 50? The key word is average. If only a single customer needs 100 elements, the array must be of size 100. In short, the array must be the size of the largest possible situation; otherwise, it won't work in that instance.

The essence of this discussion is that the array fails on both counts. If the array is too large, it wastes memory. If the array is too short, it simply won't work. Sizing an array is really a guess.

Vectors

A Better Array?

Based on the discussion in the previous section, what would be a logical proposal that would greatly enhance the functionality of an array? The answer: Design the array so that the array can change its size, or more succinctly, design an array that can dynamically grow based on the needs of the application. The word dynamically is key here because it implies that the array will change during the execution of the application. This means that the size of the array is not determined at compile time.

What makes this even more interesting is the fact that the concept of doing business dynamically is fundamental to the Java and .NET models specifically, and, in more fundamental ways, the object-oriented paradigm itself. Creating things dynamically requires that the functions such as memory allocation and network connection be dealt with at runtime. Thus, as you go in search of an improved array, you are looking for an array that will allow you to obtain memory only when you need it.

When the collection framework was first released, a collection called a Vector was included. The Java documentation (v1.3) definition presents the hierarchy for the Vector class.

java.util: Class Vector

java.lang.Object
   |
   +--java.util.AbstractCollection
      |
      +--java.util.AbstractList
         |
         +--java.util.Vector

Note that the Vector inherits from AbstractList and AbstractCollection. Thus, a Vector is both a List and a Collection. I will discuss Lists in great detail later.

The Vector is often defined as a growable array. In fact, the Java documentation (v1.3) for the Vector describes it thus:

"The Vector class implements a growable array of objects. Like an array, it contains components that can be accessed using an integer index. However, the size of a Vector can grow or shrink as needed to accommodate adding and removing items after the Vector has been created."

The documentation further describes how the Vector fits into the Java Collection Framework.

As of the Java 2 platform v1.2, this class has been retrofitted to implement List, so that it becomes a part of Java's collection framework. Unlike the new collection implementations, Vector is synchronized.

Now, take a look at a simple Vector application. Listing 2 presents a complete program that simply creates a Vector called myVec.

import java.io.*;
import java.util.*;

public class TestVector {
   public static void main(String[] args){
      Vector myVec = new Vector();
   }
}

Listing 2: TestVector.java

This code creates a Vector using its default constructor, which creates the Vector with an initial size of 10 elements. You can indicate a specific size by including an integer value in the constructor.

Vector myVec = new Vector(5);

With this syntax, it would seem that the Vector could be just like an Array.

import java.io.*;
import java.util.*;

public class TestVector {
   public static void main(String[] args){
      Vector myVec = new Vector();
         myVec[1] = 5;

   }
}

Listing 3: TestVector.java

However, as you might suspect, it is not quite this simple. When you compile this code, the following error message is generated.

C:column25>"C:Program FilesJavajdk1.5.0_06binjavac"
   -classpath . TestVector.java
TestVector.java:8: array required, but java.util.Vector found
   myVec[1] = 5;
     ^
1 error
C:column25>

The Vector is not treated as an Array at all. In fact, it is important to notice that the Array uses the square brackets []. So, in this case, when the compiler encounters the square brackets [], it expects an array.

You need to think of a Vector in an entirely different way.

Thinking in Terms of Objects

The syntax used to operate on an array makes it look like an Array is simply an extension of a primitive variable, and in some ways it really appears that way.

For example, you can assign an integer like this:

x = 5;

Likewise, you can assign an array with a similar syntax.

items[1] = 5;

The point of interest here is that this really is not object-oriented at all. You should be able to provide the reason why just by looking at the code in the array example. There are actually several reasons why the code items[1] = 5; breaks the object-oriented paradigm; however, perhaps the most obvious is that the fundamental concept of encapsulation is broken. The quick way to identify this problem is that assignments must be made via methods. In the code above, the assignment is performed directly to the array item, not via a method.

Note: See my article, Exploring Encapsulation, for a detailed explanation of encapsulation.

Based on the suspicion pertaining to the direct assignment of the array item, you may have guessed that the way to assign something to a Vector will require something a bit more object-oriented—like the use of a method. Take a look at the Vector's addElement( ) method.

Method Summary

boolean addElement(Object obj) Adds the specified component to the end of this vector, increasing its size by one.

Althugh the use of a method is a safe way to add an item to a Vector, it is also interesting to look at what is passed by the method, an object. This has an interesting implication; you can't assign primitives to a Vector because only an Object can be passed as a parameter. So, you can't do something like this:

import java.io.*;
import java.util.*;

public class TestVector {
   public static void main(String[] args){
      Vector myVec = new Vector();
      int x = 5;
      myVec.addElement(x);
   }
}

Listing 4: TestVector.java

Here is where the primitive wrappers come in play. If the Vector does not like to accept raw primitives, you need to send it an Object. However, if you really want a Vector of integers, you have to wrap the integers in Integer objects. Look at the code in Listing 5.

import java.io.*;
import java.util.*;

public class TestVector {
   public static void main(String[] args){

      Vector myVec = new Vector(5);
      Integer myInt = null;

      myInt = new Integer(1);
      myVec.addElement(myInt);
   }
}

Listing 5: TestVector.java

The code in Listing 5 successfully adds an element to the Vector. In this case, the element is an Integer object. However, getting the element into the Vector is only part of the story. You also need to get the element(s) out of the Vector. And, getting things out of a Vector is different than getting things out of an array.

The typical method for processing an array involves using loops like the code fragment listed below.

for (int j = 0; j<5; j++) {

   System.out.print(items[i][j]);

}

This is not the case for a Vector. The original method for processing a Vector involved using loops along with Enumerations.

Listing 6 displays a program that uses an Enumeration to process a Vector.

import java.io.*;
import java.util.*;

public class TestVector {
   public static void main(String[] args){
      Vector myVec = new Vector(5);
      Integer myInt = null;

      for(int i=0;i<5;i++){
         myInt = new Integer(i);
         myVec.addElement(myInt);
         System.out.println("addElement: " + myInt);
      }

      Enumeration myEnum = myVec.elements();
      while(myEnum.hasMoreElements())
         System.out.println("myEnum: "+(Integer)myEnum.nextElement());

   }
}

Listing 6: TestVector.java

The code to process the Vector involves loading the Enumeration with the Vector and then processing the Enumeration as long as there are elements left in the Enumeration using the hasMoreElements() method.

Enumeration myEnum = myVec.elements();    // load the Vector into myEnum
while (myEnum.hasMoreElements())          // loop thru myEnum
   System.out.println("myEnum: "+ (Integer) myEnum.nextElement());

When this code is executed, you get the following output.

C:column25>"C:Program FilesJavajdk1.5.0_06binjava"
   -classpath . TestVector
addElement: 0
addElement: 1
addElement: 2
addElement: 3
addElement: 4
myEnum: 0
myEnum: 1
myEnum: 2
myEnum: 3
myEnum: 4
C:column25>

So, you can see that the Vector was successfully loaded and later accessed correctly. Now, see how you now can "grow" the Vector.

First, you can determine the size and capacity of the Vector with the code added in Listing 7.

import java.io.*;
import java.util.*;

public class TestVector {
   public static void main(String[] args){
      Vector myVec = new Vector(5);
      Integer myInt = null;

      for(int i=0;i<5;i++){
         myInt = new Integer(i);
         myVec.addElement(myInt);
         System.out.println("addElement: " + myInt);
      }

      Enumeration myEnum = myVec.elements();
      while(myEnum.hasMoreElements())
         System.out.println("myEnum: "+ (Integer)myEnum.nextElement());

      System.out.println("nsize: "+myVec.size());
      System.out.println("capacity: "+myVec.capacity());

   }
}

Listing 7: TestVector.java

When this code is run, you can see that the size and the capacity are both 5, just as you expected.

C:column25>"C:Program FilesJavajdk1.5.0_06binjava"
   -classpath . TestVector

addElement: 0
addElement: 1
addElement: 2
addElement: 3
addElement: 4
myEnum: 0
myEnum: 1
myEnum: 2
myEnum: 3
myEnum: 4

size: 5
capacity: 5
C:column25>

Now, prove that you actually can "grow" the Vector. Listing 8 includes code to add two new elements to the Vector.

import java.io.*;
import java.util.*;

public class TestVector {
   public static void main(String[] args){
      Vector myVec = new Vector(5);
      Integer myInt = null;

      for(int i=0;i<5;i++){
         myInt = new Integer(i);
         myVec.addElement(myInt);
         System.out.println("addElement: " + myInt);
      }

      Enumeration myEnum = myVec.elements();
      while(myEnum.hasMoreElements())
         System.out.println("myEnum: "+ (Integer)myEnum.nextElement());

      System.out.println("nsize: "+myVec.size());
      System.out.println("capacity: "+myVec.capacity());

      myInt = new Integer(6);
      myVec.addElement(myInt);

      System.out.println("addElement: " + myInt);
      System.out.println("nsize: "+myVec.size());
      System.out.println("capacity: "+myVec.capacity());

      myInt = new Integer(7);
      myVec.addElement(myInt);
      System.out.println("addElement: " + myInt);

      System.out.println("nsize: "+myVec.size());
      System.out.println("capacity: "+myVec.capacity());

   }
}

Listing 8: TestVector.java

When this code is executed, you can see that the Vector has grown in size as you expected.

C:column25>"C:ProgramvFilesJavajdk1.5.0_06binjava"
   -classpath . TestVector

addElement: 0
addElement: 1
addElement: 2
addElement: 3
addElement: 4
myEnum: 0
myEnum: 1
myEnum: 2
myEnum: 3
myEnum: 4

size: 5
capacity: 5
addElement: 

size: 6
capacity: 10
addElement: 7

size: 7
capacity: 10
C:column25>

Note that the size of the Vector has increased by one as each element was added. The interesting thing to see here is that when the 6th element was added, the capacity increased to 10, not 6. Then when the 7th element was added, the capacity remained at 10. The Java documentation explains this feature as follows:

"Each vector tries to optimize storage management by maintaining a capacity and a capacityIncrement. The capacity is always at least as large as the vector size; it is usually larger because as components are added to the vector, the vector's storage increases in chunks the size of capacityIncrement. An application can increase the capacity of a vector before inserting a large number of components; this reduces the amount of incremental reallocation."

Regardless of how the Vector is implemented internally, you have demonstrated that it does indeed "grow."

Compiler Issues & Information Gathering

You may have noticed that when you compile the code examples above, you get the following warning. (You will explore these issues in great detail when you explore the changes that have evolved in the Vector class specifically, and the Collection framework in general.)

C:column25>"C:Program FilesJavajdk1.5.0_06binjavac"
   -classpath . TestVector.java
Note: TestVector.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
C:column25>

Although the compiler calls them Notes, the messages are basically warnings (and you should always pay attention to warnings provided by the compiler). The line between warnings and outright errors has blurred a bit over the years as new versions of the JDK/SDK have evolved. Regardless of whether they are warnings or errors, you should focus on the first note: TestVector.java uses unchecked or unsafe operations. The second note provides a clue about how you can get more information.

By using the Xlint option in the compiler's parameter list, you can get a more detailed explanation as to why the warning was provided.

"C:Program FilesJavajdk1.5.0_06binjavac" -Xlint
   -classpath . TestVector.java

When you add this option, you get the following output (notice that the compiler now identifies the note as a warning):

C:column25>"C:Program FilesJavajdk1.5.0_06binjavac"
   -Xlint -classpath . TestVector.java
TestVector.java:9: warning: [unchecked] unchecked call to addElement(E)
   as a member of the raw type java.util.Vector
   myVec.addElement(x);
           ^
1 warning
C:column25>

Be aware that this code actually does compile successfully; however, you need to address the warning to make this code safe to implement, or at least compliant with the SDK 1.5.

I will cover this topic in next month's column.

References

  • www.sun.com
  • Just Java 2, 6th Edition. Peter van der Linden. 2004, Sun Microsystems.

About the Author

Matt Weisfeld is a faculty member at Cuyahoga Community College (Tri-C) in Cleveland, Ohio. Matt is a member of the Information Technology department, teaching programming languages such as C++, Java, C#, and .NET as well as various Web technologies. Prior to joining Tri-C, Matt spent 20 years in the information technology industry gaining experience in software development, project management, business development, corporate training, and part-time teaching. Matt holds an MS in computer science and an MBA in project management. Besides The Object-Oriented Thought Process, which is now in its second edition, Matt has published two other computer books, and more than a dozen articles in magazines and journals such as Dr. Dobb's Journal, The C/C++ Users Journal, Software Development Magazine, Java Report, and the international journal Project Management. Matt has presented at conferences throughout the United States and Canada.

Sitemap | Contact Us

Thanks for your registration, follow us on our social networks to keep up-to-date