своп соседние элементы в станд :: список (

Question

Я хочу поменять местами соседних элементов в std::list

Пример перечня и значений

A B C D E F G 
3 2 1 2 1 3 2 

Что я ожидаю получить после сортировки:

A B D C F E G 
3 2 2 1 3 1 2 

Итак, простой A > B = ничего не делать, но C < D = поменять их и перейти к E сравнения.

Я понятия не имею, как менять элементы соседства.

Итак, я хочу, чтобы двигаться вперед на 1 шаг good элементы

Answer 1

Вы можете легко сделать это с помощью двух итераторов:

void biswap(std::list<int> &l) 
{ 
    if (l.size() < 2) 
     return; 
    auto it2 = l.begin(); 
    auto it1 = it2++; 
    auto e = l.end(); 
    for (;;) 
    { 
     if (*it1 < *it2) 
      std::swap(*it1, *it2); 
     it1 = it2++; 
     if (it2 == e) 
      return; 
     it1 = it2++; 
     if (it2 == e) 
      return; 
    } 
} 

Live example

Примечание: в случае, если вы не используете C++ 11 и, таким образом, вызывая size() может представлять значительные накладные расходы, вы можете заменить его на это (и, конечно же, заменить все использование auto с явными типами):

void biswap(std::list<int> &l) 
{ 
    auto it2 = l.begin(); 
    auto e = l.end(); 
    if (it2 == e) 
     return; 
    auto it1 = it2++; 
    if (it2 == e) 
     return; 
    for (;;) 
    // ... the rest as before 
} 

Answer 2

Вы можете использовать стандартный алгоритм std::adjacent_find, чтобы найти пару элементов, для которых первый < второй, а затем поменять их местами.

Например

#include <iostream> 
#include <algorithm> 
#include <list> 
#include <functional> 
#include <iterator> 

int main() 
{ 
    std::list<int> l = { 3, 2, 1, 2, 1, 3, 2 }; 

    for (int x : l) std::cout << x << ' '; 
    std::cout << std::endl; 

    auto it = std::adjacent_find(l.begin(), l.end(), std::less<int>()); 

    if (it != l.end()) std::swap(*it, *std::next(it)); 

    for (int x : l) std::cout << x << ' '; 
    std::cout << std::endl; 
} 

Выход

3 2 1 2 1 3 2 
3 2 2 1 1 3 2 

Или, если вы хотите, чтобы обработать все такие ситуации, когда первый < второй, то вы можете использовать следующий код

#include <iostream> 
#include <algorithm> 
#include <list> 
#include <functional> 
#include <iterator> 

int main() 
{ 
    std::list<int> l = { 3, 2, 1, 2, 1, 3, 2 }; 

    for (int x : l) std::cout << x << ' '; 
    std::cout << std::endl; 

    std::list<int>::iterator it = l.begin(); 

    while ((it = std::adjacent_find(it, l.end(), std::less<int>())) != l.end()) 
    { 
     std::swap(*it, *std::next(it)); 
    } 

    for (int x : l) std::cout << x << ' '; 
    std::cout << std::endl; 
} 

Выходной сигнал составляет

3 2 1 2 1 3 2 
3 2 2 1 3 2 1 

Answer 3

Это дает желаемый результат, и он переключает сравнение для «хороших» элементов, точно так, как вы просили:

#include <list> 
#include <iostream> 

using namespace std; 

template<typename Type> 
void print(const list<Type> & l) 
{ 
    for (auto element : l) cout << element << " "; 
    cout << endl; 
} 

int main(int argc, const char *argv[]) 
{ 
    list<int> l = {3,2,1,2,1,3,2}; 

    print(l); 

    auto it = l.begin(); 
    while(std::next(it) != l.end()) 
    { 
     if (*it < *std::next(it)) 
     { 
      std::swap(*it, *std::next(it)); 
      ++it; 
     } 
     ++it; 
    } 

    print(l); 

    return 0; 
} 

Исполнительные результаты с:

3 2 1 2 1 3 2 
3 2 2 1 3 1 2 

Answer 4

В случае, если вы не имеете C++ 11 поддержки, простой C++ 03 решение с использованием 2 итераторов может быть:

#include <iostream> 
#include <algorithm> 
#include <list> 

void swapNeighbours(std::list<int>& l) { 

    std::list<int>::iterator it = l.begin(); 
    std::list<int>::iterator prev = it++; 
    while (prev != l.end() && it != l.end()) { 

     // swap if needed: 
     if (*prev < *it) 
      std::swap(*prev, *it); 

     // move 2 times forward: 
     if (++it == l.end()) 
      break; 
     prev = it++; 
    } 
} 

Тогда (основано на вашем примере), если вы:

void print(const std::list<int>& l) { 
    std::list<int>::const_iterator i; 
    for (i = l.begin(); i != l.end(); ++i) { 
     std::cout << *i << ' '; 
    } 
    std::cout << std::endl; 
} 

int main() { 

    std::list<int> l; 
    l.push_back(3); l.push_back(2); l.push_back(1); l.push_back(2); 
    l.push_back(1); l.push_back(3); l.push_back(2); 

    print(l); 
    swapNeighbours(l); 
    print(l); 
} 

затем для:

A B C D E F G 
3 2 1 2 1 3 2 

будут следующие сравнения: A < B? (нет) C < D? (да, свопы) E < F? (Да, свопы тоже), получая выход:

3 2 2 1 3 1 2 

Answer 5

Если все, что вам нужно сделать, это парного обхода и свопов элементов, если первый из них меньше, чем второй, то вы можете, например, использовать std::adjacent_find как это:

using std::swap; 
for (auto it = std::begin(l); it != std::end(l); it = std::adjacent_find(it, std::end(l), std::less<int>{})) { 
    swap(*it, *std::next(it)); 
} 

Это вызовет список номеров 3 2 1 2 1 3 2 быть организованы как:

3 2 2 1 3 2 1 

Но, это не такой же, как ваш ожидаемый результат 3 2 2 1 3 1 2 и I не понятно, почему вы не хотите менять последнюю пару 1 2, как и другие?

Если вы хотите, это шаблон неустойчивый для сортировки, тогда не может быть простого решения. Вместо этого вы должны использовать специальную обработку отдельных элементов.