Как преобразовать std::set в std::array?
У меня есть std::set, и мне нужно преобразовать его в std::array. Порядок элементов не имеет значения.
Обратное преобразование кажется простым, потому что я могу просто сделать:
std::array<T> array;
std::set<T> set(array.begin(), array.end());
Но, к сожалению, у std::array нет такого конструктора, поэтому я не могу:
std::set<T> set;
std::array<T> array(set.begin(), set.end());
Каков правильный способ такого преобразования?
std::array должен знать свой размер во время компиляции, а std::set имеет динамический размер. Так что это на самом деле невозможно, если вы не знаете, что размер фиксирован.
Нет std::array<T>, есть только std::array<T,N>. Размер должен быть известен во время компиляции.
Я был уверен, что мне нужен массив, потому что я думал, что вектор имеет сложность доступа O(n). Я всегда рассматриваю его по ошибке как связанный список. Спасибо вам всем.
Не думайте, что набор быстрее, чем вектор для поиска элемента. Это для больших размеров, но не для маленьких. Для простого обхода вектор всегда быстрее.
@doug «Для простого обхода вектор всегда быстрее». обход вектора примерно такой же быстрый, как и обход контейнера, но это не обязательно делает его быстрее, чем что-то вроде набора.
@George Хотя можно спроектировать набор таким образом, чтобы все элементы хранились непрерывно, следовательно, их можно было бы перемещать так же быстро, как вектор, это было бы сделано при существенном увеличении затрат на поиск элементов. Это был бы плохой дизайн набора, так как быстрый поиск является основной причиной набора.
Ответы 1
Как упоминалось в комментариях выше, std::array не подходит для этого, так как размер должен быть известен во время компиляции. std::vector является подходящей заменой.
Вот один из способов заполнить vector из set. Должно быть просто преобразовать это в шаблон. Обратите внимание на использование reserve для эффективности:
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
int main()
{
std::set <int> s = { 1, 2, 3, 4, 5 };
std::vector <int> v;
v.reserve (s.size ());
std::copy (s.begin (), s.end (), std::back_inserter (v));
for (auto i : v)
std::cout << i << '\n';
}
Я бы порекомендовал вам объяснить, почему array не подходит в данном случае.
@ Л.Ф. Хорошо, готово (я этого не делал, потому что это уже обсуждалось в комментариях к исходному вопросу).
Вы можете сократить его до одной строки: std::vector <int> v(s.begin(), s.end());.
@HolyBlackCat Я нашел лучший способ (чем мой оригинал) с помощью std::copy. Я полагаю, что это самый эффективный способ сделать это, если набор большой, потому что вы можете вызвать reserve перед заполнением массива.
Однострочник должен быть еще быстрее.
@HolyBlackCat С чего бы это?
@PaulSanders Неважно, я профилировал его, и мое предложение оказалось примерно в два раза медленнее. С++ странный, я исправляюсь.
@HolyBlackCat Я считаю, что призыв к reserve ускоряет процесс. Без этого вектор должен постоянно изменяться (обычно экспоненциально) по мере добавления новых элементов. Чем больше набор, тем больше это будет вам стоить.
@PaulSanders Я на секунду забыл, что вы не можете получить размер set из его итераторов begin и end в O (1). Вы, вероятно, правы, но я получил некоторые странные результаты профилирования здесь: quick-bench.com/OuvJmIVWxFASUenLw0E4KS92WDQ
@HolyBlackCat Интересно. Я сделал две вещи: (1) закомментировал вызовы reserve, что, к моему удивлению, не имело никакого значения, и (2) добавил контрольный вызов push_back в цикле, который был таким же быстрым, как вызов std::copy. Иди разберись. Я также попробовал это с clang и получил те же результаты. Я думаю, это просто показывает, что не следует делать предположений, когда важна производительность. Результаты с gcc здесь.
Вы уверены, что хотите
std::array, а неstd::vector?