c++模版中的dependent type和typename

Qualified and unqualified names

A qualified name is one that specifies a scope. For instance, in the following C++ program, the references to cout and endl are qualified names:

#include <iostream>
int main()  {
   std::cout << "Hello world!" << std::endl;
}

In both cases, the use of cout and endl began with std::.

Dependent and non-dependent names

A dependent name is a name that depends on a template parameter. Suppose we have the following declaration (not legal C++):

template <class T>
class MyClass {
   int i;
   vector<int> vi;
   vector<int>::iterator vitr;
   T t;
   vector<T> vt;
   vector<T>::iterator viter;
};

The types of the first three declarations are known at the time of the template declaration. However, the types of the second set of three declarations are not known until the point of instantiation, because they depend on the template parameter T.
The names T, vector<T>, and vector<T>::iterator are called dependent names, and the types they name are dependent types. The names used in the first three declarations are called non-dependent names, at the types are non-dependent types.
如下面一段代码中,const_iterator是从属类型,需要在它前面加上typename。否则,在某些情况下,会导致编译解析时产生二义性。

template<typename C>
bool lastGreaterThanFirst(const C& container){
	if(container.empty())
		return false;
	typename C::const_iterator begin(container.begin());
	typename C::const_iterator end(container.end());
	return *--end > *begin;
}

下面进行详细解释

template <class T>
void foo() {
   T::iterator * iter;
   ...
}

如果定义一个嵌套类型的类,

class ContainsAType {
   class iterator { ... }:
   ...
};

foo<ContainsAType>();  在这种情况下,iter将会被声明为一个指向T::iterator 类型的指针变量。
但是如果有人按以下方式声明类,

class ContainsAValue {
   static int iterator;
};

foo<ContainsAValue>(); 在这种情况下,将会有两种解析结果:一个叫做iter的变量,或者静态变量T::iterator。只有在实例化后才能消除他们之间的歧义。
Before a qualified dependent type, you need typename. Without typename, there is a C++ parsing rule that says that qualified dependent names should be parsed as non-types even if it leads to a syntax error. 
头疼,先mark下来。。
参考:http://pages.cs.wisc.edu/~driscoll/typename.html
 
 

STL系列——vector

 
template < class T, class Alloc = allocator<T> > class vector; // generic template
vector用来表示数组,是大小可以动态改变的序列容器。vector内部使用动态分配的数组来存储元素。当元素增加需要分配更多空间的时候,需要将原始数组中内容拷贝到新的数组,然后销毁原始数组。z再分配是一个比较耗时的过程。为了内存使用和再分配之间的平衡,数组的长度的增长,不同的库有b不同的实现策略。
如gcc(这里使用版本是 gcc 5.2), 第一次分配时,capacity() == size()。如果后面增加内容,假设增加长度len, 原始vector长度为size( ),
若len > size(), 重新分配空间,增长后,capacity() = len + size();
若 len <= size( ) 并且 len + size()> capacity(),重新分配空间,增长后,capacity() = size()*2 ;
若len <= size( ) 并且 len+ size( ) <= capacity( ),不重新分配。

构造函数

default (1)   vector();
              explicit vector (const allocator_type& alloc);
fill (2)      explicit vector (size_type n, const allocator_type& alloc = allocator_type());
              vector (size_type n, const value_type& val,
                        const allocator_type& alloc = allocator_type());
range (3)     template <class InputIterator>
                    vector (InputIterator first, InputIterator last,
                                const allocator_type& alloc = allocator_type());
copy (4)      vector (const vector& x);
              vector (const vector& x, const allocator_type& alloc);
move (5) vector (vector&& x);
vector (vector&& x, const allocator_type& alloc);
initializer list (6) vector (initializer_list<value_type> il,
       const allocator_type& alloc = allocator_type());

几种使用方法

// constructors used in the same order as described above:
std::vector<int> first;                                // empty vector of ints
std::vector<int> second (4,100);                       // four ints with value 100
std::vector<int> third (second.begin(),second.end());  // iterating through second
std::vector<int> fourth (third);                       // a copy of third
// the iterator constructor can also be used to construct from arrays:
int myints[] = {16,2,77,29};
std::vector<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );

赋值构造函数

copy (1)               vector& operator= (const vector& x);
move (2)               vector& operator= (vector&& x);
initializer list (3)   vector& operator= (initializer_list<value_type> il);

迭代器

begin(), end(), rbegin(), rend(), cbegin(), cend(), crbegin(), crend()
当容器为空时,begin() 返回的迭代器不能解引用。(string为空时,begin() 可以解引用)

Capacity

size_type size() const noexcept;
size_type max_size() const;           // return the maximum number of elements that the vector can holds. due to known systems or library implementation limitations.

