0

我想知道列表和向量等 C++ 容器中的快速交换方法是什么，因为我还没有找到任何内置的交换函数。仅供参考，我想交换对象而不是整个列表。

例如，假设我们有这样的 int 序列 3 2 4 5 并且它们存储在列表容器（stl）中，我想交换 2 和 4。这是我想出的愚蠢方法：

list<int> numbers;
numbers.push_back(3);
numbers.push_back(2);
numbers.push_back(4);
numbers.push_back(5);
list<int>::iterator item;
item=numbers.begin();
advance(item,2);
int key = *item;
advance(item,-1);
numbers.insert(item,key);
advance(item,1);
numbers.erase(item);

所以，简单来说，我在这里所做的只是“复制、插入和删除”，我这样做的原因是我听说列表容器对于插入和删除元素非常有效，但我很确定应该是更好的算法。另外，我也听说有一个与指针相关的常量时间交换方法，请问有人知道吗？</p>

感谢您的帮助。

4

5 回答 5

5

你想要std::swap：

list<int>::iterator item1 = numbers.begin();
++item1;
list<int>::iterator item2 = item1;
++item2;
std::swap(*item1, *item2);
于 2013-07-18T21:19:23.397 回答
5

用于iter_swap将两个迭代器指向的元素交换到列表中。这会交换数据，而不是节点，但这很容易。

#include <list>
#include <iostream>

int main() {
    std::list<int> numbers;
    numbers.push_back(3);
    numbers.push_back(2);
    numbers.push_back(4);
    numbers.push_back(5);

    auto first = std::next(numbers.begin(), 2);
    auto second = std::next(numbers.begin(), 1);
    std::iter_swap(first, second);

    for(int& v : numbers) 
        std::cout << v << ' ';
}

http://coliru.stacked-crooked.com/view?id=a89b3b1ae9400367b6ff194d1b504e58-f674c1a6d04c632b71a62362c0ccfc51

如果你想交换节点而不是元素，你可以使用list::splice，虽然它有点小技巧：

int main() {
    std::list<int> numbers;
    numbers.push_back(3);
    numbers.push_back(2);
    numbers.push_back(4);
    numbers.push_back(5);

    std::list<int> temporary;
    auto move_from = std::next(numbers.begin(), 2);
    temporary.splice(temporary.begin(), numbers, move_from, std::next(move_from));
    auto move_to = std::next(numbers.begin(), 1);
    numbers.splice(move_to, temporary);

    for(int& v : numbers) 
        std::cout << v << ' ';
}
于 2013-07-18T21:20:35.033 回答
2

看来您可能正在寻找一种在列表中移动节点而不复制实际元素的方法。你可以用 list::splice 做到这一点。当然，对于不是基于节点的向量来说，这样的事情是不可能的。

像这样的东西：

list<int>::iterator to = numbers.begin();
++to;
list<int>::iterator which  = to;
++which;
numbers.splice(to, numbers, which);
于 2013-07-18T21:25:13.937 回答
1

怎么用swap？

using std::swap;
swap(numbers[1], numbers[2]);

std:swap如果为参数定义了一个，它将使用或 ADL 来确定一个适当的交换函数。

正如@Mooing Duck 正确指出的那样，std::list您需要使用迭代器。

std::iter_swap(numbers.begin()+1, numbers.begin()+2);

你也可以使用

using std::swap;
std::list<int>::iterator item(numbers.begin());
std::advance(item, 1);
std::list<int>::iterator other(item);
std::advance(other, 1);
swap(*item, *other);

或者

using std::swap;
swap(*std::next(numbers.begin(), 1), *std::next(numbers.begin(), 2));

或者

std::iter_swap(std::next(numbers.begin(), 1), std::next(numbers.begin(), 2));
于 2013-07-18T21:16:03.660 回答
0

With std::swap(),

int reverse(std::list<int>& list){
    int exchange = 0;
    int move = 0;
    int distance_lo = 0;
    int distance_hi = 0;
    std::list<int>::iterator it_lo = list.begin();
    std::list<int>::iterator it_hi = --list.end();
    while (1) {
        it_lo = list.begin();
        it_hi = --list.end();
        std::advance(it_lo, move);
        std::advance(it_hi, -move);
        distance_lo = std::distance(list.begin(), it_lo);
        distance_hi = std::distance(list.begin(), it_hi);
        if (distance_lo < distance_hi) {
            std::swap(*it_lo, *it_hi);
            exchange++;
        } else {
            break;
        }
        move++;
    }
    return exchange; }

With std::list::splice(),

int reverse(std::list<int>& list) {
    int exchange = 0;
    int move = 0;
    int distance_lo = 0;
    int distance_hi = 0;
    std::list<int>::iterator it_lo = list.begin();
    std::list<int>::iterator it_hi = --list.end();
    while (1) {
        it_lo = list.begin();
        it_hi = --list.end();
        std::advance(it_lo, move);
        std::advance(it_hi, -move);
        distance_lo = std::distance(list.begin(), it_lo);
        distance_hi = std::distance(list.begin(), it_hi);
        if (distance_lo < distance_hi) {
            std::list<int> tmp;
            tmp.splice(tmp.begin(), list, it_lo);
            tmp.splice(std::next(tmp.begin(),1), list, it_hi);

            it_lo = list.begin();
            it_hi = --list.end();
            std::advance(it_lo, move); //insert before it_lo
            std::advance(it_hi, -move);
            std::advance(it_hi, 1); //insert after it_hi
            list.splice(it_lo, tmp, std::next(tmp.begin(),1));
            list.splice(it_hi, tmp, tmp.begin());
            exchange++;
        } else {
            break;
        }
        move++;
    }
    return exchange; }

Hope it could help you :)

于 2019-03-20T03:20:06.470 回答