Thanks for looking at my question in advance.
I am completing a question for a university assignment that asks the following:
For each of std::list< >, std::map< >, std::unordered_map< > document and explain the guaranteed performance for element insertion and look-up.
I have had no trouble doing most of this, until I come to explain element look-up within a list.
I have been gathering my information from Josuttis and http://www.cplusplus.com and cannot seem to find any information about this.
I'm guessing because it's not possible?
You mention that you had no trouble except with the list portion, so I'm only going to answer for that portion.
In order to answer this question, you need to understand how std::list is implemented.
Some quick searching brings up:
List containers are implemented as doubly-linked lists.
From how I interpret it, Guaranteed Performance means the same thing as Worse-case Runtime Complexity.
For element lookup in a doubly-linked list, the worst-case scenario is that your list does not contain the item you are trying to lookup. In that case, you would have to compare every item in the list to the item you are searching for. So the worst-case runtime complexity of this operation is O(n), where n is the size of the list.