Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / C++ [игнор отключен] [закрыт для гостей] / Weak strict ordering для std::set / 3 сообщений из 3, страница 1 из 1
07.09.2017, 15:09
    #39517443
07092017
07092017
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Weak strict ordering для std::set
Здравствуйте,

Для пары двух чисел <x, y> надо чтобы:
равенство проверялось по x
больше или меньше по y, если y равны, то по x

создал структуру:

Код: plaintext
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.
struct XY {
	size_t x, y;
	XY(size_t x, size_t y) : x(x), y(y) {}
	friend bool operator<(const XY &left_, const XY &right_) {
		if (left_ == right_) return false;
		if (left_.y == right_.y) return left_.x < right_.x;
		return left_.y < right_.y;
	}
	friend bool operator==(const XY &left_, const XY &right_) {
		return left_.x == right_.x;
	}
	friend std::ostream& operator<<(std::ostream &strm, const XY &xy) {
		strm << "[" << xy.x << ":" << xy.y << "]";
		return strm;
	}
};

int main()
{
	std::set<XY> pq;

	pq.emplace(1, 2);
	pq.emplace(1, 3);
	pq.emplace(1, 4);
	pq.emplace(2, 1);
	pq.emplace(3, 4);
	pq.emplace(4, 4);
	pq.emplace(5, 4);
	pq.emplace(6, 4);
	pq.emplace(7, 4);

	for (auto &i : pq) {
		std::cout << i << " ";
	}
	std::cout << std::endl;

	std::set<XY>::iterator i;
	std::cout << std::boolalpha 
		<< (pq.end() != (i = pq.find(XY(1, 0)))) << "\n"
		<< (pq.end() != (i = pq.find(XY(2, 0)))) << "\n"
		<< (pq.end() != (i = pq.find(XY(3, 0)))) << "\n"
		<< (pq.end() != (i = pq.find(XY(4, 0)))) << "\n"
		<< (pq.end() != (i = pq.find(XY(5, 0)))) << "\n"
		<< (pq.end() != (i = pq.find(XY(6, 0)))) << "\n"
		<< (pq.end() != (i = pq.find(XY(7, 0)))) << "\n";

	pq.clear();
	pq.emplace(2, 2);
	pq.emplace(1, 3);

	for (auto &i : pq) {
		std::cout << i << " ";
	}
	std::cout << std::endl;

	std::cout << std::boolalpha 
		<< (pq.end() != (i = pq.find(XY(1, 0)))) << "\n"
		<< (pq.end() != (i = pq.find(XY(2, 0)))) << "\n";
}



Вывод программы:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
[2:1] [1:2] [3:4] [4:4] [5:4] [6:4] [7:4]
false
true   //x == 2 находит, элемент первый в списке
false
false
false
false
false
[2:2] [1:3]
false
true   //x == 2 находит, элемент первый в списке



При таком сравнении, которое определенно в структуре XY, std::set сортирует и вставляет элементы так, как надо.
Проблема в том, что если использовать поиск от std::set, то находит только первый элемент. std::set реализован, как бинарное дерево, возможно ли составить корректное сравнение с такими условиями, чтобы поиск проходил успешно.
Интересен вариант для поиска именно по бинарному дереву(std::set), простой поиск std::find работает.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.09.2017, 16:34
    #39517554
compare
compare
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Weak strict ordering для std::set
Код: plaintext
1.
2.
3.
4.
5.
6.
template<
     typename _Key
    ,typename _Compare = std::less<_Key>
    ,typename _Alloc = std::allocator<_Key> 
  >
class set
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
08.09.2017, 16:15
    #39518318
MasterZiv
MasterZiv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Weak strict ordering для std::set
07092017
При таком сравнении, которое определенно в структуре XY, std::set сортирует и вставляет элементы так, как надо.
Проблема в том, что если использовать поиск от std::set, то находит только первый элемент. std::set реализован, как бинарное дерево, возможно ли составить корректное сравнение с такими условиями, чтобы поиск проходил успешно.
Интересен вариант для поиска именно по бинарному дереву(std::set), простой поиск std::find работает.

Мультисет ?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / C++ [игнор отключен] [закрыт для гостей] / Weak strict ordering для std::set / 3 сообщений из 3, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]