Форум программистов, компьютерный форум CyberForum.ru

Ассоц. и послед. контейнеры. Разница в методах и алгоритмах. - C++

Восстановить пароль Регистрация
 
Pavel.fromBy
 Аватар для Pavel.fromBy
13 / 13 / 1
Регистрация: 31.12.2011
Сообщений: 83
06.01.2012, 20:29     Ассоц. и послед. контейнеры. Разница в методах и алгоритмах. #1
Добрый вечер всем! Возник вопрос - прошу помощи. Речь об STL... В чем проблема собственно: почему для использования у множества с пользовательскими объектами метода find() не нужен перегруженный оператор== ??? Для тех же списков или векторов, да и для двухсторонних очередей тоже, наличие == обязательно (для все того же find(), только тут это алгоритм). Тоже самое с count(). Заранее благодарен.
p.s. в голове не укладывается. Перегружен только < (и то для сортировки ключей), а find() и count() на ура работают.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.01.2012, 20:29     Ассоц. и послед. контейнеры. Разница в методах и алгоритмах.
Посмотрите здесь:

C++ контейнеры
C++ Есть ли в классе строк или в алгоритмах разбиение строку на лексемы?
Подсчет количества обменов и сравнений в алгоритмах сортировки C++
C++ Ассоц. массив
контейнеры С++ C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
06.01.2012, 22:02     Ассоц. и послед. контейнеры. Разница в методах и алгоритмах. #2
Что я могу сказать... выучи сначали Си, сам всё поймешь.
Pavel.fromBy
 Аватар для Pavel.fromBy
13 / 13 / 1
Регистрация: 31.12.2011
Сообщений: 83
06.01.2012, 23:37  [ТС]     Ассоц. и послед. контейнеры. Разница в методах и алгоритмах. #3
Спасибо, конечно, за совет, но не все такие "вундеркинды", чтобы в универе и C++, и С, и хренову тучу математики учить.
p.s. хотелось бы увидеть хоть какой-нибудь ответ.
Jupiter
Каратель
Эксперт C++
6542 / 3962 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
06.01.2012, 23:45     Ассоц. и послед. контейнеры. Разница в методах и алгоритмах. #4

Не по теме:

Цитата Сообщение от Pavel.fromBy Посмотреть сообщение
Спасибо, конечно, за совет, но не все такие "вундеркинды", чтобы в универе и C++, и С, и хренову тучу математики учить.
ошибаетесь всё



список, дек и вектор - последовательные контейнеры и хранят элементы в том порядке в каком их добавили, а множество и отображение - ассоциативные контейнеры реализованы в виде деревьев и хранят элементы в отсортированом виде
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
06.01.2012, 23:58     Ассоц. и послед. контейнеры. Разница в методах и алгоритмах. #5
Цитата Сообщение от Pavel.fromBy Посмотреть сообщение
не все такие "вундеркинды", чтобы в универе и C++, и С, и хренову тучу математики учить.
можно, например, сварщиком работать. И профессия полезная и учить мало.
greeezz
272 / 165 / 4
Регистрация: 10.07.2011
Сообщений: 441
07.01.2012, 00:01     Ассоц. и послед. контейнеры. Разница в методах и алгоритмах. #6
Pavel.fromBy, давайте на примерах разбирать. Покажите что у вас где работает а что где не работает. С примерами будет нагляднее. И будет уверенность что мы друг друга понимаем.
Pavel.fromBy
 Аватар для Pavel.fromBy
13 / 13 / 1
Регистрация: 31.12.2011
Сообщений: 83
07.01.2012, 14:36  [ТС]     Ассоц. и послед. контейнеры. Разница в методах и алгоритмах. #7
Jupiter, про хранение в виде деревьев я знаю. Если что не то скажу - поправьте (структуры данных еще особо не проходили), но по-моему при обходе мне все равно придется сравнивать с использованием операторов <, >, == (последние два не требуются во множестве ?!).

alkagolik, хотел бы сварщиком - не пошел бы на программиста. Я к тому, что и так каша в голове, а вы мне еще C советуете.


