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

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

Восстановить пароль Регистрация
 
 
Renji
1535 / 983 / 240
Регистрация: 05.06.2014
Сообщений: 2,963
23.07.2014, 14:09     Требуется собрать кучу object в один контейнер и искать их по object_name #1
Пусть дана структура вида:
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++ Нужно последовательно собрать их в один динамический массив.
про кучу и не кучу C++
C++ необходимо в шаблонном классе, один из параметров которого контейнер, объявить итератор этого контейнера
Найти, какое минимальное число поворотов на один зубчик требуется сделать, чтобы шестеренки вернулись в исходное состояние C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
23.07.2014, 14:26     Требуется собрать кучу object в один контейнер и искать их по object_name #2
Renji, Стоп. Причем тут set? Вы храните их в set? Если нет, то чем не нравится std::find?
Renji
1535 / 983 / 240
Регистрация: 05.06.2014
Сообщений: 2,963
23.07.2014, 14:33  [ТС]     Требуется собрать кучу object в один контейнер и искать их по object_name #3
Renji, Стоп. Причем тут set? Вы храните их в set? Если нет, то чем не нравится std::find?
std::find не нравится линейным временем поиска. Поэтому я даже как-то и не подумал о том, что его можно использовать в принципе.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
23.07.2014, 14:45     Требуется собрать кучу object в один контейнер и искать их по object_name #4
Renji, В set до С++14 нет возможности вызвать find без объекта типа ключа.
Если не подходит отсортированный вектор, то почему не подойдет отсортированный лист к примеру?
Renji
1535 / 983 / 240
Регистрация: 05.06.2014
Сообщений: 2,963
23.07.2014, 15:16  [ТС]     Требуется собрать кучу object в один контейнер и искать их по object_name #5
Если не подходит отсортированный вектор, то почему не подойдет отсортированный лист к примеру?
Потому что лист - двусвязный список с bidirectional iterator, в котором принципиально невозможен никакой поиск кроме последовательного (с линейным временем работы). Хоть сортируй его, хоть в масле вари, random access iterator как в векторе или древовидной структуры как в std::map там не появится.
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
23.07.2014, 15:32     Требуется собрать кучу object в один контейнер и искать их по object_name #6
А что если сделать нечто такое:
C++
1
2
3
4
5
class Proxy
{
    // нужные конструкторы и операторы сравнения делегируются в ptr
    std::unique_ptr<object> ptr; 
}
Ну, а дальше уже std::set<Proxy>
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
23.07.2014, 15:35     Требуется собрать кучу object в один контейнер и искать их по object_name #7
Renji, Вообщем, подытожим, нет нормальных вариантов сделать поиск в set-е без создания объекта. В бусте тоже нет. Либо ждите С++14, либо идите на компромиссы с производительностью / ищите другие либы.

Добавлено через 1 минуту
Tulosba, В таком раскладе насколько я понимаю нужно будет создавать при поиске новый Proxy и ptr должен будет быть создан.
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
23.07.2014, 15:52     Требуется собрать кучу object в один контейнер и искать их по object_name #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
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
23.07.2014, 16:02     Требуется собрать кучу object в один контейнер и искать их по object_name #9
Tulosba, По-моему довольно слабое отличие от std::map, который автору не подходит или я ошибаюсь?
Voivoid
 Аватар для Voivoid
580 / 256 / 12
Регистрация: 31.03.2013
Сообщений: 1,284
23.07.2014, 16:09     Требуется собрать кучу object в один контейнер и искать их по object_name #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
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
23.07.2014, 16:12     Требуется собрать кучу object в один контейнер и искать их по object_name #11
Voivoid, А вот это верно. Что-то зря я отмел upper/lower_bound-ы.
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
23.07.2014, 16:20     Требуется собрать кучу object в один контейнер и искать их по object_name #12
Цитата Сообщение от ForEveR Посмотреть сообщение
По-моему довольно слабое отличие от std::map, который автору не подходит или я ошибаюсь?
Всё верно. Ну и п.2 нарушается.
Voivoid
 Аватар для Voivoid
