Russian Qt Forum

#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;
}