C++ (Qt)// строка + место вставки + индексusing TLine = std::tuple<QString, int, int>;inline QString & Name( TLine & line ) { return std::get<0>(line); }inline int & InsP( TLine & line ) { return std::get<1>(line); }inline int & Index( TLine & line ) { return std::get<2>(line); } // исходный массив и вставляемыйstd::vector<TLine> src, arrived;...// сортируем вставляемыхfor (auto & a : arrived) InsP(a) = -1;std::sort(arrived.begin(), arrived.end()); // для каждой строки исходного обновляем места вставки всех // вставляемых с тем же первым ключомfor (size_t i = 0; i < src.size(); ++i) { auto it = std::lower_bound(arrived.begin(), arrived.end(), src[i]); for (; it != arrived.end(); ++it) { if (Name(src[i]) != Name(*it))) break; if (Index(*it) >= Index(src[i])) InsP(*it) = i; }}
C++ (Qt)std::sort(arrived.begin(), arrived.end(), [](const TLine & a, const TLine & b) -> bool{ return InsP(a) < InsP(b); }); int offset = 0;for (const auto & a : arrived) { if (insP(a) < 0) src.push_back(a); else { int insP = InsP(a) + offset; assert(Name(a) == Name(insP)); if (Index(src[index] == Index(a)) // override src[index] = a; else { src.insert(src.begin() + insP + 1, a); // insert after ++offset; } }}
#include <algorithm>#include <iostream>#include <optional>#include <string>#include <vector>#include <unordered_map>#include <assert.h>int main(int argc, char *argv[]){ struct Line { std::string name; std::optional<int> index; }; using Lines = std::vector<Line>; Lines source{ {"sphere", 1}, {"cube", 1}, {"cube", 3}, {"sphere", 2}, {"sphere", 5}, }; Lines arrived{ {"sphere", 1}, {"cube", 2}, {"cube"}, {"cube"}, {"sphere", 1}, {"sphere", 5000}, }; // usually, LinesInnerHash contains exactly 1 element in the vector => so we can use // QVarLengthArray<Line, 1> here to avoid allocations. The only case when we need multiple // elements is to store linex with no index assigned, i.e. when key is std::nullopt using LinesInnerHash = std::unordered_map<std::optional<int>, Lines>; using LinesHash = std::unordered_map<std::string, LinesInnerHash>; // first, divide lines for by their name, O(N), N == source.size() LinesHash sourceHash; for (auto line: source) { assert(line.index); // source array should not contain unindexed elements sourceHash[line.name][line.index] = {line}; } LinesHash arrivedHash; for (auto line: arrived) { // O(K), K == arrived.size() // arrivedHash[line.name][std::nullopt] will contain all unindexed elements arrivedHash[line.name][line.index].push_back(line); } // now, we need to index unindexed lines for (auto &item: arrivedHash) { // totally ~O(K) ? auto &innerHash = item.second; int index = 1; // extract unindexed lines from the hash Lines unindexedLines(std::move(innerHash[std::nullopt])); innerHash.erase(std::nullopt); for (auto &line: unindexedLines) { // find first free index while (innerHash.find(index) != innerHash.end()) index++; line.index = index; // update line innerHash[index] = {line}; // and insert it with the new index index++; // not necessary, small optimisation to avoid extra find() call } } for (const auto &item: arrivedHash) { // O(K) auto &sourceInnerHash = sourceHash[item.first]; auto &arrivedInnerHash = item.second; for (const auto &subItem : arrivedInnerHash) { // if we use unordered_map as an inner container, this will be simply sourceInnerHash[subItem.first] = std::move(subItem.second); } } Lines result; for (const auto &item: sourceHash) { // O(K) auto &innerHash = item.second; for (const auto &innerItem: innerHash) result.push_back(innerItem.second.front()); } for (const auto &line: result) { std::cout << line.name << " " << *line.index << std::endl; } return 0;}
#include <algorithm>#include <iostream>#include <optional>#include <string>#include <vector>#include <unordered_map>#include <assert.h>struct Line { std::string name; std::string payload; std::optional<int> index;};using Lines = std::vector<Line>;void logarithmic(const Lines &source, const Lines &arrived){ using LinesHash = std::unordered_map<std::string, Lines>; // first, divide lines for by their name, O(N), N == source.size() LinesHash hash; for (auto line: arrived) { hash[line.name].push_back(line); } for (auto line: source) { assert(line.index); // source array should not contain unindexed elements hash[line.name].push_back(line); } Lines result; for (auto &item: hash) { auto &lines = item.second; auto lessThan = [](const Line &lhs, const Line &rhs) { // std::nullopt should be last if (lhs.index && rhs.index) return *lhs.index < *rhs.index; if (!lhs.index && !rhs.index) return false; return lhs.index && !rhs.index; }; std::stable_sort(lines.begin(), lines.end(), lessThan); // N * log(N) // find position of the last existing element and the number of elements const auto noIndex = [](const auto &line) { return !line.index; }; auto mid = std::find_if(lines.begin(), lines.end(), noIndex); // O(N) const auto unindexedCount = std::distance(mid, lines.end()); // remove duplicates between the first existing element and the last one // this effectively implements "override" logic const auto equals = [](const auto &lhs, const auto &rhs) { return lhs.index == rhs.index; }; const auto newEnd = std::unique(lines.begin(), mid, equals); // O(N) lines.erase(newEnd, mid); // O(N) Lines indexedLines; indexedLines.reserve(lines.size()); // assign indexes to elements in the [mid..end) range mid = lines.end() - unindexedCount; // erase invalidates iterator, re-assign it int index = 1; auto it = lines.begin(); for (auto jt = mid; it != mid || jt != lines.end(); ) { // O(N) if (jt == lines.end() || it->index == index) { indexedLines.push_back(*it); ++it; } else { jt->index = index; indexedLines.push_back(*jt); ++jt; } ++index; } // add current chunk to the result result.insert(result.end(), indexedLines.begin(), indexedLines.end()); // O(N) } for (const auto &line: result) { std::cout << line.name << " " << line.payload; if (line.index) std::cout << " " << *line.index; std::cout << std::endl; }}int main(int argc, char *argv[]){ Lines source{ {"sphere", "old", 1}, {"cube", "old", 1}, {"cube", "old", 3}, {"sphere", "old", 2}, {"sphere", "old", 5}, }; Lines arrived{ {"sphere", "new", 1}, {"cube", "new", 2}, {"cube", "new"}, {"cube", "new"}, {"sphere", "new", 4}, {"sphere", "new"}, {"sphere", "new", 5000}, }; logarithmic(source, arrived); return 0;}
