Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.84/19: Рейтинг темы: голосов - 19, средняя оценка - 4.84
5231 / 3204 / 362
Регистрация: 12.12.2009
Сообщений: 8,116
Записей в блоге: 2
1

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

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

Author24 — интернет-сервис помощи студентам
Что-то голова закипает, не могу сообразить. Есть вектор пар:
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)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.08.2011, 15:54
Ответы с готовыми решениями:

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

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

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

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

17
Эксперт С++
623 / 467 / 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
Freelance
Эксперт С++
2891 / 1826 / 356
Регистрация: 09.09.2010
Сообщений: 3,841
03.08.2011, 16:22 3
Kastaneda, Такая пара (3, 8) и (3, 8) не считаеться эквивалентной ?
0
5231 / 3204 / 362
Регистрация: 12.12.2009
Сообщений: 8,116
Записей в блоге: 2
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
155 / 155 / 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
5231 / 3204 / 362
Регистрация: 12.12.2009
Сообщений: 8,116
Записей в блоге: 2
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
155 / 155 / 44
Регистрация: 03.11.2010
Сообщений: 393
03.08.2011, 17:44 7
Да, я невнимательно прочитал задание.
0
Эксперт С++
2381 / 1665 / 279
Регистрация: 29.05.2011
Сообщений: 3,399
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
5231 / 3204 / 362
Регистрация: 12.12.2009
Сообщений: 8,116
Записей в блоге: 2
03.08.2011, 17:54  [ТС] 9
grizlik78, спасибо, именно это я и хотел сделать (т.е. один хитрый предикат, с которым будет выполнена "правильная" сортировка), немного не смог додумать!
0
Эксперт С++
2381 / 1665 / 279
Регистрация: 29.05.2011
Сообщений: 3,399
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
5231 / 3204 / 362
Регистрация: 12.12.2009
Сообщений: 8,116
Записей в блоге: 2
03.08.2011, 18:00  [ТС] 11
Цитата Сообщение от grizlik78 Посмотреть сообщение
Иначе не всегда будет работать.
Ну в моем случае всегда, я же писал:

Цитата Сообщение от Kastaneda Посмотреть сообщение
Т.е. у меня такой набор пар, что если p1.first==p2.second, то автоматически p1.second==p2.first.
Т.е. существование пар, например, (1,5) и (1,6) исключенно.
А так да, для более общего случая нужно конечно максимальные сравнивать тоже.
0
ниначмуроФ
851 / 535 / 110
Регистрация: 12.10.2009
Сообщений: 1,913
04.08.2011, 13:31 12
а как этот вектор(пар) вывести на экран при помощи copy?
0
Higher
1953 / 1219 / 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
5231 / 3204 / 362
Регистрация: 12.12.2009
Сообщений: 8,116
Записей в блоге: 2
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
5231 / 3204 / 362
Регистрация: 12.12.2009
Сообщений: 8,116
Записей в блоге: 2
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
5231 / 3204 / 362
Регистрация: 12.12.2009
Сообщений: 8,116
Записей в блоге: 2
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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
15.08.2011, 18:12
Помогаю со студенческими работами здесь

Как удалить данные из access при помощи php?
Доброго времени суток!!! подскажите пожалуйста как удалить данные из access при помощи php...

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

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

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

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

При помощи двоичного поиска найти запись о конкретном сотруднике и удалить её
Есть массив с данными о сотрудниках упорядоченный по фамилии. Необходимо при помощи двоичного...


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

Или воспользуйтесь поиском по форуму:
18
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru