I l @ ve RuBoard |
This Item answers the following questions:
Using a vector as an Array: A Motivating ExampleC++ programmers are strongly encouraged to use the standard vector template instead of C-style arrays. Using a vector is easier and safer than using an array, because a vector is a better-abstracted and better-encapsulated form of containerfor example, a vector can grow and shrink as needed, whereas an array has a fixed size. Nonetheless, there's still a lot of code out there that is designed to work with C-style arrays. For example, consider the following code: // Example 7-1(a): A function that operates // on a C-style array // int FindCustomer(const char* szName, // name to search for Customer* pCustomers, // pointer to beginning // of a Customer array size_t nLength) // with nLength entries { // performs a (possibly optimized) search and // returns the index at which the specified // name was found } To use the above function, we might create, populate, and pass in an array as follows : // Example 7-1(b): Using an array // Customer c[100]; //-- populate the contents of c somehow - int i = FindCustomer("Fred Jones", &c[0], 100); Example 7-1(b) is all well and good, but as modern C++ programmers aren't we supposed to use vector s instead of arrays? Indeed, wouldn't it be nice if we could have the best of both worlds use a vector for its convenience and safety, yet still use the vector 's contents with functions that expect an array? This desire comes up most often when an organization is migrating to C++ and people want to write new parts of the system in the "new and better" way while still tying in easily with a legacy code base. So let's use a vector . Our first attempt could look something like this: // Example 7-1(c): Using a vector -- will this work? // vector<Customer> c; //-- populate the contents of c somehow - int i = FindCustomer("Fred Jones", &c[0], c.size()); In Example 7-1(c), when it comes time to call FindCustomer() , the idea is to pass in the address of the first element, and the number of elements, which is pretty much just what we did in Example 7-1(b). Before reading on, stop for a moment and consider these questions: What potential benefits does the code in Example 7-1(c) have over the code in Example 7-1(b)? Do you see any potential problems with Example 7-1(c), or do you think that it will work as intended? A Fly in the Ointment?I didn't just pull Example 7-1(c) out of a hat. It turns out there are a lot of real-world C++ programmers who have done exactly this, and with good reason, because code like that in Example 7-1(c) illustrates some of the important benefits that come from using a vector :
In short, as far as I know, Example 7-1(c) has always worked on every implementation of std::vector that has ever existed. Until 2001, a minor fly in the ointment was that the 1998 C++ standard [C++98] didn't actually guarantee that Example 7-1(c) would work portably on every C++ platform you might buy. This is because Example 7-1(c) assumes that the internal contents of the vector are stored contiguously in the same format as is an array, but the original C++ standard didn't require vendors to implement vector that way. If, for example, a vector implementation were to play games and store its contents in some other way (such as contiguously but in backwards order, or in sequential order but with an extra byte of housekeeping information between elements), then Example 7-1(c) would, in fact, fail miserably. This was fixed in 2001 as part of Technical Corrigendum #1 to the C++ standard, which now requires that the contents of a vector are stored contiguously, just like an array. Even if your compiler doesn't include support for the Technical Corrigendum yet, though, Example 7-1(c) should work in practice today. Again, I don't know of a commercial vector implementation that doesn't store its elements contiguously. Bottom line: Prefer using vector (or deque ; see below) instead of arrays. In Most Cases, Prefer Using vector
The C++ standard [C++98], in section 23.1.1, offers some advice on which containers to prefer. It says:
vector and deque offer nearly identical interfaces and are generally interchangeable. deque also offers push_front() and pop_front() , which vector does not. (True, vector offers capacity() and reserve() , which deque does not, but that's no loss. Those functions are actually something of a weakness in vector , as I'll demonstrate in a moment.) The main structural difference between vector and deque lies in the way the two containers organize their internal storage. Under the covers, a deque allocates its storage in pages, or " chunks ," with a fixed number of contained elements in each page. This is why a deque is often compared to (and pronounced as) a "deck" of cards, [13] although its name originally came from "double-ended queue" because of its ability to insert elements efficiently at either end of the sequence. On the other hand, a vector allocates a contiguous block of memory, and can only insert elements efficiently at the end of the sequence.
The paged organization of a deque offers several benefits:
Interestingly, note that within the C++ standard itself, the stack adapter prefers deque . Even though a stack can only grow in one direction and so never needs insertion in the middle or at the other end, the default implementation is required to be a deque : namespace std { template<typename T, typename Container = deque<T> > class stack { // ... }; } Despite this, for readability and simplicity, prefer using vector by default in your programs unless you know you need to efficiently insert and erase at the beginning of the container and don't need the underlying objects to be stored contiguously. Note that vector is to C++ what the array is to Cthe default container type to use in your programs, and one that does a reasonably good all-around job unless you know you need something different. The Incredible Shrinking vectorAs already noted, it's nice that vector manages its own storage, and that we can give it hints about how much capacity to keep ready under the covers as it grows. If we have a vector<T> c that we're about to grow to contain 100 elements, we can first call c . reserve(100) and incur, at most, a single reallocation hit. This allows optimally efficient growth. But what if we're doing the opposite ? What if we're using a vector that's pretty big, and then we remove elements we no longer need and want the vector to shrink to fitthat is, we want it to get rid of the now-unneeded extra capacity? You might think that the following would work:
// Example 7-2(a): A nave attempt at shrinking a vector. // vector<C> c(10000); Now c.size() == 10000 , and c.capacity() >= 10000 . Next , we erase all but the first ten elements: c.erase(c.begin()+10, c.end()); Now c . size() == 10 , and we know we don't need all that extra capacity, but the following line does not shrink c 's internal buffer to fit: c.reserve(10); The reason that the last line in Example 7-2(a) does not do what one might expect is that calling reserve() will never shrink the vector 's capacity. Calling reserve() can only increase the capacity, or do nothing if the capacity is already sufficient. Fortunately, there is a right way to get the intended effect: // Example 7-2(b): The right way to shrink-to-fit a vector. // vector<Customer> c(10000); // ...now c.capacity() >= 10000... // erase all but the first 10 elements c.erase(c.begin()+10, c.end()); // the following line does shrink c's // internal buffer to fit (or close) vector<Customer>(c).swap(c); // ...now c.capacity() == c.size(), or // perhaps a little more than c.size() Do you see how the shrink-to-fit statement works? It's a little subtle:
Note that this procedure is not needlessly inefficient. Even if vector had a special-purpose shrink_to_fit() member function, it would have to do pretty much all the same work just described.
To completely clear a vector so that it has no contents and no extra capacity at all, the code is nearly identical. We just initialize the temporary vector to be empty instead of making it a copy of c : // Example 7-3: The right way to clear out a vector. // vector<Customer> c(10000); // ...now c.capacity() >= 10000... // the following line makes // c be truly empty vector<Customer>().swap(c); // ...now c.capacity() == 0, unless the // implementation happens to enforce a // minimum size even for empty vectors Again, note that the vector implementation you use may choose to make even empty vector s have some slight capacity, but now you're guaranteed that c 's capacity will be the smallest possible allowed by your implementation. It will be the same as the capacity of an empty vector . These techniques work for deque , too, but you don't need to do this kind of thing for list , set , map , multiset , or multimap , because they allocate storage on an "exactly-as-needed" basis and so they should never have excess capacity. SummaryIt's safe to use vector s interchangeably with C-style arrays, and you should always prefer to use vector s or deque s instead of arrays. Use a vector as your default container type, unless you know you need something different and you don't need all the contained elements to be contiguous in memory. Use the swap-with-a-temporary-container idiom if you want to shrink an existing vector or deque . Finally, as noted in Item 6, unless you know that you really need the space optimization, always use deque<bool> instead of vector<bool> . |
I l @ ve RuBoard |