Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.70/10: Рейтинг темы: голосов - 10, средняя оценка - 4.70
Kastaneda
Jesus loves me
Эксперт С++
4940 / 3016 / 346
Регистрация: 12.12.2009
Сообщений: 7,612
Записей в блоге: 2
Завершенные тесты: 1
1

Удалить эквивалентные пары из вектора пар при помощи стандартных алгоритмов

03.08.2011, 15:54. Просмотров 1863. Ответов 17
Метки нет (Все метки)

Что-то голова закипает, не могу сообразить. Есть вектор пар:
C++
1
std::vector<std::pair<int,int> >
который содержит кроме всего прочего эквивалентные пары, т.е. например (3,8) и (8,3), мне нужно удалить "дубли", оставив одну пару, при чем хочу это сделать исключительно при помощи STL.
Мои соображения - использовать std::unuque() с таким предикатом:
C++
1
2
3
4
5
struct comp{
    bool operator()(std::pair<int,int> p1,std::pair<int,int> p2){
        return p1.first==p2.second && p1.second==p2.first;;
    }
};
но перед этим, естественно, вектор нужно отсортировать. Вот с сортировкой и возникла проблема - можно отсортировать либо по первым, либо по вторым элементом пар, а мне нужно, чтоб эквивалентные пары оказались соседними в векторе.
Есть подозрение, что таким способом отсортировать нереально, может подскажите другое решение?

Не по теме:

P.S. повторюсь - используя STL, так я и сам могу написать))

0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.08.2011, 15:54
Ответы с готовыми решениями:

Вычисление функций, их сумм и произведений при помощи циклических алгоритмов
1)По рекурентным формулам вычислить сумму или произведение. Рабочий набор:...

Сортировка списка строк с использованием стандартных алгоритмов библиотеки STL
Сортировка слов по количеству в них букв 'А'. Сортировка списка строк с...

Провести операцию над множествами без использования стандартных алгоритмов
Подскажите как провести операцию над множествами без использования стандартных...

При помощи встроенных функций для заполнения стандартных матриц, получите следующую матрицу
При помощи встроенных функций для заполнения стандартных матриц, индексации...

При помощи алгоритмов кластеризации выявить нетипичное поведение пользователя в сети
Всем привет. Вопрос такой: есть набор данных, собранный из заголовков пакетов...

17
Ma3a
Эксперт С++
619 / 463 / 57
Регистрация: 28.01.2011
Сообщений: 605
03.08.2011, 16:20 2
Я бы сначала прошёлся алгоритмом transform, чтобы все эквивалентные пары были переведены в одну и ту же форму, например, согласно условию p.first < p.second, а потом уже спокойно доделать дело с помощью sort и unique:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <algorithm>
#include <utility>
#include <vector>
#include <functional>
 
typedef std::pair<int,int> pair;
 
struct trans : std::unary_function<pair, pair>
    {
    pair operator() (pair const & p)
        {
        return p.first < p.second ? p : std::make_pair<int,int>(p.second, p.first);
        }
    };
 
int main()
    {
 
    typedef std::vector<pair> vector;
 
    vector vec;
    // ...
 
    std::transform(vec.begin(), vec.end(), vec.begin(), trans());
    std::sort(vec.begin(), vec.end());
    vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
    }
2
asics
Freelance
Эксперт С++
2854 / 1789 / 355
Регистрация: 09.09.2010
Сообщений: 3,841
03.08.2011, 16:22 3
Kastaneda, Такая пара (3, 8) и (3, 8) не считаеться эквивалентной ?
0
Kastaneda
Jesus loves me
Эксперт С++
4940 / 3016 / 346
Регистрация: 12.12.2009
Сообщений: 7,612
Записей в блоге: 2
Завершенные тесты: 1
03.08.2011, 16:32  [ТС] 4
Ma3a, ну да, об этом я как-то не подумал.

В общем-то мне данный вариант подойдет, однако было бы интересно посмотреть на другие решения

Добавлено через 3 минуты
Цитата Сообщение от asics Посмотреть сообщение
Такая пара (3, 8) и (3, 8) не считаеться эквивалентной ?
Забыл упомянуть, у меня таких пар не будет (исключено алгоритмом получения этих пар).

