Программа стала работать быстрее, когда Set был изменен на Vector ⇐ C++

[Anonymous]

//finding closest element
int closest(vector &s1, int x)
{
int dif = INT_MAX;
auto j = lower_bound(s1.begin(), s1.end(), x);
if(j == s1.end())
dif = min(dif, abs(*(--j) - x));
else if(j == s1.begin())
dif = min(dif, abs(*j - x));
else
{
dif = min(dif, abs(*j - x));
dif = min(dif, abs(*(--j) - x));
}
return dif;
}

void dfs(vector &G, vector &vis, int i, vector &s1 , vector &s2, int& dif1, int &dif2)
{
vis = 1;
dif1 = min(dif1, closest(s1, i));
dif2 = min(dif2, closest(s2, i));
stack stk;
stk.push(i);
while(!stk.empty())
{
int top = stk.top();
stk.pop();
for (auto &j : G[top])
{
if(vis[j] == 0)
{
vis[j] = 1;
stk.push(j);
dif1 = min(dif1, closest(s1, j));
dif2 = min(dif2, closest(s2, j));
}
}

}
}

int main()
{
// some code omitted
for (int i = 0; i < n; i++)
{
if(vis == 0)
{
int dif1 = INT_MAX;
int dif2 = INT_MAX;
dfs(G, vis, i, s1, s2, dif1, dif2);
ans = min(ans, dif1*1LL*dif1+dif2*1LL*dif2);
}
}

}


Это было решение проблемы теории графов, связанной со связностью.
Изначально s1 и s2 были наборами, полученными из другой части кода (здесь не актуально). Программа работала очень медленно в цикле внутри основной программы, как я заметил с помощью отладчика.
По прихоти я изменил наборы на векторные и отсортировал их после того, как они были получены. Чудом программа стала работать в 10 раз быстрее. Функция low_bound имеет одинаковую временную сложность для заданного и отсортированного вектора. Я не понимаю, почему это произошло. В худшем случае временная сложность — это VlogV+E в обоих случаях, верно? Это из-за какой-то оптимизации, сделанной компилятором, или я что-то упускаю?
Это был проблемный код. Я просто изменил set на вектор, вставил на push_back и отсортировал эти векторы.
#include
#define ll long long

using namespace std;

int closest(set &s1, int x)
{
int dif = INT_MAX;

auto j = lower_bound(s1.begin(), s1.end(), x);
if(j == s1.end())
dif = min(dif, abs(*(--j) - x));
else if(j == s1.begin())
dif = min(dif, abs(*j - x));
else
{
dif = min(dif, abs(*j - x));
dif = min(dif, abs(*(--j) - x));
}
return dif;
}

void dfs(vector &G, vector &vis, int i, set &s)
{
stack stk;
stk.push(i);
vis = 1;
s.insert(i);
while(!stk.empty())
{
int top = stk.top();
stk.pop();
for (auto &&j : G[top])
{
if(vis[j] == 0)
{
s.insert(j);
vis[j] = 1;
stk.push(j);
}
}

}

}

void dfs(vector &G, vector &vis, int i, set &s, set& s1, int& dif)
{
vis = 1;
s.insert(i);
dif = min(dif, closest(s1, i));
stack stk;
stk.push(i);
while(!stk.empty())
{
int top = stk.top();
stk.pop();
for (auto &&j : G[top])
{
if(vis[j] == 0)
{
s.insert(j);
vis[j] = 1;
stk.push(j);
dif = min(dif, closest(s1, j));
}
}

}
}

void dfs(vector &G, vector &vis, int i, set &s1 , set &s2, int& dif1, int &dif2)
{
vis = 1;
dif1 = min(dif1, closest(s1, i));
dif2 = min(dif2, closest(s2, i));
stack stk;
stk.push(i);
while(!stk.empty())
{
int top = stk.top();
stk.pop();
for (auto &j : G[top])
{
if(vis[j] == 0)
{
vis[j] = 1;
stk.push(j);
dif1 = min(dif1, closest(s1, j));
dif2 = min(dif2, closest(s2, j));
}
}

}
}

int main()
{
int t;
cin >> t;
while (t--)
{
int n, m;
cin >> n >> m;
vector G(n, vector());
for (int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
G[a-1].push_back(b-1);
G[b-1].push_back(a-1);
}
vector vis(n,0);
set s1;
dfs(G, vis, 0, s1);
if(s1.find(n-1) != s1.end())
{
cout

Подробнее здесь: https://stackoverflow.com/questions/785 ... -to-vector