Научите пожалуйста как с помощью STL решить следующую задачу:
имею определенный тип данных:
struct PIECE
{
.................
.................
.................
}
PIECE *one_piece;
количество элементов заранее не известно, надо все это где-то хранить, удалять ненужные, добавлять новые и самое главное обращаться к нужному данному по номеру.
Я пробовал решить эту задачу с помощь динамического массива, но заранее не известно количество элементов. И удаление ненужных элементов из середины массива создает потом проблемы с поиском свободного места, куда можно вставить новый элемент. Да и не думаю, что все это оптимально в плане скорости.
Если можно пожалуйста кусочек кода, поясняющий.
Заране благодарен.
Здравствуйте, Bell, Вы писали:
B>смотри в сторону std::vector
Спасибо.
Пробовал:
typedef vector<Piece> PEACELIST;
PEACELIST list;
добавляю элементы:
list.push_back(p);
а вот как читать то? Если p=list.pop_back(), то доступ получается последовательный, а нужен произвольный по индексу как в обычном массиве.
Или так нельзя?
Здравствуйте, ArcD, Вы писали:
AD>Здравствуйте, Bell, Вы писали:
B>>смотри в сторону std::vector
AD>Спасибо. AD>Пробовал:
AD>typedef vector<Piece> PEACELIST; AD>PEACELIST list;
AD>добавляю элементы:
AD>list.push_back(p);
AD>а вот как читать то? Если p=list.pop_back(), то доступ получается последовательный, а нужен произвольный по индексу как в обычном массиве. AD>Или так нельзя?
Ну, pop_back — это вообще удаление последнего элемента из контейнера.
Надо так:
for(int i = 0; i < list.size(); ++i)
list[i].field1 = ...
или так:
for(PEACELIST::iterator it = list.begin(), ite = list.end(), it != ite; ++it)
it->field1 = ...
ЗЫ
list — неудачное название. В STL есть контейнер с этим именем.
AD>количество элементов заранее не известно, надо все это где-то хранить, удалять ненужные, добавлять новые и самое главное обращаться к нужному данному по номеру.
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, Bell, Вы писали:
B>>ЗЫ B>>list — неудачное название. В STL есть контейнер с этим именем.
А>Удачное, удачное. А>В STL контейнер называется std::list. А>Просто не надо всюду using namespace расставлять.
У меня где-то было написано using namespace std; ?
B>for(int i = 0; i < list.size(); ++i)
B> list[i].field1 = ...
B>
B>или так:
B>
B>for(PEACELIST::iterator it = list.begin(), ite = list.end(), it != ite; ++it)
it->>field1 = ...
B>
Спасибо большое вот первый способ мне подходит, только вот как удалить элемент из середины векора?
B>
B>PIECE piece;
B>for(int i = 0; i < list.size(); i++)
B>{
B> piece=list[i];
B> if (piece.life_time>1000)
B> {
B> Здесь надо удалить элемент list[i]. list.erase(...), что ему передать в качестве параметра? i? не подходит, ругается....
B> }
B>}
B>
Здравствуйте, ArcD, Вы писали:
AD>Спасибо большое вот первый способ мне подходит,
Эти методы пракимчески идентичны.
AD>только вот как удалить элемент из середины векора?
B>>
B>>PIECE piece;
B>>for(int i = 0; i < list.size(); i++)
B>>{
B>> piece=list[i];
B>> if (piece.life_time>1000)
B>> {
B>> Здесь надо удалить элемент list[i]. list.erase(...), что ему передать в качестве параметра? i? не подходит, ругается....
B>> }
B>>}
B>>
Итак, начнем по порядку.
Удалене из середины вектора одного элемента можно сделать так:
int i = ...//позиция удаления
list.erase(list.begin() + i);
Однако это приводит к тому, что все элементы контейнера, располагавшиеся после удаленного элемента, сдвигаются на одну позицию. Поэтому в цикле применять такой метод нельзя (вернее просто так, без доп. исхищрений, нельзя). Кроме того это крайне неэффективно.
Судя по твоему коду, для твоей задачи идеально подходит стандартный алгоритм remove_if в связке с erase:
#include <vector>
#include <algorithm>
class pred
{
int n_;
public:
pred(int n) : n_(n) {}
bool operator() () { return piece.life_time>n_;}
};
...
std::erase(std::remove_if(list.begin(), list.end(), pred(1000)), list.end());
Здравствуйте, Bell, Вы писали:
B>Итак, начнем по порядку. B>Удалене из середины вектора одного элемента можно сделать так: B>
B>int i = ...//позиция удаления
B>list.erase(list.begin() + i);
B>
B>Однако это приводит к тому, что все элементы контейнера, располагавшиеся после удаленного элемента, сдвигаются на одну позицию. Поэтому в цикле применять такой метод нельзя (вернее просто так, без доп. исхищрений, нельзя). Кроме того это крайне неэффективно. B>Судя по твоему коду, для твоей задачи идеально подходит стандартный алгоритм remove_if в связке с erase:
AD>Спасибо большое вот первый способ мне подходит, только вот как удалить элемент из середины векора?
Если требуется удалять элементы из середины вектора, то это однозначно говорит о том, что использовать нужно не вектор, а list или map. Вообще, у меня складывается впечатление, что изучив vector люди радуются его возможностям и перестают что-либо еще изучать и лепят его везде где надо и не надо.
AD>>Спасибо большое вот первый способ мне подходит, только вот как удалить элемент из середины векора?
А>Если требуется удалять элементы из середины вектора, то это однозначно говорит о том, что использовать нужно не вектор, а list или map. Вообще, у меня складывается впечатление, что изучив vector люди радуются его возможностям и перестают что-либо еще изучать и лепят его везде где надо и не надо.
Спасибо.
Наверное ты прав в целом... Но это не про меня. Просто я пока про STL почти ничего не знаю. Попробую и map конечно.
AD>>Спасибо большое вот первый способ мне подходит, только вот как удалить элемент из середины векора?
А>Если требуется удалять элементы из середины вектора, то это однозначно говорит о том, что использовать нужно не вектор, а list или map.
Меня просто убивают подобные категоричные заявления
Ты знаешь, как выглядит структура PIECE, с которой нужно работать?!
Ты знаешь, насколько часто происходит удаление из середины?!
Ты знаешь, насколько важна/неважна скорость произвольного доступа?!
Ты знаешь специфику задачи?! (это я к вопросу о том, что связка vector + remove_if, вполне эффективна, и как нельзя лучше подходит под данную задачу)
B>Меня просто убивают подобные категоричные заявления
B>Ты знаешь, как выглядит структура PIECE, с которой нужно работать?! B>Ты знаешь, насколько часто происходит удаление из середины?! B>Ты знаешь, насколько важна/неважна скорость произвольного доступа?! B>Ты знаешь специфику задачи?! (это я к вопросу о том, что связка vector + remove_if, вполне эффективна, и как нельзя лучше подходит под данную задачу)
Нет, ничего этого я не знаю. Но именно поэтому нужно было с самого начала упомянуть как минимум три этих контейнера (vector, list и map) и рассказать вкратце об их отличиях и области применения, чтобы человек мог сам выбрать подходящий, а не зацикливаться на одном векторе.
Здравствуйте, SWW, Вы писали:
SWW>Нет, ничего этого я не знаю. Но именно поэтому нужно было с самого начала упомянуть как минимум три этих контейнера (vector, list и map) и рассказать вкратце об их отличиях и области применения, чтобы человек мог сам выбрать подходящий, а не зацикливаться на одном векторе.
Ладно, я поленился вчера это сделать — был уже конец рабочего дня, да и прописные истины каждый раз повторять мне тоже лень.
Однако в исходном вопросе была фраза: "...и самое главное обращаться к нужному данному по номеру...". Именно поэтому я посоветовал посмотеть в сторону вектора. Кроме того, я дал ссылку на статью, предоставив автору вопроса дополнительную возможность самому определиться с выбором.
Здравствуйте, SWW, Вы писали:
B>>Меня просто убивают подобные категоричные заявления
B>>Ты знаешь, как выглядит структура PIECE, с которой нужно работать?! B>>Ты знаешь, насколько часто происходит удаление из середины?! B>>Ты знаешь, насколько важна/неважна скорость произвольного доступа?! B>>Ты знаешь специфику задачи?! (это я к вопросу о том, что связка vector + remove_if, вполне эффективна, и как нельзя лучше подходит под данную задачу)
SWW>Нет, ничего этого я не знаю. Но именно поэтому нужно было с самого начала упомянуть как минимум три этих контейнера (vector, list и map) и рассказать вкратце об их отличиях и области применения, чтобы человек мог сам выбрать подходящий, а не зацикливаться на одном векторе.
Спасибо большое всем! Я обязательно попробую и vector и map. С map'ом даже как-то проще выглядит, если в качестве ключа задавать просто DWORD. Я так понимаю получается почти как вектор:
typedef map<DWORD,HellMeatPiece> MEATMAP;
extern MEATMAP HellMeat;
int AddMeatToMap(DWORD num,HellMeatPiece *meat)
{
int res;
HellMeat[num]=*meat;
res=HellMeat.size();
return res;
}
int CheckMeatRemove()
{
DWORD i,size;
size=HellMeat.size();
for (pos=HellMeat.begin(); pos!=HellMeat.end();)
{
MeatPiece=pos->second;
if (pos->second.life_time>20000)
{
HellMeat.erase(pos++);
}
else
++pos;
}
return HellMeat.size();
}
Вроде работает. Вот только не знаю как HellMeat[num] работает? Просто обращается по индексу или производит сложный поиск используя num как ключ?
И если так, то не сильно ли это тормозно?
Здравствуйте, ArcD, Вы писали:
AD>Спасибо большое всем! Я обязательно попробую и vector и map. С map'ом даже как-то проще выглядит, если в качестве ключа задавать просто DWORD. Я так понимаю получается почти как вектор:
Если тебе не нужно идентифицировать объект по какому-то ключу (а в твоём примере нигде это не видно), то вместо map можно использовать set или multiset.
Вообще, выбор контейнера определяется тем, какую задачу (задачи) ты решаешь.
AD>Вроде работает. Вот только не знаю как HellMeat[num] работает? Просто обращается по индексу или производит сложный поиск используя num как ключ?
Производит поиск, используя num как ключ.
Внутри мап устроен как двоичное дерево поиска (обычно — красно-чёрное дерево), поэтому время поиска — не более O(log(N)), где N — размер контейнера (количество элементов).
AD>И если так, то не сильно ли это тормозно?
Оценка времени операций над контейнерами
vector list deque map | set
несорт. сорт. несорт. сорт. несорт. сорт. сорт.
доступ к первому элементу 1 1 1 log(N)†
доступ к последнему элементу 1 1 1 log(N)†
произвольный доступ 1 N 1‡ log(N)
поиск N log(N) N N log(N) log(N)
удаление спереди N 1 1 log(N)
удаление сзади 1 1 1 log(N)
удаление из произвольного места N 1 N‡ log(N)
вставка спереди N 1 1
вставка сзади 1|N° 1 1
вставка в произвольное место N 1 N
вставка в правильную позицию N• N• N• log(N)
сортировка N*log(N) N*log(N)
° Если зарезервировано достаточно памяти, то O(1). Если нет — будет копирование всего массива
† Вообще, доступ к первому элементу дерева — это спуск от корня до самого низа. Но реализации могут оптимизировать
‡ Зависит от реализации; скорее, там O(N), но коэффициент при асимптотике гаараздо меньше, чем у списка.
• Естественно, складывается из времени поиска и времени вставки. У вектора и дека тормозит вставка, у списка — поиск. Асимптотика берётся по максимуму.
Перекуём баги на фичи!
