С наступающим Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 5.00/6: Рейтинг темы: голосов - 6, средняя оценка - 5.00
Bretbas
Каждому свое
521 / 207 / 81
Регистрация: 05.08.2013
Сообщений: 1,610
Завершенные тесты: 2
1

Какой контейнер выбрать?

26.12.2016, 18:46. Просмотров 1082. Ответов 52
Метки нет (Все метки)

Доброго времени суток, Господа. Такая есть задача.
Есть объект Scene, который является контейнером для объектов System и еще наследников. Добавление/Удаление System из System выглядит таким образом:
C++
1
2
3
4
5
6
7
8
...
scene.addSystem<RenderSystem>();
scene.addSystem<PhysicsSystem>();
scene.addSystem<SpriteSystem>();
...
scene.removeSystem<PhysicsSystem>();
...
scene.update();
В Scene все System храняться в std::map контейнере такого типа std::map<std::string,System*>, где ключ является названием системы. В методе update класса scene происходит перебор в цикле всех добавленных систем.
Так вот вопрос в том, что мне нужно выполнять перебор систем в update() в том порядке, в каком я их добавил. А std::map естественно мне сортирует их, и я не получаю на выходе то, чего хотел.

Какой контейнер подойдет в данном случае?

Да и еще, в сцене не должно быть повторяющихся систем! Поэтому std::map тут подходит
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.12.2016, 18:46
Ответы с готовыми решениями:

Какой контейнер выбрать?
Добрый день. Подскажите, какой контейнер стоит выбрать? Пара ключ-значение,...

Какой STL-контейнер выбрать?
Приветствую! Мне нужно выбрать STL-контейнер (C++11), для хранения элементов...

Какой контейнер STL выбрать?
Во входном потоке (FILE*) дано множество точек. Найти пару точек, расстояние...

Какой контейнер выбрать (Нужен массив, с возможностью добавления и удаления элементов)?
Привет, народ! Посоветуйте, что лучше использовать. В моей задаче нужен...

Какой ассоциативный контейнер выбрать? И как реализовать в нем чтение из файла?
Вот сама задание: Текстовый файл содержит следующую информацию: координату...

52
Renji
2129 / 1566 / 477
Регистрация: 05.06.2014
Сообщений: 4,549
26.12.2016, 18:50 2
Самый ленивый вариант - объекты хранятся в std::list в порядке добавления, std::map хранит итераторы указывающие на элементы std::list и отсортированные по нужному ключу.
Более крутой вариант - велосипедить свой std::map с возможностью перебора элементов в порядке добавления. Ну или рыться в Boost, возможно что там что-то готовое на эту тему есть.
1
Bretbas
Каждому свое
521 / 207 / 81
Регистрация: 05.08.2013
Сообщений: 1,610
Завершенные тесты: 2
26.12.2016, 19:17  [ТС] 3
Renji, а что скажете по поводу вот этого:
C++
1
2
3
4
5
6
7
8
9
10
11
12
        template<typename T> T*                     addSystem()                                     
        {
            for( const auto& system : _systems )
            {
                if( dynamic_cast<T*>( system ) != nullptr )
                    return dynamic_cast<T*>( system );
            }
 
            auto system = new T( this );
            _systems.push_back( system ); // std::vector
            return system;
        }
с учетом того, что добавление всех систем будут в начале запуска программы. И частично(редко) будут добавляться/удаляться во время выполнения
0
sourcerer
Модератор
Эксперт CЭксперт С++
4875 / 2061 / 325
Регистрация: 20.02.2013
Сообщений: 5,558
Записей в блоге: 24
Завершенные тесты: 1
26.12.2016, 19:28 4
Bretbas, кроме std::map существует ещё std::unordered_map.
1
Bretbas
Каждому свое
521 / 207 / 81
Регистрация: 05.08.2013
Сообщений: 1,610
Завершенные тесты: 2
26.12.2016, 19:33  [ТС] 5
gru74ik, Друг! Я только учусь. Я пока не знаю как использовать хеш таблицы. Никогда их не использовал
0
Renji
2129 / 1566 / 477
Регистрация: 05.06.2014
Сообщений: 4,549
26.12.2016, 19:34 6
Цитата Сообщение от Bretbas Посмотреть сообщение
с учетом того, что добавление всех систем будут в начале запуска программы. И частично(редко) будут добавляться/удаляться во время выполнения
Вам поиск системы по ее имени нужен или нет? Если да, то представьте себе такую ситуацию - вам надо удалить систему с именем "1234". Сначала вы ищете эту систему в std::map и удаляете из контейнера. Потом вам надо стереть систему из вектора. А для этого нужен итератор указывающий на систему. В варианте с std::list этот итератор лежит готовеньким в std::map. А в варианте с std::vector фокус не сработает, так как итераторы вектора имеют привычку дохнуть от каждого чиха связанного с вставкой/удалением элементов вектора. Придется перерывать ручками весь вектор, выясняя где же там нужная система лежит.

