按索引排列向量

我有两个向量：向量和索引向量。我怎样才能让矢量由索引矢量来排列？像：按索引排列向量

Indexes    5 0 2 1 3 4 
Values     a b c d e f 
Values after operation b d c e f a

索引矢量将始终包含范围[0, n)和每个索引只有一次。
我需要执行此操作，因为代码将在低内存的设备上运行。
我如何在C++中做到这一点？我可以使用C++ 11

来源

2011-11-22 Dani

运行（n）的时间，没有任何error.Check它你考虑[此相关问题（http://stackoverflow.com/q/236172/1025391）？ – moooeeeep

std::vector<int> indices = { 5, 0, 2, 1, 3, 4}; 
std::vector<char> values = {'a', 'b', 'c', 'd', 'e', 'f'}; 

for(size_t n = 0; n < indices.size(); ++n) 
{ 
    while(indices[n] != n) 
    { 
     std::swap(values[n], values[indices[n]]); 
     std::swap(indices[n], indices[indices[n]]); 
    } 
}

编辑：

我想这应该是O（n）的，任何人不同意？

来源

2011-11-22 19:28:39 ronag

你可以对矢量排序，你的比较操作应该比较指数。当然，当移动数据时，您也必须移动索引。

最后，您的指数将只是0，1，...（n-1），数据将在相应的位置。

由于实现注意：您可以存储的值，并在结构指数一起：

struct SortEntry 
{ 
    Data value; 
    size_t index; 
};

，并定义比较操作仅在指数看：

bool operator< (const SortEntry& lhs, const SortEntry& rhs) 
{ 
    return lhs.index < rhs.index; 
}

来源

2011-11-22 19:12:30 Vlad

有一个问题，比较运算符只给出值，而不是它们的索引 – Dani

但是然后我需要将数据复制到排序条目 – Dani

那么，你有两种方法：（1）使你的数据在适当的结构中一开始; （2）让你的代码只对索引进行排序，当将索引作为排序过程的一部分移动时，也要移动适当的数据。 – Vlad

for(int i=0;i<=indexes.size();++i) 
for(int j=i+1;j<=indexes.size();++j) 
      if(indexes[i] > indexes[j]) 
         swap(indexes[i],indexes[j]), 
         swap(values[i],values[j]);

这是为O （N 2）的复杂性，但应该适用于小数值。

你也能传递一个比较函数的C++ STL排序功能，如果你想O（N * logN）的

来源

2011-11-22 19:22:38 Cristy

由于您知道您的索引数组是[0, N)的置换，因此可以通过逐周期工作，以线性时间和就地（加上一个临时）完成此操作。事情是这样的：

size_t indices[N]; 
data_t values[N]; 

for (size_t pos = 0; pos < N; ++pos) // \ 
{          // } this loops _over_ cycles 
    if (indices[pos] == pos) continue; ///

    size_t i = pos; 
    const data_t tmp = values[pos]; 

    while (true)      // --> this loops _through_ one cycle 
    { 
    const size_t next = indices[i]; 
    indices[i] = i; 
    values[i] = values[next]; 

    if (next == pos) break; 
    i = next; 
    } 

    values[i] = tmp; 
}

这个实现的优点在每个时候，我们只需要使用一个临时变量每循环一次使用swap。

如果数据类型是仅移动的，如果所有分配都被std::move()包围，这仍然有效。

来源

2011-11-22 19:35:18

该解决方案运行在O（n）的时间：

int tmp; 
for(int i = 0; i < n; i++) 
    while(indexes[i] != i){ 
    swap(values[i], values[indexes[i]]); 
    tmp = indexes[i]; 
    swap(indexes[i], indexes[tmp]); 
    }

来源

2011-11-22 19:35:34

你能证明它的'O（n）'吗？ – Dani

这将在O于ideone

int main(int argc, char *argv[]) 
{ 
int indexes[6]={2,3,5,1,0,4}; 
char values[6]={'a','b','c','d','e','f'}; 
int result[sizeof(indexes)/4];   //creating array of size indexes or values 
int a,i; 
for(i=0;i<(sizeof(indexes)/4);i++) 
{ 
    a=indexes[i];      //saving the index value at i of array indexes 
    result[a]=values[i];    //saving the result in result array 
} 
for (i=0;i<(sizeof(indexes)/4);i++) 
    printf("%c",result[i]);    //printing the result 
    system("PAUSE"); 
    return 0; 
}

来源

2011-11-23 06:57:46

按索引排列向量

回答

相关问题