我想知道快速交换方法在C ++容器中是什么,例如list和vector,因为我还没有找到任何内置的交换函数。我想,我想交换对象而不是整个列表。
例如,假设我们有这样的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);
所以,简单来说,我在这里做的只是“复制,插入和删除”,我这样做的原因是我听说列表容器对插入和删除元素非常有效,但我很确定应该更好的算法。此外,我还听说存在一个与指针相关的恒定时间交换方法,所以任何人都知道它的一切?
谢谢你的帮助。
你想要std::swap
:
list<int>::iterator item1 = numbers.begin();
++item1;
list<int>::iterator item2 = item1;
++item2;
std::swap(*item1, *item2);
使用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 << ' ';
}
如果你想交换节点而不是元素,你可以使用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 << ' ';
}
看起来您可能正在寻找一种在列表中移动节点的方法,而无需复制实际元素。你可以用list :: splice做到这一点。当然,矢量不可能是这样的,它不是基于节点的。
像这样的东西:
list<int>::iterator to = numbers.begin();
++to;
list<int>::iterator which = to;
++which;
numbers.splice(to, numbers, which);
使用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));
使用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; }
使用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; }
希望它可以帮助你:)