-
[ Pobierz całość w formacie PDF ]
is inserted is located at the topmost position, and any subsequent elements are located at
lower positions. The two basic operations in a queue are pop() and push(). A push()
operation inserts an element into the bottom of the queue. A pop() operation removes the
element at the topmost position, which was the first to be inserted; consequently, the
element that is located one position lower becomes the topmost element. The STL queue
container can be used as follows:
#include
#include
using namespace std;
int main()
{
queue iq;
iq.push(93); //insert the first element, it is the top-most one
iq.push(250);
iq.push(10); //last element inserted is located at the bottom
cout
while (!iq.empty() )
{
cout
returns
//the top-most
element
iq.pop(); //remove the top-most element
}
return 0;
}
STL also defines a double-ended queue, or deque (pronounced "deck") container. A
deque is a queue that is optimized to support operations at both ends efficiently. Another
type of queue is a priority_queue. A priority_queue has all its elements internally
sorted according to their priority. The element with the highest priority is located at the
top. To qualify as an element of priority_queue, an object has to define the
(priority_queue is discussed in detail later, in the section titled "Function Objects").
Iterators
Iterators can be thought of as generic pointers. They are used to navigate a container
without having to know the actual type of its elements. Several member functions such as
begin() and end() return iterators that point to the ends of a container.
begin() and end()
All STL containers provide the begin() and end() pair of member functions. begin()
returns an iterator that points to the first element of the container. For example
#include
#include
#include
using namespace std;
int main()
{
vector v(1); //room for a single element
v[0] = 10;
vector::iterator p = v.begin(); // p points to the first
element of v
*p = 11; //assign a new value to v[0] through p
cout
return 0;
}
The member function end(), on the other hand, returns an iterator that points one
position past the last valid element of the container. This sounds surprising at first, but
there's nothing really unusual about it if you consider how C-strings are represented: An
additional null character is automatically appended one position past the final element of
the char array. The additional element in STL has a similar role it indicates the end of the
container. Having end() return an iterator that points one position past the container's
elements is useful in for and while loops. For example
vector v(10);
int n=0;
for (vector::iterator p = v.begin(); p
*p = n++;
begin() and end() come in two versions: const and non-const. The non-const version
returns a non-const iterator, which enables the user to modify the values of the
container's element, as you just saw. The const version returns a const iterator, which
cannot modify its container.
For example
const vector v(10);
vector::iterator p = v.begin(); //error, must use a
const_iterator
vector::const_iterator cp = v.begin(); //OK
*cp = 'a'; //error, attempt to modify a const object
cout
The member functions rbegin() and rend() (reverse begin() and reverse end()) are
similar to begin() and end(), except that they return reverse iterators, which apply to
reverse sequences. Essentially, reverse iterators are ordinary iterators, except that they
invert the semantics of the overloaded ++ and -- operators. They are useful when the
elements of a container are accessed in reverse order.
For example
#include
#include
#include
using namespace std;
void ascending_order()
{
vector v(10);
double d = 0.1;
for (vector::iterator p = v.begin(); p
//initialize
{
*p = d;
d+= 0.1;
}
//display elements of v in ascending order
for (vector::reverse_iterator rp = v.rbegin(); rp
rp++)
{
cout
}
}
Like begin() and end(), rbegin() and rend() have a const and a non-const version.
The Underlying Representation of Iterators
Most implementations of STL use pointers as the underlying representation of iterators.
However, an iterator need not be a pointer, and there's a good reason for that. Consider a
huge vector of scanned images that are stored on a 6GB disk; the built-in pointer on most
machines has only 32 bits, which is not large enough to iterate through this large vector.
Instead of a bare pointer, an implementation can use a 64-bit integer as the underlying
iterator in this case. Likewise, a container that holds elements such as bits and nibbles (to
which built-in pointers cannot refer) can be implemented with a different underlying type
for iterators and still provide the same interface. However, bare pointers can sometimes
be used to iterate through the elements of a container on certain implementations; for
example
#include
#include
using namespace std;
void hack()
{
vector vi;
vi.push_back(5);
int *p = vi.begin();//bad programming practice, although it may work
*p = 6; //assign vi[0]
cout
}
Using bare pointers instead of iterators is a bad programming practice avoid it.
"const Correctness" of Iterators
Use the const iterator of a container when the elements that are accessed through it are
not to be modified. As with ordinary pointer types, using a non-const iterator implies [ Pobierz całość w formacie PDF ] - zanotowane.pl
- doc.pisz.pl
- pdf.pisz.pl
- zambezia2013.opx.pl