И еще, предикат из первого поста может выглядеть так:
C++
1
2
3
        bool operator()(std::pair<int,int> p1,std::pair<int,int> p2){
                return p1.first==p2.second;//&& p1.second==p2.first;;
        }
Т.е. у меня такой набор пар, что если p1.first==p2.second, то автоматически p1.second==p2.first.
0
Roof
154 / 154 / 44
Регистрация: 03.11.2010
Сообщений: 393
03.08.2011, 17:25 5
Цитата Сообщение от Kastaneda Посмотреть сообщение
но перед этим, естественно, вектор нужно отсортировать. Вот с сортировкой и возникла проблема - можно отсортировать либо по первым, либо по вторым элементом пар, а мне нужно, чтоб эквивалентные пары оказались соседними в векторе.
Есть подозрение, что таким способом отсортировать нереально, может подскажите другое решение?
Я так понял использовать функции с предикатами можно.
Чтобы эквивалентные пары оказались соседними в векторе можно использовать функцию
std::stable_sort с предикатом:
C++
1
2
3
4
5
typedef pair < int, int > elem;
...
bool comp_elem ( elem a, elem b ){
     return a.first==b.second && a.second==b.first;
}
Добавлено через 17 минут
поторопился, предикат вообще не нужен.
Просто std::stable_sort;

Вот мой вариант:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
 
using namespace std;
 
#define NUM1 3
#define NUM2 8
typedef pair < int, int > elem;
 
//функция заполнения вектора
void fill_vec( vector < elem > &vec );
//функция печати вектора
void print_vec ( vector < elem > &vec );
 
int main() {
 
    vector < elem > my_vec ( 10 );
    //заполняем вектор
    fill_vec( my_vec );
    print_vec( my_vec );
 
    //сортируем вектор
    sort( my_vec.begin(), my_vec.end() );
    print_vec( my_vec );
 
    //сортируем так чтобы эквивалентные оказались рядом
    stable_sort( my_vec.begin(), my_vec.end() );
    print_vec( my_vec );
 
    //переносим уникальные элементы вначало вектора
    vector < elem >::iterator end_unique = unique( my_vec.begin(), my_vec.end() );
    print_vec( my_vec );
 
    //удаляем эквивалентные пары
    my_vec.erase( end_unique, my_vec.end() );
    print_vec( my_vec );
 
    return 0;
}
 
 
void fill_vec( vector < elem > &vec ){
    if (vec.size() == 0){
            cout << "Размер вектора равен 0! Невозможно заполнить!";
            return;
    }
 
    vector < elem >::iterator it = vec.begin();
        int n = 0;
        while ( it != vec.end() ){
            ++n % 2 ? (*it++ = make_pair( n, n )) : (*it++ = make_pair( NUM1 , NUM2 ));
        }
 
 
 
}
 
void print_vec ( vector < elem > &vec ){
 
    if (vec.size() == 0){
        cout << "Вектор пустой! Нечего печатать!";
        return;
    }
 
    vector < elem >::const_iterator it = vec.begin();
    while ( it != vec.end() ){
        cout << "( " << (*it).first << " " << (*it).second << " )  ";
        ++it;
    }
 
    cout << endl;
}
Подойдет?
0
Kastaneda
Jesus loves me
Эксперт С++
4940 / 3016 / 346
Регистрация: 12.12.2009
Сообщений: 7,612
Записей в блоге: 2
Завершенные тесты: 1
03.08.2011, 17:35  [ТС] 6
Цитата Сообщение от Roof Посмотреть сообщение
Подойдет?
Нет, он же не удаляет эквивалентные пары.
У меня создается вектор типа такого: (1,5), (2,4), (3, 3), (4, 2), (5, 1), только гораздо длиннее. Нужно оставить только (1,5), (2,4), (3, 3) (или (3, 3), (4, 2), (5, 1) - без разницы)
0
Roof
154 / 154 / 44
Регистрация: 03.11.2010
Сообщений: 393
03.08.2011, 17:44 7
Да, я невнимательно прочитал задание.
0
grizlik78
Эксперт С++
1988 / 1480 / 192
Регистрация: 29.05.2011
Сообщений: 3,059
03.08.2011, 17:48 8
Kastaneda, а одинаковые пары тоже надо удалять? Или одинаковых пар нет?

