Which stl container...

[Usura]

hey Ive been given a task which im suppose to create a chained container which recieves only 1 string, and continues chaining untill there is a repeat in the input, I was thinking that maps would be more appropriate but im not sure if I would be able to chain those, anyone have any suggestions?

[StuXYZ]

You can do this in a number of different ways. What you seem to have here is two processes to do, which have different efficient in different containers. That means that you have to have a compremise.

So, let use construct a simple consideration with the basic items:

You can use one of the assiociative containers e.g. set, map, these have the advantage of begin efficient to find items within the container BUT they do not preserve order, so although iteration from begin() to end() is guarenteed to (a) not repeat any of the items and (b) to contain all the items in the container the order is unpreserved.

Alternatively you could use a sequentual conatiner e.g. list or vector. The advantage is that it preserves the order but to search you need to step through the container.

Then there is the next decision, do you want store just strings or a composite class. So for example you could store a class like this

struct Node
{
     std::string Value;
     Node* PrevNode;
};

Finally, you can use TWO containers, e.g an set and a list. This double stores the informtion but makes life easy.
This would be used in a map (for example),

How to deside?

The key decision is which part of the problem is going to happen most.

\begin{tabular}{|l|ccc|}
\hline\\
Main/Job & Sequence & Assosiative &Two \\
\hline\\
Loop Over & X &&\\
Entry Once & X & & X \\
Large Build for result: & & X & \\
\hline
\end{tabular}
\

So I have given some typical scenarios and some typical choises (marked with an X). For example you don't want to keep two containers if you expect the build to be large.

Additionally, for SMALL problems, it is down to ease of programming, for larger problems, you might be coding several versions and profiling.