如何维护2个对象列表

Question

我的c ++程序需要维护2个对象列表.

list<A*> inuse;
list<A*> free;

因此,对象A甚至可以在"使用中"列表或"免费"列表中,但不能同时在两者中.
http://www.cplusplus.com/reference/stl/list/

我想使用'list'作为我的列表的数据结构.我的问题是

为什么我不能随机访问列表中的elmenet,我看看上面的api,我看不到有办法得到inuse[2];
如何删除列表中的元素？有一个erase(),但是如何使用它来删除元素#2？我删除元素2后？STL列表会自动填充删除的斑点吗？例如#3将成为#2,#4将成为#3,依此类推？

谢谢.

Answer 1

使用std :: vector.它具有随机元素访问([]或at()).

//does NOT check for out of range
myvector[i];

//does check for out of range
myvactor.at(i);

你可以使用erase()从vector中删除一个元素,它会自动处理空洞(#3变为#2,依此类推)

//erase the 6th element
myvector.erase (myvector.begin()+5);

// erase the first 3 elements:
myvector.erase (myvector.begin(),myvector.begin()+3);

但是如果你需要逐个删除许多对象,并且列表中不能有2个相同的对象,你可以尝试使用std :: map.使用object的一些唯一属性作为键,并将itselt对象作为值(或对象本身为键,并true作为值).它还具有类似的随机访问操作符[]和erase()功能.

Answer 2

遗憾的是,恒定时间删除和恒定时间随机访问是互斥的.

要么使用std::list线性时间std::advance进行随机访问,要么使用std::deque(我的推荐)或std::vector接受线性时间删除.

如果您总是删除系列中的第二个项目,deque则有可能保持不变的删除时间.A deque就像一个vector但是被分成与目录相关联的小块.

或者,如果您的数据已排序,请使用std::setfor进行常量时间删除和log(N)时间访问.

从任何容器的中间删除项目是通过my_container.erase( my_iterator ).列表,矢量,双端队列,地图,等等.

Answer 3

如果你需要快速访问和快速删除,请考虑std :: set,它应该具有logn查找和logn插入/删除,同时仍然被排序