访问 std::map 中元素的最有效方法是什么？

Question

我在 class 中有一个 std::map<some_type, std::vector<another_type>> 作为静态变量。我想要一个 said class 的对象对应于地图向量中的一个元素。我的直接想法是只对向量和地图使用存储迭代器，但我也考虑过存储密钥的副本，以便我可以使用 map::find 来查找与其关联的值。推荐哪种方式或更有效？

代码:

class example_class
{
private:
    static std::map<some_type, std::vector<another_type>> my_list;

    some_type::iterator map_it;

    // I could either use this
    std::vector<another_type>::iterator location_in_vector_it;

    // or this
    some_type copy_of_key;

public:
    // the constructor creates a new element, or adds the value to the end
    // of the vector in the preexisting element.
    example_class(key, val);
};

Answer 1

如果 my_list 的大小发生变化，则无法将迭代器存储到 my_list 中的向量（除非您之前保留所有内容）。

最简单的方法是将键和索引存储在向量中，假设您只推回新元素而不删除旧元素。最好的是带有索引的地图中的迭代器。

Answer 2

推荐的方法是编写正确、易于理解且有意义的代码。至于效率：

如果 vector 可以增长，那么存储 vector 的迭代器不是一个好主意，因为 vector::insert 可以无效 ate 迭代器。
将索引存储到 vector 中（如果这是一个选项——这些向量如何改变？）允许在 O(1 ) 时间，但在你的情况下你仍然需要找到向量。
存储一个 map 的迭代器可以让你在 O(1) 时间内找到向量，并且这个迭代器在之后仍然有效map 被修改（除非您删除迭代器指向的条目）。
- 在 map 中存储对 vector 的引用类似于使用迭代器，并且可能会导致代码更具可读性。
存储密钥并使用 map::find 可以让您在 O(lg n) 时间内找到向量。这种方法可以处理您要查找的向量已从 map.

所以最安全的做法就是把key和index存起来，然后写代码处理找不到元素的情况。但是.... 这是应该能够发生的事情吗？ 是否允许您的对象的元素被其他人（可能是同一类型的另一个对象）删除？可能不是，因为每个对象都应该 "correspond to an element"。这是你设计的问题吗？

如果我这样做，我可能想确保我的对象的元素不会被粗暴地拿走。一种方法是使用 shared pointers。我可能会考虑存储 std::vector<std::shared_ptr<another_type>>，而不是将 std::vector<another_type> 存储在 map 中。根据对象销毁时应该发生的情况，我可能会将 shared_ptr 更改为 weak_ptr，以便静态容器不会维护不再存在的对象的数据。在任何一种情况下，每个对象都可以为其元素维护自己的 shared_ptr。这允许快速访问元素并确保元素不会在对象被销毁之前被销毁。

当然，最理想的方法取决于您需要将这些元素存储在静态容器中的原因。

访问 std::map 中元素的最有效方法是什么？

What is the Most Efficient Way to Access Elements in an std::map?

c++

iterator

stdmap