greeezz, код скопипастил из Лафоре. (Листинг 15.31)

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
// setpers.cpp
// Применение мультимножества для хранения объектов person
#pragma warning (disable:4786)     // для множеств (для
                                   // компиляторов фирмы Microsoft)
#include <iostream>
#include <set>
#include <string>
using namespace std;
 
class person
   {
   private:
      string lastName;
      string firstName;
      long phoneNumber;
   public:                         // конструктор по умолчанию
      person() : lastName("пусто"),
                 firstName("пусто"), phoneNumber(0)
         {  }
                                   // конструктор с тремя параметрами
      person(string lana, string fina, long pho) :
              lastName(lana), firstName(fina), phoneNumber(pho)
         {  }
      friend bool operator<(const person&, const person&);
      //friend bool operator==(const person&, const person&);
 
      void display() const         // вывод данных о людях
         {
         cout << endl << lastName << ",\t" << firstName
              << "\t\tТелефон: " << phoneNumber;
         }
   };
                                   // оператор < для класса person
bool operator<(const person& p1, const person& p2)
   {
   if(p1.lastName == p2.lastName)
      return (p1.firstName < p2.firstName) ? true : false;
   return (p1.lastName < p2.lastName) ? true : false;
   }
                                   // оператор == для класса person
/*bool operator==(const person& p1, const person& p2)
   {
   return (p1.lastName == p2.lastName &&
           p1.firstName == p2.firstName ) ? true : false;
   }*/
///////////////////////////////////////////////////////////
int main()
   {                               // создание объектов person
   person pers1("Deauville", "William", 8435150);
   person pers2("McDonald", "Stacey", 3327563);
   person pers3("Bartoski", "Peter", 6946473);
   person pers4("KuangThu", "Bruce", 4157300);
   person pers5("Wellington", "John", 9207404);
   person pers6("McDonald", "Amanda", 8435150);
   person pers7("Fredericks", "Roger", 7049982);
   person pers8("McDonald", "Stacey", 7764987);
                                   // мультимножество класса person
   multiset< person, less<person> > persSet;
                                   // итератор этого мультимножества
   multiset<person, less<person> >::iterator iter;
 
   persSet.insert(pers1);          // занести объекты person в
                                   //мультимножество
   persSet.insert(pers2);
   persSet.insert(pers3);
   persSet.insert(pers4);
   persSet.insert(pers5);
   persSet.insert(pers6);
   persSet.insert(pers7);
   persSet.insert(pers8);
 
   cout << "\nЧисло записей: " << persSet.size();
 
   iter = persSet.begin();         //Вывод содержимого
                                   //  мультимножества
   while( iter != persSet.end() )
      (*iter++).display();
                                   // получение имени и фамилии
   string searchLastName, searchFirstName;
   cout << "\n\nВведите фамилию искомого человека: ";
   cin >> searchLastName;
   cout << "Введите имя: ";
   cin >> searchFirstName;
        // создание объекта с заданными значениями атрибутов
   person searchPerson(searchLastName, searchFirstName, 0);
        // сосчитать количество людей с таким именем
   int cntPersons = persSet.count(searchPerson);
   cout << "Число людей с таким именем: " << cntPersons;
 
        // вывести все записи, отвечающие запросу
   iter = persSet.lower_bound(searchPerson);
   while( iter != persSet.upper_bound(searchPerson) )
      (*iter++).display();
   cout << endl;
   return 0;
   }    // end main()
У Лафоре присутствует оператор==, но я был очень любопытный и закомментировал его - ничего не изменилось. Так же методы lower_bound и upper_bound. Метод upper_bound() цитирую, " возвращает итератор, указывающий на элемент, значение которого больше, чем аргумент" - опять загвоздка, а где оператор> ?!
greeezz
272 / 165 / 4
Регистрация: 10.07.2011
Сообщений: 441
07.01.2012, 21:01     Ассоц. и послед. контейнеры. Разница в методах и алгоритмах. #8
Цитата Сообщение от Pavel.fromBy Посмотреть сообщение
закомментировал его - ничего не изменилось.
почему вы считаете что в данном листинге что-то должно было измениться ? оператор == у вас тут нигде не применяется как я вижу
Pavel.fromBy
 Аватар для Pavel.fromBy
