实现一个动态数组类，功能包括在位置 N 增加一个数据，在位置

#include <vector> #include <iostream> #include <algorithm> #include <map> #include <assert.h>  using namespace std; template <class T> class DV { public: typedef typename vector<T>::iterator DVIterator; public:
  DV(int n)
    : contain_(n)
  { search_.insert(search_.begin(), {0, n});
  }

  DV(int n, int value)
    : contain_(value, n)
  { search_.insert(search_.begin(), {n, value});
  } void insert(DVIterator it, T v) { if(search_.find(v) == search_.end()) { search_[v] = 1;
    } else { search_[v]++;
    } contain_.insert(it, v);
  } void erase(DVIterator it) { auto i = search_.begin(); for(; i != search_.end(); ++i) { if(i->first == *it) { if(i->second > 1) {
          --i->second;
        } else { search_.erase(i);
        }
      }
    } contain_.erase(it);
  } T find_n_smallest(int n) { assert(n <= search_.size()); auto it = search_.begin(); for(int i = 1; i < n; ++i, ++it); return it->first;
  } T find_n_biggest(int n) { assert(n <= search_.size()); auto it = search_.rbegin(); for(int i = 1; i < n; ++i, ++it); return it->first;
  } DVIterator begin() { return contain_.begin();
  } DVIterator end() { return contain_.end();
  } void debug() { for(auto key_v : contain_) {
      cout << key_v << "\t";
    }
    cout << endl; for(auto key_m : search_) {
      cout << "key:" << key_m.first << " num:" << key_m.second << "\t";
    }
    cout << endl;
  } private: vector<T> contain_; map<T, int> search_;

};
/* 大致就是包装了一个vector和一个map，每次插入时map对应的数据发生变化，这样找起来的复杂度是常数级别 */ int main()
{ DV<int> dv(5, 3);
  cout << "debug1:" << endl;
  dv.debug();
  dv.erase(dv.begin());
  cout << "debug2:" << endl;
  dv.debug();
  cout << "debug3:" << endl;
  dv.insert(dv.begin(), 7);
  dv.insert(dv.begin(), 8);
  dv.insert(dv.begin(), 9);
  dv.insert(dv.begin(), 10);
  dv.debug();
  cout << "debug4:" << endl;
  cout << "smallest:" << dv.find_n_smallest(2) << endl;
  cout << "biggest:" << dv.find_n_biggest(2) << endl;
  dv.debug();
}

#ifndef Array_hpp #define Array_hpp template <class T> class DynamicArray
{ private:
    T *base; //数组首地址 //int length; //数组中元素 int size; //数组大小,以数组中元素的大小为单位 public: 
    //构造函数
    DynamicArray();  //析构函数
    //其他操作函数  bool ensureCapcity(); //检查内存是否够用，不够用就增加    bool add(T item); //添加元素到数组尾  bool insert(int index,T item); //在位置 N 增加一个数据，位置从1开始  T del(int index); //删除指定位置的元素并返回，位置从1开始   T objectAt(int index); //返回指定位置的元素   void display(); //打印数组所有元素  }; #endif /* Array_hpp */ 

	#include <iostream>



	#include <stdio.h>



	#include <algorithm>



	 



	struct my_list



	{



	    my_list *next;



	    int value;



	    my_list()



	    {



	        next = NULL;



	        value = 0;



	    }



	};



	 



	class dynamic



	{



	    my_list *head;



	    int arr[10000];



	    



	    void add_a_number(int n,int value)//在位置 n 添加一个数据，从 0 开始



	    {



	        int cal = 0;//计数



	        my_list *it = new my_list;



	        my_list *des = new my_list; des->value = value;



	        my_list *_next = new my_list;



	        for(it=head;cal<n;cal++)//it为代插入位置的上一个节点



	            it = it->next;



	        



	        _next = it->next;



	        if(_next == NULL)//插入到末尾



	            it->next = des;



	        else//在中间插入



	        {



	            it->next = des;



	            des->next = _next;



	        }



	 



	    }



	    



	    void delete_a_number(int n)//在位置 n 删除一个数据



	    {



	        int cal = 0;//计数



	        my_list *it = new my_list;



	        my_list *des = new my_list;



	        



	        for(it=head;cal<n;cal++)//it为代插入位置的上一个节点



	            it = it->next;



	        



	        des = it->next;//待删除位置



	        if(des == NULL)



	            printf("error:wrong index\n");



	        else if(des->next == NULL)



	        {



	            delete(des);



	            it->next = NULL;



	        }



	        else



	        {



	            it->next = des->next;



	            delete(des);



	        }



	    }



	    



	    int get_nth_min(int n)//获取第 n 小的数据，从 0 开始



	    {



	        int cal = 0;//计数



	        my_list *it = new my_list; it = head;



	        while(it->next)//存放到数组里



	        {



	            arr[cal++] = it->next->value;



	            it = it->next;



	        }



	        



	        std::sort(arr,arr+n);



	        return arr[n-1];



	    }



	    



	    int get_nth_number(int n)//获取第 n 个数据，从 0 开始



	    {



	        int cal = 0;//计数



	        my_list *it = new my_list; it = head;



	        while(cal<n)//遍历链表



	        {



	            cal++;



	            it = it->next;



	        }



	        



	        return it->next->value;



	    }



	};