Objasnite razlike između struktura podataka std::map i std::vector u C++ u pogledu njihove upotrebe i interne implementacije.

std::vector — это динамический массив, который хранит элементы в непрерывной области памяти. Он обеспечивает быстрый доступ по индексу (O(1)) и эффективное добавление элементов в конец. Однако вставка или удаление элементов в середине или начале вектора может быть дорогой операцией (O(n)), так как требует сдвига элементов.

std::map — это ассоциативный контейнер, реализованный обычно как сбалансированное дерево (например, красно-чёрное дерево). Он хранит пары ключ-значение, отсортированные по ключу. Доступ к элементам происходит по ключу за логарифмическое время (O(log n)). Вставка и удаление также имеют сложность O(log n). В отличие от vector, map не хранит элементы в непрерывной памяти.

Итог:

• Используйте std::vector, когда важен быстрый индексированный доступ и порядок элементов, а количество элементов меняется нечасто или добавление происходит в конец.
• Используйте std::map, когда нужно хранить пары ключ-значение с быстрым поиском по ключу и упорядочиванием по ключу.