std::list with std::map properties?

Question

Basically, I want to have a std::list but with std::map properties such as find(), do I really need to loop through every single list entry to find what I need?

Answer 1

If you want the properties of std::map, why not use std::map? It will be more efficient than looping through every element.

Answer 2

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

Answer 3

If you're worried about the search time but want to keep the order, you might keep two containers with the same data.

Answer 4

If you want a container where:

1) Insertion order is not important (this is a list)
2) Searching speed is.

Then use a

std::set<>

Answer 5

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

Answer 6

Checkout Boost.MultiIndex, it's easier and more efficient than using multiple containers with pointers.

Answer 7

Option 1

It sounds like what you want is a map of single elements, as opposed to a map of pairs. Use std::set<T>, which is an adaptor implemented as std::map<T,void>. This means all your elements will be unique; that is, there will be no duplicates in your container. It also implies your elements will not be strictly ordered; that is, you can't rely on the position of any element at any given time. Then you can use the find() member function of std::set<T>, which will perform a fast search for an element in logarithmic time.

Option 2

If what you want is a container that provides fast access to the smallest or largest element then you can use std::priority_queue<T,C> with a container C of your choice. If not specified, the default container used is a std::vector<T>. std::priority_queue<T> uses the make_heap(), push_heap() and pop_heap() algorithms and thus requires the underlying container to support random-access iterators; std::list<T> will not suffice in this case. Access the "first" (largest or smallest) element in constant time with the top() member function. Push and pop the first element with the push() and pop() member functions, which operate in logarithmic time (2*log(n), actually, because they need to search as well as bubble up).

Option 3

If what you want is merely a list that holds pairs, just declare it as such:

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

This will give nothing but a linked list with the limits and benefits of any other linked list, but will hold pairs just like a map does. You will thus use standard algorithms to manipulate the list. You will probably need to pass specialized functions or functors to the algorithms with this list, to dereference the key or value out of the pair.

If all you want is to search for an item in a list, with no concern for efficiency, you can do this with the std::find() algorithm in O(n) time. This is exactly what this algorithm is for, to provide linear time search functionality for any container than can't do better than that. This is what we use with unsorted arrays or vectors, with lists etc. It should be your last resort, because it can be much slower than the alternatives, albeit to slow by itself. Use this approach if you don't search often, if you know that the element is near the first iterator, if the container is small, when there aren't any faster alternatives etc.

Answer 8

@obecalp has a good answer. boost MultiIndex is a good suggestion. @Bklyn: It is not an "extraordinarily silly" question.

Answer 9

I needed the exact same thing, so I've written something that is a combination of list and map. I call it map_list<> and hash_map_list<>. Basically, I took the source code to xmap.h and xlist.h and combined the two to make xmap_list.h. The way this class works is by storing the key in the given map, but paired with a pointer to a node which contains the value. This node contains an iterator which points back into the map. The nodes are kept in a separate linked list. In this fashion, you can use the find function as you would normally with a map class, but you can also iterate the elements in the order in which you inserted them, like a list class. You can even iterate the keys themselves as if in a list. I didn't implement every last equivalent list function, but most of the ones you use most are there (for example, I don't handle custom Allocators, although you could easily add this yourself). It kind of looks like list<> with a find() function.

For the project I wrote this for, I eventually ended up moving to boost::multi_index, but I still use the above map_list<> class when I can because it is a lot more lightweight and is closer to the std::list<> interface.

I don't have the code uploaded anywhere, but if I see that someone has added a comment to this answer, I will try and post it somewhere, and note the location here.