Sign in to follow this  
Nanook

sequential/random access, indices and iterator

Recommended Posts

Nanook    537
My book is talking about sequential and random access.. and its talking about indices and iterators.. I understand some of it, but I'm abit confused. I dont realy understand the difference between sequential and random access.. I mean.. a for loop using indices or iterators is both going through the container in a sequential order?? pleas help me understand! :)

Share this post


Link to post
Share on other sites
Conner McCloud    1135
If you have a choice between the two, then it doesn't really matter which you chose. If you don't have a choice, then you use the one you have to use.

Sequential access means exactly what it sounds like: you access the elements in order. First element, second element, third element. Random access is equally straight forwards: you access the elements out of order. Fifth element, eighth element, first element. Random access reduces down to sequential access when you just go from one to the next, so you can use iterators [which are designed with sequential access in mind] just fine.

CM

Share this post


Link to post
Share on other sites
Rainault    154
As an example that uses container data structures, linked lists generally do not support random access, while vectors do. A linked list can only access a random element in linear time, so it's generally an inefficient operation when compared to other containers if random access is needed regularly. A vector, however, does support random access in constant time. For example, the SC++L std::vector class uses a contiguous chunk of memory to hold the data, so simple pointer arithmetic makes constant time random access easy. A std::list, however, must go through each node to get to an arbitrary element, since each node only knows about its previous and next nodes.

Iterators are generally preferable to indices, since you can let the iterator worry about the access method. All you care about is the value that the iterator returns. Indices presume that random access is supported when it may not be. (e.g. what if you change from using a vector to a linked list?)

Share this post


Link to post
Share on other sites
Zahlman    1682
0a) You can edit your posts to add extra stuff.
0b) You don't "add up to" a post; you add to it. "Add up to X" means, of a set of values, having a sum of X.

1a) Sequential access means access that is sequential, i.e. sequence-like - in order. That is, you can only easily get to element N if you are already at N-1.

1b) Random access is the most general kind of access to a container: access is arbitrary. That is, if you want element N, you just grab it directly; all that's involved is picking N and saying "fetch me element N".

When a container only properly supports sequential access, you could ask for element N, but finding that element requires finding all the previous elements, because there's no other way to know where it is. This is the case with std::list, which is a linked list implementation: to find element N (except for N == 0), you first need to find element N-1, and the "node" that holds the element will also include a pointer that points to the "next" element (technically, to the next node). (std::list is actually a doubly linked list, so the nodes have "previous"-node pointers as well, but for our purposes they are not helpful.

2) An iterator is any kind of thing that you can use to iterate over a container. There are different kinds of iterators, according to what kind of access they give you to the container. Also, containers can create iterators that iterate over themselves, of an iterator-type that depends on the container.

2a) A random access iterator provides random access (obviously enough).
2b) A bidirectional iterator provides sequential access, either forwards or backwards. The iterators provided by a std::list have this property.
2c) A forward iterator provides sequential access, but only forwards. A singly linked list would normally provide such an iterator, because you can't easily move backwards through the list.
2d) An input iterator is a restriction of a forward iterator, which only lets you read values (not modify them), and where you aren't necessarily able to "restart": data might be "consumed" by the process of reading, and not be re-readable, even by another iterator. This is the sort of iteration that an input stream would provide (e.g. once you read a number from 'cin', the stream has advanced to the next data, and you can't re-read the number). Similarly, an output iterator only lets you write values, and might not let you overwrite a previously written value (because it isn't necessarily held in memory anywhere, but could have been sent to an output stream).
2e) A trivial iterator doesn't let you move at all; it only "iterates over" a single item. This idea is still useful in some contexts.

Note that in general, only easy-to-implement iterators are provided, because more powerful ones would encourage writing slow algorithms. If std::list provided a random access iterator, for example, then actually doing the random access would require "faking it" in terms of the sequential access, which would be slow. Similarly, a singly-linked list could provide a bidirectional iterator, but moving it backwards would be slow. Changes to iterators are expected to be constant-time operations so that you can easily reason about your algorithms; since we're talking about order-of-complexity here, these concerns are considered more important than providing a higher level of abstraction.

