合并无额外内存的向量

我遇到了两个向量合并的代码段，其中一个向量的元素在重复情况下受到青睐：

std::vector<String> fields1 = fieldSource1.get();
std::vector<String> fields2 = fieldSource2.get();
// original
fields1.insert(std::end(fields1), std::begin(fields2), std::end(fields2));
std::stable_sort(std::begin(fields1), std::end(fields1));
fields1.erase(std::unique(std::begin(fields1), std::end(fields1)), std::end(fields1));
return fields1;

鉴于字符串在它们各自的向量中是唯一的，并且输出向量中字符串的顺序是无关紧要的，我认为我可以使这个算法更高效。

我想避免额外的内存分配std :: set_union（）和std :: set_diff（）。

（由于在调整大小期间迭代器失效，直接将std :: set_diff插入到原始矢量不是一个选项）

我结束了这一点，这是std :: set_diff与一个迭代器替换为索引：

std::sort(std::begin(fields1), std::end(fields1));
std::sort(std::begin(fields2), std::end(fields2));
// Initialize iterators by index in case of resizing
size_t index = 0;
size_t end = std::size(fields1);
std::remove_copy_if(std::begin(fields2), std::end(fields2), std::back_inserter(fields1),
[&fields1, &index, end](String field)->bool{
    auto begin = std::begin(fields1);
    found = std::lower_bound(begin+index, begin+end, field);
    index = std::distance(begin, found);
    return (*found) == field;
});
return fields1;

我的问题是：我可以让这个合并操作更有效率吗？ 如果没有，我可以让它更具可读性吗？

---

如果要将它们保持在已排序或可合并的状态，将一串字符串表示为向量是无效的。 最好使用另一个容器，比如std :: set或std :: unordered_set，它具有更好的性能保证。

请注意，任何尝试对字符串进行排序的解决方案都可能会进一步片段化内存，并且比首先创建正确的数据结构的内存压力增加更多。

如果您必须将它们保留为字符串向量，那么您可以考虑创建一个散列表，其中包含在每个点上看到的所有字符串，然后只允许插入其哈希尚未显示的字符串。 如果您有大量重复项，则此方法可能比独立排列每个列表更有效。

typedef std::size_t hash_type;
typedef std::string value_type;
typedef std::vector< value_type > values_type;
typedef std::hash< value_type > value_hash_type;
typedef std::unordered_set< hash_type > hash_set_type;

bool is_new_hash(hash_set_type &hash_set,
    const hash_type one_hash
    )
{
    if (hash_set.find(one_hash) == hash_set.end())
    {
        hash_set.insert(one_hash);
        return true;
    }
    return false;
}

int main()
{
    values_type str1, str2, dest;
    str1.push_back("c");
    str1.push_back("a");
    str1.push_back("b");

    str2.push_back("c");
    str2.push_back("d");

    hash_set_type hash_set;
    value_hash_type value_hash;

    for (auto &s : str1)
    {
        if (is_new_hash( hash_set, value_hash( s ) ))
            dest.push_back(s);
    }
    for (auto &s : str2)
    {
        if (is_new_hash(hash_set, value_hash(s)))
            dest.push_back(s);
    }
    std::sort(dest.begin(), dest.end());
}

链接地址: http://www.djcxy.com/p/79199.html

上一篇: Merging vectors without extra memory

下一篇: Change size of vector without destroying reserved elements