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

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

26.12.2016, 18:46. Просмотров 1012. Ответов 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 тут подходит
http://www.cyberforum.ru/cpp-beginners/thread1586919.html
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.12.2016, 18:46
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Какой контейнер выбрать? (C++):

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

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

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

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

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

52
Renji
2124 / 1483 / 453
Регистрация: 05.06.2014
Сообщений: 4,324
26.12.2016, 18:50 #2
Самый ленивый вариант - объекты хранятся в std::list в порядке добавления, std::map хранит итераторы указывающие на элементы std::list и отсортированные по нужному ключу.
Более крутой вариант - велосипедить свой std::map с возможностью перебора элементов в порядке добавления. Ну или рыться в Boost, возможно что там что-то готовое на эту тему есть.
1
Bretbas
Каждому свое
518 / 204 / 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
gru74ik
Модератор
Эксперт CЭксперт С++
4648 / 1962 / 293
Регистрация: 20.02.2013
Сообщений: 5,223
Записей в блоге: 23
26.12.2016, 19:28 #4
Bretbas, кроме std::map существует ещё std::unordered_map.
1
Bretbas
Каждому свое
518 / 204 / 81
Регистрация: 05.08.2013
Сообщений: 1,610
Завершенные тесты: 2
26.12.2016, 19:33  [ТС] #5
gru74ik, Друг! Я только учусь. Я пока не знаю как использовать хеш таблицы. Никогда их не использовал
0
Renji
2124 / 1483 / 453
Регистрация: 05.06.2014
Сообщений: 4,324
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
7517 / 4513 / 1097
Регистрация: 30.01.2014
Сообщений: 7,362
26.12.2016, 19:39 #7
Цитата Сообщение от Renji Посмотреть сообщение
Ну или рыться в Boost, возможно что там что-то готовое на эту тему есть.
Помню, мне в похожей ситуации подошла связка std::list + boost::intrusive::set.

Добавлено через 1 минуту
Цитата Сообщение от Renji Посмотреть сообщение
Придется перерывать ручками весь вектор, выясняя где же там нужная система лежит.
Для вектора можно хранить индекс, в принципе. Правда балансировать сдвиг все равно придется.
1
gru74ik
Модератор
Эксперт CЭксперт С++
4648 / 1962 / 293
Регистрация: 20.02.2013
Сообщений: 5,223
Записей в блоге: 23
26.12.2016, 19:40 #8
Цитата Сообщение от Renji Посмотреть сообщение
А он вообще выдает элементы в порядке определенном корейским рандомом. На то и unordered.
Хмм... да, точно. Тогда не подойдёт.
0
DrOffset
7517 / 4513 / 1097
Регистрация: 30.01.2014
Сообщений: 7,362
26.12.2016, 19:49 #9
Из "коробочных решений" в boost есть boost::multi_index. Там можно скомпоновать контейнер, который будет предоставлять нужные характеристики (хеш-таблица, дерево, непрерывное хранение, список и т.д.) в разных комбинациях.
2
Bretbas
Каждому свое
518 / 204 / 81
Регистрация: 05.08.2013
Сообщений: 1,610
Завершенные тесты: 2
26.12.2016, 19:53  [ТС] #10
Спасибо Всем! Попробую реализовать. Я думаю поиск систем не очень нужен. Хотя может быть пригодится в дальнейшем
0
Mr.X
Эксперт С++
3178 / 1705 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
26.12.2016, 21:03 #11
Цитата Сообщение от Bretbas Посмотреть сообщение
Да и еще, в сцене не должно быть повторяющихся систем! Поэтому std::map тут подходит
Ну, если std::map введен только для проверки уникальности при добавлении, то для оной можно использовать множество имен загруженных систем, а сами системы хранить в векторе пар имя-система.
0
Bretbas
Каждому свое
518 / 204 / 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
Эксперт С++
3178 / 1705 / 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
Каждому свое
518 / 204 / 81
Регистрация: 05.08.2013
Сообщений: 1,610
Завершенные тесты: 2
28.12.2016, 08:56  [ТС] #14
Mr.X, Можно и так Спасибо. Я понял, что эту задачу можно решить разными способами
0
Mr.X
Эксперт С++
3178 / 1705 / 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Эксперт С++
7982 / 4863 / 1424
Регистрация: 29.11.2010
Сообщений: 13,238
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
708 / 280 / 15
Регистрация: 31.03.2013
Сообщений: 1,339
28.12.2016, 17:18 #18
boost::multi_index
0
Bretbas
Каждому свое
518 / 204 / 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Эксперт С++
7982 / 4863 / 1424
Регистрация: 29.11.2010
Сообщений: 13,238
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-...

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

Какой контейнер в STL и для чего эффективнее использовать?
Какой контейнер в STL и для чего эффективнее использовать? И почему

Прочитать массив чисел неизвестной длины. Какой контейнер использовать?
Доброго времени суток! И всех с наступающими праздниками :drink: В общем...


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

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

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