#ifndef LRU_LIST_HXX
#define LRU_LIST_HXX
#include "DoubleLink.h"
/**
* A class used for mark whether the tail node is removed when insert a new element to the LRU list.
*/
template<class T>
class RemovedTail {
public:
T value;
bool tailRemoved;
public:
/**The constructor of RemovedTail */
RemovedTail() {
this->tailRemoved = false;
}
};
/**
* The class of LRUList
*/
template<class T>
class LRUList :
public DoubleLink<T>
{
private:
unsigned int maxCount;
public:
LRUList(unsigned int count);
void addNewElement(T e, RemovedTail<T> &remvedTail);
};
/**
* The constructor of LRUList, it will init a double list , with a max lenght of `count`.
*/
template<class T>
LRUList<T>::LRUList(unsigned int count) {
maxCount = count;
}
/**
* Add a new element to the lru list's head, if current length is equal `maxCount`, the tail node will be removed.
*/
template<class T>
void LRUList<T>::addNewElement(T e,RemovedTail<T> &remvedTail) {
DNode<T>* node = this->findNode(e);
if (node != NULL) {
this->removeNode(node);
this->insertNodeFirst(node);
} else {
if (this->count < this->maxCount) {
this->insertFirst(e);
} else {
remvedTail.tailRemoved = true;
this->deleteLast(&remvedTail.value);
this->insertFirst(e);
}
}
}
#endif
其中引用的DoubleLink.h的定義如下:
#ifndef DOUBLE_LINK_HXX
#define DOUBLE_LINK_HXX
#include <iostream>
using namespace std;
/**
* The class of DNode, used it for DoubleLink
*/
template<class T>
struct DNode
{
public:
T value;
DNode *prev;
DNode *next;
public:
DNode() { }
DNode(T t, DNode *prev, DNode *next) {
this->value = t;
this->prev = prev;
this->next = next;
}
};
/**
* The class of DoubleLink\n
*\n
* ```
* |----|--->|----|
* |tail| |head|
* |----|<---|----|
* ```
*\n
*/
template<class T>
class DoubleLink
{
public:
DoubleLink();
~DoubleLink();
int size();
bool isEmpty();
T get(unsigned int index);
T getFirst();
T getLast();
DNode<T>* findNode(T t);
void traversal();//traverse and print
int insert(unsigned int index, T t);
int insertFirst(T t);
int appendLast(T t);
int del(unsigned int index,T* value);
int del(unsigned int index);
int deleteFirst(T* value);
int deleteFirst();
int deleteLast(T* value);
int deleteLast();
protected:
unsigned int count;
DNode<T> *phead;
int removeNode(DNode<T>* node);
//int removeNode();
int insertNodeFirst(DNode<T>* node);
//int insertNodeFirst();
private:
DNode<T> *getNode(unsigned int index);
};
/**
* The constructor
*/
template<class T>
DoubleLink<T>::DoubleLink() : count(0)
{
// create the head, attention: this is no data in head.
phead = new DNode<T>();
phead->prev = phead->next = phead;
//
//count = 0;
}
// the destructor
template<class T>
DoubleLink<T>::~DoubleLink()
{
// delete all nodes
DNode<T>* ptmp;
DNode<T>* pnode = phead->next;
while (pnode != phead)
{
ptmp = pnode;
pnode = pnode->next;
delete ptmp;
}
// delete the head
delete phead;
phead = NULL;
}
/**
* Find a node by a T element
*/
template<class T>
DNode<T>* DoubleLink<T>::findNode(T t) {
DNode<T>* pnode = phead->next;
DNode<T>* findNode = NULL;
while (pnode != phead) {
if (pnode->value == t) {
findNode = pnode;
break;
}
pnode = pnode->next;
}
return findNode;
}
/**
* traverse all the nodes
*/
template<class T>
void DoubleLink<T>::traversal() {
DNode<T>* pnode = phead->next;
while (pnode != phead)
{
cout << pnode->value << ends;
pnode = pnode->next;
}
cout << endl;
}
/**
* Get the count of nodes
*/
template<class T>
int DoubleLink<T>::size()
{
return count;
}
/**
* Check if the list is empty.
*/
template<class T>
bool DoubleLink<T>::isEmpty()
{
return count == 0;
}
/**
* Get the node by index.
*/
template<class T>
DNode<T>* DoubleLink<T>::getNode(unsigned int index)
{
// check if the paramerter is valid
if (index<0 || index >= count)
{
cout << "get node failed! the index in out of bound!" << endl;
return NULL;
}
if (index == 0) {
return phead->next;
}
if (index == count - 1) {
return phead->prev;
}
// top half, search from begin
if (index <= count / 2)
{
unsigned int i = 0;
DNode<T>* pindex = phead->next;
while (i++ < index) {//i == index-1, end
pindex = pindex->next;
}
return pindex;
}
// bottom half, search from tail
int j = 0;
int rindex = count - index - 1;
DNode<T>* prindex = phead->prev;//the tail node
while (j++ < rindex) {
prindex = prindex->prev;
}
return prindex;
}
/**
* Get the value of the `index` node
*/
template<class T>
T DoubleLink<T>::get(unsigned int index)
{
return getNode(index)->value;
}
/**
* Get first node's value
*/
template<class T>
T DoubleLink<T>::getFirst()
{
return getNode(0)->value;
}
/**
* Get the last node's value
*/
template<class T>
T DoubleLink<T>::getLast()
{
return getNode(count - 1)->value;
}
/**
* Insert the element to the front of index's node.
*/
template<class T>
int DoubleLink<T>::insert(unsigned int index, T t)
{
if (index == 0)
return insertFirst(t);
DNode<T>* pindex = getNode(index);
DNode<T>* pnode = new DNode<T>(t, pindex->prev, pindex);
pindex->prev->next = pnode;
pindex->prev = pnode;
count++;
return 0;
}
/**
* Insert the node to the first.
*/
template<class T>
int DoubleLink<T>::insertNodeFirst(DNode<T>* pnode) {
phead->next->prev = pnode;
phead->next = pnode;
return 0;
}
/**
* Create a node and insert it to the first
*/
template<class T>
int DoubleLink<T>::insertFirst(T t)
{
DNode<T>* pnode = new DNode<T>(t, phead, phead->next);
insertNodeFirst(pnode);
count++;
return 0;
}
/**
* Create a node and insert it to the tail
*/
template<class T>
int DoubleLink<T>::appendLast(T t)
{
DNode<T>* pnode = new DNode<T>(t, phead->prev, phead);
phead->prev->next = pnode;
phead->prev = pnode;
count++;
return 0;
}
/**
* Remove an exist node
*/
template<class T>
int DoubleLink<T>::removeNode(DNode<T>* node) {
node->next->prev = node->prev;
node->prev->next = node->next;
count--;
return 0;
}
/**
* Remove the index's node, and copy the value to the porint of `value`.
*/
template<class T>
int DoubleLink<T>::del(unsigned int index,T* value)
{
if (index<0 || index >= count)
{
cout << "get node failed! the index in out of bound!" << endl;
return 1;
}
DNode<T>* pindex = getNode(index);
if (value != NULL) {
*value = pindex->value;
}
removeNode(pindex);
delete pindex;
return 0;
}
/**
* Remove the index's node.
*/
template<class T>
int DoubleLink<T>::del(unsigned int index)
{
return del(index, NULL);
}
/**
* Remove the first node, and save its value to `value`.
*/
template<class T>
int DoubleLink<T>::deleteFirst(T* value)
{
return del(0,value);
}
/**
* Remove the first node.
*/
template<class T>
int DoubleLink<T>::deleteFirst()
{
return del(0, NULL);
}
/**
* Remove the last node, and save its value to `value`.
*/
template<class T>
int DoubleLink<T>::deleteLast(T* value)
{
return del(count - 1,value);
}
/**
* Remove the last node.
*/
template<class T>
int DoubleLink<T>::deleteLast()
{
return del(count - 1, NULL);
}
#endif
在GCC5(或者之下版本)中編譯的時候,會報錯:
In file included from ../node/NodeLRUList.h:2:0,
from ../node/addon.cc:2:
../include/LRUList.h: In member function ‘void LRUList<T>::addNewElement(T, RemovedTail<T>&)’:
../include/LRUList.h:50:19: error: parse error in template argument list
if (this->count < this->maxCount) {
^
../include/LRUList.h: In instantiation of ‘void LRUList<T>::addNewElement(T, RemovedTail<T>&) [with T = std::__cxx11::basic_string<char>]’:
../node/NodeLRUList.h:18:41: required from here
../include/LRUList.h:50:9: error: ‘count’ is not a member template function
if (this->count < this->maxCount) {
^
在GCC6或者以上版本中編譯不會報錯
恭喜你, 遇到了一個編譯器的bug
這是gcc以前的一個bug: https://gcc.gnu.org/bugzilla/...
可能5.0以后才修好了.
clang也有類似的bug: https://bugs.llvm.org/show_bu... 里面的解釋值得一讀, 我節(jié)選下:
template<typename T> T end(T);
template <typename T>
void Foo() {
T it1;
if (it1->end < it1->end) {
}
}
Foo() is trying to use a public member variable of "*it1". Because there's a global template with the same name, it interprets the subsequent '<' as starting a template instantiation, and then finds trouble many tokens later when there's no matching '>'.
- possible fixit is to add parentheses around "it1->end".
北大青鳥APTECH成立于1999年。依托北京大學(xué)優(yōu)質(zhì)雄厚的教育資源和背景,秉承“教育改變生活”的發(fā)展理念,致力于培養(yǎng)中國IT技能型緊缺人才,是大數(shù)據(jù)專業(yè)的國家
北大青鳥中博軟件學(xué)院創(chuàng)立于2003年,作為華東區(qū)著名互聯(lián)網(wǎng)學(xué)院和江蘇省首批服務(wù)外包人才培訓(xùn)基地,中博成功培育了近30000名軟件工程師走向高薪崗位,合作企業(yè)超4
中公教育集團創(chuàng)建于1999年,經(jīng)過二十年潛心發(fā)展,已由一家北大畢業(yè)生自主創(chuàng)業(yè)的信息技術(shù)與教育服務(wù)機構(gòu),發(fā)展為教育服務(wù)業(yè)的綜合性企業(yè)集團,成為集合面授教學(xué)培訓(xùn)、網(wǎng)
達內(nèi)教育集團成立于2002年,是一家由留學(xué)海歸創(chuàng)辦的高端職業(yè)教育培訓(xùn)機構(gòu),是中國一站式人才培養(yǎng)平臺、一站式人才輸送平臺。2014年4月3日在美國成功上市,融資1
曾工作于聯(lián)想擔(dān)任系統(tǒng)開發(fā)工程師,曾在博彥科技股份有限公司擔(dān)任項目經(jīng)理從事移動互聯(lián)網(wǎng)管理及研發(fā)工作,曾創(chuàng)辦藍懿科技有限責(zé)任公司從事總經(jīng)理職務(wù)負責(zé)iOS教學(xué)及管理工作。
浪潮集團項目經(jīng)理。精通Java與.NET 技術(shù), 熟練的跨平臺面向?qū)ο箝_發(fā)經(jīng)驗,技術(shù)功底深厚。 授課風(fēng)格 授課風(fēng)格清新自然、條理清晰、主次分明、重點難點突出、引人入勝。
精通HTML5和CSS3;Javascript及主流js庫,具有快速界面開發(fā)的能力,對瀏覽器兼容性、前端性能優(yōu)化等有深入理解。精通網(wǎng)頁制作和網(wǎng)頁游戲開發(fā)。
具有10 年的Java 企業(yè)應(yīng)用開發(fā)經(jīng)驗。曾經(jīng)歷任德國Software AG 技術(shù)顧問,美國Dachieve 系統(tǒng)架構(gòu)師,美國AngelEngineers Inc. 系統(tǒng)架構(gòu)師。