一、c++ deque函数
C++ STL中的deque是一种支持双端插入和删除的线性容器。deque中的元素可以在两端进行push和pop。下面是deque常用的函数:
#include <deque> // deque构造函数 deque(); deque(int n); deque(int n, const T& v); deque(const deque& x); // 元素访问 reference operator[](int n); reference at(int n); reference front(); reference back(); // 容量 bool empty() const; size_type size() const; size_type max_size() const; // 修改容器 void clear(); iterator insert(iterator position, const T& x); void insert(iterator position, int n, const T& x); void insert(iterator position, InputIterator first, InputIterator last); iterator erase(iterator position); iterator erase(iterator first, iterator last); void push_back(const T& x); void push_front(const T& x); void pop_back(); void pop_front(); void swap(deque& x); // 比较器 bool operator==(const deque& x, const deque & y); bool operator!=(const deque & x, const deque & y); bool operator<(const deque & x, const deque & y); bool operator<=(const deque & x, const deque & y); bool operator>(const deque & x, const deque & y); bool operator>=(const deque & x, const deque & y);
二、c++ deque实现
c++ STL中deque的实现一般是由一个中控器(指针数组)与多个缓冲区组成,中控器维持着整个deque的结构,每个缓冲区存放着一定数量的元素,以此来保证deque的双端插入和删除。下面是一个简单的deque实现:
template <typename T, typename Alloc = alloc, size_t BufSiz = 0> class deque { public: typedef T value_type; typedef value_type* pointer; typedef size_t size_type; private: typedef simple_allocdata_allocator; typedef simple_alloc map_allocator; typedef pointer* map_pointer; size_type initial_map_size() const { return 8; } map_pointer map_; size_type map_size_; pointer allocate_node() { return data_allocator::allocate(buffer_size()); } void deallocate_node(pointer p) { data_allocator::deallocate(p, buffer_size()); } size_type buffer_size() const { return BufSiz != 0 ? BufSiz : sizeof(T) < 512 ? 512 / sizeof(T) : 1; } public: deque() : map_(nullptr), map_size_(0) { create_map_and_nodes(0); } deque(int n, const value_type& value) : map_(nullptr), map_size_(0) { fill_initialize(n, value); } void push_front(const value_type& value); void push_back(const value_type& value); void pop_front() {} void pop_back() {} reference operator[](size_type n) const {} reference at(size_type n) const {} reference front() const {} reference back() const {} size_type size() const {} bool empty() const {} void swap(deque& rhs) {} iterator begin() const {} iterator end() const {} ~deque() {} };
三、c++ deque用法
deque的使用方式与vector类似,不同的是deque可以在头尾两端进行操作。下面是一个简单的deque使用例子:
#include <iostream> #include <deque> using namespace std; int main() { deque<int> myDeque; myDeque.push_back(1); // insert 1 at the end of deque myDeque.push_front(2); // insert 2 at the beginning of deque myDeque.insert(myDeque.end(), 3); // insert 3 before the position pointed by the iterator myDeque.pop_back(); // remove the last element of deque myDeque.pop_front(); // remove the first element of deque myDeque.clear(); // remove all of the elements of deque return 0; }
四、c++ deque底层实现
deque底层一般由中控器和多个缓冲区组成,中控器维护着整个deque的结构,每个缓冲区存放着一定数量的元素,通过缓冲区之间的连接,形成了一个双向链表的结构,支持双端插入和删除。deque底层实现的优越性在于可以避免插入或删除时的数据迁移,但在空间利用率上不如vector(vector只需要一个连续的内存空间即可存放所有元素)。
五、c++的缺点
在使用deque时需要考虑与vector等其他容器的选择,c++的缺点主要在于对于大规模数据的处理严重依赖于底层硬件。同时在程序设计的过程中,需要注意指针空指针问题、内存泄漏等缺陷与陷阱。
六、c和指针选取
c和指针是很常用的高级编程语言,但与c++相比,c的面向对象能力较弱,在程序设计的过程中需要手动维护内存、支持分离编译等功能,但也由于这些特性使得c代码执行速度快、内存占用小。