Добавлено через 3 минуты
Попробуй для сортировки вот такой предикат. По-моему должен работать.
C++
1
2
3
4
5
struct comp_for_sort{
    bool operator()(std::pair<int,int> p1,std::pair<int,int> p2){
        return std::min(p1.first, p1.second) < std::min(p2.first, p2.second);
    }
};
2
Kastaneda
Jesus loves me
Эксперт С++
4940 / 3016 / 346
Регистрация: 12.12.2009
Сообщений: 7,612
Записей в блоге: 2
Завершенные тесты: 1
03.08.2011, 17:54  [ТС] 9
grizlik78, спасибо, именно это я и хотел сделать (т.е. один хитрый предикат, с которым будет выполнена "правильная" сортировка), немного не смог додумать!
0
grizlik78
Эксперт С++
1988 / 1480 / 192
Регистрация: 29.05.2011
Сообщений: 3,059
03.08.2011, 17:57 10
Kastaneda, на самом деле я его не доделал. Если минимальные равны, то надо максимальные сравнить. Иначе не всегда будет работать.

Добавлено через 1 минуту
Вот так:
C++
1
2
3
4
5
6
7
struct comp_for_sort{
    bool operator()(std::pair<int,int> p1,std::pair<int,int> p2){
        if (std::min(p1.first, p1.second) == std::min(p2.first, p2.second))
            return std::max(p1.first, p1.second) < std::max(p2.first, p2.second)
        return std::min(p1.first, p1.second) < std::min(p2.first, p2.second);
    }
};
0
Kastaneda
Jesus loves me
Эксперт С++
4940 / 3016 / 346
Регистрация: 12.12.2009
Сообщений: 7,612
Записей в блоге: 2
Завершенные тесты: 1
03.08.2011, 18:00  [ТС] 11
Цитата Сообщение от grizlik78 Посмотреть сообщение
Иначе не всегда будет работать.
Ну в моем случае всегда, я же писал:

Цитата Сообщение от Kastaneda Посмотреть сообщение
Т.е. у меня такой набор пар, что если p1.first==p2.second, то автоматически p1.second==p2.first.
Т.е. существование пар, например, (1,5) и (1,6) исключенно.
А так да, для более общего случая нужно конечно максимальные сравнивать тоже.
0
PointsEqual
ниначмуроФ
840 / 524 / 110
Регистрация: 12.10.2009
Сообщений: 1,915
04.08.2011, 13:31 12
а как этот вектор(пар) вывести на экран при помощи copy?
0
diagon
Higher
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
04.08.2011, 13:55 13
Цитата Сообщение от PointsEqual Посмотреть сообщение
а как этот вектор(пар) вывести на экран при помощи copy?
У меня при попытке скопировать его в ostream_iterator выдает километровую ошибку, хотя я даже переопределил << для пар =\
Можно с помощью for_each это сделать.
C++
1
std::for_each(vec.begin(), vec.end(),[=](const std::pair<int, int>& pair){ std::cout << pair.first << ", " << pair.second << std::endl;});
0
Kastaneda
Jesus loves me
Эксперт С++
4940 / 3016 / 346
Регистрация: 12.12.2009
Сообщений: 7,612
Записей в блоге: 2
Завершенные тесты: 1
04.08.2011, 14:34  [ТС] 14
diagon, знак "=" в квадратных скобках необязателен (точнее вообще не нужен), т.к. нет захвата переменных из внешеней области видимости, значение передается аргументом в ф-ции.


Цитата Сообщение от diagon Посмотреть сообщение
У меня при попытке скопировать его в ostream_iterator выдает километровую ошибку
Потому, что нет стандартного итератора std::ostream_iterator<std:air<int,int> >
Цитата Сообщение от diagon Посмотреть сообщение
хотя я даже переопределил << для пар
Тогда можно было так:
C++
1
std::for_each(vec.begin(), vec.end(),[](const std::pair<int, int>& pair){ std::cout <<pair<<std::endl;});
Добавлено через 49 секунд

