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?
基本上,我想有一个std :: list但是有std :: map属性,比如find(),我真的需要循环遍历每个列表条目才能找到我需要的东西吗?
9 个解决方案
#1
If you want the properties of std::map, why not use std::map? It will be more efficient than looping through every element.
如果你想要std :: map的属性,为什么不使用std :: map?它比循环遍历每个元素更有效。
#2
Checkout Boost.MultiIndex, it's easier and more efficient than using multiple containers with pointers.
Checkout Boost.MultiIndex,比使用带指针的多个容器更容易,更有效。
#3
If you want a container where:
如果你想要一个容器,其中:
1) Insertion order is not important (this is a list)
2) Searching speed is.
1)插入顺序并不重要(这是一个列表)2)搜索速度是。
Then use a
然后用一个
std::set<>#4
Use std::find or std::find_if to find the first position of some value in some iterator range.
使用std :: find或std :: find_if在某个迭代器范围内查找某个值的第一个位置。
#5
If you're worried about the search time but want to keep the order, you might keep two containers with the same data.
如果您担心搜索时间但希望保留订单,则可能会保留两个具有相同数据的容器。
#6
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.
std :: list的目的是找不到/搜索。这就是std :: map的用途。列表非常适合插入,提取,移动和使用排序算法。如果您只需要存储数据并随机查找它,那么请使用地图。如果要构建存储数据的方式和位置,请使用列表。
#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.
听起来你想要的是单个元素的地图,而不是对的地图。使用std :: set
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).
如果你想要的是一个能够快速访问最小或最大元素的容器,那么你可以使用std :: priority_queue
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.
如果您只想搜索列表中的项目而不关心效率,则可以在O(n)时间内使用std :: find()算法执行此操作。这正是该算法的用途,为任何容器提供线性时间搜索功能,而不是比这更好。这是我们使用未排序的数组或向量,列表等。它应该是你的最后的手段,因为它可能比替代品慢得多,虽然它本身就慢。如果你不经常搜索,如果你知道元素靠近第一个迭代器,如果容器很小,没有任何更快的选择等,请使用此方法。
#8
@obecalp has a good answer. boost MultiIndex is a good suggestion. @Bklyn: It is not an "extraordinarily silly" question.
@obecalp有一个很好的答案。提升MultiIndex是一个很好的建议。 @Bklyn:这不是一个“非常愚蠢”的问题。
#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.
我需要完全相同的东西,所以我写了一些列表和地图的组合。我称之为map_list <>和hash_map_list <>。基本上,我把源代码带到xmap.h和xlist.h,并将两者结合起来制作xmap_list.h。此类的工作方式是将键存储在给定的映射中,但与指向包含该值的节点的指针配对。此节点包含一个指向地图的迭代器。节点保存在单独的链表中。以这种方式,您可以像使用map类一样使用find函数,但您也可以按照插入它们的顺序迭代元素,就像列表类一样。您甚至可以像在列表中一样迭代密钥。我没有实现每个最后的等效列表函数,但是大多数你最常使用的函数都存在(例如,我不处理自定义分配器,尽管你可以自己轻松添加它)。它有点像list <>和find()函数。
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.
对于我为此编写的项目,我最终最终转向boost :: multi_index,但我仍然使用上面的map_list <>类,因为它更轻量级并且更接近std :: list <>接口。
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.
我没有在任何地方上传代码,但如果我看到有人在此答案中添加了评论,我会尝试将其发布到某个地方,并在此处记下该位置。
#1
If you want the properties of std::map, why not use std::map? It will be more efficient than looping through every element.
如果你想要std :: map的属性,为什么不使用std :: map?它比循环遍历每个元素更有效。
#2
Checkout Boost.MultiIndex, it's easier and more efficient than using multiple containers with pointers.
Checkout Boost.MultiIndex,比使用带指针的多个容器更容易,更有效。
#3
If you want a container where:
如果你想要一个容器,其中:
1) Insertion order is not important (this is a list)
2) Searching speed is.
1)插入顺序并不重要(这是一个列表)2)搜索速度是。
Then use a
然后用一个
std::set<>#4
Use std::find or std::find_if to find the first position of some value in some iterator range.
使用std :: find或std :: find_if在某个迭代器范围内查找某个值的第一个位置。
#5
If you're worried about the search time but want to keep the order, you might keep two containers with the same data.
如果您担心搜索时间但希望保留订单,则可能会保留两个具有相同数据的容器。
#6
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.
std :: list的目的是找不到/搜索。这就是std :: map的用途。列表非常适合插入,提取,移动和使用排序算法。如果您只需要存储数据并随机查找它,那么请使用地图。如果要构建存储数据的方式和位置,请使用列表。
#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.
听起来你想要的是单个元素的地图,而不是对的地图。使用std :: set
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).
如果你想要的是一个能够快速访问最小或最大元素的容器,那么你可以使用std :: priority_queue
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.
如果您只想搜索列表中的项目而不关心效率,则可以在O(n)时间内使用std :: find()算法执行此操作。这正是该算法的用途,为任何容器提供线性时间搜索功能,而不是比这更好。这是我们使用未排序的数组或向量,列表等。它应该是你的最后的手段,因为它可能比替代品慢得多,虽然它本身就慢。如果你不经常搜索,如果你知道元素靠近第一个迭代器,如果容器很小,没有任何更快的选择等,请使用此方法。
#8
@obecalp has a good answer. boost MultiIndex is a good suggestion. @Bklyn: It is not an "extraordinarily silly" question.
@obecalp有一个很好的答案。提升MultiIndex是一个很好的建议。 @Bklyn:这不是一个“非常愚蠢”的问题。
#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.
我需要完全相同的东西,所以我写了一些列表和地图的组合。我称之为map_list <>和hash_map_list <>。基本上,我把源代码带到xmap.h和xlist.h,并将两者结合起来制作xmap_list.h。此类的工作方式是将键存储在给定的映射中,但与指向包含该值的节点的指针配对。此节点包含一个指向地图的迭代器。节点保存在单独的链表中。以这种方式,您可以像使用map类一样使用find函数,但您也可以按照插入它们的顺序迭代元素,就像列表类一样。您甚至可以像在列表中一样迭代密钥。我没有实现每个最后的等效列表函数,但是大多数你最常使用的函数都存在(例如,我不处理自定义分配器,尽管你可以自己轻松添加它)。它有点像list <>和find()函数。
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.
对于我为此编写的项目,我最终最终转向boost :: multi_index,但我仍然使用上面的map_list <>类,因为它更轻量级并且更接近std :: list <>接口。
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.
我没有在任何地方上传代码,但如果我看到有人在此答案中添加了评论,我会尝试将其发布到某个地方,并在此处记下该位置。