13 / 13 / 1
Регистрация: 31.12.2011
Сообщений: 83
07.01.2012, 21:05  [ТС]     Ассоц. и послед. контейнеры. Разница в методах и алгоритмах. #9
Цитата Сообщение от greeezz Посмотреть сообщение
почему вы считаете что в данном листинге что-то должно было измениться ? оператор == у вас тут нигде не применяется как я вижу
Метод count. Разве он не должен использовать operator==? Одноименный с ним алгоритм для того же списка ( с пользовательскими объектами ) требует наличие вышеуказанного оператора. Я просто хочу понять - почему так происходит? Выше я уже написал, повторюсь - при обходе дерева (множества) необходимы будут <, >, == или я не прав?
Jupiter
Каратель
Эксперт C++
6542 / 3962 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
07.01.2012, 21:17     Ассоц. и послед. контейнеры. Разница в методах и алгоритмах. #10
std::rel_ops, достаточно реализовать два оператора: < и == для того чтобы получить весь набор операторов сравнения
greeezz
272 / 165 / 4
Регистрация: 10.07.2011
Сообщений: 441
07.01.2012, 21:38     Ассоц. и послед. контейнеры. Разница в методах и алгоритмах. #11
Цитата Сообщение от Pavel.fromBy Посмотреть сообщение
при обходе дерева (множества) необходимы будут <, >, ==
в вашем случае используется только оператор
C++
1
2
3
4
5
bool operator<(const person& p1, const person& p2) {
    if (p1.lastName == p2.lastName)
        return (p1.firstName < p2.firstName) ? true : false;
    return (p1.lastName < p2.lastName) ? true : false;
}
потому что он проверяет сразу и равенство объектов

Добавлено через 5 минут
представте что происходит сравнение двух объектов типа person.
в каком случае вернется true?
1. если фамилии и имена равны.
2. если фамилия один меньше фамилии два

а вот false вернется когда объект два "больше" первого

Добавлено через 4 минуты
для тестов сделайте так:
C++
1
2
3
4
5
bool operator<(const person& p1, const person& p2) {
//  if (p1.lastName == p2.lastName)
//      return (p1.firstName < p2.firstName) ? true : false;
    return (p1.lastName < p2.lastName && p1.firstName < p2.firstName) ? true : false;
}
а оператор == раскомментируйте
Pavel.fromBy
 Аватар для Pavel.fromBy
13 / 13 / 1
Регистрация: 31.12.2011
Сообщений: 83
07.01.2012, 22:07  [ТС]     Ассоц. и послед. контейнеры. Разница в методах и алгоритмах. #12
greeezz, не согласен с Вами. Первый случай для true не выполнится. operator< не может вернуть true, если фамилии и имена равны. Он сравнит фамилии и имена (в случае равенства фамилий) и вернет false в случае > и в случае ==. И так, что мы имеем: возвращает он false, а дальше? Откуда программе знать, что там именно ==, а не > ?
p.s. ведь поиск во множестве не только по фамилии, но и по имени.....?
p.s.s. разве приведенный ниже Вами оператор< корректен? Ведь может оказаться, что фамилии равны, но имена разные и причем 1ое меньше второго, а вернет он false.
greeezz
272 / 165 / 4
Регистрация: 10.07.2011
Сообщений: 441
07.01.2012, 23:06     Ассоц. и послед. контейнеры. Разница в методах и алгоритмах. #13
Цитата Сообщение от Pavel.fromBy Посмотреть сообщение
greeezz, не согласен с Вами. Первый случай для true не выполнится. operator< не может вернуть true, если фамилии и имена равны.
Да вы правы, чет я погорячился.
Сейчас попробую пару тестов сделать.

