写个Least Recently Used Cache的Class好像是几家公司常见题。 有没有面试可用的精简一些的Sample Code? 或哪个大拿给写一个范本。谢了。 还有,copy-on-write的string class。 我这里贡献一个smart pointer class。Code来自http://www.codeproject.com/KB/cpp/SmartPointers.aspx 。 class RC { private: int count; // Reference count public: void AddRef() { // Increment the reference count count++; } int Release() { // Decrement the reference count and // return the reference count. return --count; } }; template < typename T > class SP { private: T* pData; // pointer RC* reference; // Reference count public: SP() : pData(0), reference(0) { // Create a new reference reference = new RC(); // Increment the reference count reference->AddRef(); } SP(T* pValue) : pData(pValue), reference(0) { // Create a new reference reference = new RC(); // Increment the reference count reference->AddRef(); } SP(const SP& sp) : pData(sp.pData), reference(sp.reference) { // Copy constructor // Copy the data and reference pointer // and increment the reference count reference->AddRef(); } ~SP() { // Destructor // Decrement the reference count // if reference become zero delete the data if(reference->Release() == 0) { delete pData; delete reference; } } T& operator* () { return *pData; } T* operator-> () { return pData; }
SP& operator = (const SP& sp) { // Assignment operator if (this != &sp) // Avoid self assignment { // Decrement the old reference count // if reference become zero delete the old data if(reference->Release() == 0) { delete pData; delete reference; } // Copy the data and reference pointer // and increment the reference count pData = sp.pData; reference = sp.reference; reference->AddRef(); } return *this; } }; // Client void main() { SP p(new Person("Scott", 25)); p->Display(); { SP q = p; q->Display(); // Destructor of q will be called here.. SP r; r = p; r->Display(); // Destructor of r will be called here.. } p->Display(); // Destructor of p will be called here // and person pointer will be deleted }
参照网上的思路写了一个。哪位大拿给Review一下。谢了。 我平时只写C,不用C++。所以可能有初级错误:) #include #include // HashMap #include using namespace std; // cache entry struct Entry { int v; // dummy structure }; class LRU { private: list > mlist; unordered_map >::iterator> mht; int cnt; const static int MAX_SIZE = 10000; public: LRU () {cnt=0;} ~LRU () {} void addEntry (string mURL, Entry mEntry) { mlist.push_front(make_pair(mURL, mEntry)); mht.insert(make_pair(mURL, mlist.begin())); cnt++; if (cnt > MAX_SIZE) { mht.erase(mlist.back().first); mlist.pop_back(); cnt--; } } void delEntry (string mURL) { if (mht.find(mURL)==mht.end()) return; mlist.erase(mht[mURL]); mht.erase(mURL); cnt--; } void accessEntry (string mURL) { if (mht.find(mURL)==mht.end()) return; mlist.splice(mlist.begin(), mlist, mht[mURL]); } string recentUsed () { if (cnt==0) return NULL; return mlist.front().first; } }; Design an LRU cache with all the operations including getting the least recently used item to be O(1). Use a Hashmap along with doubly linked list. Insertion: When an element is inserted into the hashmap create a new node at the front of the doubly linked list. The hashmap entry will have the reference to this node in the douly linked list. Also the node in the liked list will have a reference to the entry in the hashmap. So Insertion : O(1) Deletion: Delete the entry from the hashmap and also following the reference to the doubly linked list, delete the node too. So O(1) Access: Get the element in the hashmap, follow the reference to the doubly linked list and just move this node in the doubly linked list to the front of the list. Recently used: Get the first element from the linked list. So Access: O(1)
【在 p*********r 的大作中提到】 : : Yes, it's Antutu. Its version may be different on different device. : Just did run my on N7 again. The new version is 3.0.3. : It actually is 12919.
Seems like different versions of Antutu result in VERY different benchmark number. My HTC one X was 7000 when it's running with Antutu 2.7.3 Today I just updated Antutu to the latest version Antutu, which is 3.0.2, and re-run the test. It give me 10030. That's really bad for this kind of benchmark, especially it collects all the benchmark data into its database.
t*2
53 楼
好怀念 之前院子里有一颗香椿树
p*r
54 楼
My Nook HD+ with CM10(12_18 build), and Samsung class 6 Micro SD and Antutu 3.0.3: The benchmark is 9363.
p*r
55 楼
I just re-run the test using a Sandisk 32GB class 4. I got 9434. Seems like the class 4 is faster than Samsung class 6 in the IO test.