6.1 list 데이터 추상(data abstraction) vector 데이터 구조는 다른 것에 비해 상대적으로 사이즈가 고정되어 있는 컨테이너이다. vector의 사이즈를 동적으로 변화시킬수 있는 연산이 제공되긴 하지만, 이러한 연산들은 비싸기 때문에 자주 사용해서는 안된다. 그리고, 대부분의 경우에, 콜렉션의 사이즈는 미리 예측하기가 힘들고, 실행 중에도 상당히 다양하게 변화한다. 따라서, 이러한 경우에는 다른 데이터 구조를 도입해야 하는데, 이 절에서는 그러한 상황에서 사용될 수 있는 데이터 구조의 하나인 list에 관해 살펴보기로 한다. list는 일렬로 나열된 원소들을 추상화한 개념이다. list의 앞쪽과 뒷쪽에서 새로운 값을 삽입하거나 삭제할 수 있으며, 반복자로 위치를 지정하여 list의 중간에서도 원소들을 추가하거나 삭제할 수 있다. 모든 경우에 대해서, 삽입 연산과 삭제연산은 항상 효율적이며, 콜렉션이 가지고 있는 원소들의 갯수와는 상관없이 상수시간내에 수행된다. 마지막으로, list는 선형 구조이다. list의 원소들은 첨자에 의해서는 접근이 불가능하고, 원소들을 접근하려면 모든 값들을 선형적으로 순회해야 한다. 6.1.1 Include 화일 list를 사용할 때는 반드시 list 헤더 화일을 포함해야 한다. #include 6.2 list 연산 리스트 데이터 타입이 제공하는 멤버 함수에 관해 아래에서 자세히 다룬다. 멤버 함수가 기초적인 연산을 제공하지만, 13장과 14장에서 설명할 generic 알고리듬을 사용함으로써 데이터 구조를 보다 유용하게 사용할 수 있게 된다. 6.2.1 list의 선언과 초기화 [Image] 메모리 관리 리스트를 선언하는 방법은 여러가지가 있다. 가장 간단한 형태는 콜렉션이 관리할 원소의 타입을 명시함으로써 리스트를 선언하는 방법이다. 원소의 타입은 integer나 double과 같은 primitive 타입이나, 포인터 타입이 될 수도 있고, 사용자 정의 타입이 될 수도 있다. 후자의 경우, 사용자 정의 타입은 반드시 기본 생성자를 반드시 정의해야 한다. 복사 생성자도 명시적으로나 묵시적으로 반드시 존재해야 한다. 이런 식으로 선언된 콜렉션은 아무런 원소도 가지지 않게 된다. list list_one; list list_two; list list_three; 또 다른 형태로는 일정수의 동일한 원소를 가지는 콜렉션을 만드는 선언이 있다. 이러한 용도로 사용되는 생성자는 explicit로 선언하여, 변환 연산자로 사용될 수 없도록 한다. 이렇게 함으로써, 정수가 list로 변환되지 않도록 한다. 이러한 형태의 생성자는 두개의 인자를 취하는데, 하나는 사이즈이고, 하나는 초기값이다. 두번째 인자는 생략가능하다. 생성될 원소의 갯수만이 인자로 주어지면, 이들 값들은 기본 생성자를 사용하여 초기화되고, 두개 인자가 모두 주어지면, 두번째 인자로 초기화된다. list list_four(5); // five elements, initialized to zero list list_five(4, 3.14); // 4 values, initially 3.14 list wlist_six(4); // default constructor, 4 elements list list_six(3, Widget(7)); // 3 copies of Widget(7) 리스트는 다른 콜렉션에 담긴 원소들로 초기화될 수 있는데, 이때는 처음과 끝을 가리키는 한쌍의 반복자를 사용하게 된다. 인자들은 어떤 종류의 반복자를 사용하더라도 상관없으므로, 반복자를 지원하는 컨테이너이기만 하면, 이 컨테이너에 담긴 원소들로 리스트를 초기화할 수 있는 것이다. 이렇게 하려면, 템플릿을 사용한 멤버 함수를 specialize할 수 있어야 하기 때문에, 어떤 컴파일러들은 이를 지원하지 않을 수 있다. 이러한 경우에는, copy() generic 알고리듬을 사용한 별도의 방법을 사용한다. copy()를 사용하여 list를 초기화할 때는 삽입 반복자를 구성하여 copy 연산이 수행하는 출력 연산을 리스트로의 삽입 연산으로 바꿔야 한다. (2.4절 참고) 삽입자는 두개의 인자를 요구하는데, 하나는 값이 삽입될 리스트이고, 하나는 값이 놓여지게 될 위치를 가리키는 반복자이다. 삽입 반복자는 현존하는 리스트의 임의 위치로 원소들을 복사하는데 사용될 수도 있다. list list_seven(aVector.begin(), aVector.end()); // the following is equivalent to the above list list_eight; copy(aVector.begin(), aVector.end(), inserter(list_eight, list_eight.begin())); 6.2.3절에서 설명하는 insert() 연산도 반복자가 가리키는 값들을 리스트에 배치하는데 사용될 수 있다. 삽입 반복자는 generator(13.2.3절 참고)가 생성하는 값들의 수열로 리스트를 초기화하는데 사용될 수 있다. 다음 코드는 이를 설명하고 있다. list list_nine; // initialize list 1 2 3 ... 7 generate_n(inserter(list_nine, list_nine.begin()), 7, iotaGen(1)); 복사 생성자를 사용하여 다른 리스트가 가지고 있는 값들로 리스트를 초기화할 수 있다. 대입 연산자도 같은 작업을 한다. 두가지 경우 모두 원소 타입에 대한 대입 연산자를 사용하여 각각의 새로운 값들을 복사한다. list list_ten(list_nine); // copy constructor list list_eleven; list_eleven = list_six; // values copied by assignment assign() 멤버 함수는 대입 연산자와 유사하지만, 더 기능이 많고, 때로는 더 많은 인자를 필요로 한다. 대입과 마찬가지로, 컨테이너에 들어있던 값들은 삭제되어, 인자로 명시된 값으로 대체된다. assign()에는 두가지 형태가 있다. 첫째는 다른 컨테이너의 부시퀀스를 명시하는 두개의 반복자를 인자로 취한다. 이 부시퀀스에 담긴 값들이 수신자의 새로운 원소가 되는 것이다. assign()의 두번째 형태는 갯수와 컨테이너의 원소 타입인 값을 인자로 취한다. 두번째 인자는 생략가능하다. 이것을 호출하고 나면, 컨테이너는 디폴트값 또는 인자로 명시한 초기값으로 첫번째 인자로 주어진 갯수만큼의 원소를 포함하게 된다. list_six.assign(list_ten.begin(), list_ten.end()); list_four.assign(3, 7); // three copies of value seven list_five.assign(12); // twelve copies of value zero 마지막으로, swap()이란 연산은 두 리스트간에 서로가 가지고 있는 내용을 완전히 바꾸는 작업을 한다. 인자로 명시된 컨테이너는 수신자의 값들을 가지게 되고, 수신자는 인자로 명시된 컨테이너의 값들을 가지게 된다. swap()은 매우 효율적인 연산이어서, 원소별 전송시에는 우선적으로 사용되어야 한다. list_ten.swap(list_nine); // exchange lists nine and ten 6.2.2 타입 정의 list 클래스는 많은 타입 정의들을 가지고 있다. 이것들은 주로 선언문에서 많이 사용된다. 예를 들어, 정수 list를 위한 반복자는 다음과 같이 선언할 수 있다. list::iterator location; iterator뿐만 아니라 다음과 같은 타입들이 정의되어 있다. value_type list에 담긴 원소의 타입 const_iterator 해당 시퀀스를 변경할 수 없는 반복자 reverse_iterator 뒷방향으로 이동하는 반복자 const_reverse_iterator 상수 반복자와 역 반복자를 합쳐 놓은 반복자 reference 원소에 대한 레퍼런스 const_reference 원소를 변경할 수 없는 레퍼런스 size_type 컨테이너의 사이즈에 사용되는 비부호형 정수 타입 difference_type 반복자간의 거리에 사용되는 부호형 정수 타입 allocator_type list가 메모리 관리에 사용하는 할당기 타입 6.2.3 list에 원소 집어넣기 list에 값들을 집어넣은 방법에는 여러가지가 있다. 원소들은 거의 대부분 리스트의 앞쪽이나 뒤쪽에서 추가된다. 이러한 작업들은 각각 push_front()와 push_back() 연산에 의해 수행된다. 이들 연산들은 두가지 타입의 컨테이너 모두에 대해서 효율적(상수시간)이다. list_seven.push_front(1.2); list_eleven.push_back(Widget(6)); 앞서 6.2.1절에서, 삽입 반복자와 함께 copy()나 generate() generic 알고리듬을 사용하여, 반복자가 지칭하는 리스트상의 위치에 값을 삽입하는 법에 관해 설명했다. insert()란 멤버 함수도 있는데, 이는 삽입자를 구축할 필요가 없다. 앞으로 간단히 설명하겠지만, begin()과 end() 함수가 만들어내는 반복자가 가지는 값들은 각각 리스트의 시작과 끝을 가리킨다. 이들 중 하나를 사용한 삽입은 각각 push_front()와 push_back()에 해당한다. 만약에 단 한개의 반복자만을 지정하면, 디폴트 원소가 삽입된다. // insert default type at beginning of list list_eleven.insert(list_eleven.begin()); // insert widget 8 at end of list list_eleven.insert(list_eleven.end(), Widget(8)); [Image] 반복자의 무효화 반복자는 리스트의 중간 위치를 지정할 수도 있다. 반복자를 만들어내는 방법에도 여러가지가 있다. 예를 들어, find() generic 알고리듬과 같은 13.3절에 설명되어 있는 검색 연산을 사용한 결과를 이용할 수가 있다. 새로운 값은 반복자가 지정한 위치 바로 앞에 삽입된다. insert() 연산은 값이 삽입된 위치를 가리키는 반복자를 반환한다. 위에서는 이 결과값이 무시되었다. // find the location of the first occurrence of the // value 5 in list list::iterator location = find(list_nine.begin(), list_nine.end(), 5); // and insert an 11 immediate before it location = list_nine.insert(location, 11); 인자로 받은 값을 정해진 갯수만큼 삽입하는 것 또한 가능하다. 이러한 형태의 insert()는 값들의 위치를 결과로 내놓지는 않는다. line_nine.insert(location, 5, 12); // insert five twelves 마지막으로, 한쌍의 반복자가 가리키는 시퀀스 전부를 리스트에 삽입할 수도 있다. 이경우에도, insert()의 반환값이 없다. // insert entire contents of list_ten into list_nine list_nine.insert(location, list_ten.begin(), list_ten.end()); 하나의 리스트를 다른 리스트에 접목하는 방법에는 여러가지가 있다. 접목은 아이템이 수신자 list에 첨가됨과 동시에 인자로 넘어온 list로부터 삭제가 일어난다는 점에서 삽입과 다르다. 이렇기 때문에, 접목은 매우 효율적이고, 적절한 때에 반드시 사용되어야 한다. 삽입에서처럼, splice() 멤버 함수는 반복자를 사용하여, 접목이 일어나는 수신자 리스트에서의 위치를 가리킨다. 인자는 리스트 전체 또는 리스트내의 한 원소(반복자로 지칭) 또는 리스트의 부시퀀스(한쌍의 반복자로 지칭)가 될 수 있다. // splice the last element of list ten list_nine.splice(location, list_ten, list_ten.end()); // splice all of list ten list_nine.splice(location, list_ten); // splice list 9 back into list 10 list_ten.splice(list_ten.begin(), list_nine, list_nine.begin(), location); 두개의 순서화된 리스트는 merge() 연산을 통해 합쳐질 수 있다. 인자로 넘겨진 리스트의 값들은 순서화된 리스트로 합쳐지고 나면, 인자로 넘겨진 리스트는 비워지게 된다. 이 때의 merge는 'stable'하다. 다시 말해서, 원소들은 원래 속해 있던 리스트에서의 상대적인 순서를 그대로 유지한다. 14.6절에서 살펴볼 같은 이름을 가진 generic 알고리듬에서처럼 merge() 멤버 함수는 두가지 형태가 지원된다. 두번째 형태는 값들을 순서짓기 위해서 인자로 제공되는 이항 함수를 사용한다. 모든 컴파일러가 두번째 형태를 지원하지는 않는다. 만약 이 두번째 형태가 필요하지만 지원되지 않는다면, 좀 비효율적이긴 하지만, 더 일반적인 generic 알고리듬을 사용할 수 있겠다. // merge with explicit compare function list_eleven.merge(list_six, widgetCompare); //the following is similar to the above list list_twelve; merge(list_eleven.begin(), list_eleven.end(), list_six.begin(), list_six.end(), inserter(list_twelve, list_twelve.begin()), widgetCompare); list_eleven.swap(list_twelve); 6.2.4 원소 삭제하기 리스트에 원소를 추가하는 방법이 여럿 있듯이, 리스트로부터 원소를 삭제하는 방법에도 여러가지가 있다. 원소를 삭제하는데 가장 많이 쓰이는 연산은 pop_front()와 pop_back()으로, 각각 리스트의 시작과 끝에서 하나의 원소를 삭제한다. 이들 멤버 함수는 단순히 주어진 원소를 삭제하기만 하고, 별다른 결과값은 반환하지 않는다. 원소들에 대해 소멸자가 정의되어 있다면, 이들 원소가 삭제될 때 소멸자가 호출된다. 삭제하기 전에 값들을 살펴보기 위해서는 front()나 back() 멤버 함수를 사용한다. erase() 연산은 반복자가 가리키는 값을 삭제하는데 사용된다. 리스트의 경우, 인자로 주어진 반복자와 동일한 지점을 가리키고 있는 다른 반복자들은 삭제가 일어난 뒤에는 무효가 된다. 하지만, 다른 지점을 가리키는 반복자들은 영향을 받지 않는다. 한쌍의 반복자가 가리키는 부시퀀스 전체를 삭제할 때도 erase()를 사용할 수 있다. 첫번째 반복자에서부터 마지막 반복자 바로 이전까지의 값들이 리스트로부터 삭제된다. 리스트 중간에서 원소를 삭제하는 것은 vector나 deque에서와는 달리 효율적인 연산이다. list_nine.erase(location); // erase values between the first occurrence of 5 // and the following occurrence of 7 list::iterator location = find(list_nine.begin(), list_nine.end(), 5); list::iterator location2 = find(location, list_nine.end(), 7); list_nine.erase(location, location2); remove() 멤버 함수는 리스트로부터 주어진 값과 같은 모든 원소들을 삭제한다. remove_if()는 주어진 조건을 만족하는 모든 값들을 삭제한다. 이들 대신에, 13.5.1절에서 설명할 remove()나 remove_if() generic 알고리듬을 사용하는 방법도 있다. 이들 generic 알고리듬들은 리스트의 사이즈를 감소시키지 않으며, 대신에 원소들을 리스트의 앞쪽에 가져다 놓고, 리스트의 나머지 부분은 내버려두고, 변경되지 않은 첫번째 원소의 위치를 가리키는 반복자를 반환한다. 이 반환값은 erase()와 함께 사용되어 나머지 값들을 삭제하는데 사용할 수 있다. list_nine.remove(4); // remove all fours list_nine.remove_if(divisibleByThree); //remove any div by 3 // the following is equivalent to the above list::iterator location3 = remove_if(list_nine.begin(), list_nine.end(), divisibleByThree); list_nine.erase(location3, list_nine.end()); unique() 연산은 리스트에서 연속적으로 같은 값이 나오면 첫번째 원소를 제외한 나머지를 모두 삭제한다. 리스트가 정렬되어 있을 필요는 없다. 또 다른 형태의 unique()는 인자로 이항 함수를 취하는데, 이 함수를 이용하여 이웃하는 원소들을 비교하여 함수가 참을 리턴값으로 반환하면 두번째 값을 삭제한다. remove_if()에서 처럼, 모든 컴파일러가 이 두번째 형태의 unique()를 지원하지는 않는다. 이럴때는 좀더 일반적인 unique() generic 알고리듬을 사용하면 된다(13.5.2절 참고). 다음 예는 이항 함수가 greater-than 연산인 경우로, 앞쪽의 원소보다 작은 값들은 모두 삭제한다. // remove first from consecutive equal elements list_nine.unique(); // explicitly give comparison function list_nine.unique(greater()); // the following is equivalent to the above location3 = unique(list_nine.begin(), list_nine.end(), greater()); list_nine.erase(location3, list_nine.end()); 6.2.5 확장 및 사이즈 변환 연산 size() 멤버 함수는 컨테이너가 담고 있는 원소들의 갯수를 리턴한다. empty() 함수는 컨테이너가 비어있을 때 참을 리턴하고, size()를 0과 비교하는 것보다 더 효율적이다. cout << "Number of elements: " << list_nine.size () << endl; if ( list_nine.empty () ) cout << "list is empty " << endl; else cout << "list is not empty " << endl; resize() 멤버 함수는 리스트의 사이즈를 인자로 넘겨준 값으로 바꾼다. 이 때, 필요하다면 collection의 끝부분에서 값들을 추가로 더하거나 삭제한다. 생략 가능한 두번째 인자는 새로 원소가 추가될 필요가 있는 경우에 초기값으로 사용된다. // become size 12, adding values of 17 if necessary list_nine.resize (12, 17); 6.2.6 접근과 반복자 front()와 back() 멤버 함수는 각각 컨테이너의 처음 원소와 마지막 원소를 반환한다. 이때 삭제는 하지 않는다. 리스트에 대해서, 다른 원소를 접근하려면, 원하는 원소가 맨 앞이나 끝에 오게 될 때까지 원소들을 지우거나, 반복자를 이용함으로써 가능하다. 리스트와 함께 사용할 수 있는 반복자에는 세가지 형태가 있다. begin()과 end() 함수는 순방향으로 이동할 수 있는 반복자를 만들어 내는데, 리스트의 경우에 begin()과 end()는 양방향 반복자를 만들어 낸다. rbegin()과 rend()는 역순으로 이동할 수 있는 반복자를 만들어내는데, 리스트의 끝에서부터 앞쪽으로 이동한다. 6.2.7 소속 검사 연산 리스트 데이터 타입은 특정 값이 자신에게 속해있는지를 판별하는데 사용되는 메쏘드를 직접 제공하지 않는다. 그러나, find()나 count() generic 알고리듬(13.3.1절과 13.6.1절 참고)를 이런 용도로 사용할 수 있다. 다음은 17이란 수가 정수 리스트에 포함되어 있는지를 검사하는 예이다. int num = 0; count(list_five.begin(), list_five.end(), 17, num); if (num > 0) cout << "contains a 17" << endl; else cout << "does not contain a 17" << endl; if (find(list_five.begin(), list_five.end(), 17) != list_five.end()) cout << "contains a 17" << endl; else cout << "does not contain a 17" << endl; 6.2.8 정렬 연산 sort() 멤버 함수는 원소들을 오름차순으로 정렬한다. '<' 연산자 이외의 비교 연산자를 원한다면, 인자로 제공하면 된다. list_ten.sort( ); // place elements into sequence list_twelve.sort(widgetCompare); // sort with widget compare // function 일단 리스트가 정렬되고 나면, 정렬 콜렉션용 generic 알고리듬을 리스트에 사용할 수 있다. 이들 알고리듬에 관해서는 14장에서 자세히 설명한다. 6.2.9 검색 연산 13.3절에서 설명할 find(), find_if(), adjacent_find(), mismatch(), max_element(), min_element(), search() 등의 다양한 형태의 검색 함수들을 리스트에 사용할 수 있다. 모든 경우에 이들은 반복자를 결과값으로 리턴하며, 이 반복자를 이용하여 원소를 참조하거나, 뒤에 이어지는 연산에서 인자로 사용될 수 있다. [Image] 검색 결과의 검사 6.2.10 In Place 변환 어떤 것들은 멤버 함수로 제공되고, 어떤 것들은 13장에서 설명할 generic 함수들을 이용하기도 한다. 리스트의 경우에는, reverse() 멤버 함수가 원소들을 순서를 뒤집는다. list_ten.reverse(); // elements are now reversed transform() generic 알고리듬(13.7.1절)을 사용하여, 입력 컨테이너와 결과 컨테이너를 같은 것으로 지정하면, 컨테이너내의 모든 값들을 바꿀 수 있다. 예를 들어, 다음은 리스트의 각 원소를 1씩 증가시키는 예이다. 자신이 필요로하는 단항 함수를 만들기 위해서, 이항 정수덧셈 함수가 1이라는 값에 연결되어 있는 것을 볼 수 있다. 두개의 시퀀스를 병렬적으로 다루는 transform()은 비슷한 방법으로 사용하면 된다. transform(list_ten.begin(), list_ten.end(), list_ten.begin(), bind1st(plus(), 1)); 이와 비슷하게, replace()와 replace_if() 함수(13.4.2절 참고)는 리스트의 원소들을 특정 값으로 치환하는데 사용된다. 순환(13.4.3절)과 분할(13.4.4절)도 리스트에 적용될 수 있다. // find the location of the value 5, and rotate around it location = find(list_ten.begin(), list_ten.end(), 5); rotate(list_ten.begin(), location, list_ten.end()); // now partition using values greater than 7 partition(list_ten.begin(), list_ten.end(), bind2nd(greater(), 7)); next_permutation()과 prev_permutation() 함수(13.4.5절)는 각각 다음번 순열과 이전 순열을 생성하는데 사용된다. next_permutation (list_ten.begin(), list_ten.end()); 6.2.11 기타 연산 for_each() 알고리듬(13.8.1절)은 콜렉션 내의 모든 원소에 함수를 적용한다. 이것이 사용되는 예는 deque 데이터 구조에 관한 절의 radix sort 예제 프로그램에 잘 나타나 있다. accumulate() generic 알고리듬은 콜렉션으로부터 하나의 값을 만들어 낸다(13.6.2절 참고). 예를 들면, 정수 리스트에 속한 모든 원소들의 합을 구하는데 사용될 수 있다. accumulate()를 좀 색다르게 사용한 예도 마찬가지로 radix sort 예에서 살펴볼 수 있다. cout << "Sum of list is: " << accumulate(list_ten.begin(), list_ten.end(), 0) << endl; 두개의 리스트를 서로 비교하는 것도 가능하다. 사이즈가 같고 대응되는 원소가 서로 같다면 두 리스트는 같다고 본다. 사전적으로 한쪽이 작은경우에 그 리스트는 나머지 리스트보다 작다고 한다(13.6.5절). 6.3 예제 프로그램 - An Inventory System We will use a simple inventory management system to illustrate the use of several list operations. Assume a business, named WorldWideWidgetWorks, requires a software system to manage their supply of widgets. Widgets are simple devices, distinguished by different identification numbers: class Widget { public: Widget(int a = 0) : id(a) { } void operator = (const Widget& rhs) { id = rhs.id; } int id; friend ostream & operator << (ostream & out,const Widget & w) { return out << "Widget " << w.id; } friend bool operator == (const Widget& lhs, const Widget& rhs) { return lhs.id == rhs.id; } friend bool operator< (const Widget& lhs, const Widget& rhs) { return lhs.id < rhs.id; } }; The state of the inventory is represented by two lists. One list represents the stock of widgets on hand, while the second represents the type of widgets that customers have backordered. The first is a list of widgets, while the second is a list of widget identification types. To handle our inventory we have two commands; the first, order(), processes orders, while the second, receive(), processes the shipment of a new widget. class inventory { public: void order (int wid); // process order for widget type wid void receive (int wid); // receive widget of type wid in shipment private: list on_hand; list on_order; }; When a new widget arrives in shipment, we compare the widget identification number with the list of widget types on backorder. We use find() to search the backorder list, immediately shipping the widget if necessary. Otherwise it is added to the stock on hand. void inventory::receive (int wid) { cout << "Received shipment of widget type " << wid << endl; list::iterator weneed = find (on_order.begin(), on_order.end(), wid); if (weneed != on_order.end()) { cout << "Ship " << Widget(wid) << " to fill back order" << endl; on_order.erase(weneed); } else on_hand.push_front(Widget(wid)); } When a customer orders a new widget, we scan the list of widgets in stock to determine if the order can be processed immediately. We can use the function find_if() to search the list. To do so we need a binary function that takes as its argument a widget and determines whether the widget matches the type requested. We can do this by taking a general binary widget-testing function, and binding the second argument to the specific widget type. To use the function bind2nd(), however, requires that the binary function be an instance of the class binary_function. The general widget-testing function is written as follows: class WidgetTester : public binary_function { public: bool operator () (const Widget & wid, int testid) const { return wid.id == testid; } }; The widget order function is then written as follows: void inventory::order (int wid) { cout << "Received order for widget type " << wid << endl; list::iterator wehave = find_if (on_hand.begin(), on_hand.end(), bind2nd(WidgetTester(), wid)); if (wehave != on_hand.end()) { cout << "Ship " << *wehave << endl; on_hand.erase(wehave); } else { cout << "Back order widget of type " << wid << endl; on_order.push_front(wid); } }