Effective STL：选择与使用容器的策略

3星 · 超过75%的资源需积分: 29 83 浏览量更新于2024-07-26 收藏 1.46MB PDF 举报

"Effective STL" 《Effective STL》是Scott Meyers所著的一本关于标准模板库（Standard Template Library，STL）的实践指南，书中详细介绍了如何更高效、更正确地使用STL容器、迭代器、算法和函数对象。以下是根据书中的部分内容提炼出的一些关键知识点： 1. 选择合适的容器：不同类型的容器有不同的特性和性能，如顺序容器（如vector、list、deque）和关联容器（如set、map）。理解它们的区别并根据实际需求选择能提供最佳性能的容器。 2. 避免容器独立代码的幻觉：虽然STL提供了一种看似与具体容器无关的抽象，但实际编写代码时，容器的选择会影响程序的效率和行为。因此，代码应考虑特定容器的特性。 3. 优化复制：对于容器内的对象，确保其复制操作既快速又正确，这可能涉及到使用浅拷贝或深拷贝，以及实现正确的赋值运算符和复制构造函数。 4. 使用`empty()`而不是检查`size()==0`：对于检查容器是否为空，直接调用`empty()`通常更高效，因为它避免了计算容器大小的开销。 5. 优先使用范围版本的成员函数：例如，使用`std::for_each(a.begin(), a.end(), func)`而不是`for`循环遍历，可以提高代码的简洁性和可读性，并利于使用算法。 6. 警惕C++的最令人困扰的解析（Most Vexing Parse）：C++的语法可能导致意外的声明，尤其是在模板和类定义中，注意避免这种歧义。 7. 管理动态分配的指针：如果容器中存储的是指向动态分配对象的指针，确保在删除容器前释放这些指针，防止内存泄漏。 8. 避免使用容器的`auto_ptr`：`auto_ptr`不适用于容器，因为它的所有权转移可能导致意外的资源丢失。推荐使用`unique_ptr`或`shared_ptr`。 9. 慎重选择erase选项：不同的删除元素方法（如`erase`和`remove_if`）有不同的效果，理解它们的差异，选择合适的方式进行元素删除。 10. 了解allocator的约定和限制：allocator在STL中用于管理内存，它们有特定的行为和限制，自定义allocator时需遵循这些规则。 11. 明智使用自定义allocator：在特定场景下，如多线程环境或特定硬件限制下，自定义allocator可以提高性能或满足特定需求。 12. 对STL容器的线程安全性有现实期望：STL容器并不是线程安全的，这意味着在多线程环境下使用它们时，必须手动处理同步问题。 13. 优先使用`vector`和`string`：对于动态数组，`vector`和`string`提供了便利的接口和内存管理，优于直接使用`new`和`delete`操作。 14. 使用`reserve`避免不必要的重新分配：在预先知道容器大小的情况下，调用`reserve`可以避免因插入元素导致的频繁内存重新分配，提高性能。 15. 注意不同`string`实现的差异：不同编译器或库的`string`实现可能有细微差别，如默认字符类型、空字符串处理等，编写跨平台代码时要注意这些差异。 16. 向旧版API传递`vector`和`string`数据：在与不支持STL的旧API交互时，可能需要将`vector`或`string`转换为旧的C风格数组或指针。 17. 利用“swap技巧”减少额外容量：通过交换来删除容器的元素，而不是直接删除，可以保留容器的剩余容量，提高效率。这些知识点构成了有效使用STL的基础，理解并应用它们可以提高C++程序的性能和质量。

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> Iist2;

...

list1.splice( // move ail nodes in Iist2

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

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

find(list2.rbegin(), Iist2.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 Iist2 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(), Iist2.end(), 5) and find(list2.rbegin(), Iist2.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

// defined elsewhere

vector<int> v;

...

v.insert(v.begin(), data, data + numValues); // insert the ints in data

//into v at the front

Using iterative calls to insert in an explicit loop, it would probably look more or less

like this:

vector<int>::iterator insertLoc(v.begin());

for (int i = 0; i < numValues; ++i) {

insertLoc = v.insert(insertLoc, data[i]);

}

Notice how we have to be careful to save the return value of insert for the next loop

iteration. If we didn't update insertLoc after each insertion, we'd have two problems.

First, all loop iterations after the first would yield undefined behavior, because each

insert call would invalidate insertLoc. Second, even if insertLoc remained valid, we'd

always insert at the front of the vector (i.e., at v.begin()), and the result would be that

the ints copied into v would end up in reverse order.

If we follow the lead of Item 43 and replace the loop with a call to copy, we get

something like this:

copy(data. data + numValues, inserter(v, v.begin()));

By the time the copy template has been instantiated, the code based on copy and the

code using the explicit loop will be almost identical, so for purposes of an efficiency

analysis, we'll focus on the explicit loop, keeping in mind that the analysis is equally

valid for the code employing copy. Looking at the explicit loop just makes it easier to

understand where the efficiency hits come from. Yes, that's "hits." plural, because the

code using the single-element version of insert levies up to three different performance

taxes on you, none of which you pay if you use the range version of insert.

The first tax consists of unnecessary function calls. Inserting numValues elements into

v one at a time naturally costs you numValues calls to insert. Using the range form of

insert, you pay for only one function call, a savings of numValues-1 calls. Of course,

it's possible that inlining will save you from this tax, but then again, it's possible that it

won't. Only one thing is sure. With the range form of insert, you definitely won't pay

it.

Inlining won't save you from the second tax, which is the cost of inefficiently moving

the existing elements in v to their final post-insertion positions. Each time insert is

called to add a new value to v. every element above the insertion point must be moved

up one position to make room for the new element. So the element at position p must

be moved up to position p+1, etc. In our example, we're inserting numValues elements

at the front of v. That means that each element in v prior to the insertions will have to

剩余197页未读，继续阅读

hcfei

粉丝: 0
资源: 8

Effective STL：选择与使用容器的策略

effective stl 中文 pdf

Effective STL中文版.pdf 带目录书签 清晰版

Effective STL Effective STL Effective STL

effective stl csdn pan

effective stl 电子书 kindle

effective stl 目录 pdf

effective stl 50条

effective stl带目录

c++ effective stl

effective stl pdf

最新资源

Effective STL中文版.pdf 带目录书签清晰版