使用unique_ptr缓存局部性

Question

我有一个自定义类的向量(例如std :: string).

向量很大,我经常迭代,所以我依赖缓存局部性.

我还有一个指向其中一个向量元素的原始指针.

现在就是诀窍:

向量是不时排序的,因此原始指针会松散实际的指向元素值,并指向一些随机元素值.

这是一个说明相同的例子:

#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),我想出了以下解决方案(指针向量):

#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

虽然后一个解决方案有效,但是有一个代价:我丢失了向量的缓存局部性,因为我在其中存储了指针,而不是实际的对象.

有没有办法维护缓存局部性(例如:将我的实际对象存储在向量中),并以某种方式管理rs指针以跟踪由于排序而其指向值四处漂移的位置？或者从另一个角度来看,有没有办法用指针向量实现缓存局部性？

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

要indexes使用自定义比较器函数对数据进行排序,该函数会从中检索值data并对其进行比较.记住:indexes可以改变,但data不应该改变!

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