Как найти объединение вектора n?
У меня есть двумерный вектор гипер-граней, а также список смежности. Я должен найти союз hyperEdges[i].size() векторы, но я могу найти только объединение только двух векторов. Какое улучшение я могу внести в мой код ниже, чтобы сделать это?
Я хочу сохранить объединение во вновь объявленном 2-D векторе connectedEdges
void find_union()
{
connectedEdges.resize(nEdges+1);
for(int i = 1; i <= nEdges; i++)
{
vector<int>::iterator it;
connectedEdges[i].resize(nEdges+1);
for(int j = 1; j < hyperEdges[i].size()-1; j++)
{
int p = hyperEdges[i][j-1];
int q= hyperEdges[i][j];
it = set_union(adjL[p].begin(), adjL[p].end(),adjL[q].begin(),adjL[q].end(), connectedEdges[i].begin());
connectedEdges[i].resize(it-connectedEdges[i].begin());
}
}
}
Пример :
{1,2,4,6,8}
{1,2,3,5,6}
{1,4,7,13,15}
Союз этих трех комплектов должен быть {1,2,3,4,5,6,7,8,13,15}
Но моя программа возвращается {1,2,3,4,5,6,8}
Решение
Если у вас много векторов, я бы посоветовал вставить их содержимое в один std::set а затем сбросить его обратно в std::vector,
Что-то вроде того:
std::vector<std::vector<int>> src = ...;
std::set<int> all;
for(int i = 0; i < src.size(); i++) {
all.insert(src[i].begin(), src[i].end());
}
std::vector<int> result(all.begin(), all.end());
Другие решения
Вы также можете запустить std::set_union со всеми соседними векторами (убедитесь, что они отсортированы), наращивая результат по шагам, как в следующем примере:
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
int main()
{
std::vector<std::vector<int>> v{{1, 1, 2}, {1, 1, 1}, {1, 5, 6, 7}};
std::vector<int> result, tmp;
for(auto&& elem: v)
{
std::set_union(elem.begin(), elem.end(),
result.begin(), result.end(),
std::back_inserter(tmp));
result = std::move(tmp);
tmp.clear(); // see http://stackoverflow.com/q/9168823/3093378
}
// in case you want to remove duplicates
result.erase(std::unique(result.begin(), result.end()), result.end());
for(auto&& elem: result)
std::cout << elem << " "; // 1 2 5 6 7
}
Вы можете переместить их в set и отступить как anxieux предлагает. Или вы можете просто вручную перебрать их все:
#include <iostream>
#include <memory>
#include <vector>
#include <algorithm>
std::vector<int> find_union(const std::vector<std::vector<int>>& vecs)
{
using iter = std::vector<int>::const_iterator;
using pr = std::pair<iter, iter>;
// construct pairs of iterators into each vector
// we will iterate over all of these simultaneously
std::vector<pr> iter_pairs;
std::vector<int> results;
iter_pairs.reserve(vecs.size());
for (auto& v : vecs) {
iter_pairs.emplace_back(v.begin(), v.end());
}
while (!iter_pairs.empty()) {
// pick the next smallest element
int m = *std::min_element(iter_pairs.begin(), iter_pairs.end(), [](const pr& a, const pr& b){
return *a.first < *b.first;
})->first;
// add it to our results
results.push_back(m);
// any vector that contained this element should be advanced
// if we're done with that vector, remove it
iter_pairs.erase(
std::remove_if(iter_pairs.begin(), iter_pairs.end(), [=](pr& p){
if (*p.first == m) {
++p.first;
return p.first == p.second;
}
return false;
}),
iter_pairs.end()
);
}
return results;
}
int main() {
for (int i : find_union({{1,2,3}, {1,2,4}, {3,5,42}})) {
std::cout << i << ' '; // prints 1 2 3 4 5 42
}
std::cout << std::endl;
}