STL容器深度解析：选择与优化技巧

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

《Effective STL》是一本由Scott Meyers编著的书籍，深入探讨了C++标准模板库（STL）的高效使用方法。本书旨在帮助程序员充分利用STL中的容器，这些容器如vector、list、map等，是C++编程中不可或缺的重要组成部分。标题“Effective STL”强调了STL在实际编程中的高效性和灵活性，特别是容器的设计和使用技巧。作者关注以下几个关键知识点： 1. **选择容器时要谨慎**：理解不同容器的特点（如vector动态增长，list连续存储，set和map查找性能），根据应用需求选择最适合的容器类型，以确保代码的效率和性能。 2. **避免假象：容器独立代码的陷阱**：提醒开发者不要过度依赖于容器的接口，而忽视了特定容器可能带来的行为差异，需要针对具体情况进行优化。 3. **优化复制操作**：对于容器中的对象，要确保复制操作（拷贝构造函数和赋值运算符）既高效又正确，这对于多线程或性能敏感的应用至关重要。 4. **推荐使用`empty()`而非检查大小**：空容器的判断应通过调用`empty()`函数，而不是直接比较大小与零，这样更符合设计意图，避免潜在的错误。 5. **范围成员函数优于单元素操作**：当处理容器操作时，使用范围版本的成员函数（如`begin()`和`end()`）能提供更好的可读性和性能。 6. **警惕C++的歧义解析**：注意避免C++中的某些语法陷阱，特别是在处理容器操作时，可能需要格外小心。 7. **内存管理**：确保在容器生命周期结束前释放指向的对象的内存，避免内存泄漏。 8. **避免使用auto_ptr**：由于auto_ptr已废弃，应避免使用它创建容器，转而使用智能指针如unique_ptr或shared_ptr。 9. **选择合适的删除操作**：理解容器提供的erase方法，不同的操作方式对性能和内存有不同影响。 10. **理解自定义分配器**：尽管默认情况下STL使用系统分配器，但在特定场景下，如内存池管理或特定性能要求，定制分配器是必要的，但需遵守相应的规范。 11. **关于线程安全性的理解**：了解STL容器的线程安全特性，合理地进行并发访问，避免数据竞争。 12. **vector和string**：推荐使用vector和string代替动态数组，它们提供了更好的内存管理，并支持多种操作。同时，使用reserve可以避免不必要的内存重新分配。 13. **内存分配与reallocations**：通过合理的内存预分配（reserve）减少内存碎片和不必要的reallocations。 14. **容器的变体差异**：在使用不同类型的容器时，注意它们内部实现的不同，以避免意外的行为。《Effective STL》这本书提供了许多实用的建议和技巧，帮助程序员充分利用STL的强大功能，编写出更加高效、健壮的C++代码。

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页未读，继续阅读

LittleJohn

粉丝: 0
资源: 1

STL容器深度解析：选择与优化技巧

快速掌握C++ STL：Effective STL中文版详解

Effective STL：深入解析STL的编程之道

Effective STL：深入理解与高效使用

Effective STL Effective STL Effective STL

EffectiveSTL

Effective STL：中文版PDF，解析STL的挑战与实践

Effective STL：深入解析STL的挑战与实践

在 Blender 2.6 中导入,导出 .x 文件.zip

基于python、open-cv、pywin32等类库搭建eve手游预警机系统详细文档+资料齐全.zip

【路径规划】蛇算法栅格地图机器人最短路径规划【含Matlab仿真 2957期】.zip

最新资源