580 / 256 / 12
Регистрация: 31.03.2013
Сообщений: 1,284
23.07.2014, 16:20     Требуется собрать кучу object в один контейнер и искать их по object_name #13
Цитата Сообщение от Voivoid Посмотреть сообщение
return x1.object_name == x2;
Тут конечно должно быть <, а не ==
Renji
1535 / 983 / 240
Регистрация: 05.06.2014
Сообщений: 2,963
23.07.2014, 16:22  [ТС]     Требуется собрать кучу object в один контейнер и искать их по object_name #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
 Аватар для Voivoid
580 / 256 / 12
Регистрация: 31.03.2013
Сообщений: 1,284
23.07.2014, 16:27     Требуется собрать кучу object в один контейнер и искать их по object_name #15
del
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
23.07.2014, 16:32     Требуется собрать кучу object в один контейнер и искать их по object_name #16
Цитата Сообщение от Renji Посмотреть сообщение
дублируется ключ сортировки, чего и хотелось избежать.
А если и на него указатель завести? Т.е. если создаем proxy с object != nullptr, то используем указатель на object->name, иначе (как при поиске) - полноценный std::string.
Voivoid
 Аватар для Voivoid
580 / 256 / 12
Регистрация: 31.03.2013
Сообщений: 1,284
23.07.2014, 16:43     Требуется собрать кучу object в один контейнер и искать их по object_name #17
Ну, тогда boost::unordered_set как вариант, там методу find можно предикат передать
Renji
1535 / 983 / 240
Регистрация: 05.06.2014
Сообщений: 2,963
23.07.2014, 17:18  [ТС]     Требуется собрать кучу object в один контейнер и искать их по object_name #18
А если и на него указатель завести? Т.е. если создаем proxy с object != nullptr, то используем указатель на object->name, иначе (как при поиске) - полноценный std::string.
Костыль, конечно, но похоже это единственное решение без написания своего std::set.
Ну, тогда boost::unordered_set как вариант, там методу find можно предикат передать
Попробовал. find скушало std::string как аргумент... И все равно полезло преобразовывать его в object.
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
#include<string>
#include<boost/unordered_set.hpp>
using namespace std;
struct object
{
    bool operator<(const object&o)const{return object_name<o.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;}
    bool operator==(const std::string&str)const{return object_name==str;}
    std::string object_name;
    char some_data[100500];
private://чтоб нельзя было выполнить преобразование строки в object
    object(const std::string&_object_name):object_name(_object_name){}
};
 
struct hash_value{int operator()(const object&str)const{return str.object_name.size();}};
struct compare{bool operator()(const object&o1,const object&o2)const{return o1==o2;}};
 
int main()
{
    boost::unordered_set<object> my_set;
    const std::string key("1234");
    my_set.find<std::string,hash_value,compare>(key,hash_value(),compare());
    return 0;
}
error: 'object::object(const string&)' is private. То есть, буст полез выполнять преобразование и обломался.
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
23.07.2014, 17:32     Требуется собрать кучу object в один контейнер и искать их по object_name #19
Цитата Сообщение от Renji Посмотреть сообщение
private://чтоб нельзя было выполнить преобразование строки в object
тут вероятно следует просто explicit конструктор сделать.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.07.2014, 17:44     Требуется собрать кучу object в один контейнер и искать их по object_name
Еще ссылки по теме:

Чем дальше в лес, тем больше дров. Не соображу, как собрать в кучу C++
C++ Как можно теперь взять и собрать группу из 4-х байтов в один float?
Как собрать файлы в кучу? C++

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

Или воспользуйтесь поиском по форуму:
Renji
1535 / 983 / 240
Регистрация: 05.06.2014
Сообщений: 2,963
23.07.2014, 17:44  [ТС]     Требуется собрать кучу object в один контейнер и искать их по object_name #20
Попробовал. find скушало std::string как аргумент... И все равно полезло преобразовывать его в object.
UPD Туплю. Сделал так и заработало:
C++
1
2
3
4
5
6
7
8
9
struct hash_value{
    int operator()(const object&str)const{return str.object_name.size();}
    int operator()(const std::string&str)const{return str.size();}
};
struct compare{
    bool operator()(const object&o1,const object&o2)const{return o1==o2;}
    bool operator()(const object&o1,const std::string&o2)const{return o1==o2;}
    bool operator()(const std::string&o1,const object&o2)const{return o2==o1;}
};
Yandex
Объявления
23.07.2014, 17:44     Требуется собрать кучу object в один контейнер и искать их по object_name
Ответ Создать тему
Опции темы

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