Sequence

[VanKha]

Please explain the concept of sequence to me . I know that sequence uses both the concept of Position of List and rank of Vector(source:cpp.datastructure.net)but how does we implement it ? Sequence simply looks like an array - it's so confusing.

[raistlinx]

A Sequence is an ADT that models, well a sequence of something. If you imagine a line of people holding hands you would have a "sequence" of people.

If you further imagine the line grows from left to right then you can imagine two things. First, every person has a number which is how many places they are from the left (this is their rank). Second, everyone has someone (or the end of the sequence) to the left and to the right so relative to them they have a "position" in the sequence such as "I am to the left of Joe and the right of Mary"

That is all there is to it conceptually.

Now, if you implement a sequence with an array it is easy to think of the "rank" and if you implement with a linked list it is easier to think of the "position". But the Sequence ADT, which is what you are asking about, doesn't worry about the implementation details so it is not limited by the ease of implementation.

A properly implemented Seqeunce will have bridging methods anyway which allows the user to use either rank or position.

[ravenspoint]

For an abstract description, that was pretty clear.

Time for some nuts and bolts!

Let's use an STL vector for this.

The rank would simply use the [] operator.

The sequence ( left or right ) would take an iterator and return an iterator for the member on the left or right, or end() if there is none. Something like this:

    typedef vector < T >::iterator P;
    vector < T > mySequence;
 
    P left( P p ) { if( p == mySequence.begin() ) return mySequence.end(); else return p - 1; }