Не по теме:

долбаные смайлы)

0
Сыроежка
Заблокирован
04.08.2011, 16:57 15
Цитата Сообщение от Kastaneda Посмотреть сообщение
Ma3a, ну да, об этом я как-то не подумал.

В общем-то мне данный вариант подойдет, однако было бы интересно посмотреть на другие решения

Добавлено через 3 минуты

Забыл упомянуть, у меня таких пар не будет (исключено алгоритмом получения этих пар).

И еще, предикат из первого поста может выглядеть так:
C++
1
2
3
        bool operator()(std::pair<int,int> p1,std::pair<int,int> p2){
                return p1.first==p2.second;//&& p1.second==p2.first;;
        }
Т.е. у меня такой набор пар, что если p1.first==p2.second, то автоматически p1.second==p2.first.
Интересно, а какова содержательная часть проблемы, которая привела к появлению этой подзадачи. Из чего вы образовывали пары и в связи с чем? Кстати сказать, у вас также будут удаляться и совпадающие значения пар { 3, 3 }, { 3, 3 }, так как они удовлетворяют вашему условию.

Что касается предиката сортировки, то он прост

C++
1
2
3
4
5
6
7
8
9
10
11
struct pair_less : public
   std::binary_function<const std::pair<int, int> &,
                        const std::pair<int, int> &,
                        bool>
{
   bool operator ()( const std::pair<int, int> &a,
                     const std::pair<int, int> &b ) const
   {
      return ( std::min( a.first, a.second ) < std::min( b.first, b.second ) );
   }
};
0
Kastaneda
Jesus loves me
Эксперт С++
4940 / 3016 / 346
Регистрация: 12.12.2009
Сообщений: 7,612
Записей в блоге: 2
Завершенные тесты: 1
04.08.2011, 18:08  [ТС] 16
grizlik78, в 8-ом посте написал такой же предикат.

Цитата Сообщение от Сыроежка Посмотреть сообщение
Интересно, а какова содержательная часть проблемы, которая привела к появлению этой подзадачи. Из чего вы образовывали пары и в связи с чем?
Да это не реальная задача, всмысле просто упражнение из книги. Люблю на досуге заморочиться)
0
Сыроежка
Заблокирован
05.08.2011, 16:38 17
Цитата Сообщение от Сыроежка Посмотреть сообщение
Интересно, а какова содержательная часть проблемы, которая привела к появлению этой подзадачи. Из чего вы образовывали пары и в связи с чем? Кстати сказать, у вас также будут удаляться и совпадающие значения пар { 3, 3 }, { 3, 3 }, так как они удовлетворяют вашему условию.

Что касается предиката сортировки, то он прост

C++
1
2
3
4
5
6
7
8
9
10
11
struct pair_less : public
   std::binary_function<const std::pair<int, int> &,
                        const std::pair<int, int> &,
                        bool>
{
   bool operator ()( const std::pair<int, int> &a,
                     const std::pair<int, int> &b ) const
   {
      return ( std::min( a.first, a.second ) < std::min( b.first, b.second ) );
   }
};
Только я сделал по невнимательности ошибку, а меня никто не подправил! Поэтому решил возвратиться к этому вопросу. У класса
C++
1
std::pair
есть свой определенный оператор '<'. Он записывается примерно следующим образом (пишу по памяти):

C++
1
2
3
4
5
6
7
template <typename T1, typename T2>
 
bool operator <( const std::pair<T1, T2> &a, std::pair<T1, T2> &b )
{
   return ( ( a.first < b.first ) ||
              ( !( b.first < a.first ) && ( a.second < b.second ) ) );
}
В исходной задаче можно рассматривать пары для сортировки как будто бы значение члена класса x.first равно std::min( x.first, x.second ), а значение x.second равно std::max( x.first, x.second ). То есть тем самым мы приводим все пары к одному виду, напоминающем дроби, когда значение в числители всегда меньше равно значению в знаменателе.

