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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Renji
1901 / 1299 / 291
Регистрация: 05.06.2014
Сообщений: 3,718
#1

Требуется собрать кучу object в один контейнер и искать их по object_name - C++

23.07.2014, 14:09. Просмотров 671. Ответов 21
Метки нет (Все метки)

Пусть дана структура вида:
C++
1
2
3
4
5
6
7
8
struct object
{
    object(const std::string&_object_name):object_name(_object_name){}
    bool operator<(const object&o)const{return object_name<o.object_name;}
    bool operator<(const std::string&str)const{return object_name<str;}
    std::string object_name;
    char some_data[100500];
};
Требуется собрать кучу object в один контейнер и искать их по object_name. При этом хочется соблюдать следующие условия:
1) У object должен сохраниться доступ к своему object_name.
2) object_name не должен дублироваться в каких-то внутренних индексах контейнера (потому что возможен алгоритм обходящийся без дублирования). То есть, std::map хранящий ключ сортировки отдельно не подходит.
3) find(object_name) не должно требовать преобразования object_name из std::string в object (там some_data на 100500 байт).
4) Вставка нового элемента не должна делать ссылки на существующие элементы невалидными (отсортированный вектор object не подойдет).

Реализуемо ли это какими-то готовыми библиотеками (например, boost)? И ясно, вроде, что алгоритмически это ничем принципиально не отличается от std::set. Но как я понимаю, find в std::set<object> принимает только аргумент типа object. Пусть даже есть operator< позволяющий сравнивать object напрямую с std::string.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.07.2014, 14:09
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Требуется собрать кучу object в один контейнер и искать их по object_name (C++):

Как собрать файлы в кучу? - C++
В книге Страуструпа для начинающих, в 8 главе квест, на создание заголовочного файла, и два сpp файла тк вот В папке с...

Чем дальше в лес, тем больше дров. Не соображу, как собрать в кучу - C++
К окончанию курсов по С++ нам приурочили мини-дипломную работу. Сначала я посчитала, что ничего сложного в этом нет. Но по мере моих...

Собрать кучу файлов в один файл Excel - C#
Добрый день! И снова смиренно прошу советов гуру. Исходные данные: около 600 файлов формата csv(3 параметра в строчке) Задача: Собрать...

VBA EXCEL: Собрать кучу файлов в один - VBA
В папке находится куча xls файлов. У всех у них одинаковая структура. Но она может меняться периодически. Необходимо все файлы собрать в...

Notepad++ как собрать все ссылки со страницы в одну кучу? - Софт
Добрый день! Как в Notepad++ можно собрать все ссылки, присутствующие на странице и положить в самый низ? То есть мне нужно записать...

Подскажите, где нужно искать конструктор класса Object? - Java SE
Всем привет! Изучаю java совсем недавно. Заинтересовал один фундаментальный момент - в исходнике класса Object нет конструктора, хотя, по...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
23.07.2014, 14:26 #2
Renji, Стоп. Причем тут set? Вы храните их в set? Если нет, то чем не нравится std::find?
Renji
1901 / 1299 / 291
Регистрация: 05.06.2014
Сообщений: 3,718
23.07.2014, 14:33  [ТС] #3
Renji, Стоп. Причем тут set? Вы храните их в set? Если нет, то чем не нравится std::find?
std::find не нравится линейным временем поиска. Поэтому я даже как-то и не подумал о том, что его можно использовать в принципе.
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
23.07.2014, 14:45 #4
Renji, В set до С++14 нет возможности вызвать find без объекта типа ключа.
Если не подходит отсортированный вектор, то почему не подойдет отсортированный лист к примеру?
Renji
1901 / 1299 / 291
Регистрация: 05.06.2014
Сообщений: 3,718
23.07.2014, 15:16  [ТС] #5
Если не подходит отсортированный вектор, то почему не подойдет отсортированный лист к примеру?
Потому что лист - двусвязный список с bidirectional iterator, в котором принципиально невозможен никакой поиск кроме последовательного (с линейным временем работы). Хоть сортируй его, хоть в масле вари, random access iterator как в векторе или древовидной структуры как в std::map там не появится.
Tulosba
:)
Эксперт С++
4393 / 3236 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
23.07.2014, 15:32 #6
А что если сделать нечто такое:
C++
1
2
3
4
5
class Proxy
{
    // нужные конструкторы и операторы сравнения делегируются в ptr
    std::unique_ptr<object> ptr; 
}
Ну, а дальше уже std::set<Proxy>
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
23.07.2014, 15:35 #7
Renji, Вообщем, подытожим, нет нормальных вариантов сделать поиск в set-е без создания объекта. В бусте тоже нет. Либо ждите С++14, либо идите на компромиссы с производительностью / ищите другие либы.

