精心挑选容器：Effective STL权威指南

需积分: 10 27 浏览量更新于2024-07-24 收藏 1.82MB PDF 举报

《Effective STL》是Scott Meyers的经典之作，专为C++程序员提供深入理解和优化STL（Standard Template Library）的最佳实践指南。作者以其丰富的经验和洞察力，针对C++ STL中的关键容器如vector、string，以及各种辅助工具，提出了十多个重要的编程建议，帮助读者提高代码效率、避免常见陷阱，并充分利用STL的优势。 1. **容器选择的艺术**： Item1强调在设计数据结构时，要精心挑选适合场景的容器。不同的容器有不同的特性和性能，如vector适合随机访问，而list更适合频繁的插入和删除操作。选择正确的容器能够确保程序的高效运行。 2. **避免容器独立代码的错觉**： Item2警告读者不要被错误地认为所有代码对容器类型都无感知，这种观念可能导致不必要的代码重复和维护困难。代码应明确依赖容器的具体特性。 3. **优化对象复制与容器**： Item3着重于如何正确处理容器中的对象复制，以确保在拷贝时既快速又正确，这对于内存管理至关重要。 4. **使用empty()而非size()==0**： Item4提倡使用empty()函数来检查容器是否为空，而不是直接比较大小，因为后者可能引发潜在的性能问题。 5. **偏好范围成员函数**： Item5指出，当处理单个元素操作时，范围成员函数通常比单独的元素函数更高效，因为它们可以利用编译器优化。 6. **警惕C++解析器的困扰**： Item6提醒开发者注意C++的语法歧义，特别是涉及模板和运算符重载时，可能产生的误解和问题。 7. **内存管理与生命周期**： Item7强调在使用newed pointers存储在容器中时，务必确保在容器销毁前释放内存，以防止内存泄漏。 8. **避免auto_ptr的滥用**： Item8提出，auto_ptr已经过时，不推荐使用，因为它会导致难以管理的资源生命周期问题。应改用智能指针如shared_ptr或unique_ptr。 9. **谨慎选择删除选项**： Item9讨论了容器内元素删除的策略，不同的删除操作方式可能会带来不同的性能影响，需根据具体需求选择。 10. **理解自定义分配器**： Item11与Item12共同探讨了自定义分配器的合理使用，包括了解其工作原理以及何时选择使用它们以扩展STL的功能。 11. **关于线程安全的预期**： Item12提醒读者，尽管有些STL容器提供了线程安全版本，但并非所有操作都是线程安全的，务必明确需求并采取适当的同步措施。 12. **vector和string的选择**： Item13建议优先使用vector和string，因为它们提供了内置的内存管理，能避免动态数组可能出现的内存分配和管理问题。 13. **使用reserve避免频繁realloc**： Item14指出，预分配空间（reserve）可以帮助减少内存碎片和不必要的realloc操作，提高性能。 14. **注意内存分配的细微差别**： Item15提到了string中字符串长度和内存分配的特殊性，了解这些细节有助于编写更加高效和稳健的代码。《Effective STL》是一本深入解读和优化C++标准库的重要参考书籍，它为开发者揭示了如何更有效地使用STL容器及其背后的原理，避免常见的编程陷阱，提升代码质量和性能。

vector<Widget> vw;

class SpecialWidget: // SpecialWidget inherits from

public Widget {...}; // Widget above

SpecialWidget sw;

vw.push_back(sw); // sw is copied as a base class

II object into vw. Its specialness

// is lost during the copying

The slicing problem suggests that inserting a derived class object into a container of

base class objects is almost always an error. If you want the resulting object to act like

a derived class object, e.g., invoke derived class virtual functions, etc., it is always an

error. (For more background on the slicing problem, consult Effective C++. Item 22.

For another example of where it arises in the STL, see Item 38.)

An easy way to make copying efficient, correct, and immune to the slicing problem is

to create containers of pointers instead of containers of objects. That is, instead of

creating a container of Widget, create a container of Widget*. Copying pointers is fast,

it always does exactly what you expect (it copies the bits making up the pointer), and

nothing gets sliced when a pointer is copied. Unfortunately, containers of pointers

have their own STL-related headaches. You can read about them in Items 7 and 33. As

you seek to avoid those headaches while still dodging efficiency, correctness, and

slicing concerns, you'll probably discover that containers of smart pointers are an

attractive option. To learn more about this option, turn to Item 7.

If all this makes it sound like the STL is copy-crazy, think again. Yes, the STL makes

lots of copies, but it's generally designed to avoid copying objects unnecessarily. In

fact, it's generally designed to avoid creating objects unnecessarily. Contrast this with

the behavior of C's and C++'s only built-in container, the lowly array:

