How to quickly swap object in containers such as list and vector in c++

Question

I am wondering what the fast swap method is in C++ containers such as list and vector, because I haven't found any builtin swap functions yet.FYI, I want to swap object rather than the whole list.

For example, assume we have such int sequence 3 2 4 5 and they are stored in a list container(stl), and I want to swap 2 and 4. Here is the dumb method that I came up with:

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);

So, briefly speaking, what I am doing here is just "Copy, insert, and remove", and the reason why I do this is that I heard list container is very efficient for inserting and removing elements,but I am pretty sure there should be better algorithms.In addition, I also heard there exists a constant time swap method related to pointers, so anyone knows anything about it？

Thanks for helping out.

Answer 1

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 :)

Answer 2

Use iter_swap to swap the elements pointed at by two iterators to the list. This swaps the data, rather than the nodes, but it's easy.

#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

If you want to swap nodes rather than elements, you can use list::splice, though it's a little tricker:

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 << ' ';
}

Answer 3

It seems you may be looking for a way to move around nodes within the list, without copying actual elements. You could do this with list::splice. Nothing like that is possible for vector, of course, which is not node-based.

Something like this:

list<int>::iterator to = numbers.begin();
++to;
list<int>::iterator which  = to;
++which;
numbers.splice(to, numbers, which);

Answer 4

How about using swap?

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

which will use std:swap or ADL to determine a proper swap-function if there is one defined for the arguments.

As @Mooing Duck correctly pointed out std::list requires you to use iterators.

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

You can also use

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);

or

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

or

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

Answer 5

You want std::swap:

list<int>::iterator item1 = numbers.begin();
++item1;
list<int>::iterator item2 = item1;
++item2;
std::swap(*item1, *item2);