Тогда для сортировки предикат можно написать следующим образом

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename T>
struct pair_less : public
   std::binary_function<std::pair<T, T>, std::pair<T, T>, bool>
{
   bool operator ()( const std::pair<T, T> &a,
                     const std::pair<T, T> &b ) const
   {
      return
      ( ( std::min( a.first, a.second ) < std::min( b.first, b.second ) ) ||
        ( !( std::min( b.first, b.second ) < std::min( a.first, a.second ) ) &&
          ( std::max( a.first, a.second ) < std::max( b.first, b.second ) ) );
   }
};
[/QUOTE]


Вот сейчас логика будет правильная.
0
Kastaneda
Jesus loves me
Эксперт С++
4940 / 3016 / 346
Регистрация: 12.12.2009
Сообщений: 7,612
Записей в блоге: 2
Завершенные тесты: 1
15.08.2011, 18:12  [ТС] 18
Лучший ответ Сообщение было отмечено как решение

Решение

Цитата Сообщение от PointsEqual Посмотреть сообщение
а как этот вектор(пар) вывести на экран при помощи copy?
Цитата Сообщение от diagon Посмотреть сообщение
У меня при попытке скопировать его в ostream_iterator выдает километровую ошибку, хотя я даже переопределил << для пар =\
Знаю, что тема уже не актуальна, но я как раз сейчас сижу читаю книгу, и прочитал про эту проблему (в цитатах выше). Когда прочитал, то вспомнил, что недавно на форуме была затронута эта тема, а правильное решение так ни кто и не предложил, поэтому вот решил написать, думаю многим будет интересно)

В общем когда компилятор ищет нужную функцию, он пользуется т.н. ADL (Argument - Dependent Lookup - поиск с учетом аргуменов). Суть его заключается в следующем - функция ищется в том пространстве имен, к которому относятся ее аргументы. Если бы ADL не существовало, то вместо :
C++
1
2
std::string s;
std::cout<<s<<std::endl;
нам приходилось бы писать такие чудовищные конструкции:
C++
1
std::operator<<(std::operator(std::cout,s),std::endl);
но этого делать не приходиться, поскольку cout, string и endl находятся в пространстве имен std, то функция operator<< ищется там же.

Теперь по поводу нашей проблемы, думаю все (и я в т.ч.) пробовали сделать так:
C++
1
2
3
4
5
6
7
8
9
10
std::ostream& operator<<(std::ostream &os, const std::pair<int,int> &ob){
    return os<<ob.first<<" "<<ob.second;
}
 
int main() {
    std::vector<std::pair<int,int> >v;
    v.push_back(std::make_pair(10,20));
    v.push_back(std::make_pair(100,200));
    std::copy(v.begin(),v.end(),std::ostream_iterator<std::pair<int,int> >(std::cout,"\n"));
}
т.к. ostream_iterator<> и аргументы, переданные ему в качестве параметра шаблона и в качестве аргументов конструктора находятся в пространстве имен std, то и функция operator<< ищется там же и, естественно, не находится.
Поэтому правильно делать так:
C++
1
2
3
4
5
namespace std{
    std::ostream& operator<<(std::ostream &os, const std::pair<int,int> &ob){
        return os<<ob.first<<" "<<ob.second;
    }
}
теперь operator<< для std:: pair<int,int> будет найден, и алгоритм std::copy с итератором ostream_iterator<> скомпилируется и, естественно, отработает правильно.

Хотя добавление пользователем своих элементов в пространство имен std считается плохим тоном, но в данном случае это единственное (как пишет автор книги) разумное решение.



Вот про ADL (выдержка из книги)
3
15.08.2011, 18:12
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.08.2011, 18:12

Модификация стандартных алгоритмов
Помогите решить пару задач плиз, сам понять не могу =((( Нужно пузырьковый...

Как удалить ячейку при помощи макроса в VBA?
Pomogite pojalujsta s macrosom. Kak mojno napisatj kod v VBE, chtoby macros...

Удалить из столбца пробелы при помощи функции Trim()
ЗДРАВИЯ ВСЕМ! Есть таблица tarif, есть в ней столбец konsultant, нужно...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
18
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru