第1页 / 共198页
第2页 / 共198页
第3页 / 共198页
第4页 / 共198页
第5页 / 共198页
第6页 / 共198页
第7页 / 共198页
第8页 / 共198页
Effective STL(英文原版).pdf
Effective STL: 50 Specific Ways to Improve Your Use of Standard Template Library
Content
Containers
1. Choose your containers with care
2. Beware illusion of container-independent code
3. Make copying cheap & correct for objects in containers
4. Call empty instead of checking size() against zero
5. Prefer range member functions to their single-element counterparts
6. Be alert for C++'s most vexing parse
7. When using containers of newed pointers, remember to delete pointers before container is destroyed
8. Never create containers of auto_ptrs
9. Choose carefully among erasing options
10. Be aware of allocator conventions & restrictions
11. Understand legitimate uses of custom allocators
12. Have realistic expectations about thread safety of STL containers
Vector & String
13. Prefer vector & string to dynamically allocated arrays
14. Use reserve to avoid unnecessary reallocations
15. Be aware of variations in string implementations
16. Know how to pass vector & string data to legacy APIs.
17. Use "swap trick" to trim excess capacity
18. Avoid using vector
Associative Containers
19. Understand difference between equality & equivalence
20. Specify comparison types for associative containers of pointers
21. Always have comparison functions return false for equal values
22. Avoid in-place key modification in set & multiset
23. Consider replacing associative containers with sorted vectors
24. Choose carefully between map::operator[] & map-insert when efficiency is important
25. Familiarize yourself with nonstandard hashed containers
Iterators
26. Prefer iterator to const iterator, reverse_iterator & const_reverse_iterator
27. Use distance & advance to convert container's const_iterators to iterators
28. Understand how to use reverse_iterator's base iterator
29. Consider istreambuf_iterators for character-by-character input
Algorithms
30. Make sure destination ranges are big enough
31. Know your sorting options
32. Follow remove-like algorithms by erase if you really want to remove something
33. Be wary of remove-like algorithms on containers of pointers
34. Note which algorithms expect sorted ranges
35. Implement simple case-insensitive string comparisons via mismatch or lexicographical compare
36. Understand proper implementation of copy_if
37. Use accumulate or for_each to summarize ranges
Functors, Functor Classes, Functions, etc.
38. Design functor classes for pass-by-value
39. Make predicates pure functions
40. Make functor classes adaptable
41. Understand reasons for ptr_fun, mem_fun & mem_fun_ref
42. Make sure less means operator<
Programming with STL
43. Prefer algorithm calls to hand-written loops
44. Prefer member functions to algorithms with same names
45. Distinguish among count, find, binary search, lower_bound, upper_bound & equal_range
46. Consider function objects instead of functions as algorithm parameters
47. Avoid producing write-only code
48. Always #include proper headers
49. Learn to decipher STL-related compiler diagnostics
50. Familiarize yourself with STL-related web sites
Content
Containers ................................................................................................................... 1
Item 1. Choose your containers with care........................................................... 1
Item 2. Beware the illusion of container-independent code................................ 4
Item 3. Make copying cheap and correct for objects in containers..................... 9
Item 4. Call empty instead of checking size() against zero. ............................. 11
Item 5. Prefer range member functions to their single-element counterparts... 12
Item 6. Be alert for C++'s most vexing parse................................................... 20
Item 7. When using containers of newed pointers, remember to delete the
pointers before the container is destroyed. ........................................................... 22
Item 8. Never create containers of auto_ptrs. ................................................... 27
Item 9. Choose carefully among erasing options.............................................. 29
Item 10.
Be aware of allocator conventions and restrictions. ......................... 34
Item 11. Understand the legitimate uses of custom allocators........................ 40
Item 12. Have realistic expectations about the thread safety of STL containers.
43
vector and string........................................................................................................ 48
Item 13.
Prefer vector and string to dynamically allocated arrays.................. 48
Item 14. Use reserve to avoid unnecessary reallocations................................ 50
Item 15.
Be aware of variations in string implementations. ........................... 52
Item 16. Know how to pass vector and string data to legacy APIs. ............... 57
Item 17. Use "the swap trick" to trim excess capacity.................................... 60
Item 18. Avoid using vector. ............................................................... 62
Associative Containers.............................................................................................. 65
Item 19. Understand the difference between equality and equivalence.......... 65
i
Item 20.
Specify comparison types for associative containers of pointers. .... 69
Item 21. Always have comparison functions return false for equal values. ... 73
Item 22. Avoid in-place key modification in set and multiset........................ 76
Item 23.
Consider replacing associative containers with sorted vectors. ....... 81
Item 24.
Choose carefully between map::operator[] and map-insert when
efficiency is important. ......................................................................................... 87
Item 25.
Familiarize yourself with the nonstandard hashed containers.......... 91
Iterators ..................................................................................................................... 95
Item 26.
and
const_reverse_iterator........................................................................................... 95
reverse_iterator,
iterator,
to
const
Prefer
iterator
Item 27. Use distance and advance to convert a container's const_iterators to
iterators.
98
Item 28. Understand how to use a reverse_iterator's base iterator................ 101
Item 29.
Consider istreambuf_iterators for character-by-character input..... 103
Algorithms .............................................................................................................. 106
Item 30. Make sure destination ranges are big enough................................. 106
Item 31. Know your sorting options. ............................................................ 111
Item 32.
something. 116
Follow remove-like algorithms by erase if you really want to remove
Item 33.
Be wary of remove-like algorithms on containers of pointers. ...... 120
Item 34. Note which algorithms expect sorted ranges.................................. 123
Item 35.
Implement simple case-insensitive string comparisons via mismatch
or lexicographical compare................................................................................. 126
Item 36. Understand the proper implementation of copy_if......................... 130
Item 37. Use accumulate or for_each to summarize ranges. ........................ 132
Functors, Functor Classes, Functions, etc............................................................... 138
Item 38. Design functor classes for pass-by-value. ...................................... 138
Item 39. Make predicates pure functions. ..................................................... 141
ii
Item 40. Make functor classes adaptable. ..................................................... 144
Item 41. Understand the reasons for ptr_fun, mem_fun, and mem_fun_ref. 148
Item 42. Make sure less means operator<.............................................. 151
Programming with the STL .................................................................................... 155
Item 43.
Prefer algorithm calls to hand-written loops. ................................. 155
Item 44.
Prefer member functions to algorithms with the same names........ 162
Item 45.
Distinguish among count, find, binary search, lower_bound,
upper_bound, and equal_range........................................................................... 165
Item 46.
parameters. 173
Consider function objects
instead of functions as algorithm
Item 47. Avoid producing write-only code................................................... 177
Item 48. Always #include the proper headers............................................... 179
Item 49.
Learn to decipher STL-related compiler diagnostics...................... 181
Item 50.
Familiarize yourself with STL-related web sites............................ 187
iii
Containers
Sure, the STL has iterators, algorithms, and function objects, but for most C++
programmers, it's the containers that stand out. More powerful and flexible than arrays,
they grow (and often shrink) dynamically, manage their own memory, keep track of
how many objects they hold, bound the algorithmic complexity of the operations they
support, and much, much more. Their popularity is easy to understand. They're simply
better than their competition, regardless of whether that competition comes from
containers in other libraries or is a container type you'd write yourself. STL containers
aren't just good. They're really good.
This chapter is devoted to guidelines applicable to all the STL containers. Later
chapters focus on specific container types. The topics addressed here include selecting
the appropriate container given the constraints you face: avoiding the delusion that
code written for one container type is likely to work with other container types: the
significance of copying operations for objects in containers: difficulties that arise when
pointers of auto_ptrs are stored in containers: the ins and outs of erasing: what you can
and cannot accomplish with custom allocators: tips on how to maximize efficiency:
and considerations for using containers in a threaded environment.
That's a lot of ground to cover, but don't worry. The Items break it down into bite-
sized chunks, and along the way, you're almost sure to pick up several ideas you can
apply to your code now.
Item 1. Choose your containers with care.
You know that C++ puts a variety of containers at your disposal, but do you realize
just how varied that variety is? To make sure you haven't overlooked any of your
options, here's a quick review.
• The standard STL sequence containers, vector, string, deque, and list.
• The standard STL associative containers, set, multiset, map and multimap.
• The nonstandard sequence containers slist and rope. slist is a singly linked
list, and rope is essentially a heavy-duty string. (A "rope" is a heavy-duty "string."
Get it?) You'll find a brief overview of these nonstandard (but commonly
available) containers in Item 50.
• The nonstandard associative containers hash_set, hash_multiset, hash_map,
and hash_multimap. I examine these widely available hash-table-based variants
on the standard associative containers in Item 25.
• vector as a replacement for string. Item 13 describes the conditions
under which such a replacement might make sense.
1
• vector as a replacement for the standard associative containers. As Item 23
makes clear, there are times when vector can outperform the standard
associative containers in both time and space.
• Several standard non-STL containers, including arrays, bitset, valarray, stack,
queue, and priority_queue. Because these are non-STL containers. I have little
to say about them in this book, though Item 16 mentions a case where arrays are
preferable to STL containers and Item 18 explains why bitset may be better
than vector. It's also worth bearing in mind that arrays can be used with
STL algorithms, because pointers can be used as array iterators.
That's a panoply of options, and it's matched in richness by the range of considerations
that should go into choosing among them. Unfortunately, most discussions of the STL
take a fairly narrow view of the world of containers, ignoring many issues relevant to
selecting the one that is most appropriate. Even the Standard gets into this act, offering
the following guidance for choosing among vector, deque, and list:
vector, list, and deque offer the programmer different complexity trade-offs
and should be used accordingly, vector is the type of sequence that should
be used by default, list should be used when there are frequent insertions
and deletions from the middle of the sequence, deque is the data structure of
choice when most insertions and deletions take place at the beginning or at
the end of the sequence.
If your primary concern is algorithmic complexity. I suppose this constitutes
reasonable advice, but there is so much more to be concerned with.
In a moment, we'll examine some of the important container-related issues that
complement algorithmic complexity, but first I need to introduce a way of categorizing
the STL containers that isn't discussed as often as it should be. That is the distinction
between contiguous-memory containers and node-based containers.
Contiguous-memory containers (also known as array-based containers] store their
elements in one or more (dynamically allocated) chunks of memory, each chunk
holding more than one container element. If a new element is inserted or an existing
element is erased, other elements in the same memory chunk have to be shifted up or
down to make room for the new element or to fill the space formerly occupied by the
erased element. This kind of movement affects both performance (see Items 5 and 14)
and exception safety (as we'll soon see). The standard contiguous-memory containers
are vector, string, and deque. The nonstandard rope is also a contiguous-memory
container.
Node-based containers store only a single element per chunk of (dynamically
allocated) memory. Insertion or erasure of a container element affects only pointers to
nodes, not the contents of the nodes themselves, so element values need not be moved
when something is inserted or erased. Containers representing linked lists, such as list
and slist, are node-based, as are all the standard associative containers. (They're
2
typically implemented as balanced trees.) The nonstandard hashed containers use
varying node-based implementations, as you'll see in Item 25.
With this terminology out of the way, we're ready to sketch some of the questions
most relevant when choosing among containers. In this discussion, I omit
consideration of non-STL-like containers (e.g., arrays, bitsets, etc.), because this is,
after all, a book on the STL.
• Do you need to be able to insert a new element at an arbitrary position in the
container? If so, you need a sequence container: associative containers won't
do.
• Do you care how elements are ordered in the container? If not. a hashed
container becomes a viable choice. Otherwise, you'll want to avoid hashed
containers.
• Must the container be part of standard C++? If so, that eliminates hashed
containers, slist, and rope.
• What category of iterators do you require? If they must be random access
iterators, you're technically limited to vector, deque, and string, but you'd
probably want to consider rope, too. (See Item 50 for information on rope.) If
bidirectional iterators are required, you must avoid slist (see Item 50) as well as
one common implementation of the hashed containers (see Item 25).
•
Is it important to avoid movement of existing container elements when
insertions or erasures take place? If so, you'll need to stay away from
contiguous-memory containers (see Item 5).
• Does the data in the container need to be layout-compatible with C? If so,
you're limited to vectors (see Item 16).
•
Is lookup speed a critical consideration? If so, you'll want to look at hashed
containers (see Item 25), sorted vectors (see Item 23), and the standard
associative containers — probably in that order.
• Do you mind if the underlying container uses reference counting? If so, you'll
want to steer clear of string, because many string implementations are
reference-counted (see Item 13). You'll need to avoid rope, too, because the
definitive rope implementation is based on reference counting (see Item 50).
You have to represent your strings somehow, of course, so you'll want to
consider vector.
• Do you need transactional semantics for insertions and erasures? That is, do
you require the ability to reliably roll back insertions and erasures? If so, you'll
want to use a node-based container. If you need transactional semantics for
multiple-element insertions (e.g., the range form — see Item 5), you'll want to
choose list, because list is the only standard container that offers transactional
3
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
