sequential access / sequential containers?

I have been learning containers. Now learning sequenial, and it says " The data structure they implement enables a sequential access" So i want to know what this means, google says "Sequential access must begin at the beginning and access each element in order" but this confuse me because, std::array is listed as sequential container but i can directly access an element of that, so I do not need to access each element. Do I not understand correctly? same as with vector, i can do vector[] and get specific element, so I do not understand what this means? Can someone please explain'?
I think the idea is that "random access" includes "sequential", but "sequential" does not necesarily include "random access".
So a vector is "random access" and also, therefore, "sequential" since random access obviously allows sequential access.
But a list is only "sequential" access.

See "iterator categories" for an example of the nesting of these categories:
https://en.cppreference.com/w/cpp/iterator
Take it back to the most basic definition...
Think of your iTunes songs in alphabetic order...

Right now I want you to get to a song in the "S"...
- In a Sequential access I would have to read every song from A - R, checking them and saying, "Nope... not that one", reading every single song, one at a time, until I got to the song I want.. That's sequential.. happening in order from start to finish, no matter what. If you want another sing, you have to start at the A's all over again (Well, unless the next song was further along the same sequential path your already on).

Random Access is like saying I want the song "Susy Q" and the system jumps DIRECTLY to that record or array element where the song "Susy Q" is and says, "here ya go!" and then it can jump anywhere else you want immediately without resetting or messing around.

In 1979 when I started, the only real data access we had was flat file Sequential or Random access with numbered records. Random Access was the Porsche of the day. Its a very old topic and very much core to just about everything in data today. Everything starts out as either sequential or random access.

I hope this helps.
John
Last edited on
this can be a little confusing at first.
do you know what a linked list is yet? If not, that will make the difference very clear when you see it, and reading ahead on the data structure just a little may help with this concept.

there are 2 things at play. first is mechanics.
random access works because the data is in memory as one long block of bytes. The basic mechanics here is that you have the starting location in memory, and you know how big each item is and how many you have. So array at memory location 1234 of 10 32 bit integers: the 4th location is 4 bytes (32 bits) times 4 spaces away -- its simple to hop to the spot you want and that is what[4] will do behind the scene of a vector or array etc. Now image that the items are not one long block of bytes but scattered in memory so that the first one is as 1234, the second a 2345, the third at 3456 or whatever values. There is no way to get from one to the next directly with just a computation, so the data structure has to actually store the next location's memory address as part of its internal workings. This is what a linked list or tree does (when using traditional pointer based designs). The way these are stored prevent hopping directly, you have to follow the chain of addresses to each one.

the second thing at play is just conceptual limitations. A queue is a data structure where you put data into one end and pull it out the other, and it comes out in the order it went in, like a line of people at a bank or whatever. You can put a queue into a vector or array, and it would be random access, but your code won't allow that, it forces sequential access upon the user to avoid breaking the rules of the container and its expected behaviors.

you will encounter both forms of sequential access at some point (mechanical and logical).
Last edited on
sorry i still have issue understanding.

I understand now about random and sequencial. I like the song example. But I do not understand why array and vector still is sequencial?

I know about lists and how they work, that you have to go through each elements in the list, but they are different from array, and that is why i am confused why they are listed as the same as vector and array.

Sorry i make edit i missed comment from dutch by accident. So does that mean that vector and array should be both sequencial and random access. the site only says sequencial, but site can be wrong.
Last edited on
I understand now about random and sequencial. I like the song example. But I do not understand why array and vector still is sequencial?

an array is a random access container. One way to randomly access it is:
for(int i = 0; i < size; i++)
array[i] = i;
which is sequentially.
another way to access it is this:
for(int i = 0; i < size; i++)
array[rand()%size] = i;
it may not make much sense to do that in a program, but it is perfectly legal.

therefore, by example, a random access container MAY BE accessed sequentially, but it does not REQUIRE the user to do so.

All that to say yes, array and vector are BOTH random and sequential access.

If the site says that lists are the same as array, the site is no good, find a better site.

maybe
https://en.wikipedia.org/wiki/Sequential_access
https://en.wikipedia.org/wiki/Random_access

if you want to look at it from a more pure side,
then think of it this way: a container requires sequential access, or it does not. If you want to make THAT distinction, then arrays and vectors are not purely sequential access, but a linked list would be. Not sure what that means for a tree or graph, though. I am not sure this is a useful direction to go in, though, unless you are doing a thesis about it. I think saying an array is both is fine and would stick to a more practical way to define the terms instead.
Last edited on
jonnin wrote:
random access works because the data is in memory as one long block of bytes.

This. Array (and vector) have their elements in a continuous block of memory. Consecutive. Successive. Sequential. That is not about access. That is about memory layout. That layout allows calculating the location of random element. Random access.

Linked list ... we have no idea how elements are in the memory. In order to find an element we need to find the element before it ... recursively from the first element of the list. Sequential access.
Random access doesn't necessarily imply contiguous. For example std::deque provides random access but does not store elements contiguously.
Last edited on
fair enough, but you can still always do random access in front to back order.
Topic archived. No new replies allowed.