deque对象可否像数组一样直接定位某个元素
deque对象能否像数组一样直接定位某个元素http://blog.csdn.net/adcxf/article/details/2991804在这里看到
deque对象能否像数组一样直接定位某个元素
C/C++ codetemplate <typename T> void CStackWithMin<T>::push(const T& value){ // append the data into the end of m_data m_data.push_back(value); // set the index of minimum elment in m_data at the end of m_minIndex if(m_minIndex.size() == 0) m_minIndex.push_back(0); else { if(value < m_data[m_minIndex.back()]) m_minIndex.push_back(m_data.size() - 1); else m_minIndex.push_back(m_minIndex.back()); }} 其中的m_data[m_minIndex.back()]可以在O(1)的时间内得到吗？
[解决办法] deque可以用[]运算符像数组一样直接定位某个元素，由于它采用分块的线性存储结构来存储数据，所以访问速度在vector和list之间，严格的来说是大于线性时间的。
[解决办法] 探讨 [解决办法] 可以参考这里或者C++标准。
[解决办法] -- m_data[m_minIndex.back()]可以在O(1)的时间内得到吗？
可以。
STL 中， deque 是用 multiple array 实现的，即 deque 中的内容存储在多个小的动态数组中，每个小的动态数组是连续的，不同的动态数组之间可以连续，也可以不连续。 小的动态数组之间的顺序由额外的索引来维持（或检索），这些额外的索引由一个动态数组来体现（动态数组的每个元素包含指向每个小动态数组的指针），当需要额外的空间时，在前端或后端分配新的小的动态数组。可以看出，dequeue 不会像 vector 一样将元素分配的新存储空间，即使之前的存储空间引用无效（这也是 在遍历 vector 时如果删除元素或插入元素会造成运行时错误的原因，也是为什么用 Iterator 遍历 vector 时，通常要写成 iter != vec.end() 而不是 iter < vec.end() 的原因，因为如果涉及到重新分配内存，这些比较会没有意义）。
上面的说明可能有些绕（详细可参考维基百科-Dequeue），附张图说明一下：
从图上可以看出，在 m_data[ m_minIndex.back() ] 中，无论是 m_minIndex.back() 运算，不是 下标[] 运算，通过两步计算都可得到。所以整个运算可以在常数时间（O(1)）完成 。
如：m_minIndex.back()，首先先到索引数组的结尾，常数时间（dequeue中维护有索引数组的大小，可直接定位），第二步根据索引数组中的指针，定位到指向的数组的结尾，常数时间（每个 smaller array 的大小是固定的，可直接定位）。
而下标运算，第一步算索引通过一步算术运算即可定位（ smaller array 大小固定，通过下标值除以该大小即可定位），第二步同样根据索引中的指针可直接定位，加上之前除法的余数即可，显然也两步运算也是常数时间完成。
从上面的分析可以看出，m_data[m_minIndex.back()] 可以在 O(1) 的时间内得到。
希望楼主可以理解，Good Luck。
