FAQ 28.13 What are the best applications for the standardized C++ sequence container classes?  | Operations that make sense for a linear sequence of objects. |
The sequence container classes store their objects in a linear sequence. They include the following container classes. vector<T> list<T> deque<T> They all expand themselves to allow an arbitrary number of elements to be inserted, and all provide numerous operations. The biggest difference between them is related to performance. For example, vector<T> has very fast array-like access to random elements and very fast insertions and removals at the end; list<T> is not as fast to access a random element, but it is faster when inserting in the middle or at the beginning; deque<T> is like vector<T> except that it also has very fast insertion and removal of elements at the beginning. Some of the operations that can be performed on a sequence follow. In the following descriptions, first and toofar represent iterators within a container, and "the range [first, toofar)" means all the elements starting at first up to but not including the element at toofar. Selected nonmutating sequence operations: for_each(first, toofar, function) applies the function to each element in the range [first, toofar). find(first, toofar, const T& value) finds the first element that is equal to value in the range [first, toofar), returning the corresponding iterator (or toofar if nothing matched). find_if() is similar, but it takes a predicate to determine if the element matches. adjacent_find(first, toofar) finds the first adjacent pair of elements that are equal in the range [first, toofar), returning the corresponding iterator (or toofar if nothing matched). An optional binary predicate can be given to determine if an adjacent pair matches. count(first, toofar, const T& value, result) counts the number of elements in the range [first, toofar) that are equal to value and stores that number in the by-reference parameter result. count_if() is similar, but it takes a predicate to determine if the element matches. mismatch(first, toofar, first2) finds the first mismatch between the two sequences. The elements from sequence 1 are in the range [first, toofar), and the corresponding elements from sequence 2 start at first2. An optional binary predicate can be used to determine if elements match. equal(first, toofar, first2) checks two sequences for element-by-element equality. It returns true if and only if the elements of sequence 1 in the range [first, toofar) match the corresponding elements of sequence 2 starting at first2. An optional binary predicate can be used to determine if elements match. search(first, toofar, first2, toofar2) finds a subsequence within a sequence. An optional binary predicate can be given to determine if an adjacent pair matches. Selected mutating sequence operations: copy(first, toofar, dest) copies elements from the range [first, toofar) into the sequence starting at dest. copy_backward() is similar, but it copies elements from right to left, which is especially useful when sliding a sequence a few slots to the right (that is, when the source and destination ranges overlap). swap_ranges(first, toofar, first2) swaps the contents of the elements from range [first, toofar) with the corresponding elements from sequence 2 starting at first2. swap(a, b) swaps the values of the elements or the entire sequences. transform(first, toofar, dest, unaryOp) calls unaryOp() on each element in the range [first, toofar) and copies the results into sequence 2 starting at dest. transform(first, toofar, first2, dest, binaryOp) calls binaryOp(), passing an element from sequence 1 in the range [first, toofar) and the corresponding element from sequence 2 starting at first2, and copies the results into sequence 3 starting at dest. replace(first, toofar, const T& oldValue, const T& newValue) replaces all elements equal to oldValue in the range [first, toofar) with newValue. replace_if() is simliar, but it takes a predicate to determine if the element matches. replace_copy() and replace_copy_if() are similar except that the original sequence is unchanged, and the results are copied to a second sequence. fill(first, toofar, const T& value) fills the range [first, toofar) with copies of value. fill_n() is similar, but it takes a starting iterator and a number. generate(first, toofar, generator) fills the range [first, toofar) with the results of successively calling generator(). generate_n() is similar, but it takes a starting iterator and a number. remove(first, toofar, const T& value) removes those elements from the range [first, toofar) that are equal to value. remove_if() is similar, but it takes a predicate to determine if the element matches. remove_copy() and remove_copy_if() are similar except that the original sequence is unchanged, and the results are copied to a second sequence. unique(first, toofar) removes successive duplicates from the range [first, toofar). An optional binary predicate can be given to determine if an adjacent pair matches. unique_copy() is similar except that the original sequence is unchanged, and the results are copied to a second sequence. reverse(first, toofar) reverses the elements of the range [first, toofar). reverse_copy() is similar except that the original sequence is unchanged, and the results are copied to a second sequence. rotate(first, middle, toofar) rotates the range [first, toofar) around the iterator middle. rotate_copy() is similar except that the original sequence is unchanged, and the results are copied to a second sequence. random_shuffle(first, toofar) randomly shuffles the elements in the range [first, toofar). partition(first, toofar, unaryOp) partitions the range [first, toofar) by moving elements where unaryOp() returns true to the left, the others to the right. stable_partition() is similar, but it preserves the relative order of the elements within each group. Selected sorting and related operations: All the operations in this section take an optional binary predicate used to compare two elements. sort(first, toofar) sorts the elements in the range [first, toofar). stable_sort(first, toofar) sorts the elements in the range [first, toofar) and never reverses two elements that compare as equal. binary_search(first, toofar, const T& value) looks for value in the sorted sequence range [first, toofar) and returns true or false based on whether value was found. includes(first, toofar, first2, toofar2) checks if the first multiset [first, toofar) is a subset of the second multiset [first2, toofar2). set_union(first, toofar, first2, toofar2, dest) copies into dest the union of the first set [first, toofar) and the second set [first2, toofar2). set_intersection(first, toofar, first2, toofar2, dest) copies into dest the intersection of the first set [first, toofar) and the second set [first2, toofar2). set_difference(first, toofar, first2, toofar2, dest) copies into dest the difference between the first set [first, toofar) and the second set [first2, toofar2). min_element(first, toofar) finds the minimum element within the range [first, toofar). max_element() is analogous. |
