插入位置问题.

gldamao

vector<**> a,b;
......
.....
.....
a.insert(a.begin(),b.begin(),b.end());
在像a插入时,为何是a.begin(),insert(X,Y,Z)函数插入位置应该是X位置的前一个.
在a.begin()位置的前一个应该为未定义啊??

zwylinux

原帖由 gldamao 于 2007-7-7 11:58 发表
vector a,b;
......
.....
.....
a.insert(a.begin(),b.begin(),b.end());
在像a插入时,为何是a.begin(),insert(X,Y,Z)函数插入位置应该是X位置的前一个.
在a.begin()位置的前一个应该为未定义啊??

哪里规定是这样子的了？应该是从a.begin这个位置开始插入的

isjfk

原帖由 gldamao 于 2007-7-7 11:58 发表
vector a,b;
......
.....
.....
a.insert(a.begin(),b.begin(),b.end());
在像a插入时,为何是a.begin(),insert(X,Y,Z)函数插入位置应该是X位置的前一个.
在a.begin()位置的前一个应该为未定义啊??

从X位置开始的旧数据往后移动，新的数据放在空出来的空间里。

gldamao

原帖由 zwylinux 于 2007-7-7 13:18 发表

哪里规定是这样子的了？应该是从a.begin这个位置开始插入的

C++ primer第四版关于顺序容器的部分
自己查去，明确说了是从X位置之前插入的。

whyglinux

原帖由 gldamao 于 2007-7-7 11:58 发表
vector a,b;
......
.....
.....
a.insert(a.begin(),b.begin(),b.end());
在像a插入时,为何是a.begin(),insert(X,Y,Z)函数插入位置应该是X位置的前一个.
在a.begin()位置的前一个应该为未定义啊??

不，不是未定义，因为 a.begin() 是一个合法的“位置”。

insert(X,Y,Z) 应该理解为在 X 所在（或所指）的元素之前插入。

converse

看了一下SGI的源码：

1. 
   
2. template <class T, class Alloc>
   
3. void vector<T, Alloc>::insert(iterator position, size_type n, const T& x) {
   
4.   if (n != 0) {
   
5.     if (size_type(end_of_storage - finish) >= n) {
   
6.       T x_copy = x;
   
7.       const size_type elems_after = finish - position;
   
8.       iterator old_finish = finish;
   
9.       if (elems_after > n) {
   
10.         uninitialized_copy(finish - n, finish, finish);
    
11.         finish += n;
    
12.         copy_backward(position, old_finish - n, old_finish);
    
13.         fill(position, position + n, x_copy);
    
14.       }
    
15.       else {
    
16.         uninitialized_fill_n(finish, n - elems_after, x_copy);
    
17.         finish += n - elems_after;
    
18.         uninitialized_copy(position, old_finish, finish);
    
19.         finish += elems_after;
    
20.         fill(position, old_finish, x_copy);
    
21.       }
    
22.     }
    
23.     else {
    
24.       const size_type old_size = size();        
    
25.       const size_type len = old_size + max(old_size, n);
    
26.       iterator new_start = data_allocator::allocate(len);
    
27.       iterator new_finish = new_start;
    
28.       __STL_TRY {
    
29.         new_finish = uninitialized_copy(start, position, new_start);
    
30.         new_finish = uninitialized_fill_n(new_finish, n, x);
    
31.         new_finish = uninitialized_copy(position, finish, new_finish);
    
32.       }
    
33. #         ifdef  __STL_USE_EXCEPTIONS
    
34.       catch(...) {
    
35.         destroy(new_start, new_finish);
    
36.         data_allocator::deallocate(new_start, len);
    
37.         throw;
    
38.       }
    
39. #         endif /* __STL_USE_EXCEPTIONS */
    
40.       destroy(start, finish);
    
41.       deallocate();
    
42.       start = new_start;
    
43.       finish = new_finish;
    
44.       end_of_storage = new_start + len;
    
45.     }
    
46.   }
    
47. }
    

复制代码

仅以这三行来说明问题：
        new_finish = uninitialized_copy(start, position, new_start);
        new_finish = uninitialized_fill_n(new_finish, n, x);
        new_finish = uninitialized_copy(position, finish, new_finish);

当start = position的时候，其实第一行代码是不起作用的，因此新插入的元素是插入在begin的前面了。

gldamao

我也是说插入在begin的前面，但是我不理解begin()前面是什么东西。给我的感觉就好像是
int a[3];
a[-1]=2;
难道访问不越界吗？
在插入到X之前以后，原来的X.begin()是不是就在。x.begin()+1的位置上了。

isjfk

原帖由 gldamao 于 2007-7-8 09:11 发表
我也是说插入在begin的前面，但是我不理解begin()前面是什么东西。给我的感觉就好像是
int a[3];
a[-1]=2;
难道访问不越界吗？
在插入到X之前以后，原来的X.begin()是不是就在。x.begin()+1的位置上了。

那你觉得a.insert(a.begin() + 1,b.begin(),b.end());能理解吗？这岂不成了：
int a[3] = { 1, 3 };
a[1] = 2;

原来的a[1]跑哪儿去了？正确的做法是先把a[1]后移一位，然后再赋值：
a[2] = a[1];
a[1] = 2;

vector会做同样的事，只不过你只需要调用vector提供的insert函数，具体移动数据的细节会由vector自行管理。vector虽然底层是用数组实现的，但使用的时候可以把它当成完全动态的，你可以在它的前面、后面、中间任意插入数据。就像链表一样。

但是需要注意一下因为底层是用静态数组实现的，所有某些操作会非常耗费资源。比如你插入数据时，vector会把插入位置之后的所有数据后移一段位置，空出来空间存放新的数据（如果原来的数组空间不够，就需要重新申请一个更大的数组，这就更耗费资源了）。如果你从begin位置开始插入，则整个数组都会后移，给新的数据空出来空间。

vector不适合需要频繁插入、删除数据的应用。

gldamao

说的好
基本理解了
不知道这个论坛有没有结贴的设置