使用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指針保持指向第七元件值（它是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; 

} 

輸出：

​​

雖然這後一種方案的工作，有是有代價的：我已經失去了我的矢量的緩存位置，因爲我存儲在指針它，而不是實際的對象。

有沒有一種方法來維護緩存的位置（例如：將我的實際對象存儲在向量中），並以某種方式管理指針來跟蹤其指向的值由於排序而四處移動的位置？或者從另一個角度來看，有沒有一種方法來實現指針向量的緩存局部性？從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); 

排序您的數據你會使用從data檢索值，並比較他們的自定義比較器功能排序indexes。記住：indexes可以更改，但data不應該！

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

Answer 2

只是一個想法：與其在矢量存儲std::string的，只是每個字符串的字符數組追加到std::vector<char>。

這將字符串緊緊包裝在內存中，改進的局部性甚至比std::string更好，同時對字符串進行了優化。如果字符串超過最大值，它也會給出更好的結果。大小爲小字符串優化。

對於排序，將每個字符串的索引和大小存儲在類似於Pubbys建議的第二個向量中。

當然這隻有在字符串長度不需要動態改變時纔有效。否則，你將不得不重建vector<char>。

#include <iostream> 
#include <algorithm> 
#include <vector> 
#include <utility> 
#include <string_view> 

using namespace std; 

using IndexAndSize = pair<size_t,size_t>; 

void push_and_index(vector<char>& v, vector<IndexAndSize>& vi, string_view s) 
{ 
    vi.emplace_back(v.size(), s.size()); 
    v.insert(end(v), begin(s), end(s)); 
} 

string_view make_string_view(vector<char> const& v, IndexAndSize is) 
{ 
    return { v.data() + is.first, is.second }; 
} 

int main() 
{ 
    vector<char> v; 
    vector<IndexAndSize> vi; 

    push_and_index(v, vi, "foo"); 
    push_and_index(v, vi, "bar"); 
    push_and_index(v, vi, "foobar"); 
    push_and_index(v, vi, "barfoo"); 

    sort(begin(vi), end(vi), [&](IndexAndSize a, IndexAndSize b) 
    { 
     return make_string_view(v, a) < make_string_view(v, b); 
    }); 

    for(IndexAndSize is : vi) 
    { 
     cout << make_string_view(v, is) << endl; 
    } 
} 

Live demo on Coliru.

注：C++ 17的string_view僅用於幫助排序和輸出，它不是這種想法至關重要。