벡터에서 하위 벡터를 추출하는 가장 좋은 방법?

Question

내가 a가 있다고 가정 해 봅시다 std::vector (그것을 부르자 myVec) 크기 N. 요소 x부터 y의 사본으로 구성된 새 벡터를 구성하는 가장 간단한 방법은 무엇입니까? 여기서 0 <= x <= y <= n-1? 예를 들어, myVec [100000] ~을 통해 myVec [100999] 크기의 벡터에서 150000.

벡터로 효율적으로 수행 할 수 없다면 대신 사용해야 할 또 다른 STL 데이터 유형이 있습니까?

Answer 1

vector<T>::const_iterator first = myVec.begin() + 100000;
vector<T>::const_iterator last = myVec.begin() + 101000;
vector<T> newVec(first, last);

새로운 벡터를 구성하는 것은 O (n) 작업이지만 실제로는 더 나은 방법은 없습니다.

Answer 2

벡터 생성자 만 사용하십시오.

std::vector<int>   data();
// Load Z elements into data so that Z > Y > X

std::vector<int>   sub(&data[100000],&data[101000]);

Answer 3

std::vector(input_iterator, input_iterator), 당신의 경우 foo = std::vector(myVec.begin () + 100000, myVec.begin () + 150000);, 예를 들어 참조하십시오 여기

Answer 4

요즘 우리는 사용합니다 span에스! 그래서 당신은 다음을 쓸 것입니다.

#include <gsl/span>

...
auto start_pos = 100000;
auto length = 1000;
auto my_subspan = gsl::make_span(myvec).subspan(start_pos, length);

동일한 유형의 1000 요소 범위를 얻으려면 myvec'에스. 자, 이건이야 사본이 아니라 단지보기 일뿐입니다 벡터의 데이터의 데이터의 경우 조심하십시오. 실제 사본을 원한다면 다음을 수행 할 수 있습니다.

std::vector<T> new_vec(my_subspan.cbegin(), my_subspan.cend());

메모:

• gsl 가이드 라인 지원 라이브러리를 나타냅니다. 자세한 내용은 gsl, 보다: http://www.modernescpp.com/index.php/c-core-guideline-thuidelines-support-library.
• 하나의 구현 gsl, 보다: https://github.com/microsoft/gsl
• C ++ 20은 구현을 제공합니다 span. 당신은 사용할 것입니다 std::span 그리고 #include <span> 보다는 #include <gsl/span>.
• 스팬에 대한 자세한 내용은 다음을 참조하십시오. "스팬"이란 무엇이며 언제 사용해야합니까?
• std::vector Gazillion 생성자가 있습니다. 사용하려고하지 않은 사람에 빠지는 것은 매우 어려운 일입니다.

Answer 5

둘 다 수정되지 않을 경우 (아이템 추가/삭제 없음 - 스레딩 문제에 대한 비용을 지불하는 한 기존 항목을 수정하는 것은 괜찮습니다). data.begin() + 100000 그리고 data.begin() + 101000, 그리고 그들이 척합니다 begin() 그리고 end() 더 작은 벡터의.

또는 벡터 스토리지가 인접 해 보장되므로 단순히 1000 개의 항목 배열을 전달할 수 있습니다.

T *arrayOfT = &data[0] + 100000;
size_t arrayOfTLength = 1000;

이 두 기술 모두 일정한 시간이 걸리지 만 데이터 길이가 증가하지 않아 재 할당을 유발해야합니다.

Answer 6

당신은 어떤 유형을 언급하지 않았습니다 std::vector<...> myVec 그러나 포인터를 포함하지 않는 간단한 유형 또는 구조물/클래스라면 최상의 효율성을 원한다면 직접 메모리 사본을 수행 할 수 있습니다 (제공된 다른 답변보다 빠를 수 있음). 다음은 일반적인 예입니다 std::vector<type> myVec 어디 type 이 경우 int:

