Vector

From DocForge

A vector is a fancy term for a smarter array. A vector is also known in Java as an ArrayList. A Vector type also exists in Java, however, it isn't as capable as the ArrayList. Advantages of the vector as a data structure are that it has extremely fast accesses, O(1). Disadvantages are that it's not very fast at insertions or sorting, where other tree and linked list based data structures excel. However, it is one of the simplest data structures there is, if not the simplest data structure, and when used effectively can be a total force-multiplier in program efficiency. It only takes a few minutes to describe the vector, but it takes a lifetime to realize its full potential.

Vector
Iterators	Random-access
Big-O
Lookup	O(1)
List Operations	O(n)+
Front Operations
Back (Stack) Operations	O(1)+
+ indicates occasionally a significant extra cost is incurred

Vector's main advantages over straight arrays make them much better than arrays, however, the increased overhead does make them highly inappropriate in many situations.

Key features of a vector are:

• A vector knows its size, or how many elements are in it. This is particularly important in languages like C++, where normal arrays do not have any information about their size. In languages like Java, where arrays already have a size field, this isn't as critical.
• Dynamic size. Unlike an array, you can add elements to vectors very easily. This removes the necessity of explicitly increasing a normal array's size, a task which is a pain even in Java. This doesn't make it any faster, it just makes code more readable because the lengthy nuances of explicit array resizing are obfuscated to the Vector functions.

In addition, most implementations of vectors use smarter memory allocation techniques, usually increasing the total size of the new array by half the size of the old array. This reduces the frequency of the use of costly operations like array copying, though it does reduce memory efficiency. Vector size can be manually ensured to be optimized, however, this could cause greater overhead due to automatic size features earlier mentioned. Generally, if a data structure is causing problems related to this, it's a good idea to write a custom one rather than revert to a more primitive solution. Most competent programmers can write a decent data structure in a few hours, and most find it a fun exercise granted the situation is correct.

• Element removal. Unlike an array, elements can be removed from a Vector relatively easily. This doesn't necessarily make it any faster, but it does increase code readability.
• Element insertion. Unlike an array, Vectors allow you to literally insert elements into the array, wherever you may choose! This ability really does speak for itself, though it is necessary to note that this, like everything else, doesn't get you out of array copies, and only hides them (encapsulates them) to a different area.
• Polymorphic storage. By utilizing the template/generic nature of a Vector, you can effectively manage object hierarchies, an invaluable tool which can be utilized in many different situations.
• Iterable. In almost all implementations of Vectors, the Vector is iterable, which allows the programmer to quickly perform actions on every element of the vector.

Some would consider the addition of the enhanced for loop in Java 1.5 to obsolete the Vector/ArrayList, since it allows the programmer to iterate over normal arrays very quickly and effectively. However, the enhanced nature of the Vector/ArrayList makes it a better choice in many different situations, specifically for it's dynamic size and element insertion/removal features.