C++最容易矢量

对不起，我的潜力nOOb'ness但在一个单一的元素移动到新位置，最有效的方法一直试图让这个几个小时，不能似乎找到C++ 98C++最容易矢量

一个优雅的解决方案

我的问题是，假设我有一个字符串{a，b，c，d，e，f}的向量，并且我想将'e'移动到第二个元素，我该怎么做呢？很显然，预期的输出结果现在可以打印出来{0128}，但是我们希望能够听到一些关于如何处理这些问题的建议做到这一点。

谢谢。

来源

2014-10-03 JoshuaBatty

如果你需要做很多事情，那么'std :: vector'可能不是容器的最佳选择。 – 2014-10-03 08:54:08

不要使用矢量。使用std :: list代替 - http://www.cplusplus.com/reference/list/list/ – 2014-10-03 08:55:02

使用'erase'和'insert'。 – Jarod42 2014-10-03 08:55:30

编辑正如评论，下面的代码实际上模仿std::rotate，这当然是上面在任何情况下我的手挽码首选的注意。

你可以用K交换完成这个w这里K是元件之间的距离：

#include <iostream> 
#include <string> 

using namespace std; 

int main() 
{ 
    string v = "abcdef"; // use string here so output is trivial 

    string::size_type insert_index = 1; // at the location of 'b' 
    string::size_type move_index = 4; // at the location of 'e' 

    while(move_index > insert_index) 
    { 
    std::swap(v[move_index], v[move_index-1]); 
    --move_index; 
    } 
    std::cout << v; 
}

Live demo here。注意我使用std::string，但算法对于std::vector保持不变。 The same can be done with iterators，所以你可以推广到没有operator[]的容器。

来源

2014-10-03 09:24:29 rubenvb

Thanks @rubenvb！这正是我所追求的。 – JoshuaBatty 2014-10-03 09:38:39

使用['std :: rotate']（http://en.cppreference.com/w/cpp/algorithm/rotate）也可以做到这一点，它具有复杂性之间的距离。 [看到它]（https://ideone.com/1hZ4jc） – WhozCraig 2014-10-03 11:51:40

@WhozCraig确实。我开始用另一个结果来写这篇文章，但事实上，你的方式会更习惯，因为我刚刚重新实现了'std :: rotate'。 – rubenvb 2014-10-03 11:53:12

由于std::vector<>存储在连续的内存中，因此您必须将旧位置和新位置之间的所有内容都移动一个元素，因此不可能通过std::vector<>“高效”执行此操作。所以它是矢量长度的线性时间（或至少移动的距离）。

天真的解决方案是insert()，然后erase()，但是这需要将您修改的最右边位置后的所有内容移动两次！因此，您可以“手动”，将b通过d一个位置复制到右边（例如用std::copy()，然后覆盖b。至少可以避免在修改范围之外移动任何东西。让std::rotate()做到这一点，因为@WhozCraig在评论中提及。

来源

2014-10-03 08:57:25

感谢John，我想过这样做，但没有追求，因为它觉得像1一样复制所有内容会效率低下......？ – JoshuaBatty 2014-10-03 09:03:24

@JoshuaBatty你会感到惊讶。取决于多大（更重要的是：如何*小*），你所谈论的事情序列可以在缓存内部非常有效。一个简单的例子（使用数组而不是简单的因为我懒得输入迭代器= P）[可以在这里找到]（https://ideone.com/mIEFpu）。它是一个选项，但对于大型序列，我可能会使用不同的数据结构，除非这是一个*罕见*操作。如果它很少，并且你花费大部分时间*列举线性顺序，那么矢量+旋转仍然可能是有保证的。 – WhozCraig 2014-10-03 09:11:57

我会用std::rotate第一次尝试，只有尝试其他手动东西（或比其他载体的容器），如果证明是不够高效：

#include <vector> 
#include <iostream> 
#include <algorithm> 

int main() 
{ 
    // move 5 from 4th to 1st index 

    std::vector<int> v {1,2,3,4,5,6}; 
    // position:  0 1 2 3 4 5 

    std::size_t i_old = 4; 
    std::size_t i_new = 1; 
    auto it = v.begin(); 

    std::rotate(it + i_new, it + i_old, it + i_old + 1); 
    for (int i : v) std::cout << i << ' '; 
}

Live demo。

来源

2014-10-03 09:29:05 jrok

C++最容易矢量

回答

相关问题