Какой самый эффективный способ доступа к элементам в std :: map?

Question

У меня есть std::map<some_type, std::vector<another_type>> в качестве статической переменной в классе.Я хочу, чтобы объект указанного класса соответствовал элементу в векторе карты.Моей непосредственной мыслью было просто использовать функцию сохранения итератора как для вектора, так и для карты, но я также подумал о сохранении копии ключа, чтобы я мог использовать 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

Рекомендованный способ - написать код, который является правильным, простым для понимания и имеет смысл.Что касается эффективности:

• Хранение итератора vector - плохая идея, если vector может расти, так как vector::insert может недействительно съел итераторы.

• Сохранение индекса в vector (если это вариант - как эти векторы могут измениться?) позволяет получить элемент в O (1) время, но в вашем случае вам все еще нужно найти вектор.

• Хранение итератора map позволит вам найти вектор в O (1) времени, и этот итератор остается действительным после изменения map (если только вы не удалите запись, на которую указывает итератор).

  • Сохранение ссылки на vector вmap аналогично использованию итератора и может привести к более читаемому коду.
• Хранение ключа и использование map::find позволит вам найтивектор во O (lg n) времени.Этот подход может справиться со случаем, когда искомый вектор был удален из map.

Так что самый безопасный подход - хранить ключ и индекс, инаписать код для обработки случаев, когда элемент не может быть найден.Но .... Это должно произойти? Хотите ли вы, чтобы элемент вашего объекта был удален кем-то другим (предположительно, другим объектом того же типа)?Вероятно, нет, поскольку предполагается, что каждый объект «соответствует элементу».Это проблема с вашим дизайном?

Если бы я делал это , я бы, вероятно, хотел бы убедиться, что элемент моего объекта не может быть грубо удален.Одним из способов сделать это является использование общих указателей .Вместо хранения std::vector<another_type> в map, я мог бы рассмотреть сохранение std::vector<std::shared_ptr<another_type>>.В зависимости от того, что должно произойти при уничтожении объекта, я могу изменить это значение с shared_ptr на weak_ptr, чтобы статический контейнер не обслуживал данные для объектов, которые больше не существуют.В любом случае каждый объект может поддерживать свой собственный shared_ptr для своего элемента.Это обеспечивает быстрый доступ к элементу и гарантирует, что элемент не будет уничтожен до того, как объект будет.

Конечно, наиболее желательный подход будет зависеть от причины, по которой вам нужно хранить эти элементы в статическом контейнере.

Answer 2

Нельзя сохранить итератор для вектора в my_list, если изменяется размер my_list (за исключением случаев, когда вы резервируете все ранее).

Самый простой способ - сохранить ключ, а затем индекс ввектор, предполагая, что вы только отталкиваете новые элементы и никогда не удаляете старые.Лучшим будет итератор на карте с индексом.