std :: list와 std :: vector 중 하나를 선택하십시오.

Question

벡터에서 반복을 찾으려고하는 코드를 작성했습니다. 반복되는 경우 목록에 위치가 추가됩니다. 예를 들어 100 110 90 100 140 90 100의 시퀀스는 2D 벡터가됩니다. 첫 번째 차원은 고유 한 문자 (또는 숫자)를 포함하고 반복 목록은 두 번째 차원으로 추가됩니다. 결과가

100 -> [0 3 6] 
110 -> [1] 
90 -> [2 5] 
140 -> [4] 

처럼 보인다 그래서 코드는 find_if 내 시험이

struct equal_addr : std::unary_function<entry,bool> 
{ 
    equal_addr(const ulong &anAddr) : theAddr(anAddr) {} 
    bool operator()(const entry &arg) const { return arg.addr == theAddr; } 
    const ulong &theAddr; 
}; 

문제처럼 (중간 입력 크기를 들면, 20M를 검색합니다

typedef unsigned long long int ulong; 
typedef std::vector<ulong> aVector; 
struct entry { 
    entry(ulong a, ulong t) { 
    addr = a; 
    time.push_back(t); 
    } 
    ulong addr; 
    aVector time; 
}; 

// vec contains original data 
// theVec is the output vector 
void compress(aVector &vec, std::vector<entry> &theVec) 
{ 
    aVector::iterator it = vec.begin(); 
    aVector::iterator it_end = vec.end(); 
    std::vector<entry>::iterator ait; 
    for (ulong i = 0; it != it_end; ++it, ++i) { // iterate over input vector 
    ulong addr = *it; 
    if (theVec.empty()) { // insert the first item 
     theVec.push_back(entry(addr, i)); 
     continue; 
    } 
    ait = find_if(theVec.begin(), theVec.end(), equal_addr(addr)); 
    if (ait == theVec.end()) { // entry doesn't exist in compressed vector, so insert 
     theVec.push_back(entry(addr, i)); 
    } else { // write down the position of the repeated number (second dimension) 
     ait->time.push_back(i); 
    } 
    } 
} 

매우 간단하다) 코드가 매우 느리고 압축 기능을 종료하는 데 하루가 걸릴 수 있습니다. std::vec 대신 std::list을 사용하여 속도 향상의 기회가 있습니까? list은 순차적 인 작업에 더 나은 성능을 발휘합니다. 그러나 그것이 도움이되는지 아닌지를 알고 싶습니다. 유용하다면 다른 코드를 변경했습니다.

조언이 필요하십니까?

Answer 1

1. 왜 시도하지 않고 결과를 직접 측정합니까?
2. 아니요, list은 "순차적 인 작업"에 대해 더 잘 수행되지 않습니다. 모든 것을으로 극적으로 저하시킵니다.

list의 요소는 안정적이며 요소를 가리키는 포인터/반복기는 목록이 수정되거나 커지면 제거되지 않습니다.