void resize (size_type n);
void resize (size_type n, const value_type& val);

如果n小于当前容器size(), 只保留开头的n个元素;如果n大于容器size(), 通过插入进行扩展。同时如果n 大于当前capacity(), 一个自动空间重分配操作会执行。
size_type capacity() const noexcept;       // 返回当前vector分配的存储空间大小(expressed in terms of elements)
bool empty() const noexcept;
void reserve (size_type n);         // request a change in capacity   当n大于当前capacity时,会导致容器重分配空间;否则没有影响。
void shrink_to_fit();    // 要求容器减小他的capacity到适合他的size,没有强制要求,具体示实现。可能会导致reallocation,但是不会修改vector的size或者内容。

Element Access

// Returns a reference to the element at position n in the vector container.
 reference operator[] (size_type n);
const_reference operator[] (size_type n) const;
// Access element
// Returns a reference to the element at position n in the vector.
reference at (size_type n);
const_reference at (size_type n) const;
//Access first element
//Returns a reference to the first element in the vector.
reference front();
const_reference front() const;
//Access last element
//Returns a reference to the last element in the vector.
 reference back();
const_reference back() const;
// Returns a direct pointer to the memory array used internally by the vector to store its owned elements.
 value_type* data() noexcept;
const value_type* data() const noexcept;

Modifier

range (1)        template <class InputIterator>
                     void assign (InputIterator first, InputIterator last);
fill (2)         void assign (size_type n, const value_type& val);
initializer list (3)  void assign (initializer_list<value_type> il);

range适用于迭代器或者数组
push_back( )、pop_back( )

single element (1)    iterator insert (const_iterator position, const value_type& val);
fill (2)              iterator insert (const_iterator position, size_type n, const value_type& val);
range (3)             template <class InputIterator>
                           iterator insert (const_iterator position, InputIterator first, InputIterator last);
move (4)              iterator insert (const_iterator position, value_type&& val);
initializer list (5)  iterator insert (const_iterator position, initializer_list<value_type> il);
iterator erase (const_iterator position);
iterator erase (const_iterator first, const_iterator last);

删除指定位置的元素,或者一段区间的元素
返回值为指向删除元素后第一个元素的iterator

void swap (vector& x);

与另一个有相同类型(T, Alloc)的容器的内容进行交换。 包括内容、capacity。其实就是相当于两个指针换了指向的位置,对应的属性(data、size、capacity等)也改变了。

void clear() noexcept;

清除vector里面的内容,将容器大小减小到0。不保证有内存的重新分配。

vector<int>( ).swap(x)

可以强制清空vector x,并重分配空间

template <class... Args>
iterator emplace (const_iterator position, Args&&... args);

C++11新特性,Construct and insert element。

The container is extended by inserting a new element at position. This new element is constructed in place using args as the arguments for its construction.
This effectively increases the container size by one.
template <class... Args>
  void emplace_back (Args&&... args);

Construct and insert element at the end

Allocator

allocator_type get_allocator() const noexcept;
// Returns a copy of the allocator object associated with the vector.

例子

// vector::get_allocator
#include <iostream>
#include <vector>
int main ()
{
  std::vector<int> myvector;
  int * p;
  unsigned int i;
  // allocate an array with space for 5 elements using vector's allocator:
  p = myvector.get_allocator().allocate(5);
  // construct values in-place on the array:
  for (i=0; i<5; i++) myvector.get_allocator().construct(&p[i],i);
  std::cout << "The allocated array contains:";
  for (i=0; i<5; i++) std::cout << ' ' << p[i];
  std::cout << '\n';
  // destroy and deallocate:
  for (i=0; i<5; i++) myvector.get_allocator().destroy(&p[i]);
  myvector.get_allocator().deallocate(p,5);
  return 0;
}

关系操作符

(1) template <class T, class Alloc>
  bool operator== (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);
(2) template <class T, class Alloc>
  bool operator!= (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);
(3) template <class T, class Alloc>
  bool operator<  (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);
(4) template <class T, class Alloc>
  bool operator<= (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);
(5) template <class T, class Alloc>
  bool operator>  (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);
(6) template <class T, class Alloc>
  bool operator>= (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);

== 操作首先比较size,如果相同,然后使用operator==顺序比较,直到第一个不匹配的
<操作则使用operator<进行顺序比较
其他比较操作内部使用 operator == 或者 operator < 操作进行比较

template <class T, class Alloc>
  void swap (vector<T,Alloc>& x, vector<T,Alloc>& y);

交换操作,类似于x.swap(y)

模板特化

template < class T, class Alloc = allocator<T> > class vector; // generic template
template <class Alloc> class vector<bool,Alloc>;               // bool specialization