Search within list c++?

Question

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?

Hint: You can always search in a sequence by testing each one of the elements. — David Rodríguez - dribeas, Jan 16 '13 at 23:05
depends on what "look up" means for a list. Do you want to look up an element by it's value or by it's index? — Mooing Duck, Jan 16 '13 at 23:09
@juanchopanza True, the "guaranteed performance" of them is identical — Mooing Duck, Jan 16 '13 at 23:12

score 2 · Accepted Answer · edited Jan 20 '13 at 18:54

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.

score 1 · Answer 2 · answered Jan 16 '13 at 23:25

From http://www.cplusplus.com/reference/list/list/

The main drawback of lists and forward_lists compared to these other sequence containers is that they lack direct access to the elements by their position; For example, to access the sixth element in a list one has to iterate from a known position (like the beginning or the end) to that position, which takes linear time in the distance between these. They also consume some extra memory to keep the linking information associated to each element (which may be an important factor for large lists of small-sized elements).

So, iterating through a std::list< > (looking up an element) is linear complexity. Also, you cannot access elements by index.

score 1 · Answer 3 · edited May 23 '17 at 12:04

I recommend that you read the following reference: What are the complexity guarantees of the standard containers?

It has a chart of order complexity of many standard containers and one of the answers links to the STL complexity specifications. (http://www.sgi.com/tech/stl/complexity.html)

Since this is a class project, I recommend that you not only read these reference for your answer, but spend some time in the STL headers and get a feel for the implementation of these containers on your architecture.

STL is a fantastic way to leverage the knowledge of true experts ... however it can also be the proverbial enough rope, if not given due diligence

score 1 · Answer 4 · answered Jan 17 '13 at 01:20

In case you want a more formal statement of what's supported, here's what the standard has to say. About the best searching we can do is with a binary search, such as std::lower_bound (§25.4.3.1/3):

Complexity: At most log₂(last − first) + O(1) comparisons.

That only tells us the number of comparisons though. To move through the container, lower_bound uses std::advance. About an std::list we find (§23.3.5.1/1):

A list is a sequence container that supports bidirectional iterators [...]

So, how does std::advance work for a collection that provides bidirectional iterators? (§24.4.4/1):

[...] for input, forward and bidirectional iterators they use ++ to provide linear time implementations.

So, to find anything in a list (by either value or position) we're going to be looking at linear complexity overall, with a logarithmic number of comparisons. To be honest, we're probably better off with std::find (§25.2.5/2):

Complexity: At most last - first applications of the corresponding predicate.

The choice between the two may not always be entirely obvious though -- traversing the list is obviously linear. std::find minimizes traversal, while std::lower_bound minimizes comparisons. If comparison is a lot more expensive than traversal, std::lower_bound will probably do better. If comparison is fairly cheap, std::find is probably better.

Search within list c++?

4 Answers4