learning note—Chapter 9. Sequential Containers

  1. This chapter completes our discussion of the standard-library sequential
    container types.
  2. It expands on the material from Chapter
    3
    ,
  3. Elements in a sequential container are stored and accessed by position.
  4. associative containers, which hold elements whose order depends on a key.
  5. Each container type offers a different set of time and functionality tradeoffs.
  6. Often a program using one type can be fine-tuned by substituting another
    container
    without changing our code beyond the need to change type declarations.
  7. The order of elements in a sequential container is independent of the value of
    the elements.
  8. Instead, the order is determined by the order in which elements are added to the
    container.
  9. Like a vector in all respects.
  10. These types differ in how elements are accessed and the relative run-time cost
    of adding or removing elements
    .
  11. Effectively, an adaptor adapts an underlying
    container type by defining a new interface in terms of the operations provided
    by the original type.
  12. the library imposes a common interface.
  13. The containers vary as to which operations they provide,
  14. will be the same for both container types.
  15. The set of operations on the container types form a kind of hierarchy:
  16. Other operations are common to only the sequential or only the
    associative containers.
  17. we must include its associated header file
  18. Recall that a default constructor takes no arguments.In most programs, using the default constructor gives the best run-time
    performance and makes using the container easier.
  19. C c(b, e);—Create c with a copy of the elements from the range
    denoted by iterators b and e. Valid for all containers
  20. One way to specify both the size and element values is to initialize a new
    container as a copy of an existing container of the same type:
  21. When we copy one container into another, the types must match exactly.The container type and element type must be the same.
  22. Although we cannot copy the elements from one kind of container to another
    directly, we can do so indirectly by passing a pair of iterators
  23. When we use iterators, there is no requirement that the container types be
    identical.
  24. The element types in the containers can differ as long as they are compatible.
  25. It must be possible to convert the element we copy into the type held by the
    container we are constructing.
  26. The iterators denote a range of elements that we want to copy.
  27. The iterators mark the first and one past the last element to be copied.
  28. Recall that pointers are iterators, so it should not be surprising that we can
    initialize a container from a pair of pointers into a built-in array:
  29. // use entire array to initialize words2
    list<string> words2(words, words + words_size);

  30. Here we use sizeof (Section 5.8, p. 167) to calculate the size of the
    array.
  31. We add that size to a pointer to the first element to get a pointer to a
    location one past the end of the array.
  32. The second pointer serves as a stopping condition; the location it addresses is
    not included in the elements to be copied.
  33. When creating a sequential container, we may specify an explicit size and an
    (optional) initializer to use for the elements.
  34. This code initializes slist to have 64 elements, each
    with the value eh?.
  35. The constructors that take a size are valid only for sequential containers; they are not supported
    for the associative containers.
  36. there are two constraints that element types must meet:
  37. References do not support assignment in its ordinary meaning, so we cannot have
    containers of references.
  38. With the exception of the IO library types
  39. We can define containers with elements that are themselves containers.
  40. The requirement to support copy and assignment is the minimal requirement on
    element types.
  41. Now, consider the following declarations:
  42. As we describe the container operations, we’ll note the constraints, if any,
    that each container operation places on the element type.
  43. Note the spacing used when specifying a container element type as a container:
  44. We must separate the two closing > symbols with a
    space to indicate that these two characters represent two symbols. Without the
    space, >> is treated as a single symbol, the right shift
    operator, and results in a compile-time error.
  45. Before we look further at the container operations
  46. For example, all the container iterators let us read an element from a
    container, and they all do so by providing the dereference operator.
  47. Similarly, they all provide increment and decrement operators to allow us to go
    from one element to the next.
  48. Increment iter to refer to the next element in the
    container.
  49. Compare two iterators for equality
  50. Two iterators are equal if they refer to the same element of the same container
    or if they are the off-the-end iterator (Section 3.4, p. 97) for the same container.
  51. These operations are summarized in Table
    9.4
    on the facing page.
  52. Adding (subtracting) an integral value n to (from) an
    iterator yields an iterator that many elements forward (backward) within the
    container. The resulting iterator must refer to an element in the container or
    one past the end of the container.
  53. Compound-assignment versions of iterator addition and
    subtraction. Assigns the value of adding or subtracting iter1 and
    iter2 into iter1.
  54. Relational operators on iterators. One iterator is less than
    another if it refers to an element whose position in the container is ahead of
    the one referred to by the other iterator. The iterators must refer to elements
    in the same container or one past the end of the container.
  55. The reason that only vector and deque support the relational
    operators is that only vector and deque offer fast, random
    access to their elements.
  56. These containers are guaranteed to let us efficiently jump directly to an
    element given its position in the container.
  57. Because these containers support random access by position, it is possible for
    their iterators to efficiently implement the arithmetic and relational
    operations.
  58. In Chapter 11 we’ll
    see that the operations an iterator supports are fundamental to using the
    library algorithms.
  59. The concept of an iterator range is
    fundamental to the standard library.
  60. An iterator range is denoted by a pair
    of iterators that refer to two elements, or to one past
    the last element
    , in the same container.
  61. These two iterators, often referred to as first and last, or
    beg and end, mark a range of elements from
    the container.
  62. Although the names last and end are common, they are a bit
    misleading.
  63. The elements in the range include the element referred to by first and
    every element from first tHRough the element just before last.
  64. This element range is called a left-inclusive interval. The
    standard notation for such a range is
  65. // to be read as: includes first and each element up to but not including last

  66. The last iterator must not refer to an element ahead of the one
    referred to by first.
  67. If the iterators are not equal, then it must be
    possible to reach last by repeatedly incrementing first
  68. In other words, last must not precede first in the container.
  69. The compiler cannot itself enforce these requirements.
  70. Programming Implications of Using Left-Inclusive Ranges
  71. Moreover, we can advance first by incrementing it some number of times
    until first == last.
  72. These properties mean that we can safely write loops such as the following to
    process a range of elements by testing the iterators:
  73. Because the condition in the while handles the case where the range is
    empty, there is no need for a special case to handle an empty range.
  74. When the range is non-empty, the loop will execute at least once.
  75. Because the loop body increments first, we know the loop will
    eventually terminate.
  76. Moreover, if we are in the loop, then we know that *first is safe: It
    must refer to an element in the non-empty range between first and
    last.
  77. In the sections that follow, we’ll see that some container operations change the
    internal state of a container or cause the elements in the container to be
    moved.
  78. Such operations invalidate all iterators that refer
    to the elements that are moved and may invalidate other iterators as well.
  79. Using an invalidated iterator is undefined, and likely to lead to the same kinds
    of problems as using a dangling pointer.
  80. Any iterator that refers to an element that is removed has an invalid value.
  81. After all, the iterator was positioned on an element that no longer exists
    within the container.
  82. It is a serious run-time error to use an iterator that has been invalidated.
  83. There is no way to examine an iterator to determine whether it has been
    invalidated. There is no test we can perform to detect that it has gone bad.
  84. Any use of an invalidated iterator is likely to yield a run-time error, but
    there is no guarantee that the program will crash or otherwise make it easy to
    detect the problem.
  85. Any use of an invalidated iterator is likely to yield a run-time error, but
    there is no guarantee that the program will crash or otherwise make it easy to
    detect the problem.
  86. a reverse iterator is an iterator that goes backward through a container and
    inverts the iterator operations:
  87. Their generosity was in inverse proportion/relation to their income.
  88. For example, saying ++ on a reverse iterator yields the previous
    element in the container.
  89. The utility of these element-related typedefs will be more apparent when we
    define our own generic programs in Chapter 16.
  90. The declaration of iter uses the scope operator to say that we want the
    name on the right-hand side of the :: from the scope of the left-hand
    side.
  91. The effect is to declare that iter has whatever type is defined for the
    iterator member from the list class that holds elements of
    type string.
  92. These iterators are most often used to form an iterator range that encompasses
    all the elements in the container.
  93. Every sequential container supports push_back, which appends an element
    to the back of the container.
  94. The following loop reads one string at a time into text_word:
  95. The call to push_back creates a new element at the end of container, increasing the
    size of container by one.
  96. The type of container can be any of list, vector, or
    deque.
  97. uses push_back to add the sequence 0, 1, 2, 3
    to the end of ilist.
  98. Because each element is inserted at the new beginning of the list, they
    wind up in reverse order.
  99. After executing both loops, ilist holds the sequence
    3,2,1,0,0,1,2,3.
  100. There is no relationship between the element in the container and the value from
    which it was copied.
  101. Subsequent changes to the element in the container have no effect on the value
    that was copied, and vice versa.
  102. Inserts element with value t before the element
    referred to by iterator p. Returns an iterator referring to the element
    that was added.
  103. Inserts elements in the range denoted by iterators b
    and e before the element referred to by iterator p. Returns
    void.
  104. Because the iterator might refer to a nonexistent element off the end of the
    container, insert inserts before the position rather than after it.
    This code
  105. We could use the return value to repeatedly insert elements at a specified
    position in the container:
  106. It is important to understand
    thoroughly how this loop operatesin particular to understand why we say that the
    loop is equivalent to calling push_front.
  107. As long as there are words to insert, each trip through the while
    inserts a new element ahead of iter and reassigns to iter the
    value of the newly inserted element.
  108. That element is always the first element, so each iteration inserts an element
    ahead of the first element in the list.
  109. we can insert all or a subset of the array elements into our list of
    strings:
  110. As we’ll see in Section
    9.4
    (p. 330),
    adding elements to a vector can cause the entire container to be
    relocated.
  111. When writing loops that insert elements into a vector or a
    deque, the program must ensure that the iterator is refreshed on each
    trip through the loop.
  112. Rather than storing the end iterator, we must
    recompute it after each insertion:
  113. The containers must be the same kind of container and must hold elements of the
    same type. We can compare a vector<int> only with another
    vector<int>.
  114. Comparing two containers is based on a pairwise comparison of the elements of
    the containers.
  115. The comparison uses the same relational operator as defined by the element type:
    Comparing two containers using != uses the != operator for the
    element type.
  116. If neither container is an initial subsequence of the other,
    then the comparison depends on comparing the first unequal elements.
  117. We can compare
    two containers only if the same relational operator defined for the element
    types.
  118. Assuming ivec1 and ivec2 are vector<int>, then
    this comparison uses the built-in int less-than operator.
  119. The resize operation takes an optional element-value argument. If this
    argument is present, then any newly added elements receive this value.
  120. Two things are noteworthy in this program:
  121. The end iterator refers "one past the end" of the container so to fetch
    the last element we must first decrement that iterator.
  122. If the list were empty all of the operations in the if would be
    undefined.
  123. When we introduced subscripting in Section 3.3.2 (p. 94), we noted that the programmer must
    ensure that an element exists at the indicated subscript location.
  124. The same caution applies to using the front or back
    operations.
  125. Using a subscript that is out-of-range or calling
    front or back on an empty container are serious programming
    errors.
  126. An alternative to subscripting is to use the at member. This function
    acts like the subscript operation but if the index is invalid, at
    throws an out_of_range exception
  127. One common use of pop_front is to use it together with
    front to process a container as a stack:
  128. To examine that value, it is necessary to call front or back
    prior to popping the element.
  129. Returns an iterator referring after the last one in the range
    that was deleted, or an off-the-end iterator if e is itself an
    off-the-end iterator.
  130. Both forms of erase return an iterator
    referring to the location after the element or range that was removed.
  131. The find function takes a pair of iterators that denote a range in
    which to look, and a value to look for within that range.
  132. find returns an iterator referring to the first element with that value
    or the off-the-end iterator:
  133. The call to erase removes the elements starting from the referred to
    by elem1 up to but not including elem2.
  134. For vectors, iterators to elements after the erasure point are also
    invalidated.
  135. Except for swap, they can be expressed in terms of erase and
    insert operations.
  136. For example, we could use assign to assign a range of char*
    values from a vector into a list of string.
  137. Because the original elements are deleted, the iterators passed
    to assign must not refer to elements in the container on which
    assign is called.
  138. After executing this statement, slist1 has 10
    elements, each of which has the value Hiya!.
  139. After the call to swap, the elements that had been in the right-hand
    operand are in the left, and vice versa:
  140. Similarly, if we resize a container to be larger than its current
    size, then additional elements must be added to the container.
  141. The library takes care of allocating the memory to hold these new elements.
  142. Ordinarily, we should not care about how a library type works:
  143. However, in the case of vectors, a bit of the implementation leaks into
    its interface.
  144. To support fast random access, vector elements are stored
    contiguouslyeach element is adjacent to the previous element.
  145. Given that elements are contiguous, let’s think about what happens when we add
    an element to a vector: If there is no room in the vector for
    the new element, it cannot just add an element somewhere else in memory because
    the elements must be contiguous for indexing to work.
  146. Instead, the vector must allocate new memory to hold the existing
    elements plus the new one, copy the elements from the old location into the new
    space, add the new element, and deallocate the old memory.
  147. If vector did this memory allocation and deallocation each time we
    added an element, then performance would be unacceptably slow.
  148. There is no comparable allocation issue for containers that do not hold their
    elements contiguously.
  149. For example, to add an element to a list, the library only needs to
    create the new element and chain it into the existing list. There is no need to
    reallocate or copy any of the existing elements.
  150. The reason is that library implementors use allocation strategies that minimize
    the costs of storing elements contiguously. That cost is usually offset by the
    advantages in accessing elements that contiguous storage allows.
  151. The way vectors achieve fast allocation is by allocating capacity
    beyond what is immediately needed.
  152. This allocation strategy is dramatically more efficient than reallocating the
    container each time an element is added. In fact, its performance is good enough
    that in practice a vector usually grows more efficiently than a
    list or a deque.
  153. The vector class includes two members, capacity and
    reserve, that let us interact with the memory-allocation part of
    vector’s implementation.
  154. Under this implementation, adding 24 elements one at a time results in a
    capacity of 32. Visually we can think of the current state of
    ivec as
  155. We might next use up that reserved capacity as follows:
  156. Because we used only reserved capacity, there is no need for
    the vector to do any allocation. In fact, as long as there is excess
    capacity, the vector must not reallocate its elements.
  157. The output indicates that at this point we’ve used up the
    reserved capacity, and size and capacity are equal:
  158. indicates that this vector implementation appears to follow a strategy
    of doubling the current capacity each time it has to allocate new storage.
  159. Moreover, every implementation is required to follow a strategy that ensures
    that it is efficient to use push_back to populate a vector.
  160. Technically speaking, the execution time of creating an n-element
    vector by calling push_back n times on an initially empty
    vector is never more than a constant multiple of n.
  161. As we saw in the previous section, allocating memory to hold elements in
    contiguous storage has impacts on the memory allocation strategies and overhead
    of a container.
  162. By using clever implementation techniques, library authors minimize this
    allocation overhead. Whether elements are stored contiguously has other
    significant impacts on:
  163. The degree to which a program does these operations should be used to determine
    which type of container to use.
  164. The vector and deque types provide fast non-sequential access
    to elements at the cost of making it expensive to add or remove elements
    anywhere other than the ends of the container. The list type supports
    fast insertion and deletion anywhere but at the cost of making nonsequential
    access to elements expensive.
  165. A list represents noncontiguous memory and allows for both forward and
    backward traversal one element at a time.
  166. Accessing an element requires traversing the intervening elements.
  167. Inserting (or removing) anywhere except at the back of a vector
    requires that each element to the right of the inserted (or deleted) element be
    moved.
  168. A deque offers some properties of both list and
    vector:
  169. Unlike list and like vector, a deque
    supports fast random access to any element.
  170. Inserting elements at the front or back of a deque
    does not invalidate any iterators. Erasing the front or back element invalidates
    only iterators referring to the element(s) erased. Inserting or erasing anywhere
    else in the deque invalidates all iterators referring to elements of
    the deque.
  171. Random access in a vector can be efficient because each access is to a
    fixed offset from the beginning of the vector.
  172. It is much slower to jump around in a list. the only way to move
    between the elements of a list is to sequentially follow the pointers.
  173. Moving from the 5th to the 15th element requires visiting every element between
    them.
  174. In general, unless there is a good
    reason to prefer another container, vector is usually the right one to
    use.
  175. There are a few rules of thumb that apply to selecting which container to use:
  176. If we need to insert elements in the middle of the container
    only while reading input and then need random access to the elements, consider
    reading them into a list and then reordering the list as
    appropriate for subsequent access and copying the reordered list into a
    vector.
  177. In general, the predominant operation of the application (whether it does more
    access or more insertion or deletion) should determine the choice of container
    type.
  178. Deciding which container to use may require profiling the performance of each
    container type doing the kinds of operations the application requires.
  179. When you are not certain which container the application should use, try to
    write your code so that it uses only operations common to both vectors
    and lists:
  180. By writing your programs this way, it will be easier to change the container
    from a vector to a list if necessary.
  181. string comparison is equivalent to (case-sensitive) dictionary
    ordering.
  182. For example, we could use iterators to print the characters of a string
    a line at a time to the standard output:
  183. Not surprisingly, this code looks almost identical to the code from page 163 that printed the
    elements of a vector<int>.
  184. These operations include additional versions of container-related operations as
    well as other, completely new functions.
  185. For example, several operations permit us to specify arguments that are pointers
    to character arrays.
  186. Given the number of functions supported, this section can be mind-numbing on
    first reading.
  187. Once you know what kinds of operations are available, you can return for the
    details when writing programs that need to use a given operation.
  188. We initialize s3 to hold four exclamation points by passing a pointer
    to the first exclamation point in c_array.
  189. This form of initialization may be called only with a null-terminated array.
    Passing an array that does not contain a null is a serious error (Section 4.3, p. 130), although it is an
    error that the compiler cannot detect.
  190. As long as the count is within the size of the array, it doesn’t matter whether
    the array is null-terminated.
  191. The other pair of constructors allow us to create a
    string as a copy of a substring of the characters in another
    string:
  192. Regardless of how many characters we ask to copy, the library copies up to the
    size of the string, but not more.
  193. Many of the container operations that string supports operate in terms
    of iterators.
  194. Similarly, the first argument to each version of insert takes an
    iterator to indicate the position before which to insert the values
    represented by the other arguments.
  195. Although string supports these iterator-based operations, it also
    supplies operations that work in terms of an index.
  196. Table 9.14 lists the operations that
    are common to both string and the containers; Table 9.15 on the facing page lists the
    string-only operations.
  197. These operations let us deal with strings positionally and/or let us
    use arguments that are pointers to character arrays rather than
    strings.
  198. It creates a new string that has that many characters, (up to the end
    of the string) from the target string, starting at the given
    position:
  199. Alternatively, we could obtain the same result by writing:
  200. The append operation is a shorthand way of inserting at the end:
  201. The ten different versions of replace differ from each
    other in how we specify the characters to remove and in how we specify the
    characters to insert in their place. The first two arguments specify the range
    of elements to remove. We can specify the range either with an iterator pair or
    an index and a count. The remaining arguments specify what new characters to
    insert.
  202. We can think of replace as a shorthand way of erasing
    some characters and inserting others in their place:
  203. There is no requirement that the size of the text removed and
    inserted be the same.
  204. The string class provides six search functions, each named as a variant
    of find.
  205. The operations all return a string::size_type value that is the index
    of where the match occurred, or a special value named string::npos if
    there is no match.
  206. There are four versions of each of the search operations, each of which takes a
    different set of arguments.
  207. The arguments to the search operations are listed in Table 9.20.
  208. Basically, these operations differ as to whether they are looking for a single
    character, another string, a C-style, null-terminated string, or a
    given number of characters from a character array.
  209. As a result, these operations (and other string operations) are case
    sensitive.
  210. The find
    operations return a string::size_type. Use an object of that type to
    hold the return from find.
  211. We can pass an optional starting position to the find operations.
  212. One common programming pattern uses this optional argument to loop through a
    string finding all occurrences.
  213. As long as the return from find_first_of is a valid index, we print our
    result and increment pos.
  214. In this case, we initialize pos to zero so that on the first trip
    through the while name is searched, beginning at position 0.
  215. Had we neglected to increment pos at the end of this loop, then it
    would never terminate.
  216. To see why, consider what would happen if we didn’t.
  217. Doing so ensures that we start looking for the next number at a point after the number we just found.
  218. Each of the find operations that we’ve seen so far executes left to
    right.
  219. The library provides an analogous set of operations that look through the
    string from right to left.
  220. The library provides an analogous set of operations that look through the
    string from right to left.
  221. The rfind member searches for the lastthat is, rightmostoccurrence of
    the indicated substring:
  222. The find_last functions operate like the corresponding
    find_first functions, except that they return the last match rather than the first:
  223. Each of these operations takes an optional second argument indicating the
    position within the string to begin searching.
  224. As we saw in Section
    3.2.3
    (p. 85),
    the string type defines all the relational operators so that we can
    compare two strings for equality (==), inequality
    (!=), and the less- or greater-than operations (<, <=, >,
    >=).
  225. Comparison between strings is lexicographicalthat is, string
    comparison is the same as a case-sensitive, dictionary ordering:
  226. The relational operators compare two strings character by character
    until reaching a position where the two strings differ.
  227. The overall comparison of the strings depends on the comparison between
    these unequal characters.
  228. in the English alphabet and so "abend" is less than "abort".
  229. If the strings are of different length, and one string is a
    substring of the other, then the shorter string is less than the
    longer.
  230. The results of these operations are similar to the C library strcmp
    function (Section
    4.3
    , p. 132).
  231. The overloaded
    set of six compare operations allows us to compare a substring of
    either one or both strings for comparison. They also let us compare a
    string to a character array or portion thereof:
  232. We use find to locate the position of the beginning of the substring
    "4th". We compare three characters starting at that position to a
    substring from third_ed. That substring begins at the position returned
    from find when looking for "3rd" and again we compare three
    characters. Essentially, this call compares "4th" to "3rd".
  233. For example, assuming that deq is a deque<int>, we could
    use deq to initialize a new stack as follows:
  234. We can override the default container type by naming a sequential container as a
    second type argument when creating the adaptor:
  235. We can use any of the sequential containers as the underlying container for a
    stack.
  236. Two adaptors of the same type can be compared for equality, inequality,
    less-than, greater-than, less-than-equal, and greater-than-equal relationships,
    provided that the underlying element type supports the equality and less-than
    operators.
  237. For these operations, the elements are compared in turn. The first pair of
    unequal elements determines the less-than or greater-than relationship.
  238. The while loop iterates through the entire stack, examining
    the top value and popping it from the stack until the
    stack is empty.
  239. Each container adaptor defines its own operations in terms of operations
    provided by the underlying container type.
  240. By default, this stack is implemented using a deque and uses
    deque operations to implement the operations of a stack.
  241. Although stack is implemented by using a deque, we have no
    direct access to the deque operations.
  242. The library queue uses a first-in, first-out (FIFO) storage and
    retrieval policy.
  243. Objects entering the queue are placed in the back. The next object retrieved is
    taken from the front of the queue.
  244. There are two kinds of queues: the FIFO queue, which we will speak of simply as
    a queue, and a priority queue.
  245. Rather than place a newly entered item at the back of the queue, the item is
    placed ahead of all those items with a lower priority.
  246. By default, the library uses the < operator on the element type to
    determine relative priorities.
  247. A real-world example of a priority queue is the line to check luggage at an
    airport.
  248. Those whose flight is going to leave within the next 30 minutes are generally
    moved to the front of the line so that they can finish the check-in process
    before their plane takes off.
  249. A programming example of a priority queue is the scheduler of an operating
    system determining which, of a number of waiting processes, should execute next.
  250. The container itself manages its storage.
  251. The sequential containers share a common, standardized interface: If two
    sequential containers offer a particular operation, then the operation has the
    same interface and meaning for both containers.
  252. Containers define constructors, operations to add or remove elements, operations
    to determine the size of the container, and operations to return iterators to
    particular elements.
  253. Containers define constructors, operations to add or remove elements, operations
    to determine the size of the container, and operations to return iterators to
    particular elements.
  254. Loops that use container operations that change the size of a container should
    be particularly careful in their use of iterators.
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s