Widget w[maxNumWidgets]; // create an array of maxNumWidgets

// Widgets, default-constructing each one

This constructs maxNumWidgets Widget objects, even if we normally expect to use

only a few of them or we expect to immediately overwrite each default-constructed

value with values we get from someplace else (e.g., a file). Using the STL instead of

an array, we can use a vector that grows when it needs to:

vector<Widget> vw; // create a vector with zero Widget

// objects that will expand as needed

We can also create an empty vector that contains enough space for maxNumWidgets

Widgets, but where zero Widgets have been constructed:

vector<Widget> vw;

vw.reserve(maxNumWidgets); // see Item 14 for details on reserve

Compared to arrays. STL containers are much more civilized. They create (by

copying) only as many objects as you ask for, they do it only when you direct them to,

and they use a default constructor only when you say they should. Yes, STL containers

make copies, and yes, you need to understand that, but don't lose sight of the fact that

they're still a big step up from arrays.

Item 4. Call empty instead of checking size() against zero.

For any container c, writing

if (c.size() == 0)...

is essentially equivalent to writing

if (c.empty())...

That being the case, you might wonder why one construct should be preferred to the

other, especially in view of the fact that empty is typically implemented as an inline

function that simply returns whether size returns 0.

You should prefer the construct using empty, and the reason is simple: empty is a

constant-time operation for all standard containers, but for some list implementations,

size takes linear time.

But what makes list so troublesome? Why can't it, too. offer a constant-time size? The

answer has much to do with list's unique splicing functions. Consider this code:

list<int> list1;

list<int> list2;

...

list1.splice( // move ail nodes in list2

list1.end(), list2, // from the first occurrence

find(list2.begin(), list2.end(), 5), // of 5 through the last

find(list2.rbegin(), list2.rend(), 10).base() // occurrence of 10 to the

); //end of list1. See Item 28

// for info on the "base()" call

This code won't work unless list2 contains a 10 somewhere beyond a 5, but let's

assume that's not a problem. Instead, let's focus on this question: how many elements

are in list1 after the splice? Clearly, list1 after the splice has as many elements as it did

before the splice plus however many elements were spliced into it. But how many

elements were spliced into it? As many as were in the range defined by

find(list2.begin(), list2.end(), 5) and find(list2.rbegin(), list2.rend(), 10).base(). Okay,

how many is that? Without traversing the range and counting them, there's no way to

know. And therein lies the problem.

Suppose you're responsible for implementing list, list isn't just any container, it's a

standard container, so you know your class will be widely used. You naturally want

your implementation to be as efficient as possible. You figure that clients will

commonly want to find out how many elements are in a list, so you'd like to make size

a constant- time operation. You'd thus like to design list so it always knows how many

elements it contains.

At the same time, you know that of all the standard containers, only list offers the

ability to splice elements from one place to another without copying any data. You

reason that many list clients will choose list specifically because it offers high-

efficiency splicing. They know that splicing a range from one list to another can be

accomplished in constant time, and you know that they know it, so you certainly want

to meet their expectation that splice is a constant-time member function.

This puts you in a quandary. If size is to be a constant-time operation, each list

member function must update the sizes of the lists on which it operates. That includes

splice. But the only way for splice to update the sizes of the lists it modifies is for it to

count the number of elements being spliced, and doing that would prevent splice from

achieving the constant-time performance you want for it. If you eliminate the

requirement that splice update the sizes of the lists it's modifying, splice can be made

constant-time, but then size becomes a linear-time operation. In general, it will have to

traverse its entire data structure to see how many elements it contains. No matter how

you look at it, something — size or splice — has to give. One or the other can be a

constant-time operation, but not both.

Different list implementations resolve this conflict in different ways, depending on

whether their authors choose to maximize the efficiency of size or splice. If you

happen to be using a list implementation where a constant-time splice was given

higher priority than a constant-time size, you'll be better off calling empty than size,

because empty is always a constant-time operation. Even if you're not using such an

implementation, you might find yourself using such an implementation in the future.

For example, you might port your code to a different platform where a different

implementation of the STL is available, or you might just decide to switch to a

different STL implementation for your current platform.

No matter what happens, you can't go wrong if you call empty instead of checking to

see if size() == 0. So call empty whenever you need to know whether a container has

zero elements.

Item 5. Prefer range member functions to their single-element

counterparts.

Quick! Given two vectors, v1 and v2, what's the easiest way to make v1’s contents be

the same as the second half of v2's? Don't agonize over the definition of "half when v2

has an odd number of elements, just do something reasonable.

Time's up! If your answer was

v1.assign(v2.begin() + v2.size() /2, v2.end());

or something quite similar, you get full credit and a gold star. If your answer involved

more than one function call, but didn't use any kind of loop, you get nearly full credit,

