c++ - 使用 unique_ptr 缓存位置

Question

我有一个自定义类的 vector (例如 std::string)。

vector 很大，我经常迭代，所以我依赖缓存局部性。

我还有一个指向 vector 元素之一的原始指针。

现在是诀窍:

vector 会不时排序，因此原始指针会丢失实际指向的元素值，并将指向一些随机元素值。

下面是一个例子来说明这一点:

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <memory>

using namespace std;

int main()
{

    vector<string> v = {"9","3", "8", "7", "6", "5", "1", "4", "2"};

    string* rs = &v[7]; //point to the 7th element

    for (size_t i = 0; i < v.size(); ++i)
        cerr << v[i];
    cerr << endl;
    cerr << "Referenced string: " << rs->c_str() << endl;

    cerr << "Sort ..." << endl;
    sort(v.begin(), v.end(), [](const string& a, const string& b)
    {
        if (a < b)
            return true;
        else
            return false;
    }
    );

    for (size_t i = 0; i < v.size(); ++i)
        cerr << v[i];
    cerr << endl;
    cerr << "Referenced string: " << rs->c_str() << endl;

    cin.get();
    return 0;

}

输出:

938765142
Referenced string before sort : 4
Sort ...
123456789
Referenced string after sort : 8

因为我希望 rs 指针即使在排序后也能继续指向第 7 个元素值(即 4)，所以我想出了以下解决方案(指针 vector ):

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <memory>

using namespace std;

int main()
{


    vector<unique_ptr<string>> v;
    v.resize(9);
    v[0] = make_unique<string>("9");
    v[1] = make_unique<string>("3");
    v[2] = make_unique<string>("8");
    v[3] = make_unique<string>("7");
    v[4] = make_unique<string>("6");
    v[5] = make_unique<string>("5");
    v[6] = make_unique<string>("1");
    v[7] = make_unique<string>("4");
    v[8] = make_unique<string>("2");

    string* rs = v[7].get();        

    for (size_t i = 0; i < v.size(); ++i)
    cerr << v[i]->c_str();
    cerr << endl;
    cerr << "Referenced string before sort: " << rs->c_str() << endl;


    cerr << "Sort ..." << endl;
    sort(v.begin(), v.end(), [](const unique_ptr<string>& a, const unique_ptr<string>& b)
    {
    if (*a < *b)
    return true;
    else
    return false;
    }
    );



    for (size_t i = 0; i < v.size(); ++i)
    cerr << v[i]->c_str();
    cerr << endl;
    cerr << "Referenced string after sort: " << rs->c_str() << endl;


    cin.get();
    return 0;

}

输出:

938765142
Referenced string before sort: 4
Sort ...
123456789
Referenced string after sort: 4

虽然后一种解决方案有效，但要付出代价:我丢失了 vector 的缓存局部性，因为我在其中存储了指针，而不是实际对象。

有没有办法保持缓存局部性(例如:将我的实际对象存储在 vector 中)，并以某种方式管理 rs 指针以跟踪其指针值因排序而四处游荡的位置？或者从另一个角度，有没有办法用指针 vector 实现缓存局部性？

来自 Pubby 的解决方案，谢谢!

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <memory>

using namespace std;

int main()
{

    vector<string> data = { "d","e", "f", "g", "i", "b", "c", "a", "h" };
    vector<int> indexes = {0,1,2,3,4,5,6,7,8};


    int si = 6;

    for (size_t i = 0; i < indexes.size(); ++i)
        cerr << indexes[i];
    cerr << endl;
    for (size_t i = 0; i < indexes.size(); ++i)
        cerr << data[indexes[i]];
    cerr << endl;
    cerr << "Referenced string before sort: " << data[si] << endl;

    cerr << "Sort ..." << endl;
    sort(indexes.begin(), indexes.end(), [&](const int a, const int b)
    {
        return data[a] < data[b];
    }
    );

    for (size_t i = 0; i < indexes.size(); ++i)
        cerr << indexes[i];
    cerr << endl;
    for (size_t i = 0; i < indexes.size(); ++i)
        cerr << data[indexes[i]];
    cerr << endl;
    cerr << "Referenced string after sort: " << data[si] << endl;

    cin.get();
    return 0;

}

Answer 1

您可以通过将字符串存储在一个不会改变的 vector 中来增加局部性，然后存储一个指向这些字符串的指针/索引 vector 。

像这样:

vector<string> data = {"9","3", "8", "7", "6", "5", "1", "4", "2"};
vector<unsigned> indexes(data.size());
std::iota(indexes.begin(), indexes.end(), 0u);

要对数据进行排序，您需要使用自定义比较器函数对索引 进行排序，该函数从data 中检索值并进行比较。请记住:indexes 可以更改，但 data 不应该!

sort(indexes.begin(), indexes.end(), [&](unsigned a, unsigned b)
    {
        return data[a] < data[b];
    });