typedef int type; //choose your custom type/struct/class
int iFirst = 100000; //first index to copy
int iLast = 101000; //last index + 1
int iLen = iLast - iFirst;
std::vector<type> newVec;
newVec.resize(iLen); //pre-allocate the space needed to write the data directly
memcpy(&newVec[0], &myVec[iFirst], iLen*sizeof(type)); //write directly to destination buffer from source buffer

Answer 7

당신이 사용할 수있는 STL 사본 m이 하위 벡터의 크기 일 때 O (m) 성능으로.

Answer 8

선형 시간이 아닌 컬렉션을 투사하는 유일한 방법은 게으름하게하는 것입니다. 그 결과 "벡터"는 실제로 원래 컬렉션을 위임하는 하위 유형입니다. 예를 들어 Scala 's List#subseq 메소드 일정한 시간에 하위 시퀀스를 만듭니다. 그러나 이것은 컬렉션이 불변과 기본 언어가 쓰레기 수거를 스포츠하는 경우에만 작동합니다.

Answer 9

확인. 이것은 꽤 오래된 토론입니다. 하지만 방금 깔끔한 것을 발견했습니다.

slice_array - 이것이 빠른 대안 일 수 있습니까? 나는 그것을 테스트하지 않았다.

Answer 10

다른 사람들을 위해 이것을 늦게 게시합니다 .. 나는 첫 번째 코더가 지금까지 이루어 졌다고 확신합니다. 간단한 데이터 유형의 경우 사본이 필요하지 않으므로 오래된 C 코드 방법으로 되돌아갑니다.

std::vector <int>   myVec;
int *p;
// Add some data here and set start, then
p=myVec.data()+start;

그런 다음 포인터 P와 Len을 하위 벡터가 필요한 것으로 전달하십시오.

Notelen은이어야합니다 !! len < myVec.size()-start

Answer 11

아마도 array_view/span GSL 라이브러리에서는 좋은 옵션입니다.

다음은 단일 파일 구현도 있습니다. Array_view.

Answer 12

한 벡터에서 다른 벡터로 요소를 복사하십시오
이 예에서는 쌍의 벡터를 사용하여 이해하기 쉽습니다.
`

vector<pair<int, int> > v(n);

//we want half of elements in vector a and another half in vector b
vector<pair<lli, lli> > a(v.begin(),v.begin()+n/2);
vector<pair<lli, lli> > b(v.begin()+n/2, v.end());


//if v = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6)]
//then a = [(1, 2), (2, 3)]
//and b = [(3, 4), (4, 5), (5, 6)]

//if v = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7)]
//then a = [(1, 2), (2, 3), (3, 4)]
//and b = [(4, 5), (5, 6), (6, 7)]

'
보시다시피 한 벡터에서 다른 벡터로 요소를 쉽게 복사 할 수 있습니다. 예를 들어 인덱스 10에서 16에서 요소를 복사하려면 사용합니다.

vector<pair<int, int> > a(v.begin()+10, v.begin+16);

인덱스 10에서 끝에서 일부 인덱스로 요소를 원한다면이 경우

vector<pair<int, int> > a(v.begin()+10, v.end()-5);

이것이 도움이되기를 바랍니다. 마지막 경우를 기억하십시오 v.end()-5 > v.begin()+10

Answer 13

또 다른 옵션 : 예를 들어 thrust::device_vector 그리고 a thrust::host_vector, 생성자를 사용할 수없는 곳.

std::vector<T> newVector;
newVector.reserve(1000);
std::copy_n(&vec[100000], 1000, std::back_inserter(newVector));

복잡성이어야합니다 o (n)

이것을 최고 Anwer 코드와 결합 할 수 있습니다

vector<T>::const_iterator first = myVec.begin() + 100000;
vector<T>::const_iterator last = myVec.begin() + 101000;
std::copy(first, last, std::back_inserter(newVector));

Answer 14

당신은 그냥 사용할 수 있습니다 insert

vector<type> myVec { n_elements };

vector<type> newVec;

newVec.insert(newVec.begin(), myVec.begin() + X, myVec.begin() + Y);