最近最少使用(LRU)缓存首先丢弃最近最少使用的项目如何设计和实现这样的缓存类？设计要求如下:
1)尽可能快地找到项目
2)一旦缓存未命中并且缓存已满,我们需要尽快替换最近最少使用的项目.
如何在设计模式和算法设计方面分析和实现这个问题？
STL中是否有分类容器？
我的意思是:我有一个std::vector<Foo>,Foo定制的类在哪里.我还有一个比较器,它将比较类的字段Foo.
现在,我在我的代码中的某个地方:
std::sort( myvec.begin(), myvec.end(), comparator );
它将根据我在比较器中定义的规则对矢量进行排序.
现在我想在Foo该向量中插入一个class元素.如果可以的话,我想写一下:
mysortedvector.push_back( Foo() );
会发生什么,矢量会根据比较器将这个新元素放到它的位置.
相反,现在我必须写:
myvec.push_back( Foo() );
std::sort( myvec.begin(), myvec.end(), comparator );
这只是浪费时间,因为矢量已经排序,我需要的是适当地放置新元素.
现在,由于我的程序的性质,我不能使用,std::map<>因为我没有键/值对,只是一个简单的向量.
如果我使用stl::list,我再次需要在每次插入后调用sort.