Если же вам поиск по имени не нужен, тогда да, вектор тоже сойдет.

Добавлено через 53 секунды
Цитата Сообщение от gru74ik Посмотреть сообщение
Bretbas, кроме std::map существует ещё std::unordered_map.
А он вообще выдает элементы в порядке определенном корейским рандомом. На то и unordered.
1
DrOffset
9017 / 4862 / 1198
Регистрация: 30.01.2014
Сообщений: 7,947
26.12.2016, 19:39 7
Цитата Сообщение от Renji Посмотреть сообщение
Ну или рыться в Boost, возможно что там что-то готовое на эту тему есть.
Помню, мне в похожей ситуации подошла связка std::list + boost::intrusive::set.

Добавлено через 1 минуту
Цитата Сообщение от Renji Посмотреть сообщение
Придется перерывать ручками весь вектор, выясняя где же там нужная система лежит.
Для вектора можно хранить индекс, в принципе. Правда балансировать сдвиг все равно придется.
1
sourcerer
Модератор
Эксперт CЭксперт С++
4875 / 2061 / 325
Регистрация: 20.02.2013
Сообщений: 5,558
Записей в блоге: 24
Завершенные тесты: 1
26.12.2016, 19:40 8
Цитата Сообщение от Renji Посмотреть сообщение
А он вообще выдает элементы в порядке определенном корейским рандомом. На то и unordered.
Хмм... да, точно. Тогда не подойдёт.
0
DrOffset
9017 / 4862 / 1198
Регистрация: 30.01.2014
Сообщений: 7,947
26.12.2016, 19:49 9
Из "коробочных решений" в boost есть boost::multi_index. Там можно скомпоновать контейнер, который будет предоставлять нужные характеристики (хеш-таблица, дерево, непрерывное хранение, список и т.д.) в разных комбинациях.
2
Bretbas
Каждому свое
521 / 207 / 81
Регистрация: 05.08.2013
Сообщений: 1,610
Завершенные тесты: 2
26.12.2016, 19:53  [ТС] 10
Спасибо Всем! Попробую реализовать. Я думаю поиск систем не очень нужен. Хотя может быть пригодится в дальнейшем
0
Mr.X
Эксперт С++
3183 / 1710 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
26.12.2016, 21:03 11
Цитата Сообщение от Bretbas Посмотреть сообщение
Да и еще, в сцене не должно быть повторяющихся систем! Поэтому std::map тут подходит
Ну, если std::map введен только для проверки уникальности при добавлении, то для оной можно использовать множество имен загруженных систем, а сами системы хранить в векторе пар имя-система.
0
Bretbas
Каждому свое
521 / 207 / 81
Регистрация: 05.08.2013
Сообщений: 1,610
Завершенные тесты: 2
28.12.2016, 08:08  [ТС] 12
Mr.X, ты имеешь ввиду std :: vector<std :: pair<std :: string, System*>>>?
0
Mr.X
Эксперт С++
3183 / 1710 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
28.12.2016, 08:43 13
Цитата Сообщение от Bretbas Посмотреть сообщение
Mr.X, ты имеешь ввиду std :: vector<std :: pair<std :: string, System*>>>?
Ну да, а имена уже вставленных пар хранить в std::set<std::string>.
При вставке вызываем names_set.count(name), и если возвращает ноль, то вставляем.
1
Bretbas
Каждому свое
521 / 207 / 81
Регистрация: 05.08.2013
Сообщений: 1,610
Завершенные тесты: 2
28.12.2016, 08:56  [ТС] 14
Mr.X, Можно и так Спасибо. Я понял, что эту задачу можно решить разными способами
0
Mr.X
Эксперт С++
3183 / 1710 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
28.12.2016, 09:05 15
Цитата Сообщение от Bretbas Посмотреть сообщение
Я понял, что эту задачу можно решить разными способами
Ну да, и каких-либо экзотических контейнеров здесь точно не требуется, вполне достаточно стандартных.
0
hoggy
Заблокирован
Эксперт С++
28.12.2016, 11:19 16
Цитата Сообщение от Bretbas Посмотреть сообщение
Какой контейнер подойдет в данном случае?
комбинация: вектор с мапой.

http://rextester.com/BXVKH61134

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <iostream>
#include <cassert>
#include <string>
#include <vector>
#include <memory>
#include <map>
 
 
#define OUT_TO_STREAM(type_)  \
template<class T>friend       \
    ::std::basic_ostream<T>&  \
        operator<<(::std::basic_ostream<T>& os, const type_& obj )
 
