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

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

Войти
Регистрация
Восстановить пароль
 
Dormeo
0 / 0 / 0
Регистрация: 31.01.2013
Сообщений: 8
#1

Выбор контейнера - C++

31.01.2013, 04:05. Просмотров 704. Ответов 16
Метки нет (Все метки)

Есть два варианта.

Первый:

C++
1
2
3
4
5
    map <pair <int,int>, int> my_map;
 
    map <pair <int,int>, int>::iterator p;
 
    p = my_map.find(make_pair(100,150));
Второй:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
    struct Object
    {
        int x;
        int y;
        int id;
    };
 
    list <Object> my_list;
 
    list <Object>::iterator pp;
 
    for(list<Object>::iterator it = my_list.begin(); it!=my_list.end(); ++it)
    {
        Object & obj = (*it);
 
        if (obj.x == 100 && obj.y == 150)
        {
            pp = it;
            break;
        }
    }
В каждом контейнере будет примерно по 300 групп данных.

Подскажите пожалуйста, какой контейнер выбрать, чтобы скорость поиска была повыше.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.01.2013, 04:05     Выбор контейнера
Посмотрите здесь:

Выбор контейнера в STL - C++
Здраствуйте! Нужно выбрать к этой задаче контейнер STL, который более выгодно подойдет, кроме вектора. Я думаю, что deque или map Помогите...