Добавлено через 1 минуту
Tulosba, В таком раскладе насколько я понимаю нужно будет создавать при поиске новый Proxy и ptr должен будет быть создан.
Tulosba
:)
Эксперт С++
4393 / 3236 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
23.07.2014, 15:52 #8
ForEveR, с std::unique_ptr я, вероятно, погорячился. Вот такой вариант вижу в первом приближении:
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
#include <iostream>
#include <string>
#include <set>
 
struct object
{
    object(const std::string&_object_name):object_name(_object_name){}
    bool operator<(const object&o)const{return object_name<o.object_name;}
    bool operator<(const std::string&str)const{return object_name<str;}
    std::string object_name;
    char some_data[100500];
};
 
class proxy
{
public:
    proxy( const std::string& name, object* ptr = nullptr ) 
    : name_(name), ptr_(ptr) {}
    bool operator<(const proxy& rhs) const { return name_ < rhs.name_; }
    std::string name() const { return name_; }
private:
    const std::string name_;
    object* ptr_;
};
 
int main() {
 
    proxy one( "john", new object("john") );
    proxy two( "jane", new object("jane") );
 
    std::multiset<proxy> ms = { one, two };
 
    proxy f("jane");
    
    auto it = ms.find(f);
    if( it != ms.end() )
    {
        std::cout << it->name() << std::endl;
    }
    else
    {
        std::cout << "not found\n";
    }
 
    return 0;
}
http://ideone.com/xdlxaI
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
23.07.2014, 16:02 #9
Tulosba, По-моему довольно слабое отличие от std::map, который автору не подходит или я ошибаюсь?
Voivoid
674 / 277 / 12
Регистрация: 31.03.2013
Сообщений: 1,339
23.07.2014, 16:09 #10
Цитата Сообщение от ForEveR Посмотреть сообщение
нет нормальных вариантов сделать поиск в set-е без создания объекта
Как это нет, std::lower_bound ( ну и др. функции из этого семейства ).

C++
1
2
3
4
  std::set<object> s;
  std::lower_bound( s.cbegin(), s.cend(), "abc", []( const object& x1, const std::string& x2 ) {
    return x1.object_name == x2;
  } );
Или я чет не так понял? Особо не вчитывался в оп-пост, слишком много букф
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
23.07.2014, 16:12 #11
Voivoid, А вот это верно. Что-то зря я отмел upper/lower_bound-ы.
Tulosba
:)
Эксперт С++
4393 / 3236 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
23.07.2014, 16:20 #12
Цитата Сообщение от ForEveR Посмотреть сообщение
По-моему довольно слабое отличие от std::map, который автору не подходит или я ошибаюсь?
Всё верно. Ну и п.2 нарушается.
Voivoid
674 / 277 / 12
Регистрация: 31.03.2013
Сообщений: 1,339
23.07.2014, 16:20 #13
Цитата Сообщение от Voivoid Посмотреть сообщение
return x1.object_name == x2;
Тут конечно должно быть <, а не ==
Renji
1901 / 1299 / 291
Регистрация: 05.06.2014
Сообщений: 3,718
23.07.2014, 16:22  [ТС] #14
ForEveR, с std::unique_ptr я, вероятно, погорячился. Вот такой вариант вижу в первом приближении:
Так здесь в proxy дублируется ключ сортировки, чего и хотелось избежать.
Как это нет, std::lower_bound ( ну и др. функции из этого семейства ).
std::lower_bound работает с итераторами предоставленными std::set, std::set отдает наружу только bidirectional iterator (а как вы двоичное дерево в random-access отобразите?), в результате "On non-random-access iterators, the iterator advances produce themselves an additional linear complexity in N on average.". И опять получаем линейное время работы.
Voivoid
674 / 277 / 12
Регистрация: 31.03.2013
Сообщений: 1,339
23.07.2014, 16:27 #15
del
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.07.2014, 16:27
Привет! Вот еще темы с ответами:

Разбить один m-файл на кучу маленьких m-файлов - Matlab
Здравствуйте. Я не новичок в Matlab. Однако просто раньше такого не требовалось. У меня ну просто огромный программный код в m-файле. Можно...

Заворачивание колонки материалов в один контейнер - HTML, CSS
Здравствуйте. Есть компонент для joomla, K2. Он не выводит материал в две колонки, хотя в joomla все в порядке, материал выводится. Бьюсь...

Программа для шифрования файлов в один контейнер. Оцените реализацию - C#
Приветствую. Написал свою первую программу. Суть такая: Выбираются файлы, добавляются в контейнер(zip) и потом этот контейнер шифруется...

Один контейнер залазит на другой при уменьшении окна браузера - HTML, CSS
Добрый вечер, для удобства размещения блоков использую &quot;flex&quot;, плюс в том что задав &quot;justify-content: space-between;&quot; я могу вставлять еще...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
23.07.2014, 16:27
Ответ Создать тему
Опции темы

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