but no gold star. If your answer involved a loop, you've got some room for

improvement, and if your answer involved multiple loops, well, let's just say that you

really need this book.

By the way, if your response to the answer to the question included "Huh?", pay close

attention, because you're going to learn something really useful.

This quiz is designed to do two things. First, it affords me an opportunity to remind

you of the existence of the assign member function, a convenient beast that too many

programmers overlook. It's available for all the standard sequence containers (vector,

string, deque, and list). Whenever you have to completely replace the contents of a

container, you should think of assignment. If you're just copying one container to

another of the same type, operator= is the assignment function of choice, but as this

example demonstrates, assign is available for the times when you want to give a

container a completely new set of values, but operator= won't do what you want.

The second reason for the quiz is to demonstrate why range member functions are

superior to their single-element alternatives. A range member function is a member

function that, like STL algorithms, uses two iterator parameters to specify a range of

elements over which something should be done. Without using a range member

function to solve this Item's opening problem, you'd have to write an explicit loop,

probably something like this:

vector<Widget> v1, v2; // assume v1 and v2 are vectors

//of Widgets

v1.clear();

for ( vector<Widget>::const_iterator ci = v2.begin() + v2.size() / 2;

ci != v2.end();

++ci)

v1.push_back(*ci);

Item 43 examines in detail why you should try to avoid writing explicit loops, but you

don't need to read that Item to recognize that writing this code is a lot more work than

is writing the call to assign. As we'll see shortly, the loop also happens to impose an

efficiency penalty, but we'll deal with that in a moment.

One way to avoid the loop is to follow the advice of Item 43 and employ an algorithm

instead:

v1.clear();

copy(v2.begin() + v2.size() / 2, v2.end(), back_inserter(v1 ));

Writing this is still more work than writing the call to assign. Furthermore, though no

loop is present in this code, one certainly exists inside copy (see Item 43). As a result,

the efficiency penalty remains. Again. I'll discuss that below. At this point, I want to

digress briefly to observe that almost all uses of copy where the destination range is

specified using an insert iterator (i.e., via inserter, back_inserter, or front_inserter) can

be — should be — replaced with calls to range member functions. Here, for example,

the call to copy can be replaced with a range version of insert:

v1 .insert(v1 .end(), v2.begin() + v2.size() / 2, v2.end());

This involves slightly less typing than the call to copy, but it also says more directly

what is happening: data is being inserted into v1. The call to copy expresses that, too,

but less directly. It puts the emphasis in the wrong place. The interesting aspect of

what is happening is not that elements are being copied, it's that v1 is having new data

added to it. The insert member function makes that clear. The use of copy obscures it.

There's nothing interesting about the fact that things are being copied, because the STL

is built on the assumption that things will be copied. Copying is so fundamental to the

STL, it's the topic of Item 3 in this book!

Too many STL programmers overuse copy, so the advice I just gave bears repeating:

Almost all uses of copy where the destination range is specified using an insert iterator

should be replaced with calls to range member functions.

Returning to our assign example, we've already identified two reasons to prefer range

member functions to their single-element counterparts.

•

It's generally less work to write the code using the range member functions.

•

Range member functions tend to lead to code that is clearer and more

straightforward.

In short, range member functions yield code that is easier to write and easier to

understand. What's not to like?

Alas, some will dismiss these arguments as matters of programming style, and

developers enjoy arguing about style issues almost as much as they enjoy arguing

about which is the One True Editor. (As if there's any doubt. It's Emacs.) It would be

helpful to have a more universally agreed-upon criterion for establishing the

superiority of range member functions to their single-element counterparts. For the

standard sequence containers, we have one: efficiency. When dealing with the

standard sequence containers, application of single-element member functions makes

more demands on memory allocators, copies objects more frequently, and/or performs

redundant operations compared to range member functions that achieve the same end.

For example, suppose you'd like to copy an array of ints into the front of a vector. (The

data might be in an array instead of a vector in the first place, because the data came

from a legacy C API. For a discussion of the issues that arise when mixing STL

containers and C APIs, see Item 16.) Using the vector range insert function, it's

honestly trivial:

int data[numValues]; // assume numValues is

剩余199页未读，继续阅读

瘦又美

粉丝: 1
资源: 22

精心挑选容器：Effective STL权威指南

c++ effective c++ Effective.STL.pdf More+Effective+Chinese.pdf

Effective.STL.pdf

Eff_STL_CN.pdf

Effective C++_cn_3rd.pdf

Effective C++_3th_CN.pdf

C++ STL学习资源：Eff_STL.pdf中文版解析

effective stl.PDF

关于C++书籍C++test_DataSheet_CN.pdf

Effective_C++_3rd笔记.pdf

Effective_STL中文版2

最新资源