C++使用std ::指針列表重新排列std :: vector元素

當我試圖寫出一個新的算法來重新對std :: vector中的元素進行排序時，我遇到了這個問題。基本的想法是，我有std :: list指向std :: vector的指點器，其方式如下：*list.begin() == vector[0],*(++list.begin()) == vector[1]等等。但是，對列表元素位置的任何修改會破壞映射。（包括附加指針）映射斷開時，列表的元素可以是隨機順序的，但它們仍然指向矢量上的正確元素。任務是重新排列向量中的元素以更正映射。C++使用std ::指針列表重新排列std :: vector元素

最簡單的方法來做到這一點（如何我現在已經做到了）：

創建新的空的std ::載體，並調整舊矢量的大小相等。
遍歷列表並從舊矢量讀取元素並將它們寫入新矢量。將指針設置爲指向新矢量的元素。
交換矢量並釋放舊的矢量。

不幸的是，只有當我需要更多的載體容量時，該方法纔有用。當包含元素的當前向量具有足夠的容量來存儲所有傳入元素時，效率很低。列表中的附加指針將指向不同矢量的storgate。簡單的方法適用於此，因爲它只從指針讀取。

所以，我想重新排列使用恆定內存量的「就地」向量。任何未指向當前矢量的storgate的指針都將移動到指向當前矢量的storgate中。元素是簡單的結構。（POD）我會嘗試發佈一個示例代碼，當我有時間的時候..

我該怎麼做才能做到這一點？我已經完成了基本想法，但我不確定是否可以用恆定的內存量進行重新排序。 PS：我很抱歉在帖子中可能有不好的語法和拼寫錯誤。我希望它仍然可讀。 :)

來源

2011-07-31 JATothrim

你需要做什麼？ –

這聽起來像是你的用例使用了不正確的數據結構。爲什麼不直接使用矢量？ – sirbrialliance

我必須將元素存儲在連續內存中。 – JATothrim

首先，爲什麼你有一個指針列表？您可能還需要將索引保存到矢量中，您可以將其計算爲std::distance(&v[0], *list_iter)。所以，讓我們先建立索引的矢量，但你可以輕鬆適應，要直接使用您的列表：

std::vector<T> v;  // your data 
std::list<T*> perm_list; // your given permutation list 
std::vector<size_t> perms; 

perms.reserve(v.size()); 
for (std::list<T*>::const_iterator it = perm_list.begin(), end = perm_list.end(); it != end; ++it) 
{ 
    perms.push_back(std::distance(&v[0], *it)); 
}

（有可能是使用std::transform和std::bind，或lambda表達式，要做到這一點，某行的路。）

現在要做的工作。我們簡單地用置換的週期分解，我們修改perms載體，因爲我們走：

std::set<size_t> done; 

for (size_t i = 0; i < perms.size(); while(done.count(++i)) {}) 
{ 
    T tmp1 = v[i]; 
    for (size_t j = perms[i]; j != i; j = perms[j]) 
    { 
    T tmp2 = v[j]; 
    v[j] = tmp1; 
    tmp1 = tmp2; 

    done.insert(j); 
    } 
    v[i] = tmp1; 
}

我使用的輔助設置done跟蹤哪些指數已經被置換。在C++ 0x中，您可以在任何地方添加std::move，以便使用可移動容器進行此項工作。

來源

2011-07-31 23:42:58

謝謝你的回答。我幾乎可以確定這個問題：「爲什麼你有指點員名單」，會被問到。:)我真正使用的列表元素不僅僅是指針，而且我使用特殊的成員函數來獲得指向矢量storgate的指針，所以我簡化了這個例子。如果某些'perm_list'元素沒有指向'v'的storgate，它會工作嗎？此外，此方法使用（暫時但仍然）比我當前版本多兩倍的內存。 'perms'可以按照你的說法選擇，但似乎我不得不使用'set' – JATothrim

你需要以某種方式從你的列表中獲得向量中的索引，但是我確信你可以找到一種方法來做到這一點。如果您將自己的排列預處理爲循環，然後將每個循環的上述算法分開應用，您可以在沒有設置的情況下離開 - 如您所見，該設置僅用於提高「i」，如果您工作循環循環。 –

C++使用std ::指針列表重新排列std :: vector元素

回答

相關問題