如何将 std::vector 的某些元素移动到向量中的新索引?
How to Move certain elements of std::vector to a new index within the vector?
我正在移植一些旧的手工数组处理 类 我写信给现在使用 std 库容器。我在移植时遇到问题的一种方法是我称之为 "ChangeRecordOrder" 的方法,因为没有更好的术语。我需要一个标准库替换。
它的定义是:
template <class T>
void ChangeRecordOrder( std::vector<T> IN OUT &inputVector,
uint newInsertIndex,
std::vector<uint> IN const &indexesToMoveToNewIndex );
例如(伪代码):
MyVector<uint> = {0,10,20,30,40,50,60,70,80,90}
IndexesToMove = {2,4}
NewIndex = 6
After call to ChangeRecordOrder( MyVector, NewIndex, IndexesToMove ):
MyVector<uint> == {0,10,30,50,20,40,60,70,80,90}
请注意,2 和 4(20 和 40)处的元素已移动到原始向量的索引 6(在 60 之前)。
当然我想就地做这件事,而不是使用另一个临时向量。我也不介意在调用之前需要对 IndexesToMove 向量进行排序的要求。
我找不到为此的标准库算法。我之前在原始内存上使用的算法没有使用 c++ 移动语义。
谢谢!
您正在寻找 std::rotate
。
#include<vector>
#include<iostream>
#include<algorithm>
int main() {
std::vector<int> values{0, 10, 20, 30, 40, 50, 60, 70, 80, 90};
std::vector<size_t> indexes_to_move{2,4};
size_t destination_index = 6;
if(destination_index > values.size()) throw std::runtime_error("Come on, bro.");
for(auto const& val : values) std::cout << val << ',';
std::cout << std::endl;
for(size_t _index = 0; _index < indexes_to_move.size(); _index++) {
size_t index = indexes_to_move[indexes_to_move.size() - _index - 1]; //We need to iterate in reverse.
if(index >= values.size()) throw std::runtime_error("We dun goofed.");
if(index >= destination_index) throw std::runtime_error("We goofed in a different way.");
std::rotate(values.begin() + index, values.begin() + index + 1, values.begin() + destination_index);
destination_index--;
}
for(auto const& val : values) std::cout << val << ',';
std::cout << std::endl;
return 0;
}
根据ideone.com,这会产生以下输出:
0,10,20,30,40,50,60,70,80,90,
0,10,30,50,20,40,60,70,80,90,
这是一个解决方案,最多移动每个未选中的元素一次:
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> values{0, 10, 20, 30, 40, 50, 60, 70, 80, 90};
vector<size_t> IndexesToMove{2,4};
size_t NewIndex = 6;
//check that your indices are sorted, non-empty, in the correct range, etc.
// move one element in front of the next element to move
// then move those two elements in front of the next element to move
// ...
auto it_next = values.begin() + IndexesToMove.front();
for(size_t i = 0; i < IndexesToMove.size() -1; i++) {
auto it_first = it_next - i;
it_next = values.begin() + IndexesToMove[i+1];
rotate(it_first, it_first + i + 1 , it_next);
}
// move the collected elements at the target position
rotate(it_next - IndexesToMove.size() + 1, it_next + 1, values.begin() + NewIndex);
}
可读性固然不太好。可以通过更好的变量名 and/or 将其中一些放入单独的函数中
来改进它
以上两个示例在输入不同时出现问题(如上所述)。我制定了处理不同情况的算法,并通过了我的单元测试。它可能会提高速度。
template <class CONTAINER_TYPE>
void ChangeRecordOrder( CONTAINER_TYPE IN OUT &values,
uint newIndex,
std::vector<uint> IN const &indexesToMove )
{
// Make a copy of the indexesToMove as we need to do fixups to them in certain cases
std::vector<uint> temporaryIndexes = indexesToMove;
for ( uint i=0; i<temporaryIndexes.size(); i++ )
{
uint indexToMove = temporaryIndexes[i];
if ( indexToMove < newIndex )
{
uint leftIndex = indexToMove;
uint rightIndex = newIndex -1;
uint newFirst = leftIndex + 1;
std::rotate( values.begin() + leftIndex, values.begin() + newFirst, values.begin() + rightIndex +1);
// fix up indexes
for( uint j=i+1; j<temporaryIndexes.size(); j++ )
{
uint &futureIndex = temporaryIndexes[j];
if ( futureIndex > leftIndex && futureIndex <=rightIndex )
--futureIndex;
}
}
else if ( indexToMove > newIndex )
{
uint leftIndex = newIndex;
uint rightIndex = indexToMove;
uint newFirst = indexToMove;
std::rotate( values.begin() + leftIndex, values.begin() + newFirst, values.begin() + rightIndex +1);
// fix up indexes
for( uint j=i+1; j<temporaryIndexes.size(); j++ )
{
uint &futureIndex = temporaryIndexes[j];
if ( futureIndex > leftIndex && futureIndex <=rightIndex )
++futureIndex;
}
++newIndex;
}
}
}
template <typename t> void move(std::vector<t>& v, size_t oldIndex, size_t newIndex)
{
if (oldIndex > newIndex)
std::rotate(v.rend() - oldIndex - 1, v.rend() - oldIndex, v.rend() - newIndex);
else
std::rotate(v.begin() + oldIndex, v.begin() + oldIndex + 1, v.begin() + newIndex + 1);
}
测试:https://coliru.stacked-crooked.com/a/5c31007000b9eeba
int main()
{
std::vector<int> v{ 3, 4, 5, 6, 7, 8, 9 };
move(v, 1, 4);
move(v, 4, 1);
move(v, 3, 3);
}
输出:
move 1 to 4: 3 [4] 5 6 7 8 9
result: 3 5 6 7 [4] 8 9
move 4 to 1: 3 5 6 7 [4] 8 9
result: 3 [4] 5 6 7 8 9
move 3 to 3: 3 4 5 [6] 7 8 9
result: 3 4 5 [6] 7 8 9
我正在移植一些旧的手工数组处理 类 我写信给现在使用 std 库容器。我在移植时遇到问题的一种方法是我称之为 "ChangeRecordOrder" 的方法,因为没有更好的术语。我需要一个标准库替换。
它的定义是:
template <class T>
void ChangeRecordOrder( std::vector<T> IN OUT &inputVector,
uint newInsertIndex,
std::vector<uint> IN const &indexesToMoveToNewIndex );
例如(伪代码):
MyVector<uint> = {0,10,20,30,40,50,60,70,80,90}
IndexesToMove = {2,4}
NewIndex = 6
After call to ChangeRecordOrder( MyVector, NewIndex, IndexesToMove ):
MyVector<uint> == {0,10,30,50,20,40,60,70,80,90}
请注意,2 和 4(20 和 40)处的元素已移动到原始向量的索引 6(在 60 之前)。
当然我想就地做这件事,而不是使用另一个临时向量。我也不介意在调用之前需要对 IndexesToMove 向量进行排序的要求。
我找不到为此的标准库算法。我之前在原始内存上使用的算法没有使用 c++ 移动语义。
谢谢!
您正在寻找 std::rotate
。
#include<vector>
#include<iostream>
#include<algorithm>
int main() {
std::vector<int> values{0, 10, 20, 30, 40, 50, 60, 70, 80, 90};
std::vector<size_t> indexes_to_move{2,4};
size_t destination_index = 6;
if(destination_index > values.size()) throw std::runtime_error("Come on, bro.");
for(auto const& val : values) std::cout << val << ',';
std::cout << std::endl;
for(size_t _index = 0; _index < indexes_to_move.size(); _index++) {
size_t index = indexes_to_move[indexes_to_move.size() - _index - 1]; //We need to iterate in reverse.
if(index >= values.size()) throw std::runtime_error("We dun goofed.");
if(index >= destination_index) throw std::runtime_error("We goofed in a different way.");
std::rotate(values.begin() + index, values.begin() + index + 1, values.begin() + destination_index);
destination_index--;
}
for(auto const& val : values) std::cout << val << ',';
std::cout << std::endl;
return 0;
}
根据ideone.com,这会产生以下输出:
0,10,20,30,40,50,60,70,80,90,
0,10,30,50,20,40,60,70,80,90,
这是一个解决方案,最多移动每个未选中的元素一次:
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> values{0, 10, 20, 30, 40, 50, 60, 70, 80, 90};
vector<size_t> IndexesToMove{2,4};
size_t NewIndex = 6;
//check that your indices are sorted, non-empty, in the correct range, etc.
// move one element in front of the next element to move
// then move those two elements in front of the next element to move
// ...
auto it_next = values.begin() + IndexesToMove.front();
for(size_t i = 0; i < IndexesToMove.size() -1; i++) {
auto it_first = it_next - i;
it_next = values.begin() + IndexesToMove[i+1];
rotate(it_first, it_first + i + 1 , it_next);
}
// move the collected elements at the target position
rotate(it_next - IndexesToMove.size() + 1, it_next + 1, values.begin() + NewIndex);
}
可读性固然不太好。可以通过更好的变量名 and/or 将其中一些放入单独的函数中
来改进它以上两个示例在输入不同时出现问题(如上所述)。我制定了处理不同情况的算法,并通过了我的单元测试。它可能会提高速度。
template <class CONTAINER_TYPE>
void ChangeRecordOrder( CONTAINER_TYPE IN OUT &values,
uint newIndex,
std::vector<uint> IN const &indexesToMove )
{
// Make a copy of the indexesToMove as we need to do fixups to them in certain cases
std::vector<uint> temporaryIndexes = indexesToMove;
for ( uint i=0; i<temporaryIndexes.size(); i++ )
{
uint indexToMove = temporaryIndexes[i];
if ( indexToMove < newIndex )
{
uint leftIndex = indexToMove;
uint rightIndex = newIndex -1;
uint newFirst = leftIndex + 1;
std::rotate( values.begin() + leftIndex, values.begin() + newFirst, values.begin() + rightIndex +1);
// fix up indexes
for( uint j=i+1; j<temporaryIndexes.size(); j++ )
{
uint &futureIndex = temporaryIndexes[j];
if ( futureIndex > leftIndex && futureIndex <=rightIndex )
--futureIndex;
}
}
else if ( indexToMove > newIndex )
{
uint leftIndex = newIndex;
uint rightIndex = indexToMove;
uint newFirst = indexToMove;
std::rotate( values.begin() + leftIndex, values.begin() + newFirst, values.begin() + rightIndex +1);
// fix up indexes
for( uint j=i+1; j<temporaryIndexes.size(); j++ )
{
uint &futureIndex = temporaryIndexes[j];
if ( futureIndex > leftIndex && futureIndex <=rightIndex )
++futureIndex;
}
++newIndex;
}
}
}
template <typename t> void move(std::vector<t>& v, size_t oldIndex, size_t newIndex)
{
if (oldIndex > newIndex)
std::rotate(v.rend() - oldIndex - 1, v.rend() - oldIndex, v.rend() - newIndex);
else
std::rotate(v.begin() + oldIndex, v.begin() + oldIndex + 1, v.begin() + newIndex + 1);
}
测试:https://coliru.stacked-crooked.com/a/5c31007000b9eeba
int main()
{
std::vector<int> v{ 3, 4, 5, 6, 7, 8, 9 };
move(v, 1, 4);
move(v, 4, 1);
move(v, 3, 3);
}
输出:
move 1 to 4: 3 [4] 5 6 7 8 9
result: 3 5 6 7 [4] 8 9
move 4 to 1: 3 5 6 7 [4] 8 9
result: 3 [4] 5 6 7 8 9
move 3 to 3: 3 4 5 [6] 7 8 9
result: 3 4 5 [6] 7 8 9