Std :: list with std :: map properties?

If you want std :: map properties, why not use std :: map? This will be more efficient than looping through each element.

Use std :: find or std :: find_if to find the first position of some value in some range of iterators.

If you are worried about the search time but want to keep the order, you can save two containers with the same data.

The purpose of std :: list is not to search / search. This is what std :: map is for. A list is great for inserting, extracting, moving, and using sorting algorithms. If you just need to store data and find it by accident, use a map. If you want to structure how and where your data is stored, use a list.

Option 1

It sounds like what you want is a map of individual elements as opposed to a map of pairs. Use std::set<T>

which is the adapter implemented as std::map<T,void>

. This means that all of your elements will be unique; that is, there will be no duplicates in your container. This also implies that your elements will not be strictly ordered; that is, you cannot rely on the position of any element at any given time. Then you can use a member function find()

std::set<T>

, which will do a quick search for an element in logarithmic time.

Option 2

If you need a container that provides quick access to the smallest or largest item, you can use std::priority_queue<T,C>

with the container C

of your choice. If not specified, the default container used is std::vector<T>

. std::priority_queue<T>

uses algorithms make_heap()

, push_heap()

and pop_heap()

therefore requires the underlying container to support random access iterators; std::list<T>

in this case will be insufficient. Access the item "first" (largest or smallest) over time using a member function top()

. Click and pull the first item using the member functions push()

and pop()

, which run in logarithmic time (2 * log (n), in fact, because they have to search, and also bubble up).

Option 3

If you just want a list containing pairs, just declare it as such:

std::list<std::pair<T> > the_list;

      

        
        
        
      

    

This will yield nothing but a linked list with the limitations and benefits of any other linked list, but will contain pairs like a map does. Thus, you will use standard algorithms to manipulate the list. You will probably need to pass specialized functions or functors to algorithms with this list to dereference a key or value from a pair.

If you want to find an item in a list without worrying about efficiency, you can do it with an algorithm std::find()

in O (n) time. This is exactly what this algorithm is designed to do, to provide a linear time search function for any container than it can do better. This is what we use with unsorted arrays or vectors, with lists, etc. This should be your last resort, because it can be much slower than alternatives, albeit slow on its own. Use this approach if you don't search often, if you know the element is near the first iterator, if the container is small, when there are no faster alternatives, etc.

@obecalp has a good answer. boost MultiIndex is a good suggestion. @Bklyn: This is not an "unusually stupid" question.