Быстрый поиск по двум параметрам. Вектор, список или двоичное дерево? ⇐ C++

[Anonymous]

У меня есть набор из более чем миллиона предметов в форме: < /p>

Код: Выделить всё

// Just an example for simplicity
struct Item {
std::string name_;
int value_;
};
< /code>
Мне нужно иметь возможность искать элементы в наборе (как по значению, так и по имени), добавить и удалить элементы в наборе. < /p>
И никакие два элемента не могут иметь одинакового или одинакового значения. < /P>
Какой лучший способ структурировать мои данные, чтобы все функции оптимизировались для скорости? < /P>
Обратите внимание, что я делаю это для домашней работы, чтобы все библиотеки были моими или от STL. Деревья с узлом, как это: < /p>
struct TreeNode {
//index of an item in the vector
int index;
//pointers to branching nodes
TreeNode* left, * right;
};
< /code>
и сортируйте его по имени, одно по значению.
Проблема здесь заключается в удалении элементов из набора, мне нужно обновить все большие индексы в обоих деревьях. /p>
(2) Вторая идея состояла в том, чтобы поместить все элементы в список и иметь такие узлы деревьев, как: < /p>
struct TreeNode {
//pointer to an item in the list
Item* item;
//pointers to branching nodes
TreeNode* left, * right;
};

Но я не знаю, собирается ли переместить элементы вокруг памяти под капюшоном, когда я добавляю и снимаю их, и оставлять узлы деревьев с разбитыми указатели.


Подробнее здесь: https://stackoverflow.com/questions/777 ... inary-tree