![]() |
Home | Libraries | People | FAQ | More |
Intrusive containers can be used for highly optimized algorithms, where speed
is a crucial issue and:
介入式容器可用於速度是關鍵問題的高度優化的算法,以及:
The last point is important if you have a lot of containers over a set of elements.
E.g. if you have a vector of objects (say, std::vector<Object>), and you also have a list storing a subset
of those objects (std::list<Object*>),
then operating on an Object from the list iterator (std::list<Object*>::iterator) requires two steps:
如果你有多個容器建立在同一組元素之上,那麼最後一點就很重要了。例如,如果你有一組對象的 vector (即 std::vector<Object>),而且你還有一個鏈表保存了這些對象的一個子集(std::list<Object*>),那麼從這個鏈表的迭代器(std::list<Object*>::iterator)操作一個 Object 就需要兩步:
Object.Object 指針的鏈表節點。
Object
to the Object stored in the vector.Object 指針訪問保存在 vector 中的 Object。
While the objects themselves are tightly packed in the memory of the vector
(a vector's memory is guaranteed to be contiguous), and form something like
a data block, list nodes may be dispersed in the heap memory. Hence depending
on your system you might get a lot of cache misses. The same doesn't hold for
an intrusive list. Indeed, dereferencing an iterator from an intrusive list
is performed in the same two steps as described above. But the list node is
already embedded in the Object, so the memory is directly tracked from the
iterator to the Object.
雖
然這些對像本身是被緊緊地壓縮在 vector 的內存中的(vector
的內存是保證連續的),形成了像一個數據塊那樣的東西,但是鏈表結點卻可能分散在堆內存中。因此,取決於你的系統,你可能會遇到大量的緩存失失敗。對於介
入式鏈表則不會這樣。事實上,解引用一個來自於介入式鏈表的迭代器同樣要執行以上兩步。但是由於鏈表結點已經被嵌入在 Object 中,所以訪問
Object 迭代器時就直接留下了這些內存。
It's also possible to use intrusive containers when the objects to be stored
can have different or unknown size. This allows storing base and derived objects
in the same container, as shown in the following example:
當被保存的對象的大小未知或很難獲知時,也可以使用介入式容器。它允許將基類對像和派生類對像保存在同一個容器中,示範如下:
#include <boost/intrusive/list.hpp> using namespace boost::intrusive; //An abstract class that can be inserted in an intrusive list 抽像類可以被插入到介入式鏈表中
class Window : public list_base_hook<> { public: //This is a container those value is an abstract class: you can't do this with std::list.
//這是一個其值為抽像類的容器:你不能用 std::list 來實現
typedef list<Window> win_list; //An static intrusive list declaration 一個靜態介入式鏈表的聲明
static win_list all_windows; //Constructor. Includes this window in the list 構造函數。將本窗口放入鏈表中
Window() { all_windows.push_back(*this); } //Destructor. Removes this node from the list 析構函數。從鏈表中移除本結點
virtual ~Window() { all_windows.erase(win_list::s_iterator_to(*this)); }
//Pure virtual function to be implemented by derived classes 純虛擬函數,由派生類實現
virtual void Paint() = 0; }; //The static intrusive list declaration 靜態介入式鏈表的定義
Window::win_list Window::all_windows; //Some Window derived classes 一些 Window 的派生類
class FrameWindow : public Window { void Paint(){/**/} }; class EditWindow : public Window { void Paint(){/**/} }; class CanvasWindow : public Window { void Paint(){/**/} }; //A function that prints all windows stored in the intrusive list 打印保存在介入式鏈表中的所有窗口的函數
void paint_all_windows() { for(Window::win_list::iterator i(Window::all_windows.begin()) , e(Window::all_windows.end()) ; i != e; ++i) i->Paint(); } //...
//A class derived from Window 一個派生自 Window 的類
class MainWindow : public Window { FrameWindow frame_; //these are derived from Window too 它們也是派生自 Window 的
EditWindow edit_; CanvasWindow canvas_; public: void Paint(){/**/} //...
}; //Main function 主函數
int main() { //When a Window class is created, is automatically registered in the global list
//當創建一個 Window 類時,會自動註冊到全局鏈表中
MainWindow window; //Paint all the windows, sub-windows and so on 畫出所有窗口、子窗口等等
paint_all_windows();
//All the windows are automatically unregistered in their destructors. 所有窗口自動在它們的析構函數中去註冊。
return 0; }
Due to certain properties of intrusive containers they are often more difficult
to use than their STL-counterparts. That's why you should avoid them in public
interfaces of libraries. Classes to be stored in intrusive containers must
change their implementation to store the hook and this is not always possible
or desirable.
由於介入式容器的特性,通常它們要比STL中的對應容器更難使用。所以你應該在庫的公有接口中避免使用它們。保存在介入式容器中的類必須修改其實現,以保存鉤子,這並非總是可以或合理的。