struct System
{
    OUT_TO_STREAM(System){ return os << obj.getName(); }
    virtual const char* const getName()const = 0;
};
struct RenderSystem : System
{
    static const char* const name(){ return "RenderSystem"; }    
    const char* const getName()const override { return name(); }
};
struct PhysicsSystem: System
{
    static const char* const name() { return "PhysicsSystem"; }    
    const char* const getName()const override { return name(); }
    
};
struct SpriteSystem: System
{
    static const char* const name(){ return "SpriteSystem"; }    
    const char* const getName()const override { return name(); }
};
 
struct Scene
{
    using system_ptr = std::shared_ptr<System>;
    using map_t = std::map<std::string, system_ptr>;
    using vec_t = std::vector<system_ptr>;
    
    
    template<class T, class... Args> void addSystem(Args&&... args)
    {
        const auto* name = T::name();
        
        const auto found = m_map.find(name);
        if(found != m_map.cend())
            return
            std::cout << "WARNING! the subsystem '" << name << "' already exists!\n"
                  "WARNING! Abort operation!\n",
            void();
        
        auto& newObject = m_map[name] = std::make_shared<T>(std::forward<Args>(args)...);
        m_vec.emplace_back(newObject);
        
        std::cout <<"SYSTEM: '" << name << "' was added success!\n";
    }
    
    template<class T> void removeSystem()
    {
        this->removeSystem(T::name());
    }
    
    void removeSystem(const char* const name)
    {
        const auto found = m_map.find(name);
        if(found == m_map.cend())
            return
            std::cout << "WARNING! the subsystem '" << name << "' not exists!\n"
                  "WARNING! Abort operation!\n",
            void();
        
        m_map.erase(found);
        
        #ifndef NDEBUG
        bool error = true;
        #endif
        for(auto i = m_vec.begin(), e = m_vec.end(); i != e; ++i)
            if((*i)->getName() == std::string(name))
            { 
                m_vec.erase(i); 
                #ifndef NDEBUG
                error = false;
                #endif
                break;             
            }
        
        assert(!error && "system must be exist");
        std::cout <<"SYSTEM: '" << name << "' was removed!\n";
    }
    
    void update()
    {
        for(const auto& system: m_vec)
            std::cout <<"SYSTEM: update '"<< system->getName() 
                << "' ... success!\n";
    }
private:
    map_t m_map;
    vec_t m_vec;
    
};
 
int main() 
{
    Scene scene;
    
    scene.addSystem<RenderSystem>();
    scene.addSystem<PhysicsSystem>();
    scene.addSystem<SpriteSystem>();
    scene.removeSystem<PhysicsSystem>();
    scene.update(); 
}
1
MrGluck
Модератор
Эксперт CЭксперт С++
8106 / 4958 / 1436
Регистрация: 29.11.2010
Сообщений: 13,454
28.12.2016, 14:14 17
Помимо уникальности имени для чего еще необходимо выделять название системы и хранить отдельно?
Если нужно сохранять порядок добавления - можно использовать std::vector<System*> с проверкой перед вставкой (каждый раз будет линейный проход). Если нужна частая вставка и поиск по имени, а перебор будет сравнительно редко - можно использовать std::unordered_set с хранением номера элемента как поле. При необходимости - создавать вектор и сортировать его по номеру.
Тут всё зависит от условий.

Если перебор в порядке добавления нужен не так часто, как вставка/поиск/удаление.
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <algorithm>
#include <iostream>
#include <memory>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
 
struct System
{
    virtual std::string getName() const = 0;
    virtual ~System() = default;
};
 
using sys_ptr = std::shared_ptr<System>;
using sys_with_order = std::pair<sys_ptr, unsigned long>;
 
struct RenderSystem : System
{
    std::string getName() const override { return "RenderSystem"; }
};
 
struct PhysicsSystem : System
{
    std::string getName() const override { return "PhysicsSystem"; }
};
 
struct SpriteSystem : System
{
    std::string getName() const override { return "SpriteSystem"; }
};
 
struct HashSys
{
    std::size_t operator()(const sys_ptr &p) const
    {
        return std::hash<std::string>()(p->getName());
    }
};
 
struct CmpSys
{
    bool operator()(const sys_ptr &lhs, const sys_ptr &rhs) const
    {
        return lhs->getName() == rhs->getName();
    }
};
 
bool operator<(const sys_with_order &lhs, const sys_with_order &rhs)
{
    return lhs.second < rhs.second;
}
 
