NOTE:
These are a little sketchy...I'll fill in details 'soon'.
If you have an vector of information that is collected together for the sake of simply keeping it together -- a phone book, a library catalog, a TV schedule, etc. -- then you have a list. (Even simpler collections of information can be treated as a list, too -- heights of students in a class, temperatures taken over the course of time, dollar amounts of items in a shopper's basket, etc.)
The list consists of the vector of data values and the number of items currently in the list -- which is managed for us by the vector class type. If you were somehow missing one or the other of these pieces of information, you wouldn't have a complete list. (Using the vector class, however, it is nigh unto impossible to have one without the other. *grin*)
Commonly we want to do certain things to a list of information:
Each of these has further facets we'll look at in more detail later.
In the code fragments below, vec refers to the vector in which the list is being stored, vec.size() represents the current number of items in the list (duh), and k is a vector<________>::size_type position variable (fill in the _________ with the base type of the vector you are using).
When the end-user wants to see the items in their list, we must print them out. This is a fairly simple for loop with one possible complication. If they just want to see their data, fine. But sometimes our interface requires us to print the list contents as a sort of menu -- for them to choose an item to work with. In this latter case, we need to number the list items so they can more easily choose the one(s) they want to work with:
for (k = 0; k != vec.size(); k++)
{
cout << (k+1) << ": "
<< vec[k] << endl;
}
Note that we print position+1 to number the list instead of position. Why? Your average end-user doesn't wish to deal with 0-based positioning. (You don't even want to, but C++ forces you to. *grin*) This way they'll have a nice 1-based set of positions to choose from.
If the user wants to place a new piece of data into the list, there are several possibilities:
Inserting a new item at the end of the list is actually the easiest, so let's tackle that first:
vec.push_back(new_item);
It's that simple. The vector class can make managing a list extremely easy!
Next comes insertion at the beginning of the list. This is a bit trickier as we need to shift all of the old elements over by one to make room for the new item at the head of the list. But, there is no place to shift them! The vector is just the right size for the things it contains right now! So, we need to create a new position at the end of the list, then shift everyone over, and finally overwrite the first position (vec[0]) with our new item:
vec.resize(vec.size()+1); // rather than push_back some arbitrary value
// we'll politely ask the vector to grow by 1
for (k = vec.size()-1; k != 0; k--)
{
vec[k] = vec[k-1];
}
vec[0] = new_item;
Note how when we shift everyone over toward the tail of the list, we start with those at the old tail position an move down toward the old head position. If we didn't, we'd end up overwriting the entire list with the old head element before inserting the new item in the new head position. (Try it if you don't believe me!)
Finally we come to inserting somewhere in the middle of the list. After a bit of thought, it is pretty easy to see that we are doing essentially the same thing as for the 'insert-in-front' case except that the destination position is not always the head. The only extra precaution here is to make sure that the new position is legally within the current vector bounds (0 and vec.size()-1):
pos = user_index-1;
if (pos < vec.size())
{
vec.resize(vec.size()+1);
for (k = vec.size()-1; k != pos; k--)
{
vec[k] = vec[k-1];
}
vec[pos] = new_item;
}
else
{
// trying to insert outside currently valid vector bounds!
vec.push_back(new_item); // just stuff it at the end...
}
Note that to test if the position is in bounds, we only need to check against the end (vec.size()) of the range. Since all size_type's are unsigned, they can never be less than 0 -- they'd just wrap to the top of the unsigned range which will surely be greater than vec.size()!
The decision of whether to print an error message here is up to you (and your user interface).
Also be careful that when getting the new position from the end-user to adjust for their view of the list. End-user's see the list as a 1-based set of positions so you'll have to subtract 1 from the position they tell you as at the top of the above code.
As with insertion, there are several possibilities for removal. We can remove:
For instance, when removing the last item from the list, we can simply:
if (vec.size() != 0)
{
vec.pop_back();
}
else
{
// no elements to remove -- error message?
}
Now there is one less element.
The only error that could happen is if they are trying to remove from an empty list. Hence the size()!=0 check before popping the back element off our list.
Again, you may want to print an error message (or not) depending on your user interface.
For removal from the beginning, we'll have to do something akin to our insertion at the beginning. No, we don't need to get bigger. But we do need to shift all the other data over -- this time toward the head -- starting near the head!
if (vec.size() != 0)
{
for (k = 1; k != vec.size(); k++)
{
vec[k-1] = vec[k];
}
vec.pop_back();
}
else
{
// no elements to remove -- error message?
}
Notice how if we had started at the tail and shifted toward the head, we'd have overwritten the entire list with copies of the tail element. *shiver* (Don't believe me? Try it!)
And, learning from the insertion case, removal from the middle is going to simply be:
pos = user_index-1;
if (pos < vec.size())
{
for (k = pos+1; k != vec.size(); k++)
{
vec[k-1] = vec[k];
}
vec.pop_back();
}
else
{
// trying to remove outside valid vector bounds!
}
Again, we -1 from the user's chosen index because we work in a 0-based world and they live in a 1-based world.
And we also +1 to the erasure start position since we are just removing one element.
What to do when they try to remove something outside the vector is up to the application/user interface.
Thinking about it, this should work for all cases, shouldn't it? If the user chose to remove the last element, then pos would be vec.size()-1. So k would start as vec.size() -- and the for loop would not execute its body. And we'd simply perform the pop_back()! Cool...
Searching a list for a particular value is the same as searching any vector. Therefore, please see the searching notes for more information.
Since we've yet to discuss the contents of the list itself, it would seem that these routines could be easily placed in a library -- they are quite generic, after all. The only problem we face is that the contents of a list isn't just differing values, it could also be differing types: a list of heights could be double, a list of the number of people passing through an intersection every 5 minutes could be short (hopefully!), a list of genders could be char (or bool...*shrug*; maybe not...), etc.
The types don't even have to be built-in for our routines to work (although searching would need a little adjustment for the != part; into, say, .not_equal()?): a list of Point2D points to plot, a list of Complex or Rational numbers for operation testing in a math course, a list of Times for appointments, etc.
To account for this, we can try to use a typedefinition (or a few) for the list content type. (This is a bit ugly, but will work for [most] cases.)
#ifndef LIST_LIBRARY_H_INC
#define LIST_LIBRARY_H_INC
#include <vector>
typedef double ListContents; // making lists of doubles!
typedef std::vector<ListContents> List; // general list type
typedef std::vector<ListContents>::size_type
ListPosit; // general list position type
ListPosit
locate_item(const List & vec, ListContents find_this,
ListPosit end_before, ListPosit start_at = 0);
inline
ListPosit
locate_item(const List & vec, ListContents find_this)
{
return locate_item(vec, find_this, vec.size());
}
void insert_item(List & vec, ListContents ins_this,
ListPosit before_here);
inline
void insert_item_tail(List & vec, ListContents ins_this)
{
insert_item(vec, ins_this, vec.size());
return;
}
inline
void insert_item_head(List & vec, ListContents ins_this)
{
insert_item(vec, ins_this, 0);
return;
}
bool remove_item(List & vec, ListPosit rem_here);
inline
bool remove_item(List & vec, ListContents rem_this)
{
return remove_item(vec, locate_item(vec, rem_this));
}
void print_list(const List & vec, ListPosit end_before,
ListPosit start_at = 0, bool numbered = false);
inline
void print_list(const List & vec, bool numbered = false)
{
print_list(vec, vec.size(), 0, numbered);
return;
}
#endif
Note the helper inline functions in case someone wants to use the list management functions in slightly different ways.
Also, note that removal returns a bool to indicate success or failure. That leaves the printing of a message up to the main application -- removing this detail from the library makes it more generic.
Now the only thing the programmer must do to use your library is change the typedefinition line to indicate the base type of their list!
The only problem left is what if you have multiple lists in a single program (perhaps even parallel lists?)? This can be quite difficult and will (for now, anyway) require you to make multiple libraries (with multiple typedefinitions/library symbols).