3) The "simplest" (conceptually; not always the simplest to use!) container is an array. The natural iterator for an array is a pointer-to-element. Therefore, other kinds of iterators provide an interface such that they pretend to be pointers. That means you can "dereference" them to get the 'current' element, compare them for equality (to see if you're at the beginning and/or end of the container), and advance them by addition and subtraction (in the case of iterators that are not random access, you can only use increment and possibly decrement, because again, adding and subtracting directly would lie to you about efficiency).

4) For cases where you do want to treat bidirectional (or more restricted) iterators as if they were random-access, there exist the library functions std::distance (determines the "distance between" two compatible iterators, in number of elements) and std::advance ("moves" an iterator by the indicated amount, either by adding, or by repeatedly incrementing or decrementing, according to the iterator type). This lets you treat the different iterators in the same way, while also giving some warning about efficiency.

5) By convention, an "end" iterator for a container actually "points to" an element one past the end; you can't validly dereference the iterator, because the element isn't there. This is to simplify the math: it preserves the invariant that std::distance(beginning of container, end of container) == number of elements in container.

6) After all of that, an "index" becomes nothing more than a distance between an iterator and the beginning of the container it iterates over.




Examples:


#include <vector>
#include <list>
#include <iterator> // std::advance and std::distance defined here
#include <algorithm> // std::fill defined here
#include <cassert>

int main() {
std::vector<char> v(1024);
std::list<char> l(1024);
char a[1024];

v.begin(); // is a random access iterator over the vector 'v'
l.begin(); // is a bidirectional (i.e. sequential) iterator over the list 'l'
a; // is a pointer to the beginning of a, i.e. a random access iterator over
// the array

v.end(); // the end of the vector
l.end(); // the end of the list
a + sizeof(a) / sizeof(a[0]);
// the end of the array, using the same conventions. (That sizeof trick is
// a usual way to avoid hard-coding the array length everywhere; note that it
// will NOT work if the array is coming in to the function as a parameter.)

// Manually iterating over the containers, to fill them with x's:
for (std::vector<char>::iterator it = v.begin(); it != v.end(); ++it) {
*it = 'x';
}
for (std::list<char>::iterator it = v.begin(); it != v.end(); ++it) {
*it = 'x';
}
for (char* it = a; it != a + sizeof(a) / sizeof(a[0]); ++it) {
*it = 'x';
}
// Notice another consequence of end iterators being "one past the end", is
// how we write the loops: the end condition works similarly to how you
// should be accustomed to looping over a plain array.
// However, we use != rather than < because it's more general - the < only
// exists for random access iterators. We can get away with this because
// there's no way of "skipping over" the end iterator :)

// Manually "iterating" over the containers by indexing:
for (int i = 0; i < v.size(); ++i) {
v[i] = 'x';
}
// Not directly possible for std::list. If we use std::advance to fake it:
for (int i = 0; i < l.size(); ++i) {
std::list<char>::iterator it = l.begin();
std::advance(it, i);
*it = 'x';
}
// then it will be very slow compared to the others.
// (Although for only 1024 elements you might not notice)
for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i) {
a[i] = 'x';
}

// Using the standard library algorithm std::fill to do it:
std::fill(v.begin(), v.end(), 'x');
std::fill(l.begin(), l.end(), 'x');
std::fill(a, a + sizeof(a) / sizeof(a[0]); 'x');
// Notice that this way, we don't have to concern ourselves with type names,
// or with making sure we got our for-loop right (incrementing the correct
// iterator or index value, etc.). As well, we can call the same function
// with different kinds of iterators; all that matters is that the iterators
// we provide "match", i.e. are the same kind (checked at compile time) and
// belong to the same container (otherwise will blow up at run time).

// Also notice that if we change a container type from a vector to a list
// or vice versa, we don't need to change a std::fill invocation on the
// container at all. This is a huge advantage for maintenance!

// The invariant I mentioned:
assert(std::distance(v.begin(), v.end()) == v.size());
assert(std::distance(l.begin(), l.end()) == l.size());
// Note that it will get the same result for the different iterator types,
// but in different ways. For a random access iterator, it can effectively
// just subtract; distance() on a sequential iterator has to traverse from
// begin to end, one element at a time. The compiler does a lot of magic
// with templates so that it's fast when it can be and at least works
// in the other cases.
}






Or you could try reading this.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this