class Scene
{
public:
    Scene() : m_systems(), p_counter(0) {}
    void addSystem(System *s)
    {
        std::shared_ptr<System> p(s);
        if (m_systems.find(p) != m_systems.end())
            std::cout << "Error. System already in scene\n";
        else
            m_systems[p] = p_counter++;
    }
    void printAll() const
    {
        std::vector<sys_with_order> buf(m_systems.begin(), m_systems.end());
        std::sort(buf.begin(), buf.end());
        for (const auto &p : buf)
            std::cout << p.first->getName() << std::endl;
    }
 
protected:
    std::unordered_map<sys_with_order::first_type, sys_with_order::second_type, HashSys, CmpSys> m_systems;
 
private:
    sys_with_order::second_type p_counter;
};
 
int main()
{
    Scene sc;
    sc.addSystem(new RenderSystem());
    sc.addSystem(new PhysicsSystem());
    sc.addSystem(new SpriteSystem());
    sc.addSystem(new RenderSystem());
    sc.printAll();
}
1
Voivoid
709 / 281 / 16
Регистрация: 31.03.2013
Сообщений: 1,339
28.12.2016, 17:18 18
boost::multi_index
0
Bretbas
Каждому свое
521 / 207 / 81
Регистрация: 05.08.2013
Сообщений: 1,610
Завершенные тесты: 2
28.12.2016, 18:03  [ТС] 19
hoggy,
Цитата Сообщение от hoggy Посмотреть сообщение
комбинация: вектор с мапой.
Можно, но не слишком ли заморочено для такой задачи? Мапа нужна, чтобы хранить только название систем...ну хрен знает. При удалении системы, нужно вначале искать ее имя в мапе, потом по вектору проходить...Ну в принципе как вариант.
Кстати, я не понял, что значит в твоем коде вот это:
C++
1
auto& newObject = m_map[name] = std::make_shared<T>(std::forward<Args>(args)...);
MrGluck,
Если нужна частая вставка и поиск по имени, а перебор будет сравнительно редко
Наоборот, вставка, поиск, и удалении по имени будет редко, а вот перебор очень очень часто Это же все-таки GameDev) Каждый кадр мне нужно проходить все системы

MrGluck, hoggy, Да, кстати, вы метод getName() переопределяете, и пишете название системы. А можно как нибудь сделать так, чтобы пользовать при создании системы не вводил ее имя, и не переопределял метод getName()? Чтобы автоматом имя получала система при наследовании. Я это реализовал за счет typeid.name(), но мне сказали что это небезопасно:
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
    class BTSSystem
    {
    public:
        BTSSystem( BTSScene* btsScene );                        
        virtual ~BTSSystem();                                           
 
        BTSScene*           getScene()  const;      
        virtual std::string     getName()   const   =   0;
 
    protected:
        BTSScene*               _btsScene;                      
    };
 
    template<typename T>
    class BTSRegisterSystem : public BTSSystem
    {
    public:
        BTSRegisterSystem( BTSScene* btsScene ) : BTSSystem( btsScene ) {}
        virtual ~BTSRegisterSystem() {}
 
        std::string getName() const
        {
            return typeid(T).name();
        }
    };
C++
1
2
3
4
5
6
    class BTSCameraSystem : public BTSRegisterSystem<BTSCameraSystem>
    {
    public:
        BTSCameraSystem( BTSScene* btsScene );                          
        ~BTSCameraSystem();                                     
    };
0
MrGluck
Модератор
Эксперт CЭксперт С++
8106 / 4958 / 1436
Регистрация: 29.11.2010
Сообщений: 13,454
28.12.2016, 18:35 20
Цитата Сообщение от Bretbas Посмотреть сообщение
А можно как нибудь сделать так, чтобы пользовать при создании системы не вводил ее имя, и не переопределял метод getName()? Чтобы автоматом имя получала система при наследовании.
На макросах.
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
#include <iostream>
 
struct A
{
    virtual std::string getName() const = 0;
    virtual ~A() = default;
};
 
#define CREATE_WITH_NAME(NAME) \
    class cl##NAME : public A \
    { \
    public: \
        std::string getName() const override { return #NAME; } \
    }; \
    class NAME : public cl##NAME
 
CREATE_WITH_NAME(B)
{};
 
CREATE_WITH_NAME(C)
{};
 
int main()
{
    B b;
    C c;
    std::cout << b.getName() << c.getName();
}
Добавлено через 1 минуту
Цитата Сообщение от Bretbas Посмотреть сообщение
Наоборот, вставка, поиск, и удалении по имени будет редко, а вот перебор очень очень часто
Тогда можно просто данные хранить в векторе, а при вставке проверять уникальность проходом с find. То, что я предложил в начале.
1
28.12.2016, 18:35
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.12.2016, 18:35

Когда какой контейнер использовать?
Поделитесь опытом, когда и при каких условиях какой контейнер особенно удобен?...

Какой контейнер для чего использовать?
для чего какой контейнер эффективней использовать? vector- list- map-...

Через какой метод лучше выводить контейнер?
Через какой метод лучше выводить контейнер? Часто видел как контейнер выводят...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

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