精心挑选STL容器：实战技巧与最佳实践

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

《Effective STL》是一本由Scott Meyers所著的经典书籍，专注于深入剖析C++标准模板库（STL）的高效使用和最佳实践。该书旨在帮助读者理解并掌握STL的核心概念，确保在实际编程中能够充分利用这些容器和算法，从而提升代码的性能和可读性。章节1至10主要探讨了关于STL容器的策略与技巧： 1. **选择合适的容器**：了解各种容器（如vector、list、set等）的特点和适用场景，确保根据数据访问模式和性能需求来明智地选用。 2. **警惕容器独立代码的幻觉**：代码应避免依赖于特定容器的实现细节，以提高代码的可移植性和灵活性。 3. **优化对象在容器中的复制**：确保对象在被放入容器时，复制操作效率高且正确，这可能涉及到深拷贝和浅拷贝的选择。 4. **优先使用`empty()`而非检查大小**：`empty()`方法比直接比较容器的大小更高效，特别是在大型容器中。 5. **范围成员函数的使用**：利用迭代器进行操作，而不是针对单个元素，这样可以提高代码的简洁性和效率。 6. **注意C++的解析陷阱**：理解和避免可能导致编译错误或不易察觉的行为，例如模板元编程中的微妙问题。 7. **内存管理的注意事项**：确保在容器生命周期结束前正确删除动态分配的指针，以防止内存泄漏。 8. **避免使用auto_ptr**：auto_ptr已被淘汰，改用智能指针如shared_ptr和unique_ptr更为安全和现代。 9. **谨慎对待erase操作**：不同的容器有不同的删除策略，理解它们的影响以减少不必要的资源消耗。 10. **了解自定义分配器**：虽然默认分配器是隐式使用的，但了解如何创建和使用自定义分配器可以帮助优化内存管理。 11. **理解合法的自定义分配器使用**：当需要特殊内存管理或性能优化时，自定义分配器提供了更大的灵活性。 12. **考虑线程安全**：尽管STL容器提供了线程安全版本，但对多线程环境的并发需求有清晰的认识很重要。 13. **vector和string的偏好**：推荐使用vector和string作为动态数组的替代，因为它们提供了内置的动态扩展能力。 14. **使用reserve避免频繁重分配**：预先预留空间可以减少不必要的内存碎片和重新分配操作。 15. **注意字符串操作的细节**：字符串类string在处理内部缓冲区时，需要注意其特定的性能特性。章节12之后，作者还特别关注了vector和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页未读，继续阅读

heloowird

粉丝: 22
资源: 6

精心挑选STL容器：实战技巧与最佳实践

effective stl 中文 pdf

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

Effective STL Effective STL Effective STL

EffectiveSTL

【中国房地产业协会-2024研报】2024年第三季度房地产开发企业信用状况报告.pdf

【中国银行-2024研报】美国大选结果对我国芯片产业发展的影响和应对建议.pdf

RM1135开卡工具B17A

毕业设计&课设_宿舍管理系统：计算机毕业设计项目.zip

毕业设计&课设_画手交易管理系统：Java 毕设项目.zip

跑腿平台系统 微信小程序+SSM毕业设计 源码+数据库+论文+启动教程.zip

最新资源

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

跑腿平台系统微信小程序+SSM毕业设计源码+数据库+论文+启动教程.zip