|
 |
|
| |
Introducing vector
With strings, we can fill up a
string object without knowing how much storage we’re going to need.
The problem with reading lines from a file into individual string objects
is that you don’t know up front how many strings you’re going
to need – you only know after you’ve read the entire file. To solve
this problem, we need some sort of holder that will automatically expand to
contain as many string objects as we care to put into
it.
In fact, why limit ourselves to holding
string objects? It turns out that this kind of problem – not
knowing how many of something you have while you’re writing a program
– happens a lot. And this “container” object sounds like it
would be more useful if it would hold any kind of object at all!
Fortunately, the Standard C++ Library has a ready-made solution: the standard
container classes. The container classes are one of the real powerhouses of
Standard C++.
There is often a bit of confusion between
the containers and algorithms in the Standard C++ Library, and the entity known
as the STL. The
Standard Template Library was the
name Alex Stepanov (who was working at Hewlett-Packard at the time) used when he
presented his library to the C++ Standards Committee at the meeting in San
Diego, California in Spring 1994. The name stuck, especially after HP decided to
make it available for public downloads. Meanwhile, the committee integrated it
into the Standard C++ Library, making a large number of changes. STL's
development continues at
Silicon
Graphics (SGI; see https://www.sgi.com/Technology/STL). The SGI STL
diverges from the Standard C++ Library on many subtle points. So although it's a
popular misconception, the C++ Standard does not “include” the STL.
It can be a bit confusing since the containers and algorithms in the Standard
C++ Library have the same root (and usually the same names) as the SGI STL. In
this book, I will say “The Standard C++ Library” or “The
Standard Library containers,” or something similar and will avoid the term
“STL.”
Even though the implementation of the
Standard C++ Library containers and algorithms uses some advanced concepts and
the full coverage takes two large chapters in Volume 2 of this book, this
library can also be potent without knowing a lot about it. It’s so useful
that the most basic of the standard containers, the vector, is introduced
in this early chapter and used throughout the book. You’ll find that you
can do a tremendous amount just by using the basics of vector and not
worrying about the underlying implementation (again, an important goal of OOP).
Since you’ll learn much more about this and the other containers when you
reach the Standard Library chapters in Volume 2, it seems forgivable if the
programs that use vector in the early portion of the book aren’t
exactly what an experienced C++ programmer would do. You’ll find that in
most cases, the usage shown here is adequate.
The vector class is a
template, which means that it can be efficiently
applied to different types. That is, we can create a vector of
shapes, a vector of cats, a vector of
strings, etc. Basically, with a template you can create a “class of
anything.” To tell the compiler what it is that the class will work with
(in this case, what the vector will hold), you put the name of the
desired type in “angle brackets,” which means ‘<’ and
‘>’. So a vector of string would be denoted
vector<string>. When you do this, you end up with a customized
vector that will hold only string objects, and you’ll get an error
message from the compiler if you try to put anything else into
it.
Since vector expresses the concept
of a “container,” there must be a way to put things into the
container and get things back out of the container. To
add a brand-new element on the end of a vector, you use the member
function push_back( ).
(Remember that, since it’s a member function, you use a
‘.’ to call it for a particular object.) The reason the name
of this member function might seem a bit verbose –
push_back( ) instead of something simpler like “put”
– is because there are other containers and other member functions for
putting new elements into containers. For example, there is an
insert( ) member
function to put something in the middle of a container. vector supports
this but its use is more complicated and we won’t need to explore it until
Volume 2 of the book. There’s also a
push_front( ) (not part of vector) to
put things at the beginning. There are many more member functions in
vector and many more containers in the Standard C++ Library, but
you’ll be surprised at how much you can do just knowing about a few simple
features.
So you can put new elements into a
vector with push_back( ), but how do you get these elements
back out again? This solution is more clever and elegant – operator
overloading is used to make the vector look like an array. The
array (which will be described more fully in the next chapter) is a data type
that is available in virtually every programming language so you should already
be somewhat familiar with it. Arrays are
aggregates, which mean they consist of a number of
elements clumped together. The distinguishing characteristic of an array is that
these elements are the same size and are arranged to be one right after the
other. Most importantly, these elements can be selected by
“indexing,” which means you can say “I want element number
n” and that element will be produced, usually quickly. Although there are
exceptions in programming languages, the indexing is normally achieved using
square brackets, so if you have an array a and you want to produce
element five, you say a[4] (note that
indexing always starts at
zero).
This very compact and powerful indexing
notation is incorporated into the vector using operator overloading, just
like ‘<<’ and ‘>>’ were
incorporated into iostreams. Again, you don’t need to know how the
overloading was implemented – that’s saved for a later chapter
– but it’s helpful if you’re aware that there’s some
magic going on under the covers in order to make the [ ] work with
vector.
With that in mind, you can now see a
program that uses vector. To use a vector, you include the header
file <vector>:
//: C02:Fillvector.cpp
// Copy an entire file into a vector of string
#include <string>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int main() {
vector<string> v;
ifstream in("Fillvector.cpp");
string line;
while(getline(in, line))
v.push_back(line); // Add the line to the end
// Add line numbers:
for(int i = 0; i < v.size(); i++)
cout << i << ": " << v[i] << endl;
} ///:~
Much of this program is similar to the
previous one; a file is opened and lines are read into string objects one
at a time. However, these string objects are pushed onto the back of the
vector v. Once the while loop completes, the entire file is
resident in memory, inside v.
The next statement in the program is
called a
for
loop. It is similar to a while loop except that it adds some extra
control. After the for, there is a “control
expression” inside of parentheses, just like the while loop.
However, this control expression is in three parts: a part which initializes,
one that tests to see if we should exit the loop, and one that changes
something, typically to step through a sequence of items. This program shows the
for loop in the way you’ll see it most commonly used: the
initialization part int i = 0 creates an integer
i to use as a loop counter and gives it an initial value of zero. The
testing portion says that to stay in the loop, i should be less than the
number of elements in the vector v. (This is produced using the member
function size( ), which I just sort of slipped in here, but you must
admit it has a fairly obvious meaning.) The final portion uses a shorthand for C
and C++, the
“auto-increment”
operator, to add one to the value of i. Effectively, i++ says
“get the value of i, add one to it, and put the result back into
i. Thus, the total effect of the for loop is to take a variable
i and march it through the values from zero to one less than the size of
the vector. For each value of i, the cout statement is
executed and this builds a line that consists of the value of i
(magically converted to a character array by cout), a colon and a space,
the line from the file, and a newline provided by endl. When you compile
and run it you’ll see the effect is to add line numbers to the
file.
Because of the way that the
‘>>’
operator works with iostreams, you can easily modify the program above so that
it breaks up the input into
whitespace-separated words instead of lines:
//: C02:GetWords.cpp
// Break a file into whitespace-separated words
#include <string>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int main() {
vector<string> words;
ifstream in("GetWords.cpp");
string word;
while(in >> word)
words.push_back(word);
for(int i = 0; i < words.size(); i++)
cout << words[i] << endl;
} ///:~
while(in >> word)
is what gets the input one
“word” at a time, and when this expression evaluates to
“false” it means the end of the file has been reached. Of course,
delimiting words by whitespace is quite crude, but it makes for a simple
example. Later in the book you’ll see more sophisticated examples that let
you break up input just about any way you’d like.
To demonstrate how easy it is to use a
vector with any type, here’s an example that creates a
vector<int>:
//: C02:Intvector.cpp
// Creating a vector that holds integers
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v;
for(int i = 0; i < 10; i++)
v.push_back(i);
for(int i = 0; i < v.size(); i++)
cout << v[i] << ", ";
cout << endl;
for(int i = 0; i < v.size(); i++)
v[i] = v[i] * 10; // Assignment
for(int i = 0; i < v.size(); i++)
cout << v[i] << ", ";
cout << endl;
} ///:~
To create a vector that holds a
different type, you just put that type in as the template argument (the argument
in angle brackets). Templates and well-designed template libraries are intended
to be exactly this easy to use.
This example goes on to demonstrate
another essential feature of vector. In the expression
v[i] = v[i] * 10;
you can see that the vector is not
limited to only putting things in and getting things out. You also have the
ability to assign (and thus to change) to any element of a
vector, also through the use of the
square-brackets indexing operator. This means that vector is a
general-purpose, flexible “scratchpad” for working with collections
of objects, and we will definitely make use of it in coming
chapters.
|
|
|
