| All iterators remain valid and continue to point to the same elements. [7] The number of comparisons is approximately N log N, where N is the slist 's size. |
Notes [1] The lists in such languages as Common Lisp, Scheme, and ML are singly linked lists. In some programming languages, almost all data structures are represented as singly linked lists.
[2] A comparison with vector is instructive. Suppose that i is a valid vector<T>::iterator . If an element is inserted or removed in a position that precedes i , then this operation will either result in i pointing to a different element than it did before, or else it will invalidate i entirely. (A vector<T>::iterator will be invalidated, for example, if an insertion requires a reallocation.) However, suppose that i and j are both iterators into a vector, and there exists some integer n such that i == j + n. In that case, even if elements are inserted into the vector and i and j point to different elements, the relation between the two iterators will still hold. An slist is exactly the opposite: iterators will not be invalidated, and will not be made to point to different elements, but, for slist iterators, the predecessor/successor relationship is not invariant.
[3] This member function relies on member template functions, which at present (early 1998) are not supported by all compilers. If your compiler supports member templates, you can call this function with any type of input iterator. If your compiler does not yet support member templates, though, then the arguments must either be of type const value_type* or of type slist::const_iterator.
[4] A similar property holds for all versions of insert() and erase() . Slist<T, Alloc>::insert() never invalidates any iterators, and slist<T, Alloc>::erase() only invalidates iterators pointing to the elements that are actually being erased.
[5] This member function relies on member template functions, which at present (early 1998) are not supported by all compilers. You can only use this member function if your compiler supports member templates.
[6] The reverse algorithm works only for bidirectional iterators. Even if reverse were extended to work with forward iterators, however, it would still be useful to have the reverse member function: it has different iterator invalidation semantics. That is, the reverse member function preserves the value that each iterator points to. Note also that the algorithm reverse(L.begin(), L.end()) uses T 's assignment operator, but the member function L.reverse() does not.
[7] The sort algorithm works only for random access iterators. In principle, however, it would be possible to write a sort algorithm that also accepted forward iterators. Even if there were such a version of sort, it would still be useful for slist to have a sort member function. That is, sort is provided as a member function not only for the sake of efficiency, but also because of the property that it preserves the values that list iterators point to.
See also Bidirectional Iterator, Reversible Container, Sequence, list, vector
Category: containers
Component type: type
Description A bit_vector is essentially a vector<bool>: it is a Sequence that has the same interface as vector. The main difference is that bit_vector is optimized for space efficiency. A vector always requires at least one byte per element, but a bit_vector only requires one bit per element.
Warning: the name bit_vector will be removed in a future release of the STL. The only reason that bit_vector is a separate class, instead of a template specialization of vector<bool>, is that this would require partial specialization of templates. On compilers that support partial specialization, bit_vector is a specialization of vector<bool>. The name bit_vector is a typedef. This typedef is not defined in the C++ standard, and is retained only for backward compatibility.
Example bit_vector V(5);
V[0] = true;
V[1] = false;
V[2] = false;
V[3] = true;
V[4] = false;
for (bit_vector::iterator i = V.begin(); i < V.end(); ++i) cout << (*i ? '1' : '0');
cout << endl;
Definition Defined in the standard header vector, and in the nonstandard backward-compatibility header bvector.h.
Template parameters None. Bit_vector is not a class template.
Model of Random access container, Back insertion sequence.
Type requirements None.
Public base classes None.
Members | Member | Where defined | Description |
value_type | Container | The type of object stored in the bit_vector: bool |