Выбор контейнера для хранения структуры - C++
Доброе время суток! Ребят нужна помочишь при выборе контейнера для хранения структуры, точнее трех структур! Первая, (если кому...

Из STL контейнера - C++
Из STL контейнера создать 3-х мерный массив и класс который содержит этот 3-х мерный массив и вывод координат(пользователь вводит...

сapacity контейнера - C++
Почему максимальное кол-во элементов увеличивается в 1,5 раза с каждым разом, когда необходимо увеличить объём? Почему именно в 1,5 раза? ...

Наследование контейнера - C++
А можно ли создать класс, который будет наследовать все функции от vector'a, и собрать его в dll, чтобы подключить на C#?

Написание собственного контейнера - C++
Доброго времени суток ! Помогите написать собственный контейнер, основанный на STL, ибо сам с этой задачей никогда не сталкивался,...

Сортировка контейнера list - C++
Как отсортировать (с помощью sort()) и вывести в текстовый документ список l ? код программы: #include &lt;iostream.h&gt; #include &lt;vector&gt;...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dr.Urban
63 / 58 / 7
Регистрация: 14.12.2011
Сообщений: 193
31.01.2013, 04:11     Выбор контейнера #2
Однозначно первый..Не вижу вариантов когда лист хорош по поиску.ИМХО

Да и красно-черное дерево для этого и нужно...
Croessmah
Модератор
Эксперт CЭксперт С++
13045 / 7308 / 814
Регистрация: 27.09.2012
Сообщений: 18,041
Записей в блоге: 3
Завершенные тесты: 1
31.01.2013, 04:18     Выбор контейнера #3
Цитата Сообщение от Dormeo Посмотреть сообщение
Есть два варианта.
Может стоит совместить?
C++
1
map<Object,int>
Dormeo
0 / 0 / 0
Регистрация: 31.01.2013
Сообщений: 8
31.01.2013, 04:25  [ТС]     Выбор контейнера #4
Цитата Сообщение от Croessmah Посмотреть сообщение
Может стоит совместить?
C++
1
map<Object,int>
Не стОит. Потому что, id во втором примере и есть map <pair <int,int>, int> my_map;
Его я при поиске в контейнере знать не буду. Соответственно не смогу корректно построить объект для поиска. Но за сообщение спасибо
Croessmah
Модератор
Эксперт CЭксперт С++
13045 / 7308 / 814
Регистрация: 27.09.2012
Сообщений: 18,041
Записей в блоге: 3
Завершенные тесты: 1
31.01.2013, 04:54     Выбор контейнера #5
Цитата Сообщение от Dormeo Посмотреть сообщение
Соответственно не смогу корректно построить объект для поиска. Но за сообщение спасибо
а подумать?

Объясню по другому:
C++
1
2
3
4
5
6
7
    struct Object
    {
        int x;
        int y;
    };
//...
std::map<Object,int> mmm;

[и не нужно выделять текст таким способом - слепых нет]
Dormeo
0 / 0 / 0
Регистрация: 31.01.2013
Сообщений: 8
31.01.2013, 05:05  [ТС]     Выбор контейнера #6
Цитата Сообщение от Croessmah Посмотреть сообщение
а подумать?

Объясню по другому:
C++
1
2
3
4
5
6
7
    struct Object
    {
        int x;
        int y;
    };
//...
std::map<Object,int> mmm;
Croessmah, спасибо. Можно и так. Какие плюсы с такого совмещения? Ясность кода из-за названий членов структуры?

Цитата Сообщение от Croessmah Посмотреть сообщение
[и не нужно выделять текст таким способом - слепых нет]
Извиняюсь, больше не буду.
Croessmah
Модератор
Эксперт CЭксперт С++
13045 / 7308 / 814
Регистрация: 27.09.2012
Сообщений: 18,041
Записей в блоге: 3
Завершенные тесты: 1
31.01.2013, 05:11     Выбор контейнера #7
Цитата Сообщение от Dormeo Посмотреть сообщение
Ясность кода из-за названий членов структуры?
Это да.
Плюс ко всему, если Вам вдруг вздумается добавить туда еще одну переменную, например, координату z, тогда в Вашем варианте придется делать
C++
1
std::map<std::pair<std::pair<int,int>,int>,int> obj;//как-то так?
а в моем просто добавить координату z в структуру.
плюс ко всему плюшки от наследования и полиморфизма можно получить при соответствующей структуры программы
Dormeo
0 / 0 / 0
Регистрация: 31.01.2013
Сообщений: 8
31.01.2013, 05:51  [ТС]     Выбор контейнера #8
Покажите пожалуйста пример поиска в контейнере map с ключом в виде структуры Object.
Somebody
2786 / 1600 / 145
Регистрация: 03.12.2007
Сообщений: 4,189
Завершенные тесты: 1
31.01.2013, 14:23     Выбор контейнера #9
Цитата Сообщение от Dormeo Посмотреть сообщение
пример поиска в контейнере map с ключом в виде структуры Object
Ничем не отличается от варианта с std::pair, только операторы == и < надо сделать.
C++
1
2
3
4
5
6
7
8
9
bool operator==(const Object& lhs, const Object& rhs)
{
    return lhs.x == rhs.x && lhs.y < rhs.y;
}
 
bool operator<(const Object& lhs, const Object& rhs)
{
    return lhs.x < rhs.x || (lhs.x == rhs.x && lhs.y < rhs.y);
}
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
31.01.2013, 14:26     Выбор контейнера #10
Somebody, А можно и компаратор...
Dormeo
0 / 0 / 0
Регистрация: 31.01.2013
Сообщений: 8
31.01.2013, 19:46  [ТС]     Выбор контейнера #11
Есть структуры данных такого типа:

C++
1
2
3
4
5
6
7
struct Object
{
    int x;
    int y;
    int unique_id;
    int weight;
};
Помогите пожалуйста подобрать оптимальный способ хранения этих данных.

- x и y могут быть одинаковые у разных структур
- unique_id уникальный у всех
- частый поиск структур отдельно по unique_id и (x && y)
- относительно частое добавление и удаление структур

Что посоветуете использовать в этой ситуации?
grindaah
20 / 20 / 0
Регистрация: 25.05.2011
Сообщений: 62
31.01.2013, 20:28     Выбор контейнера #12
Все равно map. Для поиска по x,y отдельный функтор
Dormeo
0 / 0 / 0
Регистрация: 31.01.2013
Сообщений: 8
01.02.2013, 00:33  [ТС]     Выбор контейнера #13
В таком случае покажите мне пожалуйста, как допилить поиск по (x & y).

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
#include <map>
 
struct Object
{
    int x;
    int y;
    int unique_id;
    int weight;
};
 
bool operator<(const Object& lhs, const Object& rhs)
{
    return lhs.unique_id < rhs.unique_id;
}
 
int main ()
{
    std::map <Object,int> my_map;
 
    std::map <Object,int>::iterator it;
 
    Object obj = {11, 22, 33, 44};
 
    it = my_map.find(obj);
 
    return 0;
}
DU
1481 / 1057 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
01.02.2013, 00:45     Выбор контейнера #14
если значение не предполагается, то вместо мапы можно set юзать.
а использовать один ассоциативный контейнер с быстрым поиском по двум разным критериям (по id и по x&&y) не выйдет. внутри контейнеров элементы расставлены по одному признаку. и поиск рассчитывает ищут элемент по этому же признаку. поэтому тут или использовать второй контейнер или использовать последовательный std::find_if.
ну или может быть в бусте есть ченибудь "мультикритерийное"
Dormeo
0 / 0 / 0
Регистрация: 31.01.2013
Сообщений: 8
01.02.2013, 00:51  [ТС]     Выбор контейнера #15
Цитата Сообщение от DU Посмотреть сообщение
если значение не предполагается, то вместо мапы можно set юзать.
Да, не предполагается.

Цитата Сообщение от DU Посмотреть сообщение
ну или может быть в бусте есть ченибудь "мультикритерийное"
Уже нашел в Boost - bidirectional_map. В крайнем случае буду разбиратся с ним.
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
01.02.2013, 11:44     Выбор контейнера #16
Dormeo, Тут скорее multi_index покатит. Хотя map тоже может.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.02.2013, 15:22     Выбор контейнера
Еще ссылки по теме:

Разработка класса контейнера - C++
День добрый. В общем у меня есть программа, программный код приведу ниже. Класс Очередь (CQueue) с такими же методами, как и класс...

Очистка контейнера vector - C++
Доброго времени суток господа программисты. У меня возникла дилемма. В общем, у меня есть вектор std::vector&lt;std::vector&lt;int&gt; &gt; grid;...

Использование контейнера list - C++
Не могу из методички с задачками по контейнерам решить пару из них. Есть список целых чисел (std::list&lt;int&gt;). Нужно, за один...

Использование стороннего контейнера - C++
Помогите из этого кода, сделать нормальную прогу #ifndef _GLIBCXX_ARRAY #define _GLIBCXX_ARRAY 1 #pragma GCC system_header ...

Использование контейнера map - C++
Доброе утро) Никак не пойму как пользоваться контейнером map и зачем он, вообще, нужен?! Скажем есть у меня такая программа(или точнее...


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

Или воспользуйтесь поиском по форуму:
Dormeo
0 / 0 / 0
Регистрация: 31.01.2013
Сообщений: 8
01.02.2013, 15:22  [ТС]     Выбор контейнера #17
ForEveR, спасибо. Можно и так. Я просто данные разбил на две структуры. Одна в качестве ключа, другая в качестве значения. Поиск есть и там и там. Boost это вещь.
Yandex
Объявления
01.02.2013, 15:22     Выбор контейнера
Ответ Создать тему
Опции темы

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