Добавлено через 14 минут
Для наглядности немного изменил перегруженый оператор <
C++
1
2
3
4
5
6
7
8
9
10
11
12
// оператор < для класса person
bool operator<(const person& p1, const person& p2) {
    if (p1.lastName == p2.lastName) {
        if (p1.firstName < p2.firstName) {
            cout << "!!!"<< p2.firstName << "\n";
            return true;
        }
    } else if (p1.lastName < p2.lastName) {
        return true;
    }
    return false;
}
Тест 1:
Chislo zapisei: 8
Bartoski, Peter Telephon: 6946473
Deauville, William Telephon: 8435150
Fredericks, Roger Telephon: 7049982
KuangThu, Bruce Telephon: 4157300
McDonald, Amanda Telephon: 8435150
McDonald, Stacey Telephon: 3327563
McDonald, Stacey Telephon: 7764987
Wellington, John Telephon: 9207404

Vvedite familiu: Bartoski
Vvedite imya: A
!!!Peter
Chislo ludei s takim imenem: 0
Тест 2:

Chislo zapisei: 8
Bartoski, Peter Telephon: 6946473
Deauville, William Telephon: 8435150
Fredericks, Roger Telephon: 7049982
KuangThu, Bruce Telephon: 4157300
McDonald, Amanda Telephon: 8435150
McDonald, Stacey Telephon: 3327563
McDonald, Stacey Telephon: 7764987
Wellington, John Telephon: 9207404

Vvedite familiu: Bartoski
Vvedite imya: Z
!!!Z
Chislo ludei s takim imenem: 0
Тест 3
Chislo zapisei: 8
Bartoski, Peter Telephon: 6946473
Deauville, William Telephon: 8435150
Fredericks, Roger Telephon: 7049982
KuangThu, Bruce Telephon: 4157300
McDonald, Amanda Telephon: 8435150
McDonald, Stacey Telephon: 3327563
McDonald, Stacey Telephon: 7764987
Wellington, John Telephon: 9207404

Vvedite familiu: Bartoski
Vvedite imya: Peter
Chislo ludei s takim imenem: 1
Bartoski, Peter Telephon: 6946473
Что мы видем? То что он используется дважды. Сначала для сравнения p1<p2 затем p2<p1 если оба раза вернулось false значит == есть true.
Цитата Сообщение от Pavel.fromBy Посмотреть сообщение
Откуда программе знать, что там именно ==, а не > ?
отсюда программе и знать
Pavel.fromBy
 Аватар для Pavel.fromBy
13 / 13 / 1
Регистрация: 31.12.2011
Сообщений: 83
08.01.2012, 01:57  [ТС]     Ассоц. и послед. контейнеры. Разница в методах и алгоритмах. #14
Спасибо всем! Отдельное спасибо greeezz! Вопрос закрыт...

Не по теме:

Сам бы на додумался

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.01.2012, 14:12     Ассоц. и послед. контейнеры. Разница в методах и алгоритмах.
Еще ссылки по теме:

Контейнеры с++ C++
Контейнеры C++
Передача сообщения в поток для послед. записи в файл C++

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

Или воспользуйтесь поиском по форуму:
Pavel.fromBy
 Аватар для Pavel.fromBy
13 / 13 / 1
Регистрация: 31.12.2011
Сообщений: 83
31.01.2012, 14:12  [ТС]     Ассоц. и послед. контейнеры. Разница в методах и алгоритмах. #15
Столкнулся с еще одним вопросом (по этой же теме). Выше я писал код программы - речь пойдет о ней. При вставке (insert) во множество элементов немного не догоняю, как оно их сортирует. В operator< () я добавил строку
C++
1
cout << p1.lastName << "--" << p2.lastName << endl;
и увидел следующее:
McDonald--Deauville (operator< () вернет false, okay....)
!!!Почему нету сравнения McDonald--Deauville (вдруг McDonald == Deauville) !?
Bartoski--Deauville (operator< () вернет true, okay....)
Deauville--Bartiski (здесь false, зачем ЭТО сравнение!?!?!?! Из предыдущего уже было понятно, что оно СТРОГО < !!!)
......
и т.д.
......
Т.е. при вставке, если "вставляемый" < "имеющегося" возвращает false, то операция "имеющийся" < "вставляемого" не производится. А когда "вставляемый" < "имеющегося" возвращает true, то бессмысленное сравнение "имеющийся" < "вставляемого" производится.
Прошу вкратце объяснить, почему так происходит. Как я понял - это связано с тем, при помощи какой структуры данных (а именно какого дерева) МУЛЬТИМНОЖЕСТВО хранит в себе элементы. Заранее благодарен.

