Раз пошла такая особая логика
May. 13th, 2009 03:39 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
spamsinkФён.
(C++) Есть у нас объекты двух классов: Master и Slave. У Slave есть метод Master* getMaster(). Есть у нас два списка указателей на эти классы: masterList и slaveList, причем известно, что на каждый объект из masterList ссылается не более одного объекта из slaveList. Нужно построить какой-нибудь sortedSlaveContainer (той же мощности, что и masterList), в котором для любого не-NULL элемента его расстояние от головы контейнера равно расстоянию его мастера от головы masterList.
Индийское решение:
1. Создаем вектор структур (Master*master, Slave*slave, int index), заполняем из masterList, инкрементируя index. Поле slave = NULL.
2. Сортируем этот вектор по значению указателя master.
3. Проходим по slaveList, находя соответствующий Master в векторе с помощью двоичного поиска (std::lower_bound!) и заполняя поле slave.
4. Сортируем вектор по полю index.
5. Из полей slave полученного вектора создаем sortedSlaveList.
6. Profit!
(C++) Есть у нас объекты двух классов: Master и Slave. У Slave есть метод Master* getMaster(). Есть у нас два списка указателей на эти классы: masterList и slaveList, причем известно, что на каждый объект из masterList ссылается не более одного объекта из slaveList. Нужно построить какой-нибудь sortedSlaveContainer (той же мощности, что и masterList), в котором для любого не-NULL элемента его расстояние от головы контейнера равно расстоянию его мастера от головы masterList.
Индийское решение:
1. Создаем вектор структур (Master*master, Slave*slave, int index), заполняем из masterList, инкрементируя index. Поле slave = NULL.
2. Сортируем этот вектор по значению указателя master.
3. Проходим по slaveList, находя соответствующий Master в векторе с помощью двоичного поиска (std::lower_bound!) и заполняя поле slave.
4. Сортируем вектор по полю index.
5. Из полей slave полученного вектора создаем sortedSlaveList.
6. Profit!