p.s. Код программы:
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
// setpers.cpp
// Применение мультимножества для хранения объектов person
#pragma warning (disable:4786)     // для множеств (для
                                   // компиляторов фирмы Microsoft)
#include <iostream>
#include <set>
#include <string>
#include <iomanip>
using namespace std;
 
class person
   {
   private:
      string lastName;
      string firstName;
      long phoneNumber;
   public:                         // конструктор по умолчанию
      person() : lastName("пусто"),
                 firstName("пусто"), phoneNumber(0)
         {  }
                                   // конструктор с тремя параметрами
      person(string lana, string fina, long pho) :
              lastName(lana), firstName(fina), phoneNumber(pho)
         {  }
      friend bool operator<(const person&, const person&);
      friend bool operator==(const person&, const person&);
 
      void display() const         // вывод данных о людях
         {
         cout << endl << lastName << ",\t" << firstName
              << "\t\tТелефон: " << phoneNumber;
         }
   };
                                   // оператор < для класса person
bool operator<(const person& p1, const person& p2)
   {
   cout << "Compare: " << setw(10) << left << p1.lastName << ' ' << p2.lastName << endl << right;
   if(p1.lastName == p2.lastName)
      return (p1.firstName < p2.firstName) ? true : false;
   return (p1.lastName < p2.lastName) ? true : false;
   }
                                   // оператор == для класса person
bool operator==(const person& p1, const person& p2)
   {
       cout << "operator==()" << endl;
   return (p1.lastName == p2.lastName &&
           p1.firstName == p2.firstName ) ? true : false;
   }
///////////////////////////////////////////////////////////
int main()
   {                               // создание объектов person
       setlocale(LC_ALL, "rus");
   person pers1("Deauville", "William", 8435150);
   person pers2("McDonald", "Stacey", 3327563);
   person pers3("Bartoski", "Peter", 6946473);
   person pers4("KuangThu", "Bruce", 4157300);
   person pers5("Wellington", "John", 9207404);
   person pers6("McDonald", "Amanda", 8435150);
   person pers7("Fredericks", "Roger", 7049982);
   person pers8("McDonald", "Stacey", 7764987);
                                   // мультимножество класса person
   multiset< person, less<person> > persSet;
                                   // итератор этого мультимножества
   multiset<person, less<person> >::iterator iter;
 
   persSet.insert(pers1);          // занести объекты person в
                                   //мультимножество
   persSet.insert(pers2);
   persSet.insert(pers3);
   persSet.insert(pers4);
   persSet.insert(pers5);
   persSet.insert(pers6);
   persSet.insert(pers7);
   persSet.insert(pers8);
 
   cout << "\nЧисло записей: " << persSet.size();
 
   iter = persSet.begin();         //Вывод содержимого
                                   //  мультимножества
   while( iter != persSet.end() )
      (*iter++).display();
                                   // получение имени и фамилии
   string searchLastName, searchFirstName;
   cout << "\n\nВведите фамилию искомого человека: ";
   cin >> searchLastName;
   cout << "Введите имя: ";
   cin >> searchFirstName;
        // создание объекта с заданными значениями атрибутов
   person searchPerson(searchLastName, searchFirstName, 0);
        // сосчитать количество людей с таким именем
   int cntPersons = persSet.count(searchPerson);
   cout << "Число людей с таким именем: " << cntPersons;
 
        // вывести все записи, отвечающие запросу
   iter = persSet.lower_bound(searchPerson);
   while( iter != persSet.upper_bound(searchPerson) )
      (*iter++).display();
   cout << endl;
   return 0;
   }    // end main()
Yandex
Объявления
31.01.2012, 14:12     Ассоц. и послед. контейнеры. Разница в методах и алгоритмах.
Ответ Создать тему
Опции